Set Theory – Complete Reference Guide

Notation • Operations • Identities • Relations • Functions • Cardinality • Ordinals • ZFC Axioms

Set Notation

Roster Form

$A = \{1, 2, 3\}$ - List all elements

$B = \{a, e, i, o, u\}$ - Explicit enumeration

Set-Builder Form

$S = \{x \mid P(x)\}$ - Elements satisfying $P(x)$

$E = \{x \in \mathbb{N} \mid x \text{ is even}\}$

Common Sets

$\mathbb{N} = \{1, 2, 3, \ldots\}$ - Natural numbers

$\mathbb{Z} = \{\ldots, -1, 0, 1, \ldots\}$ - Integers

$\mathbb{Q}$ - Rationals, $\mathbb{R}$ - Reals

$\emptyset$ or $\varnothing$ - Empty set

$\mathbb{U}$ or $U$ - Universal set

Set Operations

Union

$A \cup B = \{x \mid x \in A \lor x \in B\}$

Contains all elements in $A$ or $B$

Intersection

$A \cap B = \{x \mid x \in A \land x \in B\}$

Contains only common elements

Complement

$A^c = \{x \in U \mid x \notin A\}$

All elements NOT in $A$

Difference

$A - B = A \setminus B = \{x \mid x \in A \land x \notin B\}$

Elements in $A$ but not in $B$

Symmetric Difference

$A \triangle B = (A - B) \cup (B - A)$

Set Identities

De Morgan's Laws

$(A \cup B)^c = A^c \cap B^c$

$(A \cap B)^c = A^c \cup B^c$

Distributive Laws

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Absorption Laws

$A \cup (A \cap B) = A$

$A \cap (A \cup B) = A$

Idempotent

$A \cup A = A$, $A \cap A = A$

Identity

$A \cup \emptyset = A$

$A \cap U = A$

Venn Diagrams

2-Set Venn Diagram

3-Set Venn Diagram

Overlapping regions show intersections

All regions partition the universal set

Cartesian Products

Definition

$A \times B = \{(a, b) \mid a \in A, b \in B\}$

Ordered pairs from $A$ and $B$

Properties

$|A \times B| = |A| \cdot |B|$

$A \times B \neq B \times A$ (generally non-commutative)

$(A \times B) \times C \neq A \times (B \times C)$

Relations

Any $R \subseteq A \times B$ is a relation

$(a, b) \in R$ means "$a$ relates to $b$"

Example

$\{1,2\} \times \{a,b\} = \{(1,a), (1,b), (2,a), (2,b)\}$

Power Sets

Definition

$\mathcal{P}(A) = \{S \mid S \subseteq A\}$

Set of ALL subsets of $A$

Properties

$|\mathcal{P}(A)| = 2^{|A|}$

$\mathcal{P}(\emptyset) = \{\emptyset\}$ with 1 element

$\emptyset \in \mathcal{P}(A)$ for all sets $A$

$A \in \mathcal{P}(A)$ for all sets $A$

Example

$\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$

4 subsets total: $2^2 = 4$

Relations: Domain & Range

Definitions

Relation $R \subseteq A \times B$

$\text{dom}(R) = \{a \in A \mid \exists b: (a,b) \in R\}$

$\text{ran}(R) = \{b \in B \mid \exists a: (a,b) \in R\}$

Relation Properties

$R$ is reflexive on $A$: $\forall a \in A, (a,a) \in R$

$R$ is symmetric: $(a,b) \in R \Rightarrow (b,a) \in R$

$R$ is transitive: $(a,b), (b,c) \in R \Rightarrow (a,c) \in R$

Inverse Relation

$R^{-1} = \{(b,a) \mid (a,b) \in R\}$

Equivalence Relations

Definition

$R$ is equivalence if reflexive, symmetric, transitive

Often denoted $a \sim b$

Equivalence Classes

$[a] = \{x \in A \mid x \sim a\}$

All elements equivalent to $a$

Partitions

$A = [a_1] \cup [a_2] \cup \cdots$ (disjoint union)

$[a] \cap [b] = \emptyset$ if $a \not\sim b$

Quotient Set

$A/\sim = \{[a] \mid a \in A\}$

Set of all equivalence classes

