Set theory (NAIL063), 2024/2025

Jan Kynčl, KAM (kyncl - at - kam.mff.cuni.cz)

The lecture takes place on Wednesdays at 14:00 in S4.

Entry in SIS, syllabus

We can arrange consultations in person or by email.

Recommended literature

• [BS] B. Balcar, P. Štěpánek, Teorie množin, Academia, Praha, 2001 (or earlier editions). In Czech. Available in the library in Troja.

• [HJ] Karel Hrbacek, Thomas Jech: Introduction to Set Theory, 3. edition, Marcel Dekker, 1999 - an English alternative to [BS], slightly different approach, but a great overlap of topics
• Thomas Jech, Set theory, Springer, 2003 (Part I)
• Richard Evan Schwartz, Gallery of the infinite, American Mathematical Society, Providence, RI, 2016 (link)
• Mirek Olšák, Essence of Set Theory - very nice animated videos (slightly different terminology - axiom of existence, axiom of infinity, ordering, ...)

Exercise problems

Topics of lectures:

19.2.

• Introductory information
• Brief history of set theory, paradoxes
• Language of set theory (and logic): symbols, formulas, extension by additional symbols
• Examples of axioms of propositional and predicate logic

26.2.

• Examples of axioms of equality, examples of deduction rules (we will use logic intuitively)
• Zermelo–Fraenkel theory (ZF)
• Axiom of existence
• Axiom of extensionality
• Axiom schema of separation (also comprehension), intersection, set difference, empty set
• Axiom of pairing (also pair), unordered set {a,b}, one-element set {a}, ordered pair (a,b), (x,y)=(u,v) implies x=u and y=v, ordered n-tuple
• Axiom of union, union of a set a as a unary operation, union of two sets a, b, unordered n-tuple
• Axiom of power set, power set of a set a

5.3.

• Axiom Schema of replacement
• Axiom of foundation (regularity)
• Classes
• Class term, class determined by a formula ("definable collection of sets"), every set is a class, other classes are proper classes
• Extension of the language of set theory by class terms and class variables, elimination of class terms from atomic formulas
• Binary class operations: intersection, union, difference
• Universal class V, (absolute) complement of a class
• Predicates "to be a subclass", "to be a proper subclass"
• Unary class operations: union, intersection, power class
• The universal class is not a set (exercise)
• The intersection of a set and a class is a set
• Cartesian product of two classes, the Cartesian product of two sets is a set

12.3.

• Cartesian power X^n as a class of all ordered n-tuples
• Relations
• (Binary) relation, n-ary relation
• Relations of membership and identity
• Domain of (a class) X, range of X, image of a class Y by a class X, restriction of a class X to a class Y
• If x is a set, then the following classes are also sets: the domain of x, the range of x, the image of a class Y by the set x, the restriction of the set x to a class Y
• Inverse relation, composition of relations
• Shortcut for quantification over a class (relativization of quantifiers)
• Mapping (of a class X into a class Y, onto a class Y, injective), class ^aA of all mappings of a set a into a class A; if A is a set, then ^aA is also a set; if a is non-empty and A is a proper class, then ^aA is also a proper class
• Orders
• Reminder of basic properties of relations (reflexive etc.) on a class A, hereditability
• Order (ordering) on a class A, comparable elements

19.3.

• Linear ordering, strict ordering, notation
• Majorant (upper bound), maximal element, maximum (largest) element, supremum; maximum element is always maximal, in a linear ordering there is at most one maximal element (which is then also maximum), maximum element and supremum are unique and can be denoted as max(X), sup(X)
• A set bounded from above, lower set, lower set determined by an element x (principal ideal determined by x), x≤y implies an inclusion of the lower sets determined by x,y
• Remark: Dedekind cuts on the set of rational numbers as a definition of real numbers
• Well-ordering, it is a hereditary property, every well-ordering is linear
• Revision of basic information about equivalences (definition, equivalence classes, equivalence classes form a partition)
• Comparing cardinalities
• Definition using injective mappings: "sets x,y have the same cardinality" (x is equivalent to y), "a set x has cardinality smaller than or equal to the cardinality of y" (x is subvalent to y)

26.3.

• Definition "a set x has cardinality smaller than y"
• The relation "to have the same cardinality" is an equivalence; the relation of subvalence is reflexive and transitive, but not weakly antisymmetric; the relation "to have the same cardinality" implies the subvalence
• Cantor–Bernstein theorem, a proof using a fixed-point lemma of a monotone mapping on a power set
• The cardinality of a Cartesian product of two copies of natural numbers is the same as the cardinality of the set of natural numbers (so far defined intuitively, and using arithmetics)
• The cardinality of a Cartesian product does not change by changing the order of the "factors", by the change of bracketing, nor by replacing the factors by different sets of the same cardinalities
• If x,y have the same cardinality, then their power sets have the same cardinality
• The cardinality of the power set of x is equal to the cardinality of the set of all mappings from x to 2
• How can one define "x is a finite set" (using orderings, mappings, or perhaps natural numbers)?

2.4.

• Finite sets
• Tarski's definition of a finite set: x is finite if every nonempty subset of P(x) has a maximal element with respect to inclusion
• A set x is finite if and only of every nonempty subset of P(x) has a minimal element with respect to inclusion
• Dedekind-finite set: has larger cardinality than each of its proper subsets
• Every finite set is also Dedekind-finite. A remark that in ZF it is not possible to prove the opposite implication.
• In a finite ordered set every nonempty subset has a maximal and a minimal element
• Every linear ordering on a finite set is a well-ordering
• Isomorphism of classes A,B with respect to relations R, S, initial embedding of a set A to a set B with respect to orderings R, S
• Two initial embeddings of A to B with respect to well-orderings R, S are always comparable by inclusion
• For every pair of well-ordered sets there exists exactly one initial embedding that is an isomorphism of one of the sets and a lower subset of the other one (uniqueness as an exercise) (so far a first part of the proof)

