Set Theory

Jan Hubička,

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

Topics covered

Feb 14
Feb 21
Feb 28
March 4
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)
    March 25
    Countable sets (lecutre by Andres Aranda)
    Un countable sets
    April 4
    Dedekind cuts
  • 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
    May 9
    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


    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).