Partial Orders

Definition (Poset)

$R$ is a partial order if reflexive, antisymmetric, transitive

Notation: $(A, \leq)$ or $(A, \preceq)$

Properties

Antisymmetric: $(a \leq b \land b \leq a) \Rightarrow a = b$

$a < b$ means $a \leq b$ and $a \neq b$

Hasse Diagrams

Visual representation of posets

Nodes are elements, edges show relations

Omit reflexive and transitive edges

Special Elements

Minimal: No $a < b$ exists

Maximal: No $b > a$ exists

Minimum: $\leq$ all others

Maximum: $\geq$ all others

Functions: Basics

Definition

$f: A \to B$ with $\forall a \in A, \exists! b \in B, f(a) = b$

$A$ is domain, $B$ is codomain

Image & Preimage

$f(A) = \{f(a) \mid a \in A\}$ - Image/Range

$f^{-1}(B) = \{a \in A \mid f(a) \in B\}$

Function Composition

$(g \circ f)(a) = g(f(a))$

$f: A \to B, g: B \to C \Rightarrow g \circ f: A \to C$

Identity Function

$\text{id}_A: A \to A$ with $\text{id}_A(a) = a$

$f \circ \text{id}_A = f = \text{id}_B \circ f$

Function Types

Injection (One-to-One)

$f(a_1) = f(a_2) \Rightarrow a_1 = a_2$

No two inputs map to same output

Surjection (Onto)

$\forall b \in B, \exists a \in A: f(a) = b$

Every element of $B$ is mapped to

Bijection

Both injective and surjective

One-to-one correspondence

Inverse exists: $f^{-1}: B \to A$

Properties

If $f$ bijective: $|A| = |B|$

$(f^{-1})^{-1} = f$

Cardinality Basics

Cardinality Definition

$|A|$ = number of elements in $A$

$|A| = |B|$ iff bijection $f: A \to B$ exists

Finite Sets

$|A| = n$ for $n \in \mathbb{N}$

$|\mathcal{P}(A)| = 2^n$

$|A \cup B| = |A| + |B| - |A \cap B|$

Cardinality Properties

$|A| \leq |B|$ iff injection $f: A \to B$

$|A| < |B|$ iff injection but no bijection

Finite vs Infinite

$A$ finite iff $|A| = n$ for some $n$

$A$ infinite iff no such $n$ exists

Countable Sets

Definition

$A$ countable iff $|A| \leq |\mathbb{N}|$

Countably infinite: $|A| = |\mathbb{N}| = \aleph_0$

Examples: Countably Infinite

$\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ all countable

$\mathbb{N} \times \mathbb{N}$ countable (diagonal enumeration)

Finite union of countable sets is countable

Enumeration

$A = \{a_1, a_2, a_3, \ldots\}$ - ordered list

Bijection with $\mathbb{N}$ or subset of it

Properties

$A$ countable, $B \subseteq A \Rightarrow B$ countable

Uncountable Sets

Definition

$A$ uncountable iff $|A| > \aleph_0$

Cannot enumerate all elements

Examples

