Set Theory

Goal: Evaluate the truth value of each set membership and subset relation, providing formal justifications.

Analysis:

• (a) $0 \in \emptyset$:
  • By definition, the empty set $\emptyset$ contains no elements.
  • Therefore, no object can belong to it. False.
• (b) $\emptyset \in \{0\}$:
  • The set $\{0\}$ contains exactly one element: the integer $0$. Since $\emptyset \neq 0$, the empty set is not an element of $\{0\}$. False.
• (c) $\{0\} \subset \emptyset$:
  • A subset relation $A \subseteq B$ requires every element of $A$ to be in $B$. Since $0 \in \{0\}$ but $0 \notin \emptyset$, $\{0\}$ is not a subset. False.
• (d) $\emptyset \subset \{0\}$:
  • Recall that the empty set is a subset of every set. Since $\{0\}$ contains elements ($0$), $\emptyset \subseteq \{0\}$. Since $\emptyset \neq \{0\}$, the subset relation is proper ($\subset$). True.
• (e) $\{\emptyset\} \subseteq \{\emptyset\}$:
  • Any set is a subset of itself. Since $\{\emptyset\} = \{\emptyset\}$, the subset relation holds. True. ∎

Goal: Prove the logical equivalence by showing both directions of implication: (1) $\mathcal{P}(A) \subseteq \mathcal{P}(B) \implies A \subseteq B$, and (2) $A \subseteq B \implies \mathcal{P}(A) \subseteq \mathcal{P}(B)$.

Proof:

1. Part 1: Prove $A \subseteq B \implies \mathcal{P}(A) \subseteq \mathcal{P}(B)$ (Right-to-Left).
   • Assume $A \subseteq B$.
   • Let $X$ be an arbitrary element of the power set $\mathcal{P}(A)$. By definition, $X$ is a subset of $A$: $$X \subseteq A$$
   • Since subset inclusion is transitive, and we assumed $A \subseteq B$: $$X \subseteq A \text{ and } A \subseteq B \implies X \subseteq B$$
   • By definition of the power set, since $X \subseteq B$, we have $X \in \mathcal{P}(B)$.
   • Since any arbitrary element of $\mathcal{P}(A)$ belongs to $\mathcal{P}(B)$, we conclude $\mathcal{P}(A) \subseteq \mathcal{P}(B)$.
2. Part 2: Prove $\mathcal{P}(A) \subseteq \mathcal{P}(B) \implies A \subseteq B$ (Left-to-Right).
   • Assume $\mathcal{P}(A) \subseteq \mathcal{P}(B)$.
   • Recall that every set is a subset of itself: $A \subseteq A$. By definition of the power set: $$A \in \mathcal{P}(A)$$
   • By our assumption that $\mathcal{P}(A) \subseteq \mathcal{P}(B)$, every element of $\mathcal{P}(A)$ must belong to $\mathcal{P}(B)$. Therefore: $$A \in \mathcal{P}(B)$$
   • By definition of the power set, this means $A$ is a subset of $B$: $$A \subseteq B$$

Since both directions of implication are proven, the equivalence holds. ∎

Goal: Find the sizes of the union and the disjoint partitioned regions of the three sets using the Principle of Inclusion-Exclusion.

Step-by-Step Calculation:

1. Calculate $|U| = |A \cup B \cup C|$: By the Principle of Inclusion-Exclusion: $$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$$ Substitute the given values: $$|U| = 10 + 12 + 14 - 5 - 6 - 4 + 2 = 23$$
2. Calculate the number of elements in exactly two sets: Let $x_{AB}, x_{BC}, x_{CA}$ be the number of elements belonging *only* to those pairs of sets.
   • $x_{AB} = |A \cap B| - |A \cap B \cap C| = 5 - 2 = 3$
   • $x_{BC} = |B \cap C| - |A \cap B \cap C| = 6 - 2 = 4$
   • $x_{CA} = |C \cap A| - |A \cap B \cap C| = 4 - 2 = 2$
   Summing these gives the total elements in exactly two sets: $$\text{Exactly two} = 3 + 4 + 2 = 9$$
3. Calculate the number of elements in exactly one set: The union is partitioned into elements in exactly one set, exactly two sets, and all three sets: $$|U| = \text{Exactly one} + \text{Exactly two} + \text{Exactly three}$$ $$23 = \text{Exactly one} + 9 + 2 \implies \text{Exactly one} = 23 - 11 = 12$$

