1
$\begingroup$

Are the number of images from $\mathbb{N}$ to {0, 1} countably infinite or uncountably infinite?


I was thinking of counting in base 2 to make a bijection between $\mathbb{N}$ and {0, 1}. So, a table like this one:

 Image  |  0  1  2  3  ...         <- Here is N
-------------------------------
  0     |  0  0  0  0  ...         <- And here is the image in {0,1}
  1     |  1  0  0  0  ...
  2     |  0  1  0  0  ...
  3     |  1  1  0  0  ...
  4     |  0  0  1  0  ...
...

So, right now, in the left column, I can identify every number of $\mathbb{N}$ with an image on the right. Which makes it countably infinite, by definition.

But a co-student, claimed that the prof said it was uncountably infinite. Any idea why?

$\endgroup$
5
  • 1
    $\begingroup$ What about the function from $\mathbb N$ to $\{0,1\}$ which assigns $0$ to every even and $1$ to every odd number? To which binary number would it correspond in your table? In fact, allmost all of these functions cannot be represented by binary numbers. There are indeed uncountably many of them. $\endgroup$
    – Frunobulax
    Aug 17, 2014 at 13:49
  • $\begingroup$ @Frunobulax: That makes a lot of sense. Is there a rule in general that says that n^(countably infinite) = (uncountably infinite), for n > 1 ? $\endgroup$ Aug 17, 2014 at 13:52
  • $\begingroup$ The images correspond one by one with subsets of $\mathbb N$ and the number of subsets of $\mathbb N$ is uncountable $\endgroup$
    – drhab
    Aug 17, 2014 at 13:54
  • 1
    $\begingroup$ @MartijnCourteaux: Yes, in fact $n^{\aleph_0}=2^{\aleph_0}$ for all $n\in\mathbb{N}$, i.e. the result is always the same. (FWIW, $2^{\aleph_0}$ is the cardinality of the continuum, i.e. of the real numbers.) $\endgroup$
    – Frunobulax
    Aug 17, 2014 at 13:54
  • 1
    $\begingroup$ I'll add: the reason your function isn't bijective is because all the sequences in the right-hand column have trailing zeros. For instance, the sequence 1 1 1 1 1 1 ... doesn't appear. (And, necessarily, there will always be a sequence not appearing on the right-hand column since the set of functions $\mathbb{N} \to \{0,1\}$ is uncountable.) $\endgroup$ Aug 17, 2014 at 19:31

3 Answers 3

1
$\begingroup$

Another attempt at clarifying: Imagine each sequence from $\mathbb N$ to $\{0,1\}$ to represent the binary decimal places of a number between $0$ and $1$. Then you have a surjection from $\{0,1\}^{\mathbb{N}}$ onto the real interval $[0,1]$ (which is uncountable). (Almost a bijection, actually, except for minor technical differences.)

$\endgroup$
6
  • $\begingroup$ "binary decimal"? $\endgroup$
    – TonyK
    Aug 17, 2014 at 14:03
  • $\begingroup$ @TonyK: How do you call "Nachkommastellen" in English? :) $\endgroup$
    – Frunobulax
    Aug 17, 2014 at 14:06
  • $\begingroup$ The digits behind the decimal separator. (simple.wikipedia.org/wiki/Decimal_separator) $\endgroup$ Aug 17, 2014 at 14:06
  • $\begingroup$ Seems we can't get rid of the word "decimal" here... :) $\endgroup$
    – Frunobulax
    Aug 17, 2014 at 14:15
  • 1
    $\begingroup$ @Frunobulax: I see your problem! In English, the "Komma" is called the "decimal point", which is inappropriate for numbers written in binary (as is "decimal separator"). I would just say "the binary digits". If forced at gunpoint to translate "binäre Nachkommastellen von x", I would have to say "binary digits of the fractional part of x". But your number is between $0$ and $1$, so you don't need to make this explicit. $\endgroup$
    – TonyK
    Aug 17, 2014 at 14:20
1
$\begingroup$

The table you made doesn't make a bijection between $\mathbb N$ and the set of mappings from $\mathbb N$ to $\{0,1\}$. Consider such a scheme $f:\mathbb N\to\{0,1\}$ such that $f(n)=1-f_n(n)$, where $f_n$ is your $n$-th scheme. You will find that $f$ is different from any existed scheme $f_n$, while $f$ is indeed a scheme. This contradicts the number of schemes is countable.

$\endgroup$
5
  • $\begingroup$ I don't see that. Inverting the scheme twice, gives the same scheme, right? $\endgroup$ Aug 17, 2014 at 13:59
  • $\begingroup$ @MartijnCourteaux Inverting twice? Where? $\endgroup$
    – Shuchang
    Aug 17, 2014 at 14:03
  • $\begingroup$ $f_2(n) = 1 - f_1(n) = 1 - (1 - f_0(n)) = f_0(n)$ $\endgroup$ Aug 17, 2014 at 14:05
  • $\begingroup$ @MartijnCourteaux No. $f_n$ is the scheme you established in your table. $\endgroup$
    – Shuchang
    Aug 17, 2014 at 14:06
  • $\begingroup$ Aoh, now I see. Yes, indeed another proof that I'm missing out schemes. Thanks you! $\endgroup$ Aug 17, 2014 at 14:23
0
$\begingroup$

You can use that if $A\subseteq \mathbb{N}$ then $f(a)=1$ if $a\in A$ and $f(b)=0$ if $b\notin A$ then $\mid \{0,1\}^\mathbb{N}\mid=\mid P(\mathbb{N})\mid$ by Cantor's theorem, $\mid \mathbb{N}\mid<\mid P(\mathbb{N})\mid$.

$\endgroup$
2
  • $\begingroup$ I'm not familiar with these vertical bars. Does it indicate the size of the set? The cardinality? $\endgroup$ Aug 17, 2014 at 14:22
  • $\begingroup$ Yes is the cardinality. $\endgroup$ Aug 17, 2014 at 14:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .