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

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?

## marked as duplicate by Asaf Karagila♦ cardinals StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 2 at 15:19

• Have you learned about the axiom of choice and the well-ordering theorem yet? If not, the proof will be too complicated to explain. It's a lot harder that proving that the product of two countable sets is countable. – bof May 2 at 11:07
• There is one exception on this. Also the empty set is countable and $X\times\varnothing=\varnothing$. – drhab May 2 at 11:09
• |X| <= |X|×|Z| <= |X|×|X| = |X| – William Elliot May 2 at 12:47
• @WilliamElliot The claim $|X|\times |X|=|X|$ is far more difficult to prove than $|X|\times |N|=|X|$ for countable $N$. – freakish May 2 at 14:43
• Of course, this follows easily from $|X\times X|=|X|$, and that can be found in many other threads on the site. – Asaf Karagila May 2 at 15:25

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.