Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
diagonal_construction [2016/01/13 10:28] nikolaj |
diagonal_construction [2016/04/05 00:43] nikolaj |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| ==== Discussion ==== | ==== 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. | 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$. Hence, for all $x,X,Y$, we have | + | //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),$ | $(X=Y) \Rightarrow \neg(x\in X\land x\notin Y),$ | ||
| Line 17: | Line 31: | ||
| $(x\in X\land x\notin Y) \Rightarrow \neg(X=Y).$ | $(x\in X\land x\notin Y) \Rightarrow \neg(X=Y).$ | ||
| - | Specifically, for any $x\in D_f$ and using $X=D_f$ and $Y=f(x)$, the left hand side reads $x\in D_f\land x\notin f(x)$, and so $\neg(f(x)=D_f)$, which means $\nexists x\ (f(x)=D_f)$. But since $D_f\subseteq C$, i.e. $D_f \in \mathcal P(C) =\text{codom}(f)$, we see that no such $f$ is a surjection, let alone a bijection. So the cardinality of any set is less than that of its power set. $\Box$ | + | This holds always. |
| + | Now, specifically, for any $x\in D_f$ and using $X=D_f$ and $Y=f(x)$, the left hand side reads $x\in D_f\land x\notin f(x)$ (which by definition of $D_f$ is the same as just $x\in D_f$) and the right hand side reads $\neg(f(x)=D_f)$. The same happens for $x\in C$ but not in $D_f and where we then switch $X$ and $Y$. This means $\nexists x\ (f(x)=D_f)$. | ||
| + | Since $D_f\subseteq C$, i.e. $D_f \in \mathcal P(C) =\text{codom}(f)$, we see that no such $f$ is a surjection, let alone a bijection. So the cardinality of any set is less than that of its power set. $\Box$ | ||
| If, in a similar spirit, $C,f$ are taken to be a sequence and an enumeration of sequences, then we see that there is at least once sequence which escapes enumeration. This further translates to the uncountability of real numbers. | If, in a similar spirit, $C,f$ are taken to be a sequence and an enumeration of sequences, then we see that there is at least once sequence which escapes enumeration. This further translates to the uncountability of real numbers. | ||
