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.

  • 2
    $\begingroup$ What is your statement of Upwards Löwenheim-Skolem? (Also the statement $\forall A |A\times A|=|A|$ should require $A$ to be infinite!) $\endgroup$ Sep 24, 2020 at 1:11
  • $\begingroup$ Yes infinite A of course! As for the Upwards Lowenheim Skolem, I forgot about that for some reason. But the formulation seems to be the traditional: "If $M$ is an infinite structure, then for every cardinal $\lambda \geq |M| + |L(M)|$ $M$ has an elementary superstructure of cardinality $at$ $least$ $\lambda$". I'm not really sure of how AC plays with cardinality, would this statement be sketchy without AC? $\endgroup$ Sep 24, 2020 at 1:18

1 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.

  • $\begingroup$ " Without AC, it is not necessarily true that every infinite cardinality is greater than or equal to $\aleph_0$" Wow I didn't know that! Also slightly confused about your phrasing, when you write "... rather than just $|N| \leq |A|$", there's no version of Lowenheim Skolem that says $|N| = |A|$ right (which is what is implied)? So this problem would arise with any version of Lowenheim Skolem, not just mine? In any case, I'm satisfied with this answer. Thank you! $\endgroup$ Sep 24, 2020 at 1:53
  • 1
    $\begingroup$ Well, the version of Löwenheim-Skolem that uses cardinal addition does so as a convenience in the presence of AC, where addition just means "max". Here's an alternate statement of Löwenheim-Skolem where there wouldn't be an issue with $\aleph_0$: if $M$ is an infinite structure over a countable language and $A$ is any infinite subset of $M$, then $M$ has an elementary submodel which contains $A$ and has the same cardinality as $A$. $\endgroup$ Sep 24, 2020 at 1:58
  • $\begingroup$ Hmm I always thought you necessarily needed an additional $\aleph_0$ along with $|A|$ as "padding" to make everything work out. I'll take a look at the proofs of the theorems again. Thank you once again! $\endgroup$ Sep 24, 2020 at 2:03
  • $\begingroup$ Well (in the presence of AC), an equivalent way to state that "padding" is to just require $A$ to be infinite. $\endgroup$ Sep 24, 2020 at 2:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .