Infinite sets (NMAI074), WS 2019/2020
Česká verze (Czech version)
Jan Kynčl, KAM (kyncl  at  kam.mff.cuni.cz)
The lecture takes place on Thursdays at 14:00 in S9.
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
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)

Transfinite recursion as a fundamental principle in set theory  equivalence of the transfinite induction and the replacement axiom
 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
 Cantor's_Attic  encyclopedia of infinities: large ordinals and cardinals, hierarchy of functions
 How to write aleph by hand
 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
The lecture will be very similar to the last year.
Exercise problems
Topics of lectures:
3.10.
 Introductory information, recapitulation of some notions, axioms and statements from set theory
 Proof of the theorem about the type of a wellordering
 Principle of transfinite induction (statement)
10.10.
 Theorem about construction by transfinite recursion, with proof
 Wellordering principle (statement), remark about generalization to proper classes
 Maximality principle (Zorn's lemma), with proof by transfinite recursion; version where instead of chains it is enough to consider wellordered subsets
17.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
 Fixedpoint theorem for normal functions
 Ordinal sum and product, basic properties, examples of noncommutativity
individual reading [BS, p. 154159, 3.163.32] [HJ, p. 120125, 5.46.4]
 Monotonicity of 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, alternative expansions of ordinals
24.10.
 Ordinal epsilon_0
 Hydra and Herkules
 Goodstein sequences, Goodstein theorem, formal proof without verification of all formulas
31.10.
 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 wellordered sets, finite and countable cardinals
 The class Cn of all cardinal numbers is closed
 For each cardinal there is a larger cardinal, and so the class Cn is proper
7.11.
 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, cofinal of a limit ordinal number, examples of ordinals with cofinal omega
 Note about the independence of the statement "the cofinal of every limit ordinal is omega" in ZF
 The cofinal of a limit ordinal alpha satisfies cf(cf(alpha))=cf(alpha)
14.11.
 The cofinal of a limit ordinal is always a cardinal
 Regular and singular cardinal, examples
 The cofinal 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, a remark about possible values of alpha for which it is consistent that 2^{aleph_0}=aleph_alpha
 Generalized continuum hypothesis
 Cardinal arithmetics (in ZFC)
 Cardinal power and its basic properties
 Cardinality of the continuum
21.11.  Open doors day, the lecture is cancelled
28.11.
 The number of open subsets of the real numbers, the number of continuous functions between the real numbers
 (Infinite) sum and product of cardinal numbers
 The cardinality of the set of lambdaelement subsets, and subsets of cardinality less than lambda
 Computation of the infinite sum of cardinal numbers, characterization of singular cardinals by infinite cardinal sum
 Inequality between the cardinal sum and product
 König's inequality
 Consequences for cardinal arithmetics: cf(kappa^lambda)>lambda, lambda^{cf(lambda)}>lambda
5.12.
 Information about posible values of 2^{alef_alfa}
 Infinite combinatorics
 Tree as an ordered set where sets of predecessors are wellordered, examples of trees
 König's theorem (in ZFC): a tree of height omega whose every level is finite has a cofinal branch
 A remark about generalizations of König's theorem to larger heights and "widths".
12.12.
 Compactness principle for partial selectors on a system of finite sets, proof from the maximality principle
 Coloring infinite hypergraphs, infinite Hall's theorem
 Infinite Ramseytype theorems
 Homogeneous set for a partition of a set of (unordered) rtuples, and for a function from a set of rtuples
 Partition arrow as a shortcut for a Ramseytype theorem
 Pigeonhole principle for a regular and a singular cardinal as a special case of a Ramseytype theorem
 Finite Ramsey's theorem (statement), infinite Ramsey's theorem for countable sets (idea of a proof)
19.12.
 Paris–Harrington theorem strengthening Ramsey's Theorem, proof from the infinite Ramsey's theorem by compactness principle
 Corollary of the infinite Ramsey's theorem for chains and antichains in infinite ordered sets
 Sierpinski's Theorem about the nonexistence of an uncountable homogeneous set for colorings of pairs of real numbers
 Generalization of Sierpinski's theorem for successors of infinite cardinals (without proof)
 Erdős–Rado theorem generalizing Ramsey's theorem for successors of infinite cardinals (without proof)
 Counterexample for a generalization of Ramsey's theorem for colorings of countable subsets
 Weakly compact cardinal, Ramsey cardinal
 Chromatic numbers of infinite graphs
 The problem of the chromatic number of the plane
 An example of a distance graph on the real numbers that is bipartite in ZFC but has uncountable chromatic number in ZF + AC_{alef_0} + LM (without proof)
9.1.
 Paradoxical decompositions
 Congruence, equidecomposability using n parts, basic properties
 Generalization of Cantorovy–Bernstein theorem for equidecomposability
 Unit sphere is equidecomposable with the complement of its countable subset using two parts
 Existence of two "independent" rotations of the sphere by 180 and 120 degrees (without proof)
 Banach–Tarski paradox: unit ball is equidecomposable with two disjoint unit balls using 10 parts