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

4.11.

• Hierarchy of fast growing functions: fundamental sequence of a limit ordinal, Hardy hierarchy, fast growing hierarchy
• Expressing the Goodstein function using functions of the fast growing hierarchy (without proof)
• Cardinal numbers (in ZF)
• Cardinal numbers as a subclass of ordinal numbers, cardinalities of well-ordered sets, finite and countable cardinals
• The class Cn of all cardinal numbers is closed
• For each cardinal there is a larger cardinal (so far only statement), and so the class Cn is proper

11.11.

• For each cardinal there is a larger cardinal
• Successor and predecessor of a cardinal, limit cardinal
• Function aleph numbering infinite cardinals
• The cardinality of a Cartesian product aleph_alpha x aleph_alpha is aleph_alpha
• Cardinal sum and product and its computation
• Examples of partitioning a cardinal into subsets, (non)generalizability of the pigeonhole principle
• Cofinal set, cofinality of a limit ordinal number, examples of ordinals with cofinality omega
• Note about the independence of the statement "the cofinality of every limit ordinal is omega" in ZF

18.11.

• The cofinality of a limit ordinal alpha satisfies cf(cf(alpha))=cf(alpha)
• The cofinality of a limit ordinal is always a cardinal
• Regular and singular cardinal, examples
• The cofinality of a limit ordinal is thus a regular cardinal
• A cardinal kappa is singular if and only if it is a union of less than kappa sets of cardinality less than kappa (corrected proof of the backward implication from [BS])
• Corollary: a generalized pigeonhole principle for regular cardinals
• In ZFC, the union of at most aleph_alpha sets of cardinality at most aleph_alpha has cardinality at most aleph_alpha (proof as exercise)
• Corollary: In ZFC, aleph_{alpha+1} is always a regular cardinal
• A weakly inaccessible cardinal, it is a fixed point of the aleph function (but not the smallest one), a remark about unprovability of its existence in ZFC, inaccessible cardinal
• Continuum hypothesis
• Generalized continuum hypothesis
• Cardinal arithmetics (in ZFC)
• Cardinal power and its basic properties
• Computation of the cardinal power in simple cases
• Cardinality of the continuum