• The role of set theory in general

• As an application:

Proof sketch that there are no infinite opc lattices.

Size and counting

Pre-math: singular plural
ancient math:  1, 2, 3, 4, 5, …
or even:  1, 2, 3, 4, 5, …,  ∞
or sometimes:  1, 2, 3, 4, 5, …,  verboten
India? 0, 1, 2, 3, 4, 5, …

20th century naive mathematics: 0,1,2,3,4,5,…, countable, uncountable

Cantor, 19th century: there is much more than that. Not only two infinite cardinalities, but really infinitely many. In fact, uncountably many.

A ∼ B iff there is a bijection f : A → B [“equipotent”, “equinumerous”, “gleichmächtig”] A ≤ B iff there is a 1-1 map f : A → B A < B iff A ≤ B but A ≁ B Theorem: If A ≤ B and B ≤ A then A ∼ B. Theorem: For all A, B: A ≥ B or A ≤ B.

Definition: A “cardinality” is an equivalence class of equipotent sets.

Approximative Definition: Set theory is the classification of sets up to equipotency.

Second approximation: Set theory is the theory of well-orders (and of well-foundedness), and hence of “transfinite induction”.

INDUCTION on ℕ — an example.

Theorem: If L is a countable lattice then there is a cofinal chain C ⊂ L. [cofinal = ∀l ∈ L ∃c ∈ C : l ≤ c]

Proof: Let L = {l_{0}, l_{1}, l_{2}, ...}, let c_{0} be arbitrary, c_{n+1} = c_{n} ∨ l_{n}.

In other words: Well-order L in a NICE way [ L is infinite, but each element has only finitely many predecessors] and then construct C “by induction”.

Does this work for uncountable lattices?

TRANSFINITE INDUCTION:

To infinity and beyond!

Theorem: If L is of cardinality ℵ_{1}, and then there is a cofinal chain C ⊂ L. Proof: Well-order L in a NICE way [ L is uncountable, but each element has only countably many many predecessors] and then proceed by induction: c_{0} = arbitrary, c_{1} c_{0} ∨ l_{1}, etc. In “limit stages” ? Use σ-completeness!

Question: Is there an uncountable Boolean algebra B such that

– All chains in B are countable

– All (Boolean) antichains are countable ?

Note that 𝒫(ℚ) has no uncountable antichains, but there is an uncountable chain:

{A_{r} : r ∈ ℝ}

where A_{r} = {q : q < r}.

Answer: perhaps no.

Answer: perhaps yes. Well-order 𝒫(ℕ) and construct an uncountable increasing sequence of countable subalgebras with nice properties. [Baumgartner+Komjath] Notation: |A| = cardinality of A

2^{A} = set of all characteristic functions on A (isomorphic to 𝒫(A))

If κ is a cardinal, say κ = |A|, we write 2^{κ} for |2^{A}| = |𝒫(A)|.

To simplify the exposition we will use the [not true] assumption

2^{ℵ_{0}} = ℵ_{1}, 2^{ℵ_{1}} = ℵ_{2}, 2^{ℵ_{2}} = ℵ_{3}, …

A^{A} = set of all functions from A to A.

Cantor’s theorem: |2^{A}| > |A|. For infinite sets A we have |2^{A}| = |A^{A}|, so

|A| < |A^{A}|

From now on all lattices will be bounded: (L, ∨, ∧, 0, 1).

Definition: A lattice is called opc iff: For all n: Every monotone function f : L^{n} → L is represented by a polynomial.

Note: If L is countable, then there are only contably many polynomials. More generally, if |L| = κ, then there are only κ many polynomials, but there are 2^{κ} > κ many functions from L to L.

From now on all functions will be monotone.

Example: There are 2^{ℵ_{0}} many monotone functions from ℚ to ℚ. But there are also only 2^{ℵ_{0}} many monotone functions from ℝ to ℝ (and not 2^{2^{ℵ0}} ).

Fact: Let P be a partial order (with 0 and 1). If P^{n} contains an antichain [or a well-ordered chain] A of size κ, then there are 2^{κ} many monotone functions from A to A (trivial), and they can all be extended to monotone functions from P^{n} to P (easy).

Proof: There are 2^{κ} many functions from A to A. We can extend them to functions from L to A ∪ {0, 1}.