$\mathbb{R}$ - uncountable (Cantor's diagonal argument)

$(0,1) \subset \mathbb{R}$ - uncountable

$\{0,1\}^\mathbb{N}$ - all infinite binary sequences

Cardinality of $\mathbb{R}$

$|\mathbb{R}| = 2^{\aleph_0} = \mathfrak{c}$ (continuum)

$|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$

Continuum Hypothesis

CH: No cardinal between $\aleph_0$ and $2^{\aleph_0}$

Independent of ZFC (Cohen, Gödel)

Cantor's Theorem

Main Theorem

$|A| < |\mathcal{P}(A)|$ for any set $A$

No surjection from $A$ to $\mathcal{P}(A)$ exists

Proof Sketch

Suppose $f: A \to \mathcal{P}(A)$ surjective

Define $D = \{a \in A \mid a \notin f(a)\}$

Then $D \in \mathcal{P}(A)$ but $D \neq f(a)$ for all $a$

Consequences

$\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$

Infinite hierarchy of infinities

Diagonal Argument

Classic method: If $A$ countable, $\mathcal{P}(A)$ isn't

Cardinal Arithmetic

Cardinal Operations

$\kappa \cdot \lambda = |A \times B|$

$\kappa^\lambda = |A^B|$ (all functions $B \to A$)

Infinite Cardinal Rules

$\aleph_0 + n = \aleph_0$ for finite $n$

$\aleph_0 + \aleph_0 = \aleph_0$

$\aleph_0 \cdot \aleph_0 = \aleph_0$

$2^{\aleph_0} > \aleph_0$

König's Theorem

$\text{cf}\left(\sum_i \kappa_i\right) > \kappa_i$ for all $i$; also $\text{cf}(2^\kappa) > \kappa$

Exponentiation

$2^\kappa > \kappa$ always (Cantor)

Ordinal Numbers

Definition

Ordinal: Well-ordered set representing order type

$\alpha$ is ordinal iff $(\alpha, \in)$ is well-ordered

Basic Ordinals

$0 = \emptyset$

$1 = \{0\} = \{\emptyset\}$

$2 = \{0, 1\}$, $n = \{0, 1, \ldots, n-1\}$

$\omega = \{0, 1, 2, 3, \ldots\}$ - first infinite ordinal

Ordinal Properties

$\alpha < \beta$ iff $\alpha \in \beta$

Every set of ordinals is well-ordered by $\in$

$\sup(\text{ordinals}) = $ next ordinal

Successor & Limit

Successor: $\alpha + 1 = \alpha \cup \{\alpha\}$

Limit ordinal: No immediate predecessor

Ordinal Arithmetic

Ordinal Addition

$\alpha + \beta$ - $\alpha$ followed by $\beta$ in order

$1 + \omega = \omega$ but $\omega + 1 > \omega$

Not commutative in general

Ordinal Multiplication

$\alpha \cdot \beta$ - $\beta$ copies of $\alpha$

$2 \cdot \omega = \omega$ but $\omega \cdot 2 > \omega$

Ordinal Exponentiation

$2^\omega = \omega$ (next ordinal)

$\omega^\omega$ - grows very rapidly

Properties

Ordinals form a class, not a set

Transfinite induction works on ordinals

ZFC Axioms (Part 1)

Axiom 1: Extensionality

Sets equal iff same elements: $\forall x(x \in A \leftrightarrow x \in B) \Rightarrow A = B$

Axiom 2: Empty Set

$\exists \emptyset: \forall x (x \notin \emptyset)$

An empty set exists and is unique

Axiom 3: Pairing

$\forall a, b \exists A: A = \{a, b\}$

Can form 2-element sets

Axiom 4: Union

$\forall A \exists U: U = \bigcup A$

$U$ contains all elements of elements of $A$

Axiom 5: Infinity

$\exists I: \emptyset \in I$ and $x \in I \Rightarrow x \cup \{x\} \in I$

Guarantees existence of $\mathbb{N}$

ZFC Axioms (Part 2)

Axiom 6: Power Set

$\forall A \exists P: P = \mathcal{P}(A)$

Set of all subsets exists

Axiom 7: Replacement

If $F$ is function-like, $F(A)$ is a set

Image of set under definable mapping is set

Axiom 8: Regularity/Foundation

$\forall x(x \neq \emptyset \Rightarrow \exists y \in x: x \cap y = \emptyset)$

No infinite descending $\in$-chains

Axiom 9: Separation (Specification)

$\forall A \exists B: B = \{x \in A \mid P(x)\}$

Can form subsets by property

Axiom 10: Choice (AC)

For any family of nonempty sets, can pick one element from each

Equivalent to: Every set has a well-ordering

Transfinite Induction

Principle

If $P(\alpha)$ holds for all $\beta < \alpha$ and implies $P(\alpha)$, then $P(\alpha)$ holds for all ordinals

Proof Template

Base case: Show $P(0)$

Successor step: $P(\alpha) \Rightarrow P(\alpha+1)$

Limit step: $P(\beta)$ for all $\beta < \lambda \Rightarrow P(\lambda)$

Well-Ordered Induction

Works on any well-ordered set, not just ordinals

$(S, \leq)$ well-ordered: Every nonempty subset has minimum

Recursion Theorem

Can define functions recursively on ordinals

Specify $F(0)$ and $F(\alpha+1)$ in terms of $F(\alpha)$

Well-Ordered Sets

Definition

$(A, \leq)$ well-ordered iff:

Total order: $\forall a,b \in A: a \leq b$ or $b \leq a$

Well-founded: Every nonempty subset has minimum element

Examples

$\mathbb{N}$ with $\leq$ is well-ordered

$\mathbb{Z}$ with $\leq$ is NOT well-ordered

Ordinals with $\in$ form well-ordered class

Comparability

Any two well-ordered sets are comparable by order type

Unique ordinal corresponds to each order type

Segments

Initial segment: $\{y \in S \mid y < x\}$ for some $x$

Axiom of Choice Equivalences

Zorn's Lemma

If $(P, \leq)$ poset where every chain has upper bound, then $P$ has maximal element

Equivalent to Axiom of Choice

Well-Ordering Theorem

Every set can be well-ordered

Equivalent to Axiom of Choice

Multiplicative Axiom

Product of nonempty sets is nonempty

$\prod_{i \in I} A_i \neq \emptyset$

Consequences of AC

$\aleph_0 \cdot \aleph_0 = \aleph_0$

Hamel basis for vector spaces

Banach-Tarski paradox is possible

Set Construction & Reflection

Cumulative Hierarchy

$V_0 = \emptyset$

$V_{\alpha+1} = \mathcal{P}(V_\alpha)$

$V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha$ for limit $\lambda$

$V = \bigcup_{\alpha \in \text{Ord}} V_\alpha$ - all sets

Rank of Set

$\text{rank}(x) = $ minimum $\alpha$ such that $x \in V_{\alpha+1}$

Reflection Principle

Any property true in $V$ is true in some $V_\alpha$

Key Theorems Summary

Schröder-Bernstein

Injections $f: A \to B, g: B \to A \Rightarrow \exists$ bijection $A \leftrightarrow B$

$|A| \leq |B|$ and $|B| \leq |A| \Rightarrow |A| = |B|$

Cantor's Theorem

$|A| < |\mathcal{P}(A)|$ strictly

Burali-Forti

There is no "set of all ordinals"

Ordinals form a proper class

Russell's Paradox

$R = \{x \mid x \notin x\}$ leads to contradiction

Resolved by restricting set formation (Axiom of Separation)

Operations Summary

Set Op. Laws

Commutative: $A \cup B = B \cup A$, $A \cap B = B \cap A$

Associative: $(A \cup B) \cup C = A \cup (B \cup C)$

Distributive: $A \cap(B \cup C) = (A \cap B) \cup (A \cap C)$

Complement Laws

$A \cup A^c = U$, $A \cap A^c = \emptyset$

$(A^c)^c = A$, $\emptyset^c = U$, $U^c = \emptyset$

De Morgan's Laws

$(A \cup B)^c = A^c \cap B^c$

$(A \cap B)^c = A^c \cup B^c$

Quick Reference

Symbols

$\in$ - element of, $\notin$ - not element of

$\subseteq$ - subset, $\subset$ - proper subset

$\cup$ - union, $\cap$ - intersection, $-$ - difference

$\mathcal{P}(A)$ - power set, $|A|$ - cardinality

Standard Sets

$\emptyset$ - empty set, $\mathbb{N}$ - naturals, $\mathbb{Z}$ - integers

$\mathbb{Q}$ - rationals, $\mathbb{R}$ - reals, $\mathbb{C}$ - complex

Cardinalities

$\aleph_0 = |\mathbb{N}|$, $\mathfrak{c} = |\mathbb{R}| = 2^{\aleph_0}$

Common Mistakes

Confusion Points

$\emptyset \neq \{\emptyset\}$ (empty vs set containing empty set)

$A \subseteq B$ allows $A = B$ (subset includes equality)

$A \times B \neq B \times A$ (order matters in Cartesian product)

Function Errors

Function must map EVERY element in domain

Codomain $\neq$ range (codomain contains range)

Cardinality Errors

$\aleph_0 + 1 = \aleph_0$ (infinite + finite = infinite)

Two distinct infinities can have same cardinality

Axiom of Choice

Not needed for finite collections; countable collections require Countable Choice (weaker form)

Controversial in constructive mathematics

SET THEORY Complete Reference