Set theory is the foundational language of modern mathematics and computer science. Virtually every other structure — numbers, functions, graphs, relations, sequences, languages, databases — is ultimately built out of sets.
In mathematics: sets define numbers ($\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$), give us functions ($f \subseteq A \times B$), and underpin probability, topology and logic.
In computer science: types are sets of values, databases are relations (sets of tuples), and many algorithms operate on sets (search, deduplication, joins, hashing).
In Python: the built-in set, frozenset, dict and SymPy's FiniteSet let us experiment with set theory directly.
Goal of this course: present sets rigorously — every notion gets a formal definition, every non-trivial claim gets a proof — and then verify it in Python so you can see the theory at work.
2 / 25
What Is a Set?
Definition (intuitive, Cantor 1874)
A set is a well-defined collection of distinct objects, considered as a whole. The objects belonging to a set are called its elements (or members).
Two key properties follow immediately from this informal definition:
No order. A set has no first element, no second element, etc. $\{1,2,3\}=\{3,2,1\}=\{2,1,3\}$.
No repetition. An element is either in the set or it is not — it cannot appear "twice". $\{1,1,3,9\}=\{1,3,9\}$.
We write $x \in A$ to mean "$x$ is an element of $A$", and $x \notin A$ to mean "$x$ is not an element of $A$".
Example
Let $A = \{2, 4, 6, 8\}$. Then $4 \in A$, $5 \notin A$, $\{4\} \notin A$ (because $A$ does not contain the set $\{4\}$ — only the number $4$).
3 / 25
Two Ways to Describe a Set
1. Roster (extensional) notation
List the elements between braces:
$A = \{2, 4, 6, 8\}, \quad V = \{a, e, i, o, u\}$
For obvious patterns we may use "…": $\mathbb{N}=\{0,1,2,3,\dots\}$.
2. Set-builder (intensional) notation
Describe the elements by a property $P$:
$\{\, x \mid P(x) \,\} \quad\text{or}\quad \{\, x \in U \mid P(x) \,\}$
Read as: "the set of all $x$ (in $U$) such that $P(x)$ holds".
Examples
$\{\, n \in \mathbb{N} \mid n \text{ is even} \,\} = \{0, 2, 4, 6, \dots\}$
$\{\, x \in \mathbb{Q} \mid x^2 = 2 \,\} = \varnothing$ (no rational squares to 2)
Python — set-builder via comprehensionevens = {n for n in range(20) if n % 2 == 0}
squares10 = {n*n for n in range(1, 11)}
print(evens)
print(squares10)
4 / 25
Equality of Sets
Axiom of extensionality
Two sets are equal if and only if they have exactly the same elements:
$$A = B \;\Longleftrightarrow\; \forall x\;(x \in A \,\Leftrightarrow\, x \in B).$$
This is the rule that tells us "a set is determined by its elements". In particular, the order in which we list the elements and any repetitions are irrelevant.
Standard proof technique: double inclusion
To prove $A = B$, it suffices to prove the two inclusions:
$A \subseteq B$ and $B \subseteq A$.
Theorem
$\{1,1,3,9\} = \{1,3,9\}$.
Proof.
Let $A=\{1,1,3,9\}$ and $B=\{1,3,9\}$. Pick any $x\in A$. Then $x \in \{1,3,9\}$ (the only values listed are 1, 3, 9), hence $x\in B$. Conversely, every $x \in B$ is among the values $1,3,9$ listed in $A$, so $x\in A$. Therefore $A\subseteq B$ and $B\subseteq A$, hence by extensionality $A=B$.
A subtle but important point: cardinality counts distinct elements, even when they are sets themselves.
Example (nested sets)
$|\{\varnothing\}| = 1$ (one element, namely the empty set).
$|\{\varnothing,\, \{\varnothing\}\}| = 2$ (two distinct elements: $\varnothing$ and $\{\varnothing\}$).
7 / 25
Subsets, Proper Subsets, Supersets
Definition
$A$ is a subset of $B$, written $A \subseteq B$, iff every element of $A$ is also an element of $B$:
$$A \subseteq B \;\Longleftrightarrow\; \forall x \,(x \in A \,\Rightarrow\, x \in B).$$
$A$ is a proper subset of $B$, written $A \subsetneq B$ (or $A \subset B$), iff $A \subseteq B$ and $A \neq B$.
$B$ is a superset of $A$ iff $A \subseteq B$; we then write $B \supseteq A$.
Basic properties
Theorem
For any sets $A, B, C$:
Reflexivity: $A \subseteq A$.
Antisymmetry: if $A \subseteq B$ and $B \subseteq A$ then $A = B$.
Transitivity: if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$.
Proof.
(1) For any $x$, $x \in A \Rightarrow x \in A$ trivially, so $A \subseteq A$.
(2) This is the axiom of extensionality.
(3) Take $x \in A$. Since $A \subseteq B$, we have $x \in B$. Since $B \subseteq C$, we have $x \in C$. Thus $A \subseteq C$.
Python — subset / proper subsetA, B = {2, 4}, {2, 4, 6}
print(A <= B) # True → A ⊆ B
print(A < B) # True → A ⊊ B (proper)
print(A == B) # False
8 / 25
The Empty Set
Definition
The empty set, written $\varnothing$ or $\{\}$, is the unique set containing no elements: $\forall x\;(x \notin \varnothing)$.
Theorem (uniqueness of $\varnothing$)
There is exactly one empty set.
Proof.
Suppose $\varnothing_1$ and $\varnothing_2$ are both empty. For every $x$ we have $x\in\varnothing_1 \Leftrightarrow \bot \Leftrightarrow x\in\varnothing_2$ (both biconditionals are vacuously true). By extensionality, $\varnothing_1 = \varnothing_2$.
Theorem
For every set $A$, $\varnothing \subseteq A$.
Proof.
We must show $\forall x\,(x\in\varnothing \Rightarrow x\in A)$. The hypothesis $x\in\varnothing$ is always false, so the implication is vacuously true. Hence $\varnothing \subseteq A$.
Don't confuse $\varnothing$ and $\{\varnothing\}$: $|\varnothing|=0$ but $|\{\varnothing\}|=1$. The set $\{\varnothing\}$ contains one element — the empty set itself.
9 / 25
Power Set
Definition
The power set of $S$, written $\mathcal{P}(S)$ or $2^S$, is the set of all subsets of $S$:
$$\mathcal{P}(S) \;=\; \{\, X \mid X \subseteq S \,\}.$$
Theorem
If $|S| = n$ (finite), then $|\mathcal{P}(S)| = 2^n$.
Proof (induction on $n$).Base case $n = 0$: then $S = \varnothing$ and $\mathcal{P}(\varnothing) = \{\varnothing\}$, so $|\mathcal{P}(\varnothing)| = 1 = 2^0$. ✓ Inductive step. Assume any set of size $n$ has $2^n$ subsets. Let $S$ have size $n+1$. Pick any $a \in S$ and let $S' = S \setminus \{a\}$ with $|S'|=n$. Every subset $X$ of $S$ is of exactly one of two kinds:
$X \subseteq S'$ (does not contain $a$) — by IH there are $2^n$ of these;
$X = Y \cup \{a\}$ with $Y \subseteq S'$ (contains $a$) — again $2^n$.
These two kinds are disjoint and exhaust $\mathcal{P}(S)$, so $|\mathcal{P}(S)| = 2^n + 2^n = 2^{n+1}$. ✓
Python — power set via itertoolsfrom itertools import chain, combinations
def powerset(s):
s = list(s)
return list(chain.from_iterable(
combinations(s, r) for r in range(len(s) + 1)))
print(len(powerset({'a','b','c'}))) # 8 = 2**3
10 / 25
Union and Intersection
Definition
Union: $A \cup B = \{\, x \mid x \in A \;\vee\; x \in B \,\}$.
Intersection: $A \cap B = \{\, x \mid x \in A \;\wedge\; x \in B \,\}$.
$A$ and $B$ are disjoint iff $A \cap B = \varnothing$.
Python — built-inA = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
print(A | B) # union
print(A & B) # intersection
print(A.isdisjoint({9, 10})) # True
SymPyfrom sympy import FiniteSet, Union, Intersection
A = FiniteSet(1,2,3,4,5)
B = FiniteSet(4,5,6,7,8)
print(Union(A,B))
print(Intersection(A,B))
11 / 25
Difference, Symmetric Difference, Complement
Definitions
Difference: $A \setminus B = \{\, x \mid x \in A \,\wedge\, x \notin B \,\}$.
Symmetric difference: $A \triangle B = (A \setminus B) \cup (B \setminus A)$.
Complement (relative to a universe $U$): $\overline{A} = A^c = U \setminus A$.
Theorem (equivalent form of $\triangle$)
$A \triangle B = (A \cup B) \setminus (A \cap B)$.
Proof.
For any $x$:
\begin{align*}
x \in (A\setminus B)\cup(B\setminus A)
&\Leftrightarrow (x\in A\wedge x\notin B)\vee(x\in B\wedge x\notin A)\\
&\Leftrightarrow (x\in A\vee x\in B)\wedge \neg(x\in A\wedge x\in B)\\
&\Leftrightarrow x\in A\cup B \;\wedge\; x\notin A\cap B\\
&\Leftrightarrow x\in (A\cup B)\setminus(A\cap B).
\end{align*}
Hence the two sets contain exactly the same elements; by extensionality they are equal.
Python — three operatorsA, B = {1, 2, 3, 4}, {3, 4, 5, 6}
print(A - B) # {1, 2} A \ B
print(B - A) # {5, 6} B \ A
print(A ^ B) # {1, 2, 5, 6} symmetric difference
print((A | B) - (A & B)) # same {1, 2, 5, 6}
12 / 25
Algebraic Laws of Set Operations
Law
Union form
Intersection form
Commutative
$A\cup B = B\cup A$
$A\cap B = B\cap A$
Associative
$(A\cup B)\cup C = A\cup(B\cup C)$
$(A\cap B)\cap C = A\cap(B\cap C)$
Distributive
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
Identity
$A\cup\varnothing = A$
$A\cap U = A$
Domination
$A\cup U = U$
$A\cap\varnothing = \varnothing$
Idempotent
$A\cup A = A$
$A\cap A = A$
Absorption
$A\cup(A\cap B) = A$
$A\cap(A\cup B) = A$
Complement
$A\cup A^c = U$
$A\cap A^c = \varnothing$
Double complement
$(A^c)^c = A$
Theorem (distributivity of $\cap$ over $\cup$)
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
Proof.
For any $x$:
\begin{align*}
x \in A\cap(B\cup C)
&\Leftrightarrow x\in A \wedge (x\in B \vee x\in C)\\
&\Leftrightarrow (x\in A \wedge x\in B)\vee(x\in A \wedge x\in C) \quad\text{(distrib. of $\wedge$ over $\vee$)}\\
&\Leftrightarrow x\in (A\cap B) \vee x\in(A\cap C)\\
&\Leftrightarrow x\in (A\cap B)\cup(A\cap C).
\end{align*}
Conclude by extensionality.
13 / 25
De Morgan's Laws
Theorem (De Morgan)
For any sets $A, B$ in a universe $U$:
$$\overline{A\cup B} = \overline{A}\cap\overline{B}, \qquad \overline{A\cap B} = \overline{A}\cup\overline{B}.$$
Proof of the first identity.
For any $x \in U$:
\begin{align*}
x \in \overline{A\cup B}
&\Leftrightarrow x\notin A\cup B \\
&\Leftrightarrow \neg(x\in A \vee x\in B)\\
&\Leftrightarrow \neg(x\in A)\wedge\neg(x\in B) \quad\text{(De Morgan for logic)}\\
&\Leftrightarrow x\in\overline{A}\wedge x\in\overline{B}\\
&\Leftrightarrow x\in \overline{A}\cap\overline{B}.
\end{align*}
The second identity follows by replacing $A,B$ with $\overline{A},\overline{B}$ and using double complement.
Python — empirical verification on small universesfrom itertools import product
U = set(range(6))
def complement(X): return U - X
for A in [set(x) for r in range(7) for x in __import__('itertools').combinations(U, r)]:
for B in [set(x) for r in range(7) for x in __import__('itertools').combinations(U, r)]:
assert complement(A | B) == complement(A) & complement(B)
assert complement(A & B) == complement(A) | complement(B)
print("De Morgan verified for every (A,B) ⊆ U with |U|=6")
14 / 25
The Inclusion–Exclusion Principle
Theorem (two sets)
For any finite sets $A, B$:
$$|A \cup B| \;=\; |A| + |B| - |A \cap B|.$$
Example
A partition of $\{1,2,3,4,5,6\}$ into three blocks of size 2: $\{\{1,2\},\{3,4\},\{5,6\}\}$.
A partition into evens / odds: $\{\{2,4,6\},\{1,3,5\}\}$.
A cover drops the disjointness requirement: the blocks may overlap as long as their union is still $S$.
Python — partition into chunks of size ndef partition(seq, n):
seq = list(seq)
return [seq[i:i+n] for i in range(0, len(seq), n)]
P = partition(range(1, 13), 4)
print(P) # disjoint blocks
print(set().union(*map(set, P)) == set(range(1, 13))) # True (covers)
16 / 25
Cartesian Product
Definition
The Cartesian product of two sets $A$ and $B$ is the set of ordered pairs:
$$A \times B = \{\, (a, b) \mid a \in A,\; b \in B \,\}.$$
More generally $A_1 \times A_2 \times \cdots \times A_n = \{(a_1, \dots, a_n) \mid a_i \in A_i\}$. We write $A^n$ for $A \times A \times \cdots \times A$ ($n$ times).
Theorem
For finite sets, $|A \times B| = |A| \cdot |B|$. More generally $|A^n| = |A|^n$.
Proof.
To build a pair $(a, b)\in A\times B$ we make two independent choices: $a$ from $A$ ($|A|$ options) and $b$ from $B$ ($|B|$ options). By the multiplication principle the total number of pairs is $|A|\cdot|B|$. The general statement $|A^n|=|A|^n$ follows by induction on $n$.
Theorem
$A \times \varnothing = \varnothing \times A = \varnothing$ for every set $A$.
Proof.
A pair $(a,b) \in A\times\varnothing$ would require $b\in\varnothing$, which is impossible. Hence $A\times\varnothing$ has no elements; by uniqueness of the empty set it equals $\varnothing$. Symmetric for $\varnothing\times A$.
Python — itertools.productfrom itertools import product
A, B = {1, 3, 5}, {'x', 'y'}
P = list(product(A, B))
print(P, len(P)) # 3 * 2 = 6 pairs
SymPy — ProductSetfrom sympy import FiniteSet, ProductSet
A = FiniteSet(1, 3, 5)
B = FiniteSet('x', 'y')
print(list(ProductSet(A, B)))
17 / 25
Countable Sets
Definition
A set $S$ is countable if it is finite, or there exists a bijection $f : \mathbb{N} \to S$. Otherwise $S$ is uncountable.
Theorem
$\mathbb{Z}$ is countable.
Proof.
Define $f : \mathbb{N} \to \mathbb{Z}$ by
$$f(n)=\begin{cases} n/2, & n \text{ even},\\ -(n+1)/2, & n \text{ odd}.\end{cases}$$
Then $f(0)=0$, $f(1)=-1$, $f(2)=1$, $f(3)=-2$, $f(4)=2$, …
The function $f$ is injective (different $n$ give different signs/sizes) and surjective (every integer is reached). Hence $f$ is a bijection and $\mathbb{Z}$ is countable.
Theorem (without proof)
$\mathbb{Q}$ is countable. ($\mathbb{N}\times\mathbb{N}$ can be enumerated by diagonals, and each rational $p/q$ corresponds to a pair $(p,q)$.)
Python — bijection N → Zdef f(n): # N -> Z
return n // 2 if n % 2 == 0 else -(n + 1) // 2
def f_inv(z): # Z -> N
return 2*z if z >= 0 else -2*z - 1
print([f(n) for n in range(10)])
print([f_inv(z) for z in [0, -1, 1, -2, 2, -3, 3]])
print(all(f_inv(f(n)) == n for n in range(100))) # True
18 / 25
Uncountable Sets — Cantor's Diagonal Argument
Theorem (Cantor, 1891)
The set $\mathbb{R}$ (and even the interval $(0,1)$) is uncountable.
Proof (sketch, by contradiction).
Suppose $(0,1)$ were countable. Then we could list all of its elements in a sequence $r_1, r_2, r_3, \dots$ Write each in decimal form:
$$r_1 = 0.d_{11}d_{12}d_{13}\dots,\;\; r_2 = 0.d_{21}d_{22}d_{23}\dots,\;\; r_3 = 0.d_{31}d_{32}d_{33}\dots$$
Construct a new real $x = 0.x_1 x_2 x_3\dots$ where
$$x_k = \begin{cases} 5, & d_{kk} \neq 5,\\ 6, & d_{kk} = 5.\end{cases}$$
Then $x \in (0,1)$ but $x$ differs from every $r_k$ in the $k$-th decimal digit. So $x$ is not in our list — contradicting the assumption that every real in $(0,1)$ was listed. Hence $(0,1)$ is uncountable, and so is $\mathbb{R} \supseteq (0,1)$.
Corollary
There are more reals than integers: $|\mathbb{N}| < |\mathbb{R}|$. There is a strict hierarchy of infinite cardinalities (Cantor's theorem $|S| < |\mathcal{P}(S)|$ for every $S$).
19 / 25
A Warning — Russell's Paradox
Cantor's "naive" definition says we can form any set of the form $\{x \mid P(x)\}$ for any property $P$. Russell (1901) showed this is too permissive.
Theorem (Russell, 1901)
Let $R = \{\, x \mid x \notin x \,\}$ — the "set of all sets that do not contain themselves". Then both $R \in R$ and $R \notin R$ lead to a contradiction.
Proof.
Suppose $R \in R$. By definition of $R$, that means $R \notin R$ — contradiction.
Suppose instead $R \notin R$. Then $R$ satisfies the property defining $R$, so $R \in R$ — contradiction.
Either way we derive a contradiction, so $R$ cannot exist as a set.
The resolution is axiomatic set theory (Zermelo–Fraenkel with the Axiom of Choice, ZFC): we cannot freely form $\{x\mid P(x)\}$. Instead the Axiom of Separation only allows $\{x \in A \mid P(x)\}$ inside an already-existing set $A$. For everyday discrete math this distinction never bites — but it is good to know the foundation.
20 / 25
Functions Are Sets Too
Definition
A function $f : A \to B$ is a subset $f \subseteq A \times B$ such that for every $a \in A$ there exists exactly one $b \in B$ with $(a,b) \in f$. We then write $f(a) = b$.
Functions are special binary relations (themselves subsets of $A \times B$). Different flavours:
Bijective: both injective and surjective — used in the previous slide to count infinities.
Example
$f : \mathbb{Z} \to \mathbb{Z},\; f(n) = 2n$ is injective (different $n$ give different $2n$) but not surjective (no odd number is reached).
This is why sets are foundational: once we have sets we get pairs, then relations, then functions, then sequences, then everything else. The next lesson "Operations on Sets" builds on this directly.
21 / 25
Intervals — Infinite Sets in SymPy
Definition
Let $a, b \in \mathbb{R}$ with $a \le b$. The intervals are:
Closed: $[a, b] = \{x \in \mathbb{R} \mid a \le x \le b\}$
Open: $(a, b) = \{x \in \mathbb{R} \mid a < x < b\}$
Half-open: $[a, b) = \{x \mid a \le x < b\}$, $(a, b] = \{x \mid a < x \le b\}$
Python — dataset (list of dicts)titanic = [
{"class":"1st","age":29,"survived":True},
{"class":"3rd","age":27,"survived":False},
]
print([r for r in titanic if r["survived"]])
The same conceptual machinery — membership ($\in$), union, intersection, projection ($\pi$) — powers SQL, pandas DataFrames, and the relational model of databases.
23 / 25
Summary — What You Now Know
A set is a collection of distinct elements — order and multiplicity are irrelevant (extensionality).
The empty set $\varnothing$ is unique and is a subset of every set.
The power set $\mathcal{P}(S)$ contains $2^{|S|}$ subsets — proved by induction.
Set operations $\cup, \cap, \setminus, \triangle, {}^c$ obey a clean algebra: commutative, associative, distributive, De Morgan.
Inclusion–exclusion gives $|A\cup B|=|A|+|B|-|A\cap B|$ — basis of counting arguments.
Prove De Morgan's second law $\overline{A\cap B} = \overline{A}\cup\overline{B}$ by the double-inclusion method.
Prove by induction that for any finite sets $A_1,\dots,A_n$, $|A_1 \times \cdots \times A_n| = \prod |A_i|$.
Next lesson
Once sets are mastered, the next lesson develops the computations on them — relations, equivalence classes, partitions induced by relations, functions, sequences and series.
A note on rigor: every "obvious" identity on sets corresponds to a tautology in propositional logic via the dictionary
$\cup \leftrightarrow \vee,\; \cap \leftrightarrow \wedge,\; {}^c \leftrightarrow \neg$.
If you can prove a logical tautology on a truth table, you can prove the corresponding set identity by element-chasing — that is the unifying idea of this lesson.