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/11 10:52] nikolaj |
diagonal_construction [2016/01/13 10:28] nikolaj |
||
|---|---|---|---|
| Line 9: | Line 9: | ||
| 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 $ (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)$. 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$ | + | //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 |
| + | |||
| + | $(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).$ | ||
| + | |||
| + | 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$ | ||
| 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. | ||
