Let $\mathbb{N}^{\{0,1\}} :=\{f: \mathbb{N} \to \{0,1\}\}$ is uncountable

I have never heard of the table approach, and all the proofs say uncountability of $\mathcal {P}(\mathbb{N})$ I have seen so far do not use the table approach. There was a hint how to do this without listing stuff in a table: Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ countable or uncountable?

Suppose that $f_1,…$ is a countable sequence of functions in $\{0,1\}^\mathbb{N}$, we define the function $F(n)=1−f_n(n)$. Check that $F:\mathbb{N}\to\{0,1\}$, and now show that it differs from $f_1,f_2,…$. If $\{0,1\}^\mathbb{N}$ was countable we could have enumerated it like that, but then $F$ would be somewhere in the list. This is impossible and therefore $\{0,1\}^\mathbb{N}$ is uncountable.

Couple of questions:

  1. Does $\{0,1\}^\mathbb{N} = \{f: \mathbb{N} \to \{0,1\}\}$, I maybe using conflicting notations

If that is the case, then the function $F$ makes sense

  1. What does it mean by "now show that it differs from $f_1,f_2,…$"?

Does it mean suppose $f_k(n) = F(n)$, then $F(n) = 1 - f_k(n) = 1 - F(n)$, so $F(n) = \dfrac{1}{2}$ so this is impossible.

  • 1
    $\begingroup$ By definition, $A^B$ is the set of functions from $B$ to $A$, for all sets $A$ and $B$. $\endgroup$ – Git Gud Jun 7 '16 at 21:37
  • $\begingroup$ @GitGud Oh that's a terrible convention, your pre-image should come before your image. Looking at $A^B$ makes me think of $f: A \to B$ $\endgroup$ – Shamisen Expert Jun 7 '16 at 21:39
  • 3
    $\begingroup$ @TheSilenceoftheCows I disagree, since for finite sets, you have $|A^B| = |A|^{|B|}$. It feels more akward to have $|A^B| = |B|^{|A|}$ $\endgroup$ – JMoravitz Jun 7 '16 at 21:39
  • 2
    $\begingroup$ @TheSilenceoftheCows "Before" is a relative term. You're reading from left to right. Anyway, the motivation behind the notation is this. Consider the number $2^3$. Now take a set with two members, say $\{0,1\}$ and another one with three elements, say $\{0,1,2\}$. You can prove that the set of functions from the latter to the form has exactly $8$ elements (which equals $2^3$). This is true for any choice of finite sets, hence the generalization of the notation. $\endgroup$ – Git Gud Jun 7 '16 at 21:42
  • 1
    $\begingroup$ @TheSilenceoftheCows You couldn't be more mistaken about the definition of $A^B.$ It's perfectly natural. $\endgroup$ – zhw. Jun 7 '16 at 21:48

Your Answer

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

Browse other questions tagged or ask your own question.