BioStart Logo

Set Theory: Learning Objectives 1, 2, 3

Question 1: A set is a collection of objects. We denote $A = \{a_1, a_2, ...,a_n \}$ as a set, where $a_i$ is the ith element in the set A. Provide a numeric example of each of the following:
  1. A finite set.
  2. A countable but infinite set.
  3. An uncountable set.

"Countable" means you can, in principle, list out all the elements, even if the list goes on forever. "Uncountable" means you cannot.

  1. Example: The set of the first five positive integers, $A = \{1, 2, 3, 4, 5\}$.
  2. Example: The set of all integers, $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$.
  3. Example: The set of all real numbers, $\mathbb{R}$.
Question 2: The symbol $\in$ denotes set membership. Recall $\mathbb{R}$ (real numbers), $\mathbb{Z}$ (integers), and $\mathbb{Q}$ (rational numbers). Let:
  • $A = \{x \in \mathbb{Z}: x^2 < 20\}$
  • $B = \{y \in \mathbb{R}: y = 2n+1, n \in \mathbb{Z}\}$
  • $C = \{z \in \mathbb{Q}: 0 < z < 1\}$
Determine if each of the following statements are true or false.
  1. $4 \in A$
  2. $5 \in A$
  3. $\pi \in A$
  4. $7 \in B$
  5. $6 \in B$
  6. $\frac{1}{2} \in C$

To check if an element belongs to a set, verify it meets all conditions. For an element $x$ to be in set $A$, it must first be an integer and second, its square must be less than 20. Apply similar logic for sets B and C.

  1. True
  2. False
  3. False
  4. True
  5. False
  6. True

a) True. 4 is an integer and $4^2 = 16$, which is less than 20.
b) False. 5 is an integer, but $5^2 = 25$, which is not less than 20.
c) False. $\pi$ is not an integer ($\pi \notin \mathbb{Z}$).
d) True. Set B is the set of all odd integers. 7 is an odd integer (it can be formed with $n=3$).
e) False. 6 is an even integer, so it is not in the set of odd integers.
f) True. $\frac{1}{2}$ is a rational number, and $0 < \frac{1}{2} < 1$.
Question 3: Let $A$ and $B$ be sets. $B$ is defined to be a subset of $A$, $B \subseteq A$, if and only if every element of $B$ is also an element of $A$.
  1. Complete the following to define a subset using set notation: $B \subseteq A \iff \rule{4cm}{0.15mm}$.
  2. Let $A = \{0,1,2\}$. List all possible subsets of $A$.
  3. Let $A = \mathbb{Z}$, the set of all integers. If $B = \{x \in \mathbb{R} | 2x^2 - 3x -2 = 0\}$, is $B$ a subset of $A$?

For part (b), remember that the empty set ($\emptyset$) and the set itself are always subsets. For part (c), you must first find the elements of set B by solving the equation, and then check if all of those elements belong to set A.

  1. $\forall x (x \in B \implies x \in A)$
  2. $\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}$
  3. No

a) The formal definition is: $B \subseteq A \iff \forall x (x \in B \implies x \in A)$. This reads "for all x, if x is an element of B, then x is an element of A."

b) The set of all subsets is called the power set. For a set with 3 elements, there are $2^3 = 8$ subsets. They are: $\emptyset$ (the empty set), $\{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}$.

c) We must first find the elements of set B by solving the quadratic equation $2x^2 - 3x - 2 = 0$. Factoring gives $(2x+1)(x-2)=0$. The solutions are $x = -1/2$ and $x=2$. So, $B = \{-1/2, 2\}$. For $B$ to be a subset of $A=\mathbb{Z}$, every element of $B$ must be an integer. Since $-1/2$ is not an integer, $B$ is not a subset of $A$.
Question 4: Prove that two sets $A$ and $B$ are equal ($A=B$) if and only if $A \subseteq B$ and $B \subseteq A$.

An "if and only if" proof requires proving two directions. First, assume $A=B$ and show that $A \subseteq B$ and $B \subseteq A$. Second, assume $A \subseteq B$ and $B \subseteq A$ and show that $A=B$. For two sets to be equal, every element of $B$ must be and element of $A$ and vice versa.

This is a proof of set equality, which requires showing mutual inclusion.

Part 1 (Forward direction, $\implies$): Assume $A=B$. Show that $A \subseteq B$ and $B \subseteq A$.
If $A=B$, then by definition, they contain the exact same elements.
  • To show $A \subseteq B$, we must show that for any element $x$, if $x \in A$, then $x \in B$. Since $A=B$, if $x \in A$, it must also be in $B$. Thus, $A \subseteq B$.
  • To show $B \subseteq A$, we must show that for any element $x$, if $x \in B$, then $x \in A$. Since $A=B$, if $x \in B$, it must also be in $A$. Thus, $B \subseteq A$.