Conclusion: $|U| = 23$, size of exactly two is $9$, and size of exactly one is $12$. ∎

Goal: Find the maximum and minimum possible cardinality of the intersection of three sets $P, M, S$ within a universal set $U$ of size 100.

Step-by-Step Derivation:

1. Find Maximum possible intersection: The intersection of sets cannot exceed the size of the smallest set in the intersection. $$\text{Max} = \min(|P|, |M|, |S|) = \min(73, 80, 52) = 52$$
2. Find Minimum possible intersection: Let's analyze the complements. The size of the complement union is: $$|P^c \cup M^c \cup S^c| \leq |P^c| + |M^c| + |S^c|$$ Where:
   • $|P^c| = 100 - 73 = 27$
   • $|M^c| = 100 - 80 = 20$
   • $|S^c| = 100 - 52 = 48$
   Thus: $$|P^c \cup M^c \cup S^c| \leq 27 + 20 + 48 = 95$$ Using De Morgan's Law, the intersection is the complement of the union of complements: $$|P \cap M \cap S| = 100 - |P^c \cup M^c \cup S^c| \geq 100 - 95 = 5$$ So the minimum size is 5.
3. Calculate difference: $$\text{Max} - \text{Min} = 52 - 5 = 47$$

Conclusion: The difference between the maximum and minimum number of students studying all three is 47. ∎

Goal: Find the union and intersection of the nested sequence of sets $A_i$ for $i = 1, \ldots, n$.

Step-by-Step Analysis:

1. Observe the set relations: Let's write out the first few sets:
   • $A_1 = \{1\}$
   • $A_2 = \{1, 2\}$
   • $A_3 = \{1, 2, 3\}$
   Clearly, $A_1 \subset A_2 \subset A_3 \subset \cdots \subset A_n$. This is a nested chain of sets.
2. Determine Union: For any nested chain $A_1 \subseteq A_2 \subseteq \dots \subseteq A_n$, the union is the largest set in the chain: $$\bigcup_{i=1}^n A_i = A_n = \{1, 2, \ldots, n\}$$
3. Determine Intersection: Similarly, the intersection is the smallest set in the chain: $$\bigcap_{i=1}^n A_i = A_1 = \{1\}$$ ∎

Goal: Find the union and intersection of the infinite-subset sequence $A_i = \{x \in \mathbb{Z} : x \leq i\}$ over the indices $i=1, \dots, n$.

Step-by-Step Analysis:

1. Observe the set relation: We can write:
   • $A_1 = \{\dots, -1, 0, 1\}$
   • $A_2 = \{\dots, -1, 0, 1, 2\}$
   Since every element in $A_k$ is also in $A_{k+1}$, we have the chain: $$A_1 \subset A_2 \subset \dots \subset A_n$$
2. Determine Union: The union of a nested chain is the largest set: $$\bigcup_{i=1}^n A_i = A_n = \{x \in \mathbb{Z} : x \leq n\}$$
3. Determine Intersection: The intersection of a nested chain is the smallest set: $$\bigcap_{i=1}^n A_i = A_1 = \{x \in \mathbb{Z} : x \leq 1\}$$ ∎

Goal: Find the infinite union and intersection for each of the given families of sets.

Analysis:

• (a) $A_i = \{i, i+1, \ldots\}$:
  • Union: $A_1 \cup A_2 \cup \dots = \{1, 2, \dots\} \cup \{2, 3, \dots\} \cup \dots = \mathbb{N}$.
  • Intersection: Suppose some integer $x \in \bigcap A_i$. This means $x \geq i$ for all $i \geq 1$. By the Archimedean property, no such integer exists. Thus, the intersection is empty: $\emptyset$.
• (b) $A_i = \{0, i\}$:
  • Union: The element $0$ is in every set, and every positive integer $i$ appears in the set $A_i$. Thus: $\bigcup A_i = \{0, 1, 2, \dots\} = \mathbb{N}_0$.
  • Intersection: Only $0$ is present in every set $A_i$. Hence: $\bigcap A_i = \{0\}$.
• (c) $A_i = (0, i)$ (open intervals in $\mathbb{R}$):
  • Union: As $i \to \infty$, the upper bound grows arbitrarily large. Thus: $\bigcup A_i = (0, \infty)$.
  • Intersection: The smallest interval in the family is $A_1 = (0, 1)$. Since $A_1 \subset A_2 \subset \dots$, the intersection is $A_1 = (0, 1)$.