Strategy: Let L be an infinite lattice, say of size κ. We will try to find an antichain of size κ. [Hence L will not be opc] If we do not succeed, then our failure will give us another reason why L is not opc.

Definition: κ → (λ)_{3} means: Whenever you color the unordered pairs of a κ-element set with 3 colors, then there is a λ-element “homogeneous” subset.

Theorem: ℵ_{0} → (ℵ_{0})_{3}.

Fact: If κ → (λ)_{3}, then: Every partialorder with κ many elements contains a “uniform set” of size at least λ. (“Uniform” means: antichain, or well-ordered chain, or dually well-ordered chain.)

Theorem: ℵ_{1} ↛ (ℵ_{1})_{3}. In fact, the relation κ → (κ)_{3} is quite rare.

However: ℵ_{n+1} → (ℵ_{n})_{3}.

First step: If L is countable, then L contains an antichain [or chain – we will ignore this case for simplicity] of size ℵ_{0}, so there are unctbly many monotone functions from L , not all of them can be polynomials.

Next step: ℵ_{1}. Unfortunately, ℵ_{1} → (ℵ_{1})_{3} does not hold.

However: If L contains an antichain of size ℵ_{0}, then there are ℵ_{1} many functions f_{i} from L to L. They can be chosen to be pairwise incomparable. Now since the lattice is opc, this gives us an antichain of pw incomparable polynomials. Wlog they are all of the same type, i.e. there is some k and a k + 1-ary term t = t(x, y_{1}, ...y_{k}) , and for all i: f_{i}(x) = t(x, c̄_{i}), where c̄_{i} ∈ L^{k} are the “coefficients”.

So the c_{i} form an antichain of size ℵ_{1} in some L^{k}, this gives us ℵ_{2} many functions from L^{k} to L, etc. [Haviar and Ploscica].

What about ℵ_{ω}?

We know ℵ_{n+1} → (ℵ_{n})_{3}, so for each n we have an antichain A_{n} in L of size ℵ_{n}.

Together they have size ℵ_{ω}, but are there 2^{ℵ_{ω}} many monotone functions?

Yes. This uses the “canonisations theorem” and again ℵ_{0} → (ℵ_{0})_{3}.

For ℵ_{ω+1} use the same argument as for ℵ_{1}. …

For ℵ_{ω+ω} use the same argument as for ℵ_{ω}.

For ℵ_{ω_{1}} we use a new argument: Let L be opc, |L| = ℵ_{ω_{1}}.

Let Ω be a NICE well-order of size ℵ_{ω_{1}}. (so all initials segments of this wellorder have fewer than ℵ_{ω_{1}} many elements.

By transfinite induction on j ∈ ω, construct an increasing sequence L_{j} : j ∈ Ω such that:

– for all j: |L_{j}| is smaller than ℵ_{ω_{1}}.

– there are a_{j}, b_{j} ∈ L \ L_{j} which have the same “type” over L_{j} , i.e., L_{j} cannot distinguish between them.

(This exists, because there are only 2^{|L_{i}|} < ℵ_{ω_{1}} many possible “types” = sets of equations)

– There is a monotone function that maps a_{j} to 0 and b_{j} to 1. This functions is realized by a polynomial t(x, c̄_{j}):

t(a_{j}, c̄_{j}) = 0, t(b_{j}, c̄_{j}) = 1

c̄_{j} ∈ L^{n} are the n “coefficients” of the polynomial:

– a_{j}, b_{j}, c̄_{j} ∈ L_{j′} for all j′ > j.

Now check that the n + 2-tuples (a_{j}, b_{j}, c̄_{j}) form an antichain in L^{n+2} :

If j < j′ and (a_{j}, b_{j}, c̄_{j}) ≤ (a_{j′}, b_{j′}, c̄_{j′}) , then

0 = t(a_{j′}, c̄_{j′})  t(b_{j′}, c̄_{j′}) = 1
|  |
t(a_{j′}, c̄_{j}) ∼ t(b_{j′}, c̄_{j})
|  |
0 = t(a_{j}, c̄_{j})  t(b_{j}, c̄_{j}) = 1

But the equations t(a_{j′}, c̄_{j}) = 0 t(b_{j′}, c̄_{j}) = 1 distiguish between a_{j′} and b_{j′}, using only coefficients from L_{j′}, contradiction.