Do we need choice to prove that $|\mathbb{N} \times A| = |A|$ for all infinite sets $A$?

Question

I can't think of any way to prove it without choice.

Answer 1

Yes. You need the axiom of choice. To see this note that we can prove the following (without the axiom of choice):

$$|A\times\Bbb N|=|A|\iff |A\times\{0,1\}|=|A|.$$

So it suffices to show that it is consistent that the latter fails. For this we can have many nice counterexamples. My favorites are $\kappa$-amorphous sets.

Definition. We say that $A$ is $\kappa$-amorphous, for an ordinal $\kappa$ if $|A|\nleq\kappa$, and for every $B\subseteq A$ either $|B|<\kappa$ or $|A\setminus B|<\kappa$.

Clearly if such set exists then $|A|<|A\times\{0,1\}|$ since the latter can be split into two sets neither of which is smaller than $\kappa$ in size. And such sets consistently exist.