• (d) $A_i = (i, \infty)$:
  • Union: $A_1 = (1, \infty)$ contains all other intervals in the chain ($A_1 \supset A_2 \dots$). Thus: $\bigcup A_i = A_1 = (1, \infty)$.
  • Intersection: No real number can be greater than all integers $i$. Thus: $\bigcap A_i = \emptyset$. ∎

Goal: Prove the characteristic function relations for basic set operations.

Proof: We evaluate the truth value of membership for any element $x \in U$. The characteristic function $f_S(x) = 1$ if $x \in S$ and $0$ if $x \notin S$.

• (a) Intersection: $x \in A \cap B \iff x \in A \text{ and } x \in B$.
  • If $x \in A$ and $x \in B$, then $f_A(x) = 1, f_B(x) = 1$, and $f_A(x)f_B(x) = 1 \cdot 1 = 1 = f_{A \cap B}(x)$.
  • If $x \notin A$ or $x \notin B$, then at least one is 0, product is 0, and $f_{A \cap B}(x) = 0$. Both sides match.
• (b) Union: $x \in A \cup B \iff x \in A \text{ or } x \in B$.
  • If $x \in A$ and $x \in B$: $f_A(x)+f_B(x)-f_A(x)f_B(x) = 1 + 1 - 1 = 1$. True.
  • If $x \in A, x \notin B$: $1 + 0 - 0 = 1$. True.
  • If $x \notin A, x \notin B$: $0 + 0 - 0 = 0$. False. Both sides match.
• (c) Complement: $x \in \bar{A} \iff x \notin A$.
  • If $x \in A$: $f_A(x) = 1$, $1 - f_A(x) = 0 = f_{\bar{A}}(x)$.
  • If $x \notin A$: $f_A(x) = 0$, $1 - f_A(x) = 1 = f_{\bar{A}}(x)$. Both sides match.
• (d) Symmetric Difference: $x \in A \oplus B \iff x$ is in exactly one of $A$ or $B$.
  • If $x \in A, x \in B$: $1 + 1 - 2(1) = 0$. False.
  • If $x \in A, x \notin B$: $1 + 0 - 0 = 1$. True.
  • If $x \notin A, x \notin B$: $0 + 0 - 0 = 0$. False. Both sides match. ∎

Goal: Determine the cardinality class of each set and define an explicit bijection with $\mathbb{N}$ if countably infinite.

Analysis:

• (a) Negative integers ($S = \{-1, -2, -3, \dots\}$): Countably infinite. The function $f(n) = -n$ provides a bijection $\mathbb{N} \to S$.
• (b) Even integers ($S = \{0, 2, -2, 4, -4, \dots\}$): Countably infinite. We can list the elements as: $0, 2, -2, 4, -4, \dots$. The bijection $f: \mathbb{N} \to S$ is: $$f(n) = \begin{cases} n - 1 & n \text{ is odd} \\ -n & n \text{ is even} \end{cases}$$
• (c) Integers $< 100$ ($S = \{99, 98, 97, \dots\}$): Countably infinite. The function $f(n) = 100 - n$ maps $1 \to 99$, $2 \to 98$, etc., providing a bijection $\mathbb{N} \to S$.
• (d) Positive integers $< 10^9$: Finite. The set has a finite cardinality of $10^9 - 1$ elements. No bijection to $\mathbb{N}$ exists.
• (e) Multiples of 7 ($S = \{\dots, -14, -7, 0, 7, 14, \dots\}$): Countably infinite. Let $g: \mathbb{N} \to \mathbb{Z}$ be the standard bijection mapping natural numbers to all integers. Then $f(n) = 7 \cdot g(n)$ is a bijection $\mathbb{N} \to S$. ∎

Goal: Prove that the set of all real roots of quadratic equations with integer coefficients is countable.

Proof:

1. Let $E$ be the set of all quadratic equations $ax^2 + bx + c = 0$ with $a, b, c \in \mathbb{Z}$. Each equation is uniquely identified by a triple of integers $(a, b, c) \in \mathbb{Z}^3$.
2. The Cartesian product $\mathbb{Z}^3$ is countable because it is a finite product of countable sets ($\mathbb{Z}$). Thus, $E$ is countable.
3. Each quadratic equation has at most 2 real roots. Let $S(a,b,c)$ be the set of real roots for the equation corresponding to $(a,b,c)$. Clearly, $|S(a,b,c)| \leq 2$ (finite).
4. The set of all such roots $R$ is the union of the root sets over all integer triples: $$R = \bigcup_{(a,b,c) \in \mathbb{Z}^3} S(a,b,c)$$
5. Since $R$ is a countable union of finite sets, by theorem, $R$ is countable. ∎