9.4.

• Finishing the proof of the theorem about comparing well-orderings
• Every pair of well-orderings on a finite set are isomorphic
• Finiteness is preserved for subsets, sets of the same cardinality, sets of smaller cardinality
• The union of two finite sets is finite
• Induction principle for finite sets
• The power set of a finite set is finite (proof by induction)
• The Cartesian product of two finite sets is finite
• The union of finitely many finite sets is finite
• Every finite set is comparable with every other set by the subvalence relation

16.4.

• Natural numbers
• Von Neumann's definition of natural numbers one by one, alternatives
• Inductive set
• Axiom of infinity
• The set of all natural numbers as the intersection of all inductive sets, it is the smallest inductive set
• Remark about nonstandard models of natural numbers
• Successor function
• Induction principle for natural numbers
• Elements of a natural number are again natural numbers
• The membership relation is transitive and antireflexive on the set of all natural numbers, and therefore a strict ordering
• Every natural number is a finite set
• A set x is finite if and only if ther exists a natural number n that has the same cardinality as x
• The set of all natural numbers, and therefore every inductive set, is infinite
• The membership relation and strict inclusion are identical on the set of all natural numbers

23.4.

• The membership relation is trichotomic on the set of all natural numbers, and therefore a linear ordering
• The membership relation is a (strict) well-ordering on the set of all natural numbers
• Characterisation of linear orderings isomorphic to the set of natural numbers ordered by membership
• Countable sets
• Countable, at most countable and uncountable set
• Sets of natural numbers bounded from above are finite, and those unbounded from above are infinite; a subset of a countable set is finite or countable
• Lexicographic and maximum-lexicographic ordering on the set of ordered pairs of natural numbers

30.4.

• The union of two countable sets is countable, the Cartesian product of two countable sets is countable
• Corollaries: the countability of the sets of integers and rational numbers, finite unions and finite products of countable sets, pigeonhole principle for finite unions and partitions
• Remark that in ZF it is not possible to prove that the countable union of countable sets is countable, or that every infinite set contains a countable subset
• Cantor's theorem and real numbers
• Cantor's theorem: the power set of x has always strictly larger cardinality than x; in fact, there exists no mapping of x onto the power set of x, proof by diagonal method
• Corollaries: the power set of the set of all natural numbers is uncountable, the universal class is not a set
• The set of all real numbers has the same cardinality as the power set of the set of all natural numbers (the cardinality of the continuum)
• The set of all real algebraic numbers is countable (assuming that the set of all finite sequences of natural numbers is countable)
• Continuum hypothesis
• Axiom of choice
• The problem of the existence of an injective mapping g of Rng(f) to Dom(f) for a general function f, satisfying f(g(y))=y (that is, g is a right inverse of f)
• Principle of choice: every partition of a set has a set of representatives (a transversal)
• Axiom of choice (AC): every set has a choice function (a selector)

7.5.

• Examples of statements equivalent to AC, examples of consequences of AC in various areas of mathematics
• Indexed collection of sets
• Union, intersection and Cartesian product of a collection of sets
• Equivalent statements (in ZF): principle of choice; axiom of choice; existence of a function that is a subset of a given set relation and has the same domain; Cartesian product of a nonempty collection of nonempty sets is nonempty
• (AC) The union of a countable collection of (at most) countable sets is (at most) countable
• Remark that in ZF it is consistent that the set of real numbers is a countable union of countable sets
• Maximality principle (PM), also called Zorn's lemma
• Trichotomy of the subvalence relation (PT) (that is, every pair of sets can be compared by their relative cardinality)
• PM implies PT

14.5.

• (PT) Every infinite set has a countable subset (hence it is Dedekind infinite)
• Well-ordering principle (WO)
• WO implies AC
• Ordinal numbers
• Informal intro
• Transitive class, examples: natural numbers, the set of all natural numbers, the universal class
• The intersection and union of two transitive classes are transitive, the intersection and union of a class of transitive sets are transitive
• If X is a transitive class, then the membership relation is transitive on X if and only if every element of X is a transitive class (proof as exercise)
• Ordinal number (ordinal) and the class On, examples: natural numbers and the set of all natural numbers
• The class On is transitive
• The membership relation is antireflexive on On, the intersection of two ordinals is an ordinal, the membership and the strict inclusion are identical relations on On
• The membership relation is a strict well-ordering on On; moreover, every nonempty subclass of On has a minimum element
• On is a proper class
• If X is a transitive class, strictly well-ordered by membership, then X=On (proof as exercise)
• Labeling ordinals by Greek letters, relation < on On
• A set of ordinals is an ordinal if and only if it is transitive
• The intersection of a nonempty class of ordinals is its smallest element, the union of a set of ordinals is its supremum in (On,<)
• The set of all natural numbers (omega) is the supremum of omega in (On,<) (proof as exercise)

21.5.

• Finite ordinals are exactly natural numbers
• Successor and predecessor, isolated and limit ordinals
• Theorem about the existence and uniqueness of an isomorphism of a well-ordered set with an ordinal (without proof), type of a well-ordering
• Transfinite induction principle, two variants
• Theorem about construction by transfinite recursion, several variants (without proof)
• Example of an application of transfinite recursion: AC implies WO (sketch of proof)
• Aplication of transfinite recursion
• (AC) R^3 is the union of pairwise disjoint unit circles (proof by transfinite recursion, using the well-ordering principle for labeling R^3 by ordinal numbers smaller than continuum)