# Prove that set is uncountable

$$\{f \mid f : \mathbb{N} → \{0, 1\}\} - \{f\mid f : \{0, 1\} → \mathbb{N}\}$$ Where $$f$$ is a function. Prove that this difference is an uncountable set.

I am pretty stuck on how to start this problem. I understand that the set from $$0$$ to $$1$$ is uncountable while the set of natural numbers is countable, but I can't seem to start off the proof.

• Calling the sets $A$ and $B$, it seems that $B \cap A = \varnothing$. None of the elements of $A$ have domain $\{0,1\}$. Commented Dec 2, 2021 at 20:39
• I agree with @William. Since the sets are disjoint, the difference is $\{f \mid f : \Bbb{N} \to \{0, 1\}\}$, which is uncountable straightforwardly by Cantor (well, it has the usual bijection with the power set of $\Bbb{N}$). In general, if $A$ is uncountable and $B$ is countable, then $A - B$ is uncountable. Why? As always, we have $A \subseteq (A - B) \cup B$. If $A - B$ and $B$ are countable, then so is $(A - B) \cup B$, and hence $A$. This would be a contradiction. Commented Dec 2, 2021 at 20:48
• "I understand that the set from 0 to 1 is uncountable": that does not make sense Commented Dec 2, 2021 at 20:48
• @miracle173 I would guess they mean $[0,1]\subset\mathbb{R}$. Commented Dec 2, 2021 at 20:49
• These sets as disjoint as sets of functions. The domains of the functions in set A and set B intersect. But the functions are distinct. No element of the first set is an element of the second set and vice versa. Commented Dec 2, 2021 at 21:21

The set $$\{f\mid f:\Bbb N\to\{0,1\}\}$$ has cardinality $$2^{|\mathbb N|}=2^{\aleph_0}$$. To see this, notice that each element of $$\Bbb N$$ can be mapped to one of two elements, either $$0$$ or $$1$$.
The set $$\{f\mid f:\{0,1\}\to\Bbb N\}$$ has cardinality $$|\Bbb N|^2=\aleph_0$$. To see this, notice that each element of $$\{0,1\}$$ can be mapped to one of $$|\Bbb N|$$ elements, either $$0,1,2,3,\dots$$.
We start with $$2^{\aleph_0}$$ (uncountably many) elements and remove at most $$\aleph_0$$ (countably many) elements, so our set difference has at least $$2^{\aleph_0}-\aleph_0=2^{\aleph_0}$$ elements, i.e., it is uncountable.