Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
diagonal_construction [2016/01/13 10:28] nikolaj |
diagonal_construction [2016/04/05 00:21] 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)$, which 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. |