If $X$ is an infinite set and $N$ is a countable set, then what is the cardinality of $X \times N$?

Question

If $X$ is countable, then the cartesian product is countable. However, what about general cases? The googling suggests that the answer is the cardinality of $X$. But why? Could anyone please provide me with the proof?

Answer 1

Assume the Axiom of Choice and let $N$ be a non-empty countable set.

Lemma. $|X\times N|=|X|$.

Proof. Indeed, put a well ordering on $X$. I will call an element $x\in X$ initial if it has no direct predecessor. Direct successors will be denoted by $x+n$ for natural $\mathbb{N}$. Let

$$I(x)=\{y\in X\ |\ y=x+n\text{ for some }n\in\mathbb{N}\}$$ $$J=\{x\in X\ |\ x\text{ is initial}\}$$

It is easy to see that

$$X=\bigcup_{x\in J}I(x)$$ $$I(x)\cap I(y)=\emptyset\text{ for }x, y\in J, x\neq y$$

Finally each $I(x)$ is order isomorphic to either $\mathbb{N}$ or some of its subset. Note that there is at most one $x\in J$ such that $I(x)$ is finite. Denote that element by $f$. In case it doesn't exist we assume $I(f)=\emptyset$.

So now we have

$$X\times N=\bigcup_{x\in J}I(x)\times N=\big(\bigcup_{x\neq f}I(x)\times N\big)\cup \big(I(f)\times N\big)$$

Now since $I(x)$ is infinite countable for $x\neq f$ we get that $I(x)\times N\simeq I(x)$ by the standard snake proof. Thus we have

$$X\times N\simeq\bigcup_{x\neq f}I(x)\cup \big(I(f)\times N\big)$$

Note that the set $I(f)\times N$ is at most infinite countable (and so it does not have to be equinumerous with $I(f)$). But it does contain a copy of $I(f)$ inside. So we can move that copy to the left side of the union and so for $Y=(I(f)\times N)\backslash (I(f)\times\{0\})$ we get

$$X\times N\simeq X\cup Y$$

where $Y$ is at most infinite countable. This finally leads to $X\times N\simeq X$ because you can always remove a sequence from an infinite set without changing its cardinality (which again I believe requires the Axiom of Choice). $\Box$

Side note: it is also true that $|X\times X|=|X|$. But can we replace $N$ with $X$ in that proof? Sort of. We calculate

$$X\times X=\bigcup_{x\in J}I(x)\times\bigcup_{x\in J}I(x)=\bigcup_{(x,y)\in J\times J}I(x)\times I(y)$$

Now $J\times J$ is the problematic set. Note however that for infinite $X$ we have that $J$ is stricly less then $X$ in the well order ordering. Meaning there is an injective order preserving function $J\to X$ but not vice versa. So by reducing the problem from $X$ to $J$ we can prove the result. And this is done by the transfinite induction. Although I haven't worked out the details yet.