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.

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.

Other resources:

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

The lecture will be in English, the topics very similar to the last year.

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

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

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

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

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)

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

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)

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

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