Consider the function $f : \mathbb N \to \mathcal P (\mathbb N)$ Given $f(n) = Ø$, What is the set D?

Question

Full Question:

Consider the function f : ℕ → ℘(ℕ) defined as f(n) = Ø. Trace through the formal proof of Cantor's theorem with this choice of f in mind. In the middle of the argument, the proof defines set D = { $ x \in S$ | $x \notin f(x)$} in terms of f. Given that f(n) = Ø, what is that set D? Provide your answer without using set-builder notation. Is it clear why f(n) ≠ D for any n ∈ ℕ?

This question is based of the proof of cantor's theorem.

I understood the theorem and applied the diagonalization used in cantor's theorem to this problem.

My working:

$n_1 \to$ {}, $n_2 \to$ {}, $n_3 \to$ {}, $n_4 \to$ {}, $n_5 \to$ {}, $n.._i \to$ {}

Therefore I concluded D = {Ø}, because every set was empty and I didn't have anything to "flip" when i used diagonalization.

The part I found tricky was how do you "flip" an empty set? I was wondering if someone can check this for me or tell me if i'm on the right track.

Answer 1

The usual formal definition of a set $D$ that witnesses that a function $f:S\rightarrow P(S)$ was not surjective is $$D=\{x\in S:x\not\in f(x)\}$$ You can imagine, in the case where $S=\mathbb N$, drawing a function $f:\mathbb N\rightarrow P(\mathbb N)$ in the following way: for each natural number $n$, draw an infinite row of boxes labelled as $1,2,3,\ldots$. Color a box in this row black if that element is in the set $f(n)$ and leave it white otherwise. This gives a visual representation of a function $f:\mathbb N\rightarrow P(\mathbb N)$: such functions are just ways to color a grid. The function you describe would be the coloring where every box is left white.

You're trying to show that there is some possible row of white/black boxes that does not appear as a row in the diagram you made before; Cantor's solution to this is to go down the diagonal of this - to the cells $(1,1)$ and $(2,2)$ and so on, and to create a new row whose colors are the opposite of those on the diagonal. This row can't be the first row because its first color is different, nor can it be the second, because the second color is wrong - and so on. Thus, it must be a new row that did not appear.

In the given situation, every square in the original grid was white, so the opposite of the diagonal is every square being black - hence would be the whole set. Thus $D=\mathbb N$ by this pictorial reasoning. Note that the empty set is not such a special choice - you still have the same grid, you just chose not to color it - so you still have something to "flip": a whole bunch of empty boxes!

In formal terms, you are trying to find those $x$ such that $x\not\in f(x)$. However, $f(x)=\emptyset$, so you really want to find those $x$ such that $x\not\in \emptyset$. Nothing is in the empty set, so this is just every $x$ in the domain, which is $\mathbb N$ in this case. Moreover, you should be really concerned if you try to construct $D$ and find out that it was in the image of $f$ - because the whole point of $D$ is that it's definitely not!

Answer 2

If $f(n)=\emptyset$ then $n\not \in f(n) = \emptyset$ ever. So the set of all $n \not \in f(n)$ is the set of all $n$ or $\mathbb N$.

$D = \mathbb N$.

As for why $\mathbb N \ne f(n) = \emptyset$ ... well, other than the obvious, ....

I think we aren't supposed to actually figure out what $D$ is.

If $f(n) = D$ for some $n$, then $D= \emptyset$ so that means there is no $n$ so that $n \not \in f(n)$ so that means all $n \in f(n)$ but all $f(n) = \emptyset$ so all $n \in \emptyset$ which means there are no $n$ at all and the natural numbers do not exist.

That's ... not the way the universe works.... so $f(n)\ne D$ for all $n$.

.... are you sure we should be doing this? I thought Cantor's argument had no specific $f$ in mind but was a proof that no function $\mathbb N \to \mathcal P(\mathbb N)$ is injective. Obviously $f(n) = \emptyset$ (or any constant function) isn't injective and I'm not sure why we are even bothering with this.

Shouldn't we cut to the chase and consider $f$ as potentially any function?

If $f(n) = D$ for some $D$ then if $n\in D$ then $n\not \in f(n) = D$ which is a contradiction. And if $n\not \in D$ then $n \not \in D=f(n)$ and $n \in D$. Also a contradiction.

But this is of course assuming that $D = \{n|n\not \in f(n)\}$ is definable by ZFC....