Goal: Prove the existence of uncomputable functions using cardinality arguments.

Proof:

1. (a) Programs are countable: Let $\Sigma$ be the finite alphabet of characters used to write code. Any computer program is a finite string of length $k \geq 0$ over $\Sigma$. For each length $k$, there are $|\Sigma|^k$ possible strings (which is finite). The set of all programs is the union over all possible string lengths: $$\text{Programs} \subseteq \bigcup_{k=0}^\infty \Sigma^k$$ Since the set of all programs is a subset of a countable union of finite sets, it is countable.
2. (b) Functions $\mathbb{N} \to \{0,\ldots,9\}$ are uncountable: Suppose, for contradiction, that the set of functions $F = \{f_1, f_2, \dots\}$ is countable. We construct a function $h: \mathbb{N} \to \{0,\dots,9\}$ as follows: $$h(n) = \begin{cases} 5 & \text{if } f_n(n) \neq 5 \\ 6 & \text{if } f_n(n) = 5 \end{cases}$$ Since $h(n) \neq f_n(n)$ for every $n$, $h$ differs from every function in the list. Thus, $h \notin F$, contradicting that $F$ is complete. Hence, the set of functions is uncountable.
3. (c) Uncomputable functions exist: Every computable function must be computed by some computer program. Since there is a surjection from the countable set of programs to the set of computable functions, the set of computable functions is countable. However, the set of all functions is uncountable. Thus, the set of all functions is strictly larger than the set of computable functions. Therefore, there must exist functions that are not computable. ∎

Goal: Provide the room mapping functions for each Hilbert Hotel scenario.

Solutions:

• (a) $k$ new guests: Move the guest in room $n$ to room $n+k$. This frees up rooms $1, \dots, k$ for the new guests. Mapping: $f(n) = n + k$.
• (b) Close even rooms: Move the guest in room $n$ to room $2n-1$ (the $n$-th odd room). This shifts all guests to odd rooms, freeing up all even rooms. Mapping: $f(n) = 2n - 1$.
• (c) Two hotels: Move guest in room $n$ of the original hotel to room $2n-1$ of the first hotel. Move guest in room $n$ of the second hotel to room $2n$ of the first hotel. Mappings: $f_1(n) = 2n-1, f_2(n) = 2n$.
• (d) Countably many new guests: Move existing guest in room $n$ to room $2n$. Place the $k$-th new guest in room $2k-1$.
• (e) Countably many buses, each with countably many guests: First, move all current guests to odd rooms: $f(n) = 2n-1$. Index the new guests as pairs $(b, s) \in \mathbb{N} \times \mathbb{N}$ (bus $b$, seat $s$). Since $\mathbb{N} \times \mathbb{N}$ is countable, we apply a diagonal traversal to map $(b,s)$ to the remaining even rooms: $$g(b, s) = 2 \cdot \left[ \frac{(b+s-1)(b+s-2)}{2} + s \right]$$ ∎

Goal: Prove the cardinality class of the set of all binary-valued functions on $\mathbb{N}$.

Proof (by Contradiction):

1. Suppose $G$ is countable. Then we can list all functions in $G$ as a sequence: $G = \{g_1, g_2, g_3, \dots\}$.
2. We define a new function $h: \mathbb{N} \to \{0, 1\}$ by: $$h(n) = 1 - g_n(n)$$
3. By construction, $h(n) \in \{0, 1\}$ for all $n$, so $h$ is a valid function in $G$.
4. However, if we compare $h$ to any listed function $g_k$ at the input $k$: $$h(k) = 1 - g_k(k) \neq g_k(k)$$ Therefore, $h \neq g_k$ for any $k \geq 1$.
5. This contradicts the assumption that the list contains all functions in $G$. Thus, $G$ must be uncountable. ∎

Goal: Define Russell's Set and show how its existence leads to a contradiction in naive set theory.

Solution:

