Infinite sets (NMAI074), WS 2025/2026

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

The lecture takes place on Tuesdays at 17:20 in S10.

Entry in SIS, syllabus

This course is a sequel to Set theory (NAIL063). In the first part we focus on ordinal and cardinal arithmetics, in the second part on combinatorial properties of infinite sets and graphs, and consequences of the axiom of choice in combinatorics and geometry. We will also see examples of "elementary" combinatorial statements whose validity depends on the chosen axioms (axiom of infinity, axiom of choice).

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. Covers approximately the first two thirds of the course.
• S. Shelah and A. Soifer, Axiom of choice and chromatic number of the plane - an example of a "distance" graph whose chromatic number depends on the axioms
• Carl W. Lee, The Banach-Tarski Paradox: How to Disassemble a Ball the Size of a Pea and Reassemble it into a Ball the Size of the Sun

• Jakub Smolík, Infinite Sets

• Mirek Olšák, Essence of Set Theory - very nice animated videos (ordinal numbers, Zorn's lemma, transfinite recursion)
• [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)
• Transfinite recursion as a fundamental principle in set theory - equivalence of the transfinite induction and the replacement axiom
• The axiom of well-ordered replacement is equivalent to full replacement over Zermelo + foundation - the replacement axiom for well-ordered sets implies the replacement axiom even without AC
• A simple proof of Zorn's lemma, Zorn's lemma - proofs of Zorn's lemma without transfinite recursion or ordinal numbers
• Zorn's lemma on proofwiki - two proofs, with recursion and without
• L. Kirby and J. Paris, Accessible Independence Results for Peano Arithmetic - proof of the theorem about Goodstein sequences and about the hydra, unprovability in Peano arithmetics, using external results from logic
• Will Sladek, The Termite and the Tower: Goodstein sequences and provability in PA - Goodstein sequences, fast growing hierarchy of functions, equivalence of Peano arithmetics and the theory of finite sets
• M. Loebl, Hercules and Hydra - strengthening of the theorem by Kirby and Paris: in PA it is not provable that a particular strategy MAX is winning
• M. Loebl and J. Matoušek, Hercules versus hidden Hydra helper - a "short" strategy of Hercules, which defeats the hydra in a number of steps bounded by a tower function; thus PA proves that it is a winning strategy
• Hardy Hirarchy Calculator - computation of values of functions from Hardy's hierarchy, uses a slightly different definition of a fundamental sequence
• Cantor's_Attic - encyclopedia of infinities: large ordinals and cardinals, hierarchy of functions
• How to write aleph by hand
• Dana Scott, A proof of the independence of the continuum hypothesis - a more elementary proof of the independence of the continuum hypothesis by modeling real numbers as random variables
• B. Bukh, Walk through Combinatorics: Compactness principle - compactness principle for coloring of hypergraphs
• B. Osofsky and S. Adams, Problem 6102 and solution - a nontrivial combination of rotations by 180 and 120 degrees aroud two axes with mutual angle 45 degrees is never an identity

Exercise problems

Topics of lectures:

30.9.

• Introductory information, recapitulation of some notions, axioms and statements from set theory
• Proof of the theorem about the type of a well-ordering

7.10.

• Principle of transfinite induction (statement)
• Theorem about construction by transfinite recursion, with proof
• Well-ordering principle (statement), remark about generalization to proper classes
• Maximality principle (Zorn's lemma), with proof by transfinite recursion; including a version where instead of chains it is enough to consider well-ordered subsets

14.10.

• Ordinal arithmetics
• Ordinal function (increasing, nondecreasing)
• Icreasing ordinal function grows at least as fast as the identity
• The ordinal type of a subset B of A is smaller or equal to the ordinal type of A (even if B is a proper subset, its type can be the same as the type of A)
• Closed class of ordinals, normal ordinal function (continuous and increasing)
• Basic properties of normal functions
• Fixed-point theorem for normal functions
• Ordinal sum and product, basic properties, examples of noncommutativity
• Overview of basic properties of ordinal arithmetics (details as recommended individual reading [BS, p. 154–159, 3.15–3.34] [HJ, p. 120–125, 5.4–6.4])
  • Monotonicity of the sum and product
  • Distributivity from the left
  • Existence of the "right" difference
  • Division with a remainder
  • Continuity of the sum and product in the second variable
  • Ordinal powers - recursive definition, basic properties, monotonicity, continuity, addition and multiplication in the exponent
  • Expansion of an ordinal number in powers of omega (Cantor normal form), alternative expansions of ordinals, expansions using an arbitrary base
  • Ordinal epsilon_0

21.10.

• Hydra and Hercules, the existence of a winning strategy without proof (exercise)
• Goodstein sequences, Goodstein theorem, formal proof without verification of all formulas
• Kirby–Paris theorem without proof