Talk:Tarski's theorem about choice

Knaster-Tarski theorem?

Did the requester really want the Knaster-Tarski theorem?David.Monniaux 20:58, 17 Sep 2003 (UTC)

I don't think so. I think they're two completely different things. The Mathworld page on the Tarski theorem shows it as having to do with arithmetic operations on real numbers while the Knaster-Tarski theorem has to do with sets of points in a lattice. -- Ortonmc 21:23, 17 Sep 2003 (UTC)

I'm no longer sure about this. After a bit more poking around, it appears there may be more than one theorem called "Tarski's Theorem", the Knaster-Tarski theorem being one of them. -- Ortonmc 21:52, 17 Sep 2003 (UTC)

Question on proof

"Since the collection of all ordinals such that there exist a surjective function from B to the ordinal is a set..."

Why is that? It smells like it should be the replacement axiom, but I don't see it.--80.109.80.78 (talk) 17:33, 23 January 2014 (UTC)[reply]

No set can be greater than every ordinal, that's actually a Theorem of Hartogs-Sierpinski. It constructs for every infinte set B a well-ordered subset C of 2^2^2^B with no possible injection from C into B. Then the proof of Tarski's theorem goes through identically, replacing only β with C and surjective with injective. — Preceding unsigned comment added by 87.171.165.186 (talk) 01:49, 22 June 2016 (UTC)[reply]

You could take the Hartogs number of the powerset of B. Since any surjection from B to an ordinal determines an injection from the ordinal to the non-empty elements of the powerset of B, this should be an upper bound on the desired ordinal. JRSpriggs (talk) 06:23, 24 August 2019 (UTC)[reply]

Simplified proof

The proof in the article seems unnecessarily complicated to me. Here is a simpler proof.

We show the well-ordering theorem and thus the axiom of choice. Let S be any set. We wish to show that it can be well-ordered.

Let H be the maximum of ω and the Hartogs number of S. Then A := S∪H will be an infinite set. By hypothesis, there is an injection from A×A to A. Thus there is an injection f from S×H to S∪H.

For any element x∈S, there must be at least one element in { f(x,α) : α∈H } − S ⊆ H−S, otherwise we would have an injection from H to S which is contrary to the choice of H. Let g(x) be the least such element (in the ordering of H). g is an injection from S to H−S. Then we order S according to the ordering pulled back from H−S thru g. This is a well-ordering of S as required.

OK? JRSpriggs (talk) 06:58, 24 August 2019 (UTC)[reply]

Compared to the proof in the article, this reverses the direction of the bijection and uses the property of injection rather than surjection. JRSpriggs (talk) 07:13, 24 August 2019 (UTC)[reply]

Proof of the converse

As the article says, "the opposite direction was already known". However, since it was not entirely obvious to me, here is a proof that the axiom of choice implies that there is a bijection between A×A and A when A is an infinite set.

We will show in ZF (without choice) that for any infinite ordinal α, α×α ≈ α. Since the axiom of choice implies that there is an α ≈ A, we get A×A ≈ α×α ≈ α ≈ A.

We proceed by transfinite induction with inductive hypothesis: ω≤α → α×α ≈ α. It is well-known that there are many pairing functions which realize ω×ω ≈ ω.

If α is an infinite ordinal which is not an initial ordinal, then there is an ordinal β such that ω≤β<α with α ≈ β. In this case, α×α ≈ β×β ≈ β ≈ α.

Otherwise, α>ω is initial.

Now I need to define a specific ordering, <_csq, on α×α. ("csq" stands for "continuous square".) For any β, γ, δ, ε less than α, let

(β,γ) <_csq (δ,ε) ←→ max(β,γ) < max(δ,ε) or ( max(β,γ) = max(δ,ε) and ( γ<ε or ( γ=ε and β<δ ) ) ).

This is a well-ordering on α×α. So it gives us α×α ≈_csq ζ for some ordinal ζ. If ζ=α, then we are done.

If α<ζ, then there is some (β,γ) in α×α at the location corresponding to α in the <_csq ordering. Let η = max(β,γ)+1 which is less than α. Then α can be injected into η×η ≈ η which can be injected into α, so the Schröder–Bernstein theorem gives us α ≈ η contradicting the fact that α is initial.

If ζ<α, then we can inject α into α×α using the map which takes η to (η,0). So α injects into α×α ≈ ζ which injects into α. Again using the Schröder–Bernstein theorem gives α ≈ ζ contradicting the fact that α is initial.

OK? JRSpriggs (talk) 21:42, 26 August 2019 (UTC)[reply]

If we extend the analysis of ζ to situations where α is not initial, we find:

ζ<α never occurs because ζ is a strictly increasing and continuous function of α. See normal function.
The class of α for which ζ=α is closed. (I suspect that it includes all α of the form ω^{ω^ν}.)

OK? JRSpriggs (talk) 07:14, 30 August 2019 (UTC)[reply]