# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | |||

diagonal_construction [2016/04/05 00:43] nikolaj |
diagonal_construction [2019/08/25 13:48] (current) nikolaj fix $ |
||
---|---|---|---|

Line 32: | Line 32: | ||

This holds always. | 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)$. | + | 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$ | + | Since $D_f\subseteq C$, i.e. $D_f \in \mathcal P(C) = \mathrm{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. |