# 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:
The lecture will be very similar to the last year.

### 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

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