This is an old revision of the document!

## Diagonal construction

### Set

 context $f:C\to \mathcal {\mathcal P}(C)$ definiendum $x\in D_f$ inclusion $D_f \subseteq C$ postulate $x \notin f(x)$

### Discussion

We take an arbitrary set $C$ and argue about all the functions $f:C\to \mathcal {\mathcal P}(C)$ from $C$ to the powerset ${\mathcal P}(C)$. For any such $f$, we define $D_f$ as the subset of $C$ containing the elements $x\in C$ for which $x \notin f(x)$.

So for example we might consider

$C=\{0,1\}$

so that

${\mathcal P}(C)=\{\{\},\{0\},\{1\},\{0,1\}\}$

and if we were to consider the function $f$ that maps $0$ to $f(0)=\{0,1\}$ and $1$ to $f(1)=\{0\}$, then as $0\in \{0,1\}$ but $1\notin \{0\}$, we are left with $D_f=\{1\}$.

The point of $D_f \subseteq C$ defined as above is this: Given any set $C$, if one attempted to use its elements to index its subsets, i.e. via a function $f:C\to \mathcal P(C)$, then the “flipped diagonal subset” $D_f \in {\mathcal P}$ will always be found to be missed.

Proof of the above and also proof of Cantor's theorem: For all $x,X$, we eighter have $x\in X$ or $x\notin X$. If $X=Y$, then $x\in X$ has the same truth value as $x\in Y$. So for all $x,X,Y$, we have

$(X=Y) \Rightarrow \neg(x\in X\land x\notin Y),$

which is the same as

$(x\in X\land x\notin Y) \Rightarrow \neg(X=Y).$