Set Theory and Operations

Set Theory

The Language of Mathematics

Set theory is the universal language of mathematics. All mathematical objects—numbers, functions, structures—can be defined through sets.

Georg Cantor created set theory in the 1870s, despite opposition from conservative mathematicians. David Hilbert called his theory "a paradise from which we shall not be driven."

Operations on Sets

Union: $A \cup B = {x : x \in A \text{ or } x \in B}$. Intersection: $A \cap B = {x : x \in A \text{ and } x \in B}$. Difference: $A \setminus B = {x : x \in A,\ x \notin B}$. Symmetric difference: $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)$. Complement: $A^c = U \setminus A$ ($U$ is the universe).

De Morgan's Laws: $(A \cup B)^c = A^c \cap B^c$; $(A \cap B)^{\complement} = A^c \cup B^c$.

Cardinality of Sets

Sets $A$ and $B$ are equinumerous if there exists a bijection $A \to B$. Finite: $|A|$ is the number of elements. Infinite: compare by bijection.

Countable sets: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ (bijection with $\mathbb{N}$). Uncountable: $\mathbb{R}$, $[0,1]$, all subsets of $\mathbb{N}$.

Cantor's Theorem: $|A| < |2^A|$ for any $A$. There is no "largest" infinite set.

Continuum Hypothesis: $|\mathbb{R}| = 2^{|\mathbb{N}|}$. There is no cardinal strictly between $|\mathbb{N}|$ and $|\mathbb{R}|$. Independent from ZFC axioms (Gödel 1940, Cohen 1963).

Cartesian Product

$A \times B = {(a,b) : a \in A,\ b \in B}$. $|A \times B| = |A| \cdot |B|$.

A function $f: A \to B$ is a subset of $A \times B$ such that for each $a \in A$ there is exactly one pair $(a, b)$.

Axiomatic Systems: ZF and ZFC

Set theory itself requires strict axiomatization—otherwise paradoxes arise. Russell's paradox: consider $R = {x : x \notin x}$—"the set of all sets not containing themselves." Then $R \in R \iff R \notin R$—a contradiction! This showed that one cannot build "too large" sets without restrictions.

The Zermelo-Fraenkel system of axioms (ZF) solves this problem. Main axioms: Extensionality (two sets are equal if they have the same elements), Empty Set ($\emptyset$ exists), Pairing (${a,b}$ exists), Union ($\bigcup A$ exists), Power Set ($2^A$ exists), Infinity ($\mathbb{N}$ exists), Subset (separation axiom: ${x \in A : \varphi(x)}$ exists for formula $\varphi$), Replacement (the image of a function on a set exists), Regularity (no infinitely descending $\in$ chains). Adding the axiom of choice (AC) yields ZFC.

Axiom of Choice: For any collection of non-empty sets, there exists a choice function selecting one element from each. Equivalent forms: Zorn's Lemma, Tychonoff's theorem (the product of compacts is compact), Basis theorem (any vector space has a Hamel basis). The axiom of choice is necessary for most modern mathematics but leads to "strange" consequences—for example, the Banach–Tarski theorem: a sphere can be partitioned into a finite number of parts and reconstructed into two spheres of the same size.

Cantor's Hierarchy of Infinities

Cantor showed that there are different "sizes" of infinity. Two sets are equinumerous ($|A| = |B|$) if there is a bijection between them. Alephs: $\aleph_0 = |\mathbb{N}|$, $\aleph_1$ is the next cardinal after $\aleph_0$. Cantor's theorem $|A| < |2^A|$ gives an infinite hierarchy: $|\mathbb{N}| < |2^{\mathbb{N}}| < |2^{2^{\mathbb{N}}}| < \cdots$

Proof: suppose there is a bijection $f : A \to 2^A$. Consider $D = {a \in A : a \notin f(a)}$. If $D = f(d)$ for some $d$, then $d \in D \iff d \notin f(d) = D$—a contradiction. This is a generalization of Cantor's diagonal argument.

The cardinality $|\mathbb{R}| = 2^{\aleph_0} = \mathfrak{c}$ is called the continuum cardinality. Continuum Hypothesis asserts that $\aleph_1 = \mathfrak{c}$, i.e., there is no cardinal between $|\mathbb{N}|$ and $|\mathbb{R}|$. Gödel (1940) proved consistency, Cohen (1963) proved independence from ZFC. The truth of CH is fundamentally undecidable within ZFC.

Applications of Set Theory in Computer Science

In programming, data types are sets of permissible values. Type Boolean = ${\text{true}, \text{false}}$, type Int is a finite subset of $\mathbb{Z}$, function type $A \to B$ corresponds to $B^A$. Operations on types: union types, intersection types, Cartesian product (product types—structures and tuples).

Relational algebra of databases is a direct application of set theory. A table is a relation (set of tuples), SELECT is separation, JOIN is the Cartesian product with a filter, UNION and INTERSECT are union and intersection. SQL literally implements operations on finite sets.

Cardinality of Sets and Cantor's Theorem

Two sets are equinumerous ($|A| = |B|$) if there exists a bijection between them. Cantor's theorem: $|A| < |P(A)|$ for any $A$. Consequence: there is no "largest" infinite set. Countable sets: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ (all bijective with each other). Uncountable: $\mathbb{R}$, $P(\mathbb{N})$, $(0,1)$—Cantor's diagonal argument. The cardinality of $\mathbb{R}$ is denoted $\mathfrak{c} = 2^{\aleph_0}$. Continuum hypothesis: there is no cardinality strictly between $\aleph_0$ and $\mathfrak{c}$—independent of ZFC (Gödel 1940, Cohen 1963).

Numerical Example: Cantor's Diagonal Argument

Problem: Show that $|P({1,2,3})| > |{1,2,3}|$ by constructing a "diagonal" set.

Step 1: $P({1,2,3}) = {\emptyset, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}$—8 elements. $|{1,2,3}|=3$.

Step 2: Try a bijection $f: 1 \mapsto {1,3},\ 2 \mapsto {2},\ 3 \mapsto {1,2,3}$. Construct $D = {n \in {1,2,3} : n \notin f(n)}$.

Step 3: $1 \notin {1,3}?$ No ($1 \in {1,3}$), so $1 \notin D$. $2 \notin {2}?$ No ($2 \in {2}$), so $2 \notin D$. $3 \notin {1,2,3}?$ No, so $3 \notin D$. $D = \emptyset$.

Step 4: $\emptyset \notin {f(1), f(2), f(3)} = {{1,3}, {2}, {1,2,3}}$—the bijection missed $\emptyset$. Any 3 elements from $P({1,2,3})$ do not cover all 8. Cantor's theorem: $|P(A)| = 2^{|A|} > |A|$ for any $A$, even infinite ones.