Introduction to Set Theory

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Given a countably infinite set $S$ and its power set $\mathcal{P}(S)$, formulate a precise argument, leveraging Zermelo’s Axiom of Choice, demonstrating the existence of a surjection from $\mathcal{P}(S)$ onto $S$. Detail any subtle dependencies on choice principles.

Assuming the Axiom of Choice, for each non-empty subset $A \subseteq S$, choose an element $f(A) \in A$. This defines a function $f: \mathcal{P}(S) \setminus {\emptyset} \to S$. Since $S$ is countably infinite, its cardinality is $\aleph_0$, while the cardinality of $\mathcal{P}(S)$ is $2^{\aleph_0}$, which is strictly greater than $\aleph_0$ (Cantor's Theorem). Without additional axioms, constructing a surjection is not straightforward. The ability to choose such an element from each subset necessitates the Axiom of Choice, particularly if we seek such a function explicitly.

Consider an uncountable set $X$ within a universal set $U$. Construct a rigorous proof demonstrating that either the complement of $X$ in $U$, denoted $X^c$, is also uncountable, or provide a counterexample and a justification for why a general proof is unattainable within ZFC set theory.

Assume, for contradiction, $X^c$ is countable. Then $U = X \cup X^c$. If both $X$ and $X^c$ are countable, then $U$ would be countable, which contradicts the premise that $X$ is uncountable and a subset of a universal set $U$. Therefore $X^c$ must be uncountable, unless $U$ is countable, in which case the premise that X is uncountable is violated. A counterexample within ZFC is unattainable, as that would violate fundamental properties of set theory.

Given two sets $A$ and $B$, define a third set $C$ such that $C \subseteq A \cup B$, $C \cap A \neq \emptyset$, and $C \cap B \neq \emptyset$. Formulate a necessary and sufficient condition, expressed in terms of set inclusion or equality involving $A$, $B$, and $C$, under which $C = A \cup B$.

The necessary and sufficient condition is that $A \subseteq C$ and $B \subseteq C$. This ensures that every element in $A$ and every element in $B$ is also in $C$, and since $C$ is already a subset of $A \cup B$, this implies that $C$ must be equal to $A \cup B$.

Let $A$ and $B$ be arbitrary sets. Prove that $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$, where $\mathcal{P}(X)$ denotes the power set of $X$.

Let $X \in \mathcal{P}(A \cap B)$. Then $X \subseteq A \cap B$, implying $X \subseteq A$ and $X \subseteq B$. Thus, $X \in \mathcal{P}(A)$ and $X \in \mathcal{P}(B)$, so $X \in \mathcal{P}(A) \cap \mathcal{P}(B)$. Conversely, if $Y \in \mathcal{P}(A) \cap \mathcal{P}(B)$, then $Y \in \mathcal{P}(A)$ and $Y \in \mathcal{P}(B)$, meaning $Y \subseteq A$ and $Y \subseteq B$. Thus, $Y \subseteq A \cap B$, so $Y \in \mathcal{P}(A \cap B)$. Therefore, $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$. Signup and view all the answers

Consider an infinite sequence of sets $A_1, A_2, A_3, \dots$. Define $\liminf_{n \to \infty} A_n$ and $\limsup_{n \to \infty} A_n$. Provide a comprehensive example where $\liminf_{n \to \infty} A_n \neq \limsup_{n \to \infty} A_n$, and justify why they differ.

$\liminf_{n \to \infty} A_n = \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k$ and $\limsup_{n \to \infty} A_n = \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k$. Let $A_n = {0, 1}$ if $n$ is even, and $A_n = {1, 2}$ if $n$ is odd. Then $\bigcap_{k=n}^{\infty} A_k = {1}$ if $n$ is odd and $ \emptyset$ if $n$ is even, so $\liminf_{n \to \infty} A_n = {1}$. But $\bigcup_{k=n}^{\infty} A_k = {0, 1, 2}$ for all $n$, so $\limsup_{n \to \infty} A_n = {0, 1, 2}$. Thus, they differ because the intersection of the 'tail' of the sequence is not stable as n approaches infinity. Signup and view all the answers

Given sets $A$, $B$, and $C$, prove or disprove: If $A \cup B = A \cup C$, then $B = C$. If the statement is false, provide a counterexample and then specify additional conditions under which the implication becomes valid.

The statement is false. Counterexample: $A = {1}$, $B = {1, 2}$, $C = {1, 3}$. Then $A \cup B = {1, 2}$ and $A \cup C = {1, 3}$, so $A \cup B \neq A \cup C$, hence the premise false, showing the statement doesn't hold. However, if we also have $A \cap B = A \cap C$, and $A \cup B = A \cup C$, and A, B, and C are finite sets, then $B = C$. Signup and view all the answers

Formally define the concept of a 'hereditarily finite set'. Then, using only the axioms of ZFC set theory (without the Axiom of Infinity), prove that the set of all hereditarily finite sets is itself a set.

A set $x$ is hereditarily finite if $x$ is finite, and every element of $x$ is finite, and every element of every element of $x$ is finite, and so on. Formally, a set $x$ is hereditarily finite if its transitive closure, $TC({x})$, contains only finite sets. To prove the set of hereditarily finite sets exists, we can construct it inductively using the Power Set Axiom and the Axiom of Union. Let $V_0 = \emptyset$, $V_{n+1} = \mathcal{P}(V_n)$. Each $V_n$ is finite, and the set of all hereditarily finite sets is $\bigcup_{n \in \omega} V_n$. This construction, relying only on the Power Set and Union axioms (and without the Axiom of Infinity, since each $V_n$ is finite), shows that the set of all hereditarily finite sets is a set. Signup and view all the answers

Given the universal set $U = \mathbb{R}$, let $A = {x \in \mathbb{R} \mid x^2 < 2}$ and $B = {x \in \mathbb{R} \mid |x - 1| < 1}$. Determine the complement of $A \cap B$ with respect to $U$, expressing it in interval notation and rigorously justifying each step.

$A = (-\sqrt{2}, \sqrt{2})$ and $B = (0, 2)$. Thus, $A \cap B = (0, \sqrt{2})$. The complement of $A \cap B$ with respect to $U$ is $(-\infty, 0] \cup [\sqrt{2}, \infty)$. Signup and view all the answers

Let $S$ be a collection of sets. Define the properties that $S$ must satisfy to be considered a σ-algebra. Provide a non-trivial example of a σ-algebra on the set $X = {a, b, c}$.

A σ-algebra on a set $X$ is a collection $S$ of subsets of $X$ such that: 1) $\emptyset \in S$, 2) If $A \in S$, then $A^c \in S$, and 3) If $A_1, A_2, A_3, ... \in S$, then $\bigcup_{i=1}^{\infty} A_i \in S$. A non-trivial example on $X = {a, b, c}$ is $S = {\emptyset, {a}, {b, c}, {a, b, c}}$. Signup and view all the answers

