0
$\begingroup$

I have been doing a little reading on Cantor's diagonal argument being used to prove the uncountability of various sets. I recently tried my hand at proving that the set of partial functions $f: \mathbb{N} \rightarrow \left\{0,1 \right\}$ is uncountable. We assume this set is countable, list the functions as $\left\{ f_{1}, f_{2}, ... \right\}$, and construct some $\widetilde{f}$ such that $\widetilde{f}(k)=1-f_{k}(k)$ for all $k \in \mathbb{N}$. This is then a member of the set of partial functions considered. However, for any $k$ we have that $\widetilde{f}(k) \neq f_{k}(k)$ and $\widetilde{f} \neq f_{k}$. Thus, we have our function both in and not in the set of partial functions. Contradiction, so the set is not countable.

First off, does my argument look to be fine? It seems fast, but works! Furthermore, I was wondering how this might be extended, e.g., it seems that the set of partial functions $f: \mathbb{N} \rightarrow \left\{1,2,3 \right\}$ and $f: \mathbb{N} \rightarrow \left\{1,2,3,4 \right\}$ etc. are uncountable as well. What might this look like?

$\endgroup$
1
$\begingroup$

The collection of sequences $f:\mathbb{N}\to \{0,1\}$ is a subset of the collection of partial functions $f':\mathbb{N}\to\{0,1\}$ which is a subset of the collection of partial functions $f'':\mathbb{N}\to \{0,1,2\}$ which is a subset of the collection of partial functions $f''':\mathbb{N}\to \{0,1,2,3\}$, which is...etc.

Since you already know sequences of 0 or 1 is uncountable, it follows that all collections that contain it are also uncountable.

$\endgroup$
1
$\begingroup$

No, the argument doesn't work.

If $f_k(k)=\bot$, then $\bar f(k) = 1-f_k(k)$ is $\bot$ too, and therefore you have no way to conclude that $\bar f$ will differ from $f_k$.

Instead you could define $$ \bar{\bar f}(k) = \begin{cases} \bot & \text{if }f_k(k)\text{ is defined} \\ 0 & \text{otherwise} \end{cases} $$ which will guarantee that $\bar{\bar f}$ differs from every $f_k$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.