The Upwards and Downwards Lowenheim Skolem Theorem together imply the axiom of choice (in ZF)

Question

Here the hints were to use the facts that $ZF \vdash (\forall$ infinite$ A |A \times A| = |A|) \rightarrow AC$ and that there is a bijection between $\omega \times \omega$ and $\omega$.

My idea was then to simply consider the theory with a single function symbol $f$, where the theory says "$f$ is a bijection". Call this $T$. $T$ has a model, $\omega$, and by applying the upwards and downwards lowenheim skolem theorem, we can get models of arbitrary cardinality, and thus bijections on sets of arbitrary cardinality.

There are a few problems with this of course: one is the straightforward problem that not every set is accounted for in this manner, only the sets lucky enough to become models (and $ZF$ requires that for all sets $A$, $|A^2| = |A|$, to prove Choice). I was hoping to get around this by looking at the proof of this statement and notice that it only requires this to hold for cardinals or something, but that doesn't seem to be true. A subtler concern is that all this talk of cardinals is suspect to begin with in the absence of choice, and I'm not sure if I'm being too flippant with my use of cardinals in a choice-free setting.

Is my approach on the right track?

For reference, here's the 'cardinal free' version of Downward Lowenheim Skolem theorem:

Given an infinite structure $M$, then for all $A \subseteq M$, there is a $N \prec M$ such that $A \subseteq N$ and $|N| \leq |A| + \aleph_0 + |L|$

All references to cardinality here can be thought of choice free.

Answer 1

Well, given an infinite set $A$, in order to prove $|A\times A|=|A|$, you only really care about the cardinality of $A$: in other words, it suffice to prove that $|B\times B|=|B|$ for some $B$ such that $|B|=|A|$ (since you can transport a bijection $B\times B\to B$ along a bijection between $B$ and $A$). So it doesn't matter what specific sets we get in our models, as long as we hit every possible cardinality.

Unfortunately, though, your argument doesn't work: starting from $\omega$ and going up and down as your statement of Löwenheim-Skolem allows, you cannot reach all infinite cardinalities in the absence of AC. In particular, your version of Downward Löwenheim-Skolem will never guarantee the existence of a model of any cardinality that is not greater than or equal to $\aleph_0$ (because the conclusion has $|N|\leq |A|+\aleph_0+|L|$ rather than just $|N|\leq |A|$). Without AC, it is not necessarily true that every infinite cardinality is greater than or equal to $\aleph_0$.

Here, then, is a more careful version of the argument you propose in the special case that $|A|\geq \aleph_0$. Starting from the model $\omega$, Upward Löwenheim-Skolem gives a model $M$ of cardinality at least $|A|$. Picking a subset of $M$ which is in bijection with $A$, Downward Löwenheim-Skolem then gives a submodel $N$ of $M$ such that $|A|\leq |N|$ (since $N$ contains our chosen subset of size $|A|$) and $|N|\leq |A|+\aleph_0$. But since $|A|\geq \aleph_0$, $|A|+\aleph_0=|A|$ (since $|A|\geq\aleph_0$, we can write $|A|=\aleph_0+|B|$ for some $B$, and then $|A|+\aleph_0=(|B|+\aleph_0)+\aleph_0=|B|+(\aleph_0+\aleph_0)=|B|+\aleph_0=|A|$). Thus $|N|=|A|$, and since we have $|N\times N|=|N|$ we conclude that $|A\times A|=|A|$.

Of course, this still leaves the issue: what if $|A|\not\geq\aleph_0$? Well, it turns out that if you look at the proof that $|A\times A|=|A|$ for all infinite $A$ implies AC, it actually only ever uses sets $A$ such that $|A|\geq\aleph_0$. (Specifically, it uses $A$ of the form $X\sqcup \aleph(X)$ where $X$ is an infinite set and $\aleph(X)$ is its Hartogs number, and $\aleph(X)$ always contains $\omega$.) So actually, the weaker conclusion obtained above is still enough to deduce AC.