# Cartesian product of finite set and countable set is countable

I want to prove that the product of a finite set and a countable set is countable. Is it enough to prove that a finite set is countable and use Cantor's theorem to prove that Cartesian product of two countable sets is also countable?

• Yeah, sure it is – Hagen von Eitzen Jan 26 '17 at 15:39
• @eereenah I can;t be sure of course, buit I am guessing your instructor doesn't want you to rely on Cantor's theorem, but prove this more directly. Maybe you should ask your instructor about that. – Bram28 Jan 26 '17 at 15:39
• @Bram28, I asked my professor and he said that in our class we do consider Cantor's theorem to be rigorous proof. I was more concerned about the notion of countability being applied to finite sets. Thanks! – eliott Jan 26 '17 at 16:17
• @eereenah Ah, OK! Well, that proof is easy enough ... I'll add my Answer. – Bram28 Jan 26 '17 at 16:26

Let the finite set be $\{1,...,N\}$ and let the countable set be $\mathbb{N}$, then define $\phi(k,n) = k+(n-1)N$. This defines a bijection $\phi:\{1,...,N\} \times \mathbb{N} \to \mathbb{N}$.

OK, so your strategy is to use Cantor's proof together with the following Lemma:

Lemma: "Every finite set is countable"

OK, so how do you prove that Lemma?

First, let's get clear on what we mean by 'countable'. In general, a set $X$ is 'countable' when there is a function from $\mathbb{N}$ to $X$ that is onto (it does not have to be a bijection ... indeed, that would only make infinite sets possibly countable!)

OK, so suppose $X$ is a finite set. Then we can say that $X = \{ x_1,x_2,...x_k \}$ for some $k$

OK, so let's define a mapping $f$ from $\mathbb{N}$ to $X$:

$$f(n) = x_{(n \: mod \: k) + 1}$$

Since this mapping is onto, that means $X$ is countable. So, any finite set is countable.

• Thank you (I do not have enough reputation to upvote your answer yet). That's what I was looking for! – eliott Jan 26 '17 at 16:43
• @eereenah Glad I could help! – Bram28 Jan 26 '17 at 16:46

Some people define "countable" to mean countably infinite, but in my experience "countable" usually means that the set can be put in bijection with some subset of $\mathbb{N}$. That is to say, a countable set is either finite or countably infinite. With that definition, a finite set is countable, so Cantor's theorem gives you the result you want.