Let $A$ and $B$ be subsets of a universal set $U$. Without using Venn diagrams, prove De Morgan's Law: $(A \cup B)^c = A^c \cap B^c$.

Let $x \in (A \cup B)^c$. This means $x \in U$ and $x \notin (A \cup B)$. Thus, $x \notin A$ and $x \notin B$, which implies $x \in A^c$ and $x \in B^c$. Therefore, $x \in A^c \cap B^c$. Conversely, let $x \in A^c \cap B^c$. This means $x \in A^c$ and $x \in B^c$, so $x \notin A$ and $x \notin B$. Thus, $x \notin (A \cup B)$, which implies $x \in (A \cup B)^c$. Hence, $(A \cup B)^c = A^c \cap B^c$. Signup and view all the answers

Define the symmetric difference of two sets $A$ and $B$, denoted $A \triangle B$. Prove that $A \triangle B = (A \cup B) \setminus (A \cap B)$.

The symmetric difference $A \triangle B = (A \setminus B) \cup (B \setminus A)$. Now, $(A \cup B) \setminus (A \cap B) = (A \cup B) \cap (A \cap B)^c = (A \cup B) \cap (A^c \cup B^c) = (A \cap (A^c \cup B^c)) \cup (B \cap (A^c \cup B^c)) = (A \cap A^c) \cup (A \cap B^c) \cup (B \cap A^c) \cup (B \cap B^c) = \emptyset \cup (A \setminus B) \cup (B \setminus A) \cup \emptyset = (A \setminus B) \cup (B \setminus A) = A \triangle B$. Signup and view all the answers

