Does $\operatorname{card}(X) < \operatorname{card}(Y)$ imply $\operatorname{card}(X^2) < \operatorname{card}(Y^2)$ without choice?

Question

I looked to see if this question was already posted, but did not find anything. Please let me know if this is a duplicate.

Assume $X, Y$ are infinite sets such that there is an injection $X \to Y$ but no injection $Y \to X$. Using the axiom of choice, we have that $\operatorname{card}(X) = \operatorname{card}(X^2)$ and similarly for $Y$, so under the hypothesis there is no injection $Y \times Y \to X \times X$.

I really have two questions relating to the title:

1) How much (if any) choice do we need to prove that there is no injection $Y \times Y \to X \times X$?

And for my own interest, as I could not come up with an argument:

2) Assuming choice, is there a direct argument to prove that there is no injection $Y \times Y \to X \times X$ without relying on cardinalities of the squares?

It is definitely possible that the answer to 1) already answers 2). Perhaps this is really a trivial question, but I have thought about it for a little while and have not made any progress.

Answer 1

This is false without the axiom of choice.

Mostowski constructed a model of $\sf ZFA$ (set theory with atoms), and in that model for every $n\in\Bbb N$ there is some $A$ such that: $$|A|<|A|^2<\ldots<|A|^n=|A|^{n+1}$$ So taking a large enough $n$ (e.g. $n=2$) we can take $X=A^{n-1}$ and $Y=A^n$. The Jech-Sochor theorem is enough to transfer this part of the model to a model without atoms.

So all in all, $\sf ZF$ cannot prove that if $|X|<|Y|$, then $|X|^2<|Y|^2$.

Answer 2

As to your question (1), the answer is: all of AC is needed.

Lemma: if $f:A\times B\to C\cup D$ is injective, $C\cap D=\varnothing$, and at least one of $A,B,C,D$ is well ordered, we have $|A|\leq|C|\vee|B|\leq|D|$. (By symmetry, one has $|A|\leq|D|\vee|B|\leq|C|$ as well!).

Proof: By symmetry, we may assume either $A$ or $C$ can be well ordered.

Let $R$ well order $A$. If $\forall_{b\in B}\exists_{a\in A}f(a,b)\in D$, then $b\mapsto f(a,b)$ gives an injection $B\to D$, where for $b\in B$ we take $a$ to be the $R$-minimal $x\in A$ such that $f(x,b)\in D$. If not, it follows that $\exists_{b\in B}\forall_{a\in A}f(a,b)\in C$, and in that case the assignment $a\mapsto f(a,b)$ injects $A$ into $C$ for such a $b$.

Now let $S$ well order $C$. If $\forall_{a\in A}\exists_{b\in B}f(a,b)\in C$, we get an injection $A\to C$ by letting $a\mapsto$ the $S$-minimal $c\in C$ for which there exists a $b\in B$ with $f(a,b)=c$. And if $\exists_{a\in A}\forall_{b\in B}f(a,b)\in D$, then for such an $a$ the prescription $b\mapsto f(a,b)$ defines an injection $B\to D$.

Hence $|A|\leq|C|\vee|B|\leq|D|$ in both situations. Reversing the roles of $C$ and $D$ in the $R$ wo $A$ case, and of $A$ and $B$ in the $S$ wo $C$ case, we find that, equally, $|A|\leq|D|\vee|B|\leq|C|$, $\Box$.

EDIT: the condition $C\cap D=\varnothing$ was never used in the proof, so it can be discarded.

Proposition: $(\forall_{X,Y}(|X|<|Y|\Rightarrow|X|^{2}<|Y|^{2}))\Rightarrow AC$

Proof: assuming the antecedent, we show that every set can be well ordered. (As is well known, the well ordering principle is equivalent to the AC.) Let $A$ be a set which we wish to well-order. We can assume $|A|\geq\aleph_{0}$ (else replace $A$ with $A\cup\mathbb{N}$; a well ordering for that set will induce one for $A$). Put $B:=A^{\mathbb{N}}$. Then $|A|\leq|B|$ and $|B|^{2}=|B|$. We now have to become slightly technical, and consider $C:=\Gamma(B)$ where $\Gamma$ is Hartogs' function; that is, $C$ is the set of all ordinals $\alpha$ that have an injection $\alpha\to B$. The facts that $\Gamma(B)$ is indeed a set, and that it is the smallest ordinal that does not allow an injection $\to B$, can be found in most text books on set theory.

Write $\kappa:=|B|$ and $\mu:=|C|$. Since both are $\geq\aleph_{0}$, one has $\kappa+\mu\leq\kappa.\mu$ (indeed, we find that $\kappa.\mu=(\kappa+1).(\mu+1)=\kappa.\mu+\kappa+\mu+1\geq\kappa+\mu$). Let us assume $\kappa+\mu=\kappa.\mu$. As C is an ordinal, the Lemmma applies, giving $\kappa\leq\mu\vee\mu\leq\kappa$. The latter option is impossible, as no injection $C\to B$ can exist. So $\kappa\leq\mu$, that is, an injection $B\to C$ exists, and as $C$ is well ordered, $B$ inherits a well ordering from $C$ via this injection. But $|A|\leq|B|$, so that $A$ inherits a well ordering from the one on $B$ via an injection $A\to B$.

Now assume $\kappa+\mu<\kappa.\mu$. By our hypothesis, this yields $(\kappa+\mu)^{2}<(\kappa.\mu)^{2}=\kappa^{2}.\mu^{2}=\kappa.\mu$. The latter equality follows from the fact that $|B|^{2}=|B|$, as we have already remarked, while $|C|^{2}=|C|$ since $C$ is an infinite ordinal. However, one has: $(\kappa+\mu)^{2}=\kappa^{2}+2\kappa.\mu+\mu^{2}=\kappa+\kappa.\mu+\mu$; again, $2|C|=|C|$ since $C$ is an infinite ordinal. Thus $(\kappa+\mu)^{2}=\kappa+\kappa.\mu+\mu=\kappa+\kappa.\mu+\mu+1=(\kappa+1)(\mu+1)=\kappa.\mu$, in contradiction with $(\kappa+\mu)^{2}<\kappa.\mu$, $\Box$.