1. (a) Definition of Russell's Set: $$R = \{S : S \notin S\}$$ "$R$ is the set containing all sets $S$ that are not members of themselves."
2. (b) Contradiction derivation: If $R$ is a valid set, we must determine the truth value of the proposition $R \in R$.
   • Case 1 ($R \in R$): If $R \in R$, then $R$ satisfies the condition to be a member of $R$. The condition is $S \notin S$, so we must have $R \notin R$. This is a contradiction.
   • Case 2 ($R \notin R$): If $R \notin R$, then $R$ satisfies the defining property $S \notin S$. Thus, $R$ must be an element of $R$, so $R \in R$. This is also a contradiction.
   Since both cases lead to a contradiction ($R \in R \iff R \notin R$), the set $R$ cannot exist in a consistent axiomatic framework. ∎

Goal: Prove that the set $S$ of all infinite binary strings is uncountable using Cantor's diagonalization argument.

Proof (by Contradiction):

1. Suppose $S$ is countable. Then we can list all infinite binary strings as a sequence: $S = \{s_1, s_2, s_3, \dots\}$.
2. Let $s_{i,j}$ denote the $j$-th bit of the $i$-th string in our list. $$s_1 = s_{1,1}s_{1,2}s_{1,3}\dots$$ $$s_2 = s_{2,1}s_{2,2}s_{2,3}\dots$$ $$s_3 = s_{3,1}s_{3,2}s_{3,3}\dots$$
3. We construct a new binary string $t = t_1 t_2 t_3 \dots$ by flipping the diagonal bits: $$t_n = 1 - s_{n,n} \quad \text{for all } n \geq 1.$$
4. The string $t$ consists only of bits in $\{0, 1\}$, so $t \in S$.
5. However, for any string $s_k$ in the list, $t$ differs from $s_k$ at the $k$-th position ($t_k \neq s_{k,k}$). Therefore, $t$ is not in the list.
6. This contradicts the completeness of the list. Thus, $S$ is uncountable. ∎

Goal: Provide a sketch of the proof of the undecidability of the Halting Problem.

Proof Sketch (by Diagonalization/Contradiction):

1. Suppose there exists a program $H(P, x)$ that decides the Halting Problem: $$H(P, x) = \begin{cases} 1 & \text{if program } P \text{ halts on input } x \\ 0 & \text{if program } P \text{ loops forever on input } x \end{cases}$$
2. We construct a new adversarial program $D(P)$ which takes a program $P$ as input:

   D(P):
     if H(P, P) == 1:
         loop forever
     else:
         halt

3. We now evaluate the execution of $D$ when passed itself as input: $D(D)$.
   • Case 1 ($D(D)$ halts): If $D(D)$ halts, then by definition of $H$, we must have $H(D, D) = 1$. Looking at the code of $D(D)$, since $H(D,D)==1$, the program enters the infinite loop and does not halt. Contradiction.
   • Case 2 ($D(D)$ loops forever): If $D(D)$ loops forever, then $H(D, D) = 0$. By the code of $D(D)$, the program enters the `else` branch and halts. Contradiction.
4. Since both cases lead to a logical contradiction, the program $H$ cannot exist. Thus, the Halting Problem is undecidable. ∎

Goal: Prove that the cardinality of the power set of any set $S$ is strictly greater than the cardinality of $S$.

Proof:

1. To show $|\mathcal{P}(S)| > |S|$, we must show there exists an injection from $S$ to $\mathcal{P}(S)$, but no bijection (surjection) exists.
2. Injection: Define $f: S \to \mathcal{P}(S)$ by $f(x) = \{x\}$. This is clearly injective. Thus, $|\mathcal{P}(S)| \geq |S|$.
3. No Surjection (Contradiction): Suppose there exists a surjective map $g: S \to \mathcal{P}(S)$. We define the "diagonal set" $D \subseteq S$ as: $$D = \{x \in S : x \notin g(x)\}$$
4. Since $D$ is a subset of $S$, $D \in \mathcal{P}(S)$. Since $g$ is assumed to be surjective, there must exist some element $d \in S$ such that: $$g(d) = D$$
5. We test whether $d \in D$:
   • If $d \in D$, then by definition of $D$, $d \notin g(d)$. Since $g(d) = D$, this means $d \notin D$. Contradiction.
   • If $d \notin D$, then $d \in g(d)$ must be true. Since $g(d) = D$, this means $d \in D$. Contradiction.
6. Thus, no such element $d$ can exist, meaning $g$ cannot be surjective. Therefore, $|\mathcal{P}(S)| > |S|$. ∎