# Differences

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

Both sides previous revision Previous revision | |||

diagonal_construction [2016/04/05 00:21] nikolaj |
diagonal_construction [2016/04/05 00:43] (current) nikolaj |
||
---|---|---|---|

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)$, which 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) =\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$ | ||