Talk:Tarski's theorem about choice
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Knaster-Tarski theorem?
[edit]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
[edit]- "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)
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)
- 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)
Simplified proof
[edit]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)
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)
Proof of the converse
[edit]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)
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)
Start a discussion about improving the Tarski's theorem about choice page
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "Tarski's theorem about choice" page.