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
-
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
- 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 well-ordering
- Principle of transfinite induction (statement)
10.10.
- 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; version where instead of chains it is enough to consider well-ordered 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
- Fixed-point theorem for normal functions
- Ordinal sum and product, basic properties, examples of noncommutativity
individual reading [BS, p. 154-159, 3.16-3.32] [HJ, p. 120-125, 5.4-6.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 well-ordered 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 lambda-element 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 well-ordered, 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 Ramsey-type theorems
- Homogeneous set for a partition of a set of (unordered) r-tuples, and for a function from a set of r-tuples
- Partition arrow as a shortcut for a Ramsey-type theorem
- Pigeonhole principle for a regular and a singular cardinal as a special case of a Ramsey-type 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