Good day!
Found this tricky exercise in an elementary set theory course:
Given the set: $L = \mathcal{P}(\mathbb{N} \times \mathbb{N}) \setminus {}^\mathbb{N}\mathbb{N}$ (where ${}^\mathbb{N}\mathbb{N}$ donotes all the functions from $\mathbb{N}$ to $\mathbb{N}$)
show it is uncountable. (More precisely show that it's cardinality is greater than $\aleph_0$)
I started by finding a countable set (which is trivial to do) with in $L$. That means $|L|\geq \aleph_0$.
Now, suppose for the sake of contradiction that $|L| = \aleph_0$ and let $\varphi: \mathbb{N} \rightarrow L$ be a bijection.
This is where the harder part begins.
To reach a contradiction one must construct a relation $R$ over $\mathbb{N}$ which is either not serial or not functional (or both) and satisfies: $\forall n \in \mathbb{N} : R \neq \varphi(n)$.
I am not quite sure how to construct such a relation… For all $n \in \mathbb{N}$, $\varphi(n)$ is not serial or not functional.
So I can see how to construct a relation, for example $\mathbb{N} \times \{0\}$ that will differ from all the non-serial relations $\varphi(n)$ by at least one element (that is because it is serial).
However, I am not sure how to proceed from this point and build a relation that will differ from all the other non-functional relations and still be a member of $L$.
Any hints will be greatly appreciated.
Thanks to any readers! Have a lovely day!
Best Answer
Proof 1 (using cardinality)
Let $$\begin{array}{l|rcl} \psi : & \mathcal P(\mathbb N) & \longrightarrow & L \\ & k & \longmapsto & \{\langle 1, l\rangle \mid l \in k\} \end{array}$$ $\psi$ is injective. As $\vert \mathcal P(\mathbb N) \vert \le \vert L \vert \le \vert \mathcal P(\mathbb N \times \mathbb N) \vert = \mathfrak c \gt \aleph_0$, where $\mathfrak c$ stands for the cardinality of the continuum, we get the desired result.
Proof 2 (diagonal argument)
Suppose that $\varphi: \mathbb{N} \rightarrow L$ is a bijection. Let $l \in \mathcal P(\mathbb N \times \mathbb N)$ be defined as
$$l = \{\langle 1, m\rangle \mid m \notin p_2(\varphi(m))\}$$ where $p_2(u) = \{u_2 \mid \langle u_1, u_2 \rangle \in u\}$ for any $u \in \mathcal P(\mathbb N \times \mathbb N)$. We have $l \in L$ and get a contradiction if we raise the question $l \in \varphi[\mathbb N]$?