Let $f: X \to Y$ be a function, and let $A, B \subseteq X$. Prove or disprove: $f(A \cap B) = f(A) \cap f(B)$. If the statement is false, provide a counterexample and then specify conditions under which the implication becomes valid.

The statement is false. Counterexample: Let $X = {1, 2}$, $Y = {3}$, $f(1) = 3$, $f(2) = 3$, $A = {1}$, $B = {2}$. Then $A \cap B = \emptyset$, so $f(A \cap B) = \emptyset$. However, $f(A) = {3}$ and $f(B) = {3}$, so $f(A) \cap f(B) = {3}$. Thus, $f(A \cap B) \neq f(A) \cap f(B)$. The implication becomes valid if $f$ is injective (one-to-one). Signup and view all the answers

Let $A, B, C$ be sets. Prove the distributive law: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

Let $x \in A \cap (B \cup C)$. This means $x \in A$ and $x \in (B \cup C)$. Thus, $x \in A$ and ($x \in B$ or $x \in C$). This implies ($x \in A$ and $x \in B$) or ($x \in A$ and $x \in C$), which means $x \in (A \cap B)$ or $x \in (A \cap C)$. Therefore, $x \in (A \cap B) \cup (A \cap C)$. Conversely, let $x \in (A \cap B) \cup (A \cap C)$. This means $x \in (A \cap B)$ or $x \in (A \cap C)$. Thus, ($x \in A$ and $x \in B$) or ($x \in A$ and $x \in C$). This implies $x \in A$ and ($x \in B$ or $x \in C$), which means $x \in A$ and $x \in (B \cup C)$. Therefore, $x \in A \cap (B \cup C)$. Hence, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. Signup and view all the answers

Suppose $A$ and $B$ are sets such that $A \subseteq B$. Prove that $B^c \subseteq A^c$.

Let $x \in B^c$. This means $x \notin B$. Since $A \subseteq B$, if $x \notin B$, then $x \notin A$. Therefore, $x \in A^c$. Hence, $B^c \subseteq A^c$. Signup and view all the answers

Formulate a statement, equivalent to the Axiom of Choice, using only the concepts of sets, functions, and surjections. Justify the equivalence rigorously.

A statement equivalent to the Axiom of Choice is: For every surjection $f: A \to B$, there exists a function $g: B \to A$ such that $f(g(b)) = b$ for all $b \in B$. This $g$ is called a section of $f$. Justification: AC implies the existence of a choice function, and the selection function can be leveraged to make choices in this context. Without AC, such a function, $g$, might not be guaranteed to exist. Signup and view all the answers

Given a set $A$, characterize the set of all subsets of $A$ that are both open and closed in the discrete topology on $A$. Provide a proof for your characterization.

In the discrete topology on $A$, every subset of $A$ is both open and closed. Proof: In the discrete topology, every singleton set ${x}$ for $x \in A$ is open. Any subset $B \subseteq A$ can be written as the union of its singleton sets: $B = \bigcup_{x \in B} {x}$. Since any union of open sets is open, $B$ is open. Similarly, since every singleton set is open, its complement is closed. Therefore, every subset must be both open and closed. Signup and view all the answers

Let $A$ be a set. Prove that there is no surjection from $A$ to its power set $\mathcal{P}(A)$. (Cantor’s Theorem)

Suppose, for the sake of contradiction, there exists a surjection $f: A \to \mathcal{P}(A)$. Consider the set $B = {x \in A \mid x \notin f(x)}$. Since $B \subseteq A$, $B \in \mathcal{P}(A)$. Because $f$ is a surjection, there exists an element $a \in A$ such that $f(a) = B. Now ask: Is $a \in B$? If $a \in B$, then by definition of $B$, $a \notin f(a) = B$, a contradiction. If $a \notin B$, then by definition of $B$, $a \in f(a) = B$, again a contradiction. Therefore, our assumption that such a surjection $f$ exists must be false. Signup and view all the answers

Consider a partially ordered set $(X, \leq)$. Define what it means for a subset $C \subseteq X$ to be a chain. Then, leveraging Zorn's Lemma, prove that every set $A$ contains a maximal chain with respect to set inclusion.

