Set theory Study Guide

📖 Core Concepts Set: A collection of distinct objects (elements). Element membership: $o \in A$ means o is in set A. Subset: $A \subseteq B$ ⇔ every element of A is also in B. Proper subset: $A \subset B$ ⇔ $A \subseteq B$ and $A \neq B$. Power set: $\mathcal{P}(A)=\{\,S\mid S\subseteq A\,\}$, the set of all subsets of A. Cardinality: Size of a set; two sets have the same cardinality iff there is a bijection between them. Countable vs. Uncountable: Countable: can be listed (bijection with $\mathbb{N}$). Uncountable: cannot be listed (e.g., $\mathbb{R}$). Transfinite numbers: Cardinals: $\aleph0, \aleph1,\dots$ (sizes of infinite sets). Ordinals: $\omega, \omega+1,\dots$ (order types of well‑ordered sets). Axiomatic set theory (ZFC): Formal system (Zermelo–Fraenkel + Choice) that avoids paradoxes by restricting set formation. Universe $V$: The class of all sets obtainable from the ZFC axioms; a model of ZFC. --- 📌 Must Remember Cantor’s Theorem: $|\mathcal{P}(A)| > |A|$ for any set $A$ (even infinite). Uncountability of $\mathbb{R}$: No bijection $\mathbb{R}\leftrightarrow\mathbb{N}$ (proved by diagonalization). Empty set: $\varnothing$ has no elements; $\varnothing \subseteq A$ for any $A$. Union / Intersection: $A\cup B = \{x\mid x\in A\lor x\in B\}$ $A\cap B = \{x\mid x\in A\land x\in B\}$ Complement: $A^{c}=U\setminus A$ (relative to a universal set $U$). Symmetric difference: $A\triangle B = (A\setminus B)\cup(B\setminus A)$. Cartesian product: $A\times B=\{(a,b)\mid a\in A,\,b\in B\}$. Axiom of Choice (AC): For any family of non‑empty sets $\{Ai\}{i\in I}$, there exists a function $f$ with $f(i)\in Ai$ for each $i$. --- 🔄 Key Processes Proving a set is countable Find an explicit bijection $f:\mathbb{N}\to S$ or show $S\subseteq\mathbb{N}$. Diagonalization (showing uncountability) Assume a listing of $\mathbb{R}$, construct a new real by flipping the $n^{\text{th}}$ digit of the $n^{\text{th}}$ entry → contradiction. Using Cantor’s Theorem Given $A$, define $g:A\to\mathcal{P}(A)$ by $g(a)=\{a\}$ (injective). Show no surjection $h:A\to\mathcal{P}(A)$ can exist via the classic “Russell set” $R=\{a\in A\mid a\notin h(a)\}$. Building sets in ZFC (von Neumann hierarchy) $V0=\varnothing$, $V{\alpha+1}=\mathcal{P}(V\alpha)$, $V\lambda=\bigcup{\beta<\lambda}V\beta$ for limit ordinal $\lambda$ → $V=\bigcup{\alpha}V\alpha$. --- 🔍 Key Comparisons Subset vs. Proper Subset $A\subseteq B$: $A$ may equal $B$. $A\subset B$: $A$ is strictly smaller; $A\neq B$. Union vs. Intersection Union adds elements (logical OR). Intersection keeps only common elements (logical AND). Power Set vs. Original Set $\mathcal{P}(A)$ contains all subsets, so $|\mathcal{P}(A)|$ is strictly larger than $|A|$. Naive Comprehension vs. Axiomatic (ZFC) Naive: “any property defines a set” → paradoxes (Russell). ZFC: Restricts comprehension to subsets of existing sets (Separation), avoiding paradoxes. --- ⚠️ Common Misunderstandings “Every infinite set is larger than $\mathbb{N}$.” False: $\mathbb{Z}$ and $\mathbb{Q}$ are countably infinite, same size as $\mathbb{N}$. “The power set of a finite set has the same cardinality as the set.” Wrong: $|\mathcal{P}(A)|=2^{|A|}$, always larger for $|A|\ge 1$. “A set cannot be an element of itself.” In ZFC this is guaranteed by the Foundation axiom; naive set theory allowed such “self‑membership” leading to paradoxes. “Choice is needed for every selection problem.” Not always; many finite or constructive selections can be made without AC. --- 🧠 Mental Models / Intuition Bijection = “perfect pairing”: Think of two groups of people shaking hands one‑to‑one; if every person in each group gets exactly one partner, the groups have the same size. Power set as “all possible committees”: From a pool $A$, each subset is a possible committee; the number of committees grows exponentially. Diagonalization as “changing the diagonal”: Visualize a list of infinite binary strings; flipping the diagonal creates a new string guaranteed to differ from every listed one. --- 🚩 Exceptions & Edge Cases Empty set in power set: $\mathcal{P}(\varnothing)=\{\varnothing\}$ (size 1, not 0). Singleton sets: $|\{x\}|=1$, but $\mathcal{P}(\{x\})=\{\varnothing,\{x\}\}$ (size 2). Axiom of Choice fails in some models: In the Cohen model, AC does not hold, showing that many results (e.g., every vector space has a basis) depend on AC. --- 📍 When to Use Which Counting problems → Try to construct an explicit bijection with $\mathbb{N}$ (countable) before declaring a set “infinite”. Comparing sizes of infinite sets → Use Cantor’s theorem (power set) or construct explicit bijections (e.g., $\mathbb{N}\leftrightarrow\mathbb{Z}$). Defining a new set → In ZFC, apply the Separation axiom: define $B=\{x\in A\mid \varphi(x)\}$ rather than unrestricted comprehension. Need a choice function → If you have an indexed family of non‑empty disjoint sets and must pick one element from each, invoke AC. --- 👀 Patterns to Recognize “Listability” ⇒ Countable: Whenever a problem mentions “can be listed” or “enumerated”, think countable. Diagonal argument structure: Assume a complete list, construct an element differing in the $n^{\text{th}}$ place of the $n^{\text{th}}$ entry → uncountable. Subset‑of‑Power‑Set growth: Whenever you see $\mathcal{P}$ appear, expect an exponential increase in cardinality. Paradox clues: Statements like “the set of all sets that do not contain themselves” signal the need for axiomatic restrictions. --- 🗂️ Exam Traps Mistaking “subset” for “proper subset” – answer choice may say “$A\subset B$” when $A=B$; the correct notation for “could be equal” is $\subseteq$. Assuming all infinite sets are uncountable – $\mathbb{Q}$ is a classic counter‑example. Confusing power set size with original set size – $|\mathcal{P}(A)| = 2^{|A|}$, never equal unless $A=\varnothing$. Forgetting the need for AC – statements like “every family of non‑empty sets has a choice function” are false without AC; exam may present a finite family to trick you. Misapplying diagonalization – it proves uncountability of $\mathbb{R}$, not that $\mathbb{R}$ is “larger than any set”; the correct conclusion is $|\mathbb{R}| > |\mathbb{N}|$. ---