# Set Theory

Jan Hubička, hubicka@kam.mff.cuni.cz

Consultations by email arrangement. Use "Set Theory" in subjects of emails.

• Lecture: Tue 14:00, S4
• Tutorials: Andres Aranda, web
• Czech Class: Honza Kyncl, web

## Topics covered

Feb 14
• Brief history of proofs in mathematics (Pythagoras theorem and its visual proof, Euclid's elements and a gap in proof of Proposition I). Not required for exam.
• Why do we want to study set theory? We want solid foundation to mathematics to resolve some problems:
• Russel's paradox: set X is extraordinary if X ∈ X, ordinary otherwise. Let O be the set of all ordinary sets. Is O ∈ P?
• Russel's paradox in popular language: "There is one barber in a town. He shaves exactly those men, who do not shave themselves. Does he shave himself?"
• Berry paradox: "X is the smallest positive integer not definable in under sixty letters." Arguably X both exists and does not exist.
• There are also highly counter-intuitive but correct results such at the Banach-Tarski paradox on sphere doubling.
In 1900 these problems culminated thanks to the Hilbert's programme and led to the foundational crisis.
• Brief history: Bolzano introduced set theory to study infinity. Cantor's work initiated modern set theory. Russel-Whitehead: Principia mathematica and its proof that 1+1=2 as an attempt to resolve the foundational crisis, Goedel and his incompleteness results (very briefly)
• Brief crash-course on first order formulas. We will be most of time informal and use English, however we keep in mind that the underlying language is the predicate logic and everything we do can be expressed by it.
• Axiomatic approach: we will follow Zermelo--Fraenkel axiomatization from 1908 (Van Neumann-Gödel-Bernays is other popular)
• The Axiom of Existence (Axiom existence): empty set exists. We found way to express it as formula
• The Axiom of Extensionality (Axiom extenzionality): If two sets have precisely same elements they are equal. Again we wrote a formula
• Thorem: Empty set is unique. Proof.
Feb 21
• The Axiom of Pair -- "exists {A, B}"
• for every A,B ex. C s.t. x ∈ C iff x=A or x=B
• Notation {A,B} or {A} -- can be used, as it is unique.
• the first axiom that provides more than an empty set!
• The Axiom of Union -- for every S ex. U s.t. x ∈ U iff x ∈ A for some A ∈ S
• notation $$U = \cup S$$ (usually $$\cup_{A \in S} A$$)
• examples ... in particular union of two sets
• The Axiom of Power Set ⊆ -- a shortcut for subset0 for every S ex. P s.t. X ∈ P iff X ⊆ S
• examples:
• Elementary operations with sets: union, symmetric difference, set minus,.... Proofs that those are also sets.
• Intersection of empty set is an empty set
• Ordered pair (due to Kuratowski): $$(a,b)=\{a,\{a,b\}\}$$

This is a smart definition which makes it possible to define relations and functions and prove basic facts. Ordered n-tuples are also easy: (a,b,c)=((a,b),c).

Feb 28
• Relations (following what we know from discrete mathematics). Dom R, ran R, field R all of them are sets because they are subsets of $$\cup \cup R$$
• Image, preimage
• Inverse relations: we need scalar product to show it is a set.
• exercise: image under inverse relation is the inverse image
Functions
• Compatible functions
• Theorem: union of compatible functions is a function.
Building $$\mathbb N$$:
• $$0 = \{\}, 1 = \{0\}, \ldots , 17 = \{0,1,..., 16\}$$
• This is another smart definition. It makes it possible to define successor operation: $$S(x)=x\cup \{x\}$$. We will also write $$x+1$$ for $$S(x)$$.
• inductive set $$I$$: $$0 \in I$$ and $$x \in I \implies S(x) \in I$$
• Axiom of Infinity: An inductive set exists.

(We need new axiom here: this does not follow from what we already have)

• Def: The set of all natural numbers is defined by $$\mathbb N= \{x | x \in I$$ for every inductive set $$I\}$$.
• This definition is legal: $$\mathbb N$$ is a set because it is a subset of any given inductive set and is unique.
• $$\mathbb N$$ is inductive and it is a subset of every inductive set
• Def ordering on $$\mathbb N$$ by $$\in$$
• The induction principle : P(x) a property (a formula with free variable x), assume
• P(0)
• $$\forall n \in N: P(n) \implies P(n+1)$$
Then P(n) holds for all $$n \in \mathbb N$$

Proof: The set $$A = \{n \in N : P(n) \}$$ is inductive

• Thm $$(\mathbb N, <)$$ is a linearly ordered set

To prove this we used induction principle to show transitivity, assymetricity. Hard step was linearity that needed double induction.

March 4
• Recursion: we want to define sequences recursively. For exaple factorial is defined as f(0)=1, f(n+1)=(n+1)*f(n).
• Recursion theorem: If $$A$$ is a set, a its element and $$g:A\times \mathbb N$$ a function then there is unique function $$f:\mathbb N\to A$$ such that
• f(0)=a
• f(n+1)=g(f(n),n)
Proof using union of sets of computations.
• Parametric version of the recursion theorem.
• Arithmetics on $$\mathbb N$$: Use induction to define functions +,* and exponentiation. We proved basic properties by induction (such as commutativity).
March 11
Cardinality of sets, Cantor-Bernstein
• Def: Sets A and B are equipotent (have the same cardinality) if there exists one-to-one functions with domain A and range B. In this case we write |A|=|B|.
• Theorem:
• $$|A|=|A|$$
• $$|A|=|B|\implies |B|=|A|$$
• $$(|A|=|B|)=|C| \implies |A|=|C|$$
• Being equipotent is an equivalence "relation". Not in the sense we defined relations before because its domain is the class of all sets, but we can speak of class relations.
• Def: $$|A|\leq |B|$$ if there exists $$f:A\to B$$ that is injective.
• Theorem:
• $$|A|\leq |A|$$
• $$|A|=|B|\leq |C|=|D|\implies |A|\leq |C|$$ and $$|B|\leq |D||$$
• $$|A|\leq |B|\leq |C|\implies |A|\leq |C|$$
• We know that $\leq$ is an order. Is it linear? This is an important theorem.
• Theorem (Cantor-Bernstein) $$|X|\leq |Y|$$ and $$|Y|\leq |X|$$ implies $$|X|=|Y|$$.
• Proof using the following Lemma: If $$A_1\subseteq B\subseteq A$$ and $$|A_1|=|A|$$ then $$|A|=|B|$$. Proof of lemma is quite smart and requires careful definition of the bijection.
• March 18
Finite sets (lecture by Andres Aranda)
• More disucssion on the Cantor-Bernstein theorem. Alternative proof using bipartite graph and sequences.
• Def: Set A is finite if it is equipotent to some eleemnt of $$\mathbb N$$.
• Theorem: There is no bojection from $$n\in \mathbb N$$ to a proper subset of $$n$$.
• Corollaries:
• $$m \neq n \implies$$no bijection m to n
• $$|S| = m$$ and $$|S|=n \implies m=n$$
• $$\mathbb N$$ is infinite.
• Def |S| := n for such n that |S| = n
• Theorem: X is finite, f function $$\implies$$ f[X] is finite. Moreover, $$|f[X]| \leq |X|$$
• Corollary: if X,Y are finite then $$X\cup Y$$ are finite
• Theorem: S is finite and each element of S is finite $$\implies$$ union of S is finite.
• Theorem: if X is finite then P(X) is finite
• Theorem: If X is infinite then for every $$n\in \mathbb N, |X|\geq n$$.
March 25
Countable sets (lecutre by Andres Aranda)
• Def: A set S is countable if $$|S| = |\mathbb N|$$. A set S is at most countable if $$|S| \leq |\mathbb N|$$.
• Def: $$|S| := N$$ (or $$\aleph_0$$) if S is countable.
• Thm: An infinite subset of a countable set is countable. Proof using recursion theorem.
• Corollary: A set is at most countable if it is finite or countable.
• Theorem: X is countable, f function $$\implies$$ f[X] is countable. Moreover, $$|f[X]| \leq |X|$$.
• Theorem: Union of two countable sets is countable.
• Theorem: Product of two countable sets is countable.
• Theorem: Assume that for each n, $$A_n$$ is countable and $$a_n$$: $$\mathbb N$$ onto $$A_n$$ is given. Then $$\cup A_n$$ is at most countable.
• Corolaries: $$\mathbb N, \mathbb Q, \mathbb Z$$ are countable.
Un countable sets
• Cantor theorem: $$|P(X)|>|X|$$
• Continuum hypothesis (proposed by Cantor): There is no set of size in between $$\mathbb N) and \(P(\mathbb N)$$, I.e., a set $$X$$ such that $$|\mathbb N| < |X| < |P(\mathbb N)|$$. This hypothesis is undecidable.
April 4
Dedekind cuts
• One of possible constructoins of reals
• A cut is a tuple $$(A,B)$$ such that $$\mathbb Q = A \cup B$$ and $$A,B$$ are disjoint and nonempty and $$a \in A, b \in B$$ implies that $$a\(\mathbb R$$ is the set of all reals. Cut (A,B) corresponds to real number that is a supremum of A. Based on this we can define operations and linear ordering.
• Cardinal numbers
• For now we will assume that there is a set of cardial numbers that does represent the equivalence classes given by the property $$|X|=|Y|$$
• Arithmetic on cardinal numbers:
• Suppose $$|X| = \kappa$$, $$|Y| = \lambda$$, $$X$$ and $$Y$$ are disjoint. Then we define $$\kappa + \lambda$$ as $$|X \cup Y|$$.
• Suppose $$|X| = \kappa$$, $$|Y| = \lambda$$, $$X$$. Then we define $$\kappa \cdot \lambda$$ as $$|X \times Y|$$.
• Suppose $$|X| = \kappa$$, $$|Y| = \lambda$$, $$X$$. Then we define $$\kappa ^ \lambda$$ as $$|X^Y|$$. Here $X^Y$ is the set of all functions $$f:Y\to X$$.
In all cases we verified that the definitions are correct.
• Theorem: $$|P(X)| = 2^{|X|}$$.
• Theorem: $$|P(X)| = 2^{|X|}$$
• Theorem: The set of all functions $$\mathbb R \to \mathbb R$$ has cardinality $$(2^\omega)^{2^\omega} = 2^{\omega . 2^\omega} = 2^{2^\omega}$$. The set of all continuous functions from $$\mathbb R$$ to $$\mathbb R$$ has cardinality $$2^\omega$$.
• Well ordered sets (introduction)
• Def: Suppose $$(W,<)$$ is a linearly ordered set (the ordering is strict: no $$x<x$$). We say $$W$$ is well-ordered iff every nonempty subset of $$W$$ has a least element.
• Lemma If $$(W,<)$$ is a well-ordered set and $$S$$ is an initial segment of it. (Meaning: $$x < y \in S$$ implies $$x \in S$$.) Then there is $$a \in W$$ s.t. $$S = \{ x \in W : x < a \}$$. Note: we denote this set by $$W[a]$$.
• Lemma: If $$(W,<)$$ is a well-ordered set and $$f: W \to W$$ is an increasing function, then $$f(x) >= x$$ for every $$x \in W$$.
April 11
More Well ordered sets
• Corolaries:
• No well-ordered set is isomorphic to its initial segment.
• Each well-ordered set has just one isomorphism, the identity.
• Two isomorphic well-ordered sets have just one isomorphism between them.
• Theorem:Main Thm Suppose $$W_1$$, $$W_2$$ are two well-ordered sets. Then exactly one of the following holds:
• $$W_1$$ and $$W_2$$ are isomorphic,
• $$W_1$$ is isomorphic to an initial segment of $$W_2$$,
• $$W_2$$ is isomorphic to an initial segment of $$W_1$$.
Ordinal numbers
• Def: A set $$T$$ is transitive if $$a \in b \in T$$ implies $$a \in T$$. (Eq: every element of $$T$$ is a subset of $$T$$.) .
• Def: A set $$\alpha$$ is an ordinal number (or ordinal) if it is transitive and well-ordered by $$\in$$.
• Theorem: Every natural number is an ordinal.
• Def: $$\omega=\mathbb N$$.
• Theorem: $$\omega$$ is ordinal.
• Lemma: If $$\alpha$$ is ordinal then $$S(\alpha)$$ is ordinal.
• Def: $$S(\alpha)$$ is an sucessor ordinal. Other ordinals are limit ordinals.
• Def: $$\alpha<\beta$$ iff $$\alpha\in \beta$$.
Apr 18
More on ordinal nunbers
• Theorem: Let $$\alpha, \beta, \gamma$$ be ordinals.
• $$\alpha < \beta < \gamma \implies \alpha < \gamma$$
• Not $$\alpha < \beta$$ and $$\beta < \alpha$$
• always $$\alpha < \beta$$ or $$\alpha = \beta$$ or $$\alpha > \beta$$)
• Every nonempty set of ordinals has a least element. Thus, every set of ordinals is well-ordered by $$\in$$.
• For every set $$X$$ of ordinals the set $$\cup X$$ is an ordinal.
• For every set $$X$$ of ordinals there is an ordinal $$\alpha \not\in X$$.
• Theorem: $$\mathbb N$$ is precisely the set of finite ordinals.
• Theorem: Every well-ordered set is isomorphic to a unique ordinal. This theorem needs a new axiom, it will be next time
• May 2
• Axiom of replacement
• Finish proof of the theorem from previous lecture (every well-ordered set is isomorphic to an ordinal)
• Transfinite induction
• Transfinite recursion
May 9
• Ordinal arithmetics (+,*, powers); examples
May 10
Axiom of choice; Zorn's lemma and its equivalence to axiom of choice.
May 17
More on consequences of the axiom of choice

## Literature

Many recommended books are mentioned in the SIS description of the class. We loosely follow the book by Hrbacek and Jech. You may want to consult notes of Václav Končický (in Czech).