A chain in a partially ordered set $(X, \leq)$ is a subset $C \subseteq X$ such that for all $x, y \in C$, either $x \leq y$ or $y \leq x$. To prove every set $A$ contains a maximal chain, let $S$ denote the set of all chains in $A$, partially ordered by set inclusion. Let $C$ be a chain in $S$. Then $ \bigcup C$ is also a chain in A, and is an upper bound for $C$. Thus, by Zorn's Lemma, $S$ has a maximal element, which is a maximal chain in A. Signup and view all the answers

Let $A$ be a set. Define the characteristic function $\chi_A(x)$ of $A$. Then, given two sets $A$ and $B$, express the characteristic function of $A \cup B$, $A \cap B$, and $A^c$ in terms of $\chi_A(x)$ and $\chi_B(x)$. Where complements are defined with respect to a universal set, $U$.

The characteristic function $\chi_A(x)$ of a set $A$ is defined as $\chi_A(x) = 1$ if $x \in A$, and $\chi_A(x) = 0$ if $x \notin A$. Then: $\chi_{A \cup B}(x) = \chi_A(x) + \chi_B(x) - \chi_A(x)\chi_B(x)$, $\chi_{A \cap B}(x) = \chi_A(x)\chi_B(x)$, and $\chi_{A^c}(x) = 1 - \chi_A(x)$. Signup and view all the answers

Let $A$ and $B$ be two sets. Prove or disprove that $\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(B)$. If false, provide a counterexample and describe the correct relationship between the two sets.

The statement is false. Counterexample: Let $A = {1}$ and $B = {2}$. Then $A \cup B = {1, 2}$, so $\mathcal{P}(A \cup B) = {\emptyset, {1}, {2}, {1, 2}}$. However, $\mathcal{P}(A) = {\emptyset, {1}}$ and $\mathcal{P}(B) = {\emptyset, {2}}$, so $\mathcal{P}(A) \cup \mathcal{P}(B) = {\emptyset, {1}, {2}}$. The correct relationship is $\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$. Signup and view all the answers

Let $f:X \rightarrow Y$ be a function. For any subset $B$ of $Y$, define $f^{-1}(B) = {x \in X | f(x) \in B}$ as the preimage of $B$. Prove that for any collection of subsets ${B_i}{i \in I}$ of $Y$, $f^{-1}(\bigcup{i \in I} B_i) = \bigcup_{i \in I} f^{-1}(B_i)$.

Let $x \in f^{-1}(\bigcup_{i \in I} B_i)$. Then $f(x) \in \bigcup_{i \in I} B_i$, which implies that there exists some $i_0 \in I$ such that $f(x) \in B_{i_0}$. This means that $x \in f^{-1}(B_{i_0})$, and therefore $x \in \bigcup_{i \in I} f^{-1}(B_i)$. Conversely, let $x \in \bigcup_{i \in I} f^{-1}(B_i)$. Then there exists some $i_0 \in I$ such that $x \in f^{-1}(B_{i_0})$. This means that $f(x) \in B_{i_0}$, and therefore $f(x) \in \bigcup_{i \in I} B_i$. This implies that $x \in f^{-1}(\bigcup_{i \in I} B_i)$. Therefore, $f^{-1}(\bigcup_{i \in I} B_i) = \bigcup_{i \in I} f^{-1}(B_i)$. Signup and view all the answers

Let $A$ and $B$ be two sets. Prove that if $A \subseteq B$, then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$, where $\mathcal{P}(X)$ denotes the power set of $X$.

Suppose $A \subseteq B$. Let $X \in \mathcal{P}(A)$. Then $X \subseteq A$. Since $A \subseteq B$, it follows that $X \subseteq B$. Thus, $X \in \mathcal{P}(B)$. Therefore, if $A \subseteq B$, then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$. Signup and view all the answers

Flashcards

What is a Set?

A well-defined collection of distinct objects, considered as an object in its own right.

What are Elements?

Objects that make up a set.

What is the Roster Method?

Listing all elements within curly braces. E.g., A = {1, 2, 3, 4}.

What is Set-Builder Notation?

Defining a set by specifying a property that its elements must satisfy. E.g., B = {x | x is an even number}.