3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yeah, sure it is $\endgroup$ – Hagen von Eitzen Jan 26 '17 at 15:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Bram28 Jan 26 '17 at 15:39
  • $\begingroup$ @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! $\endgroup$ – eliott Jan 26 '17 at 16:17
  • $\begingroup$ @eereenah Ah, OK! Well, that proof is easy enough ... I'll add my Answer. $\endgroup$ – Bram28 Jan 26 '17 at 16:26
2
$\begingroup$

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} $.

$\endgroup$
1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.