Equivalents of the axiom of choice
David Libert
In the recent thread
[1] 18 articles Jan 30 '03 - Feb 6 '03 "Group Structure on any set"
http://mathforum.org/discuss/sci.math/t/478403
the question arose of the relations of AC to the proposition that any
infinite set is bijective with the set of all its finite subsets.
[1] noted this proposition is equivalent to AC over ZF. [1] also
discussed a related proposition: that every infinite set is bijective
with its square. This is also equivalent to AC over ZF.
That discussion referenced
[2] Mike Oliver Feb 11 '99 "Re: Addition on Infinities"
http://mathforum.org/discuss/sci.math/a/m/135314/135349
which proved that 2nd proposition about squares -> AC, giving also a
proof in ZF of a technical claim,
for X an infinite set and Y the Hartog number of X,
if XxY can be injected into the disjointified union X union Y
then X can be well-ordered.
The proof about squares used this claim. The same claim was used in
one proof from [1] that the finite subsets proposition -> AC. Fred
Galvin gave another proof of this implication just using the squares
prosition -> AC, this also in [1].
Here is a web page claiming to give some equivalents of AC from the
1963 book co-authored by Herman Rubin, Equivalents of the Axiom of
Choice:
[3] AC.html http://www.nd.edu/~rweber/AC.html
That includes the square one from above, and many other interesting
ones.
I think a lot of the cardinal based equivalents in [3] can be
proved to -> AC using the technical claim above proved in [2].
I don't presently have access to the book cited (there was also a
later version: with Roman numeral II, and then the more recent
Consequences of the Axiom of Choice by Jean Rubin and Paul Howard).
I will give my own proof that I apparently just found (ie modulo
mistakes etc) of one of the equivalents from [3], ie that it -> AC.
Namely: if m,n are infinite cardinals (allowing cardinals for
non-well-orderable sets) then m^2 = n^2 -> m = n.
Ie: squaring is injective on infinite cardinals.
Note this property is a trivial consequence of everything being its
own square, so this one implying AC gives another proof that the
squares proposition -> AC.
So suppose this injectivity property. We seek to show an arbitrary
infinite set X can be well-ordered, thereby over all X showing AC.
Let X1 be the closure over X of taking all 2-tuples, ie starting
with X as base set throw into X1 iteratively all <x1,x2> from
previous X1 elements x1,x2.
Then X1xX1 injects into X1, ie by inclusion. And X1 injects
into X1xX1 by _x(x_0) for any fixed x_0, so X1^2 ~ X1.
Let Y be the Hartog number of X1. Y is an infinite ordinal, so
Y^2 ~ Y, ie these are bijective.
So (X1xY)^2 ~ X1xY.
For X1 union Y being the disjointified union, X1xY is included in
(X1 union Y)^2, by X1 and Y respectively included in X1 union Y.
So combining the last two,
(X1xY)^2 injects into (X1 union Y)^2.
Conversely, X1 union Y injects into X1xY. Namely, send x1 in
X1 to <x1,0> and send y in Y to <x_0, 1+y> for some fixed
x_0 in X1.
So from X1 union Y injecting into X1xY, we get
(X1 union Y)^2 injects into (X1xY)^2.
We have both directions, so (X1xY)^2 ~ (X1 union Y)^2.
Now apply the assumed injectivity property to X1xY and
X1 union Y, from this bijection of squares we get
X1xY injects into X1 union Y.
Now apply the proof from Mike's [2] to this X1, obtaining X1 is
well-orderable.
But the original X is included in X1, so X is well-orderable too.
QED injectivity proposition -> AC
Another couple of interesting equivalents from [3] are the weak
unpard and downward Lowenhiem Skolem theorems. Namely if a sentence
has a countable model it has all uncountable cardinalities of models,
and if a sentence has an uncountable cardinality model it has all
smaller uncountable cardinalities of models.
I posted a few weeks ago counterexamples in choiceless models of
upward and downward Lowenhiem Skolem. But now [3] is claiming these
are outright equivalences to AC.
--
David Libert ah...@FreeNet.Carleton.CA
Martin Goldstern
> [3] AC.html http://www.nd.edu/~rweber/AC.html
> Another couple of interesting equivalents from [3] are the weak
> unpard and downward Lowenhiem Skolem theorems. Namely if a sentence
> has a countable model it has all uncountable cardinalities of models,
> and if a sentence has an uncountable cardinality model it has all
> smaller uncountable cardinalities of models.
>
> I posted a few weeks ago counterexamples in choiceless models of
> upward and downward Lowenhiem Skolem. But now [3] is claiming these
> are outright equivalences to AC.
Proof that upward LS implies AC: (not my own proof)
Consider a language with a binary function symbol f, and the
sentence "f is 1-1" (or: bijective).
This sentence has a countable model, hence a model on every infinite set.
However:
Note that this refers to the upward L-S theorem as stated in your post,
not the one stated on page [3]. You talk about "uncountable" (which
I read as "infinite and not countable") but page [3] talks about
"cardinalities greater than aleph0". Without AC, an infinite
Dedekind finite set is not countable, but also not "greater than aleph0".
Comments on http://www.nd.edu/~rweber/AC.html :
Btw, this page also mentions the existence of a nonmeasurable subset of R
(which is only a consequence of AC, not equivalent).
It also claims that "large cardinals" imply AC, which is a bit
confusing to me. Perhaps s/he uses "large cardinals" in a nonstandard
context? Certainly (and trivially) the existence of a class of
inaccessibles implies AC, because it implies that every P(kappa)
can be wellordered, but this is not interesting.
Rather, a converse is true: "large cardinals" imply that AC
*fails* (in a dramatic way) in certain canonical subclasses of
the universe.
David Libert
> In article <m3u1fcz...@localhost.localdomain>, David Libert wrote:
>
> > [3] AC.html http://www.nd.edu/~rweber/AC.html
>
> > Another couple of interesting equivalents from [3] are the weak
> > unpard and downward Lowenhiem Skolem theorems. Namely if a sentence
> > has a countable model it has all uncountable cardinalities of models,
> > and if a sentence has an uncountable cardinality model it has all
> > smaller uncountable cardinalities of models.
> >
> > I posted a few weeks ago counterexamples in choiceless models of
> > upward and downward Lowenhiem Skolem. But now [3] is claiming these
> > are outright equivalences to AC.
>
> Proof that upward LS implies AC: (not my own proof)
>
> Consider a language with a binary function symbol f, and the
> sentence "f is 1-1" (or: bijective).
> This sentence has a countable model, hence a model on every infinite set.
That is a nice argument. By the way, my previous LS counterexamples
involved a theory with individual constants for each member of a set
which cannot be linearly ordered (ie such a set in certain ~AC
models). So my previous examples involved a theory in an uncountable
language, with uncountably many axioms: ie axioms asserting the
constants are pairwise ~=.
The example above just involves one unary function symbol (as
opposed to an uncountable set of contants) and only involves one
sentence as axiom (instead of uncountably many axioms.)
> However:
>
> Note that this refers to the upward L-S theorem as stated in your post,
> not the one stated on page [3]. You talk about "uncountable" (which
> I read as "infinite and not countable") but page [3] talks about
> "cardinalities greater than aleph0". Without AC, an infinite
> Dedekind finite set is not countable, but also not "greater than aleph0".
You are right. I was thinking of infinite and not countable for
uncountable. I had read the statement in [3] earlier, and just
recalled it as being LS style.
My version and [3]'s version are each equivalent to AC over ZF. For
my version, use your proof above, getting from my LS statement that
every uncountable cardinal is bijective with its square, invoking the
Tarski theorem mentioned earlier.
To get from [3]'s LS to AC, we can run the same proof you gave
above, but the immediate conclusion we get from that is every cardinal
> aleph_0 is bijective with its square. But we can get a
strengthening of the original Tarski theorem, namely all cardinals >
aleph_0 are bijective with their own square -> AC.
To see this, suppose X is an arbitrary uncountable set, not
necessarily > aleph_0. We assume all sets > aleph_0 are bijective
with their squares, and seek to prove X can be well-ordered. Doing
this for all uncountable X suffices for AC.
So toward showing X can be well-ordered, let X1 = X union omega.
Then omega injects into X1. Now we run the old proof from Mike's
post, cited in the base of this thread, well-ordering X1 by getting
an injection X1xY >-> X1 disjoint-union Y where Y is the Hartog
number of X1.
To get such an injection, Mike's proof needed there is a bijection
(X1 disjoint-union Y)^2 <-> X1 disjoint-union Y. Since omega
injects into X1, omega injects into X1 disjoint-union Y, so the
weakened Tarski hypothesis about bijective with square applies to
X1 disjoint-union Y.
Everything else in Mike's article goes through without special
hypothesis, so we get a well-ordering of X1.
But the original X is a subset of X1, so X can be well-ordered.
My version with all uncountable sets is the more straightforward, to
immediately get to the original Tarksi theorem about squares, but the
version in [3] works with that minor adjustment above.
> Comments on http://www.nd.edu/~rweber/AC.html :
>
> Btw, this page also mentions the existence of a nonmeasurable subset of R
> (which is only a consequence of AC, not equivalent).
Yes. They did note that this one didn't come from the book. :-)
> It also claims that "large cardinals" imply AC, which is a bit
> confusing to me. Perhaps s/he uses "large cardinals" in a nonstandard
> context? Certainly (and trivially) the existence of a class of
> inaccessibles implies AC, because it implies that every P(kappa)
> can be wellordered, but this is not interesting.
>
> Rather, a converse is true: "large cardinals" imply that AC
> *fails* (in a dramatic way) in certain canonical subclasses of
> the universe.
Yes, I think they were speculating at that section. There is
something along those lines that can be said though.
I will paste the closing paragraph from [3] (reformating to shorter
lines):
>Most of these are not interesting by themselves (the cardinal
>arithmetic ones, for example, are obvious), but what is very
>interesting is that they are each equivalent to AC. In their full
>generality, of course. What I understand to be going on here is that
>the axiom of choice is implied by certain large cardinal axioms, and
>vice-versa, and so when you get into large cardinals (really big
>uncountable ones) a lot of what you say is going to be equivalent to
>AC. So the last list of cardinal arithmetic statements might not be
>equivalent to AC if you restricted yourself to reasonably small, maybe
>regular or accessible cardinals. But again, in full generality, each
>statement above is equivalent to AC.
They do say "axiom of choice is implied by certain large cardinals"
which is not a correct summary of the preceding results. Rather those
results that certain simple properties holding uniformly in the
universe imply AC. These properties were along the lines of things
falling into simple patterns generalizing omega, but not about
cardinals being large.
On the other hand, they close with comments about restricting the
statements to small cardinals not implying AC. There is a sort of
locality going on: if you had those cardinal properties are true in
an inaccessible rank then run the equivalence proofs in that rank,
obtaining it satisfies AC. AC is a local statement about its
instances, so an inaccessible rank satisfying AC implies in the real
universe those instances of AC from the rank are still true (ie sets
from the rank can be well ordered, or sets from the rank have choice
functions).
So a localized version of those statements (ie in some small defined
rank) implies a local version of AC. And it does not imply more:
given a starting countable ZFC model with levels beyond such a rank,
you can extend the model to mess up AC high in the universe, while
preserving the ground model small rank. So you end up with the local
versions of the cardinal statements and AC only.
So for example, if inaccessible cardinals are consistent, then
ZF + infinite sets below the least inaccessible are bijective with
their squares |-/- AC.
This is kind of along the lines of the last 2 sentences in [3]:
>So the last list of cardinal arithmetic statements might not be
>equivalent to AC if you restricted yourself to reasonably small, maybe
>regular or accessible cardinals. But again, in full generality, each
>statement above is equivalent to AC.
But large cardinal properties are something of a red herring in all
this.
A completely different question from [3]. [3] says results eithout
specific attribution are due to Tarski, so that would apply to this.
This is for m,n uncountable cardinals. The equivalence to AC is
claimed:
There is a cardinal number n such that m = n^2.
Ie: every uncountable set is bijective with some square.
Wow.
Note this also immediately implies the previous theorem: every
uncountable set is bijective with its own square -> AC.
So: ?????
--
David Libert ah...@FreeNet.Carleton.CA
David Libert
[...]
> > > [3] AC.html http://www.nd.edu/~rweber/AC.html
[...]
> A completely different question from [3]. [3] says results eithout
> specific attribution are due to Tarski, so that would apply to this.
>
> This is for m,n uncountable cardinals. The equivalence to AC is
> claimed:
>
> There is a cardinal number n such that m = n^2.
>
> Ie: every uncountable set is bijective with some square.
>
> Wow.
>
> Note this also immediately implies the previous theorem: every
> uncountable set is bijective with its own square -> AC.
>
> So: ?????
I think I have this. So we assume for every uncountable set there
is some set with its square isomorphic to the first set, and we seek
to show for X uncountable that X can be well-ordered.
Let alpha be the least ordinal beta s.t. there is no surjection
: X^2 ->> beta. In the notation from my last article of the group
structure thread referenced at the base of this thread, that would be
s(X^2), ie the surjective version of Hartog's number for X^2.
We apply the assumed premise to the set X disjoint-union alpha,
that is we find a set N s.t.
X disjoint-union alpha is isomorphic to N^2.
Picture this as a square with sides of N, with points on the square
labelled by either X elements or by ordinals < alpha.
We proceed by cases on the properties of this labelling, showing in
each case there is a well-ordering of X.
I claim there is no point <n_0, n_1> in N^2 s.t.
{n_0} x N union N x {n_1} is labelled entirely by X elements, ie
with no ordinal labels.
To prove this, suppose for contradiction that <n_0, n_1> is such a
point.
Then the labels on {n_0} x N give a subset X0 of X which we have
isomorphic to N, ie reading their occurence along that line.
Similarly looking at the labels on N x {n_1}, we get X1 a subset
of X which is isomorphic to N.
So we can map X0 x X1 isomorphically to N x N by using these
isomorphisms on each coordinate.
But N x N was isomorphic to X disjoint-union alpha, so X0 x X1
is isomorphic to X disjoint-union alpha.
We can surject X x X onto X0 x X1, since X0 and X1 are subsets
of X, ie use the identity function on X0 x X1, and send to some
fixed point in X0 x X1 in (X x X) - (X0 x X1).
So we compose from X x X to X0 x X1 to X disjoint-union alpha.
Then we surject from X disjoint-union alpha onto alpha by constant
0 on X and identity on apha.
Compose these and get surjection X^2 ->> alpha, this
contradicting that alpha was the surjective Hartog number for X^2.
So from this contradiction, as claimed above there is no point in
N^2 making a row and column of X labels.
We continue from this by cases, ie each case defining a
well-ordering of X from the labelling.
First assumption, suppose there is n_0 in N so that
{n_0} x N is labelled only by X elements.
Ie there is a row of X labels.
By the last claim, no point <n_0, n_1> in that n_0 row can have
a column of X labels over it. Ie <n_0, n_1> is required to have at
least one of its row or column not being entirely X labels, and we
are assuming the row is all X labels, so the column can't be all X
labels.
So we have our {n_0} x N row, and each point in that row has at
least one ordinal label occuring in its column.
To each point <n_0, n_1> in {n_0} x N, associate the smallest
ordinal occuring in that collumn, which must exist by the last
comment.
These labels on N x N came about by the isomorphism of N^2 to
X disjoint-union alpha, so all ordinal labels on N^2 are distinct,
so the association of points in {n_0} x N to oridnals just defined
is injective into ordinals.
So this induces a well ordering of the row {n_0} x N, ie by
injecting it into ordinals.
So we have jsut discovered that N can be well-ordered.
So N^2 can be well-ordered lexicographically, by two copies of
this last well-ordering.
N^2 was isomorphic to X disjoint-union alpha, so this can be
well-ordered, and that induces a well-ordering of its subset X, as
required.
This completes the case: some row in N^2 is all X labels.
Next case: suppose some column in N^2 is all X labels. This is
symmetric with the last case, so also induces a well-ordering of X,
and that case is done.
Final case: suppose no row or column of N^2 is all X labels, ie
each row and each column in N^2 contains at least one ordinal label.
We had our isomorphism : X disjoint-union alpha >->> N^2.
So given x in X, send it to <n_0, n_1> in N^2 by that
isomorphism, then look at the n_0 row and n_1 column, these each
contain at least one ordinal label by the present case, so take
alpha_0 the smallest ordinal occuring in the n_0 row and
alpha_1 the smallest ordinal occuring in the n_1 column.
So in this way given x in X we define <alpha_0, alpha_1> an
ordered pair of ordinals < alpha, so we define a map
: X -> alpha x alpha (cartesian product of alpha with itself).
Distinct rows have disjoint labels, since the labels were induced by
an isomorphism between X disjoint-union alpha and N^2.
So when we take the smallest ordinal appearing in respective
distinct rows, we get different smallest ordinals.
Similarly for columns.
So given x_0, x_1 distinct in X, the corresponding N^2 elements
are distinct, so at least the row or column must differ, so the
associated ordinals at such a row pair or column pair must differ.
So the map just defined X -> alpha x alpha is injective.
But alpha x alpha is well-orderable lexicographically on the
well-ordering on alpha.
So we have injected X into a well-orderable set. So X can be
well-ordered.
This completes the last case.
So QED: if every uncountable cardinal is a square, then AC.
This is striking. Consider the squaring function on infinite
cardinals. May as well take all infinite cardinals, because the
countable case is for free.
Squaring on infinite cardinals is injective iff AC. That was the
base article of this thread.
And now from the present article: squaring on infinite cardinals is
surjective iff AC.
(Well, I have been discussing the -> AC direction. The other
direction is standard theory of AC.)
So in particular: squaring (on infinite cardinals) is
injective <-> it is surjective.
Who knew?
In fact, by the other result mentioned in the base, each of these is
also equivalent to that squaring being the identity function.
Remarkable: it might be injective or it might not, and it might be
surjective or it might not, but it is injective <-> it is surjective.
--
David Libert ah...@FreeNet.Carleton.CA