Part 2 (Backward direction, $\impliedby$): Assume $A \subseteq B$ and $B \subseteq A$. Show that $A=B$.
To show $A=B$, we must show that they contain the exact same elements.
  • Let $x$ be an arbitrary element in $A$ ($x \in A$). Since $A \subseteq B$, it follows that $x \in B$. This shows that every element of A is also in B.
  • Let $y$ be an arbitrary element in $B$ ($y \in B$). Since $B \subseteq A$, it follows that $y \in A$. This shows that every element of B is also in A.
Since the sets contain identical elements, we can conclude that $A=B$.
Question 5: Let $A = \{1,2,3, 4\}$. The power set of $A$, written $PS(A)$, is the set of all subsets of $A$. Determine if each of the following statements are true or false.
  1. $4 \in PS(A)$
  2. $\{1, 2\} \subseteq PS(A)$

Remember the difference between membership ($\in$) and subset ($\subseteq$). The elements of a power set are themselves sets.

  1. False
  2. False

The power set $PS(A)$ is the set of all subsets of $A$. Its elements are sets like $\emptyset, \{1\}, \{2\}, \{1,2\}, \dots, \{1,2,3,4\}$.

a) False. The statement $4 \in PS(A)$ asks if the number 4 is an element of the power set. The elements of the power set are sets, not numbers. The set $\{4\}$ is an element of the power set, but the number 4 is not.

b) False. The statement $\{1, 2\} \subseteq PS(A)$ asks if the set containing the numbers 1 and 2 is a subset of the power set. For this to be true, every element of $\{1, 2\}$ must also be an element of $PS(A)$. The elements of $\{1, 2\}$ are the numbers 1 and 2. As established in part (a), numbers are not elements of the power set. Therefore, this statement is false. (Note: The statement $\{1, 2\} \in PS(A)$ would be true).
Question 6: A set $A$ is a superset of another set $B$ ($A \supseteq B$) if all elements in set $B$ are also elements of set $A$. Determine whether each of the following statements are true or false.
  1. If $A$ is a superset of $B$, $B$ is a subset of $A$.
  2. The empty set $\emptyset$ is a superset of every set.
  3. Every set is a superset of the empty set $\emptyset$.
  4. Every set is a superset of itself.
  5. Every set has a finite number of supersets.

The statement "$A$ is a superset of $B$" ($A \supseteq B$) is equivalent to "$B$ is a subset of $A$" ($B \subseteq A$). Use this relationship to evaluate the statements. For the last statement, consider an infinite set like $\mathbb{Z}$.

  1. True
  2. False
  3. True
  4. True
  5. False

a) True. The definitions of superset and subset are two ways of stating the same relationship. $A \supseteq B$ means that every element of $B$ is in $A$, which is precisely the definition of $B \subseteq A$.

b) False. The empty set $\emptyset$ has no elements. For it to be a superset of a non-empty set $S$, it would need to contain all elements of $S$, which is impossible.

c) True. For any set $A$, $A$ is a superset of $\emptyset$. This is because all elements of $\emptyset$ (of which there are none) are contained in $A$. This is known as a vacuously true statement.

d) True. Any set $A$ is a superset of itself because every element in $A$ is, trivially, an element in $A$.

e) False. Consider the set $A = \{1\}$. We can create an infinite number of supersets: $\{1, 2\}, \{1, 3\}, \{1, 4\}, \dots$. More formally, for any set $A$, we can form an infinite number of supersets by taking the union of $A$ with any set containing elements not in $A$.
Question 7: The union of two sets $A$ and $B$ contains all elements in $A$ or $B$: $A \cup B = \{x: x \in A \text{ or } x \in B \}$. Prove that if $A \subseteq B$, then $A \cup B = B$.

To prove the set equality $A \cup B = B$, you must show two things: (1) $A \cup B \subseteq B$ and (2) $B \subseteq A \cup B$.

We must prove two inclusions.

Part 1: Show $A \cup B \subseteq B$.
Let $x$ be an arbitrary element in $A \cup B$. By the definition of union, this means $x \in A$ or $x \in B$. We consider these two cases:
  • Case 1: If $x \in A$, then since we are given that $A \subseteq B$, it must be that $x \in B$.
  • Case 2: If $x \in B$, then $x \in B$.
In both possible cases, if $x \in A \cup B$, then $x \in B$. Therefore, by definition of a subset, $A \cup B \subseteq B$.

Part 2: Show $B \subseteq A \cup B$.
Let $x$ be an arbitrary element in $B$. By the definition of union, $A \cup B$ contains all elements that are in $A$ OR in $B$. Since $x$ is in $B$, it is automatically included in $A \cup B$. Therefore, by definition of a subset, $B \subseteq A \cup B$.

Since we have shown mutual inclusion ($A \cup B \subseteq B$ and $B \subseteq A \cup B$), we can conclude that $A \cup B = B$.
©