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

Improve this question
$\endgroup$
4
  • 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, 2014 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, 2014 at 10:43
  • $\begingroup$ This is a math question and so more suitable for math.se. $\endgroup$
    – Yuval Filmus
    Mar 19, 2014 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, 2014 at 17:38

1 Answer 1

Reset to default
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 ).

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