0
$\begingroup$

I'm stuck on a theory/set proof question:

$S$ is the set of all total functions $f : \{0, 1\} \to \mathbb{N}$ (natural numbers), prove that S is countable.

I have found a sample solution already but I do not understand what is going on.

Quoting from here:

To show this, we define a mapping $g$ from $S$ to $N × N$ and show the mapping is a bijection.

  1. Why must I prove bijection when the definition of countable (according to wikipedia) states "A set $S$ is called countable if there exists an injective function $f$ from $S$ to the natural numbers"?

  2. Also why a bijection/injection from $S$ to $\mathbb{N} \times \mathbb{N}$ and not just $S$ to $\mathbb{N}$?

$\endgroup$
  • 1
    $\begingroup$ What have you tried? What ways do you know to show that a set is countable? This is a paste of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. $\endgroup$ – D.W. Mar 19 '14 at 10:24
  • $\begingroup$ I will rephrase my question. I am not after a solution. More an explanation of a sample solution. I will ask more specific questions. $\endgroup$ – user15860 Mar 19 '14 at 10:43
  • $\begingroup$ This is a math question and so more suitable for math.se. $\endgroup$ – Yuval Filmus Mar 19 '14 at 13:44
  • $\begingroup$ injection from $S$ to $\mathbb N$ seems sufficient to me. Possibly your instructor considers that the part $\mathbb N\times\mathbb{N}\rightarrow \mathbb{N}$ is already known, or possibly he was only giving a hint, to be completed on your own. But injection is certainly enough. $\endgroup$ – babou Mar 19 '14 at 17:38
1
$\begingroup$

ad a) showing that $g$ is injective should suffice.

ad b) because it's easier. or put differently: how would you define an injective mapping $h: S \rightarrow \mathbb{N}$ ? it is feasible (eg. $f \rightarrow 2^{f(0)}\,*\,3^{f(1)}$) but complicates matters unnecessarily ( to prove injectivity you'd have to exploit additional information eg. the unique prime factor decomposition of natural numbers ).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You don't need to use prime factor decompositions; cf. Cantor's scheme. $\endgroup$ – Raphael Mar 19 '14 at 15:28
  • $\begingroup$ @Raphael Yes, that claim was too strong, thank you for pointing out the mistake. $\endgroup$ – collapsar Mar 19 '14 at 15:39