Una "marcha atrás" en diagonal argumento?

Question

Cantor de la diagonal argumento puede ser utilizado para mostrar que un conjunto $S$ es siempre menor que su poder establecer $\wp(S)$. La prueba de obras por mostrar que existe una función $f : S \rightarrow \wp(S)$ puede ser surjective por la construcción del conjunto explícito $D = \{ x \in S | x \notin f(s) \}$ a partir de una función de $f$ y demostrar que ningún elemento de $S$ mapas a $D$.

Esta prueba funciona porque todos bijections son surjections, así que si no surjection de $S$ $\wp(S)$existe, entonces no puede ser un bijection entre el$S$$\wp(S)$.

Mi pregunta es si es posible ejecutar un "reverse diagonalización" que funciona en lugar de mostrar que no hay inyección de$\wp(S)$$S$. Tengo curiosidad acerca de esto porque nunca he visto el Cantor del teorema demostrado de esta manera (o, más generalmente, cualquier diagonal argumento estructurado como este).

Es posible tomar un Cantor de la diagonal argumento y "reverse" para mostrar que no puede ser una inyección de$\wp(S)$$S$, en lugar de mostrar que no puede haber surjection de$S$$\wp(S)$?

Gracias!

Answer 1

Supongamos $f : \mathcal{P}(S) \to S$ fueron una inyección. Considere el siguiente recursivo de construcción:

• $s_0 = f(\emptyset)$
• $s_\alpha = f(\{s_\beta\}_{\beta < \alpha})$

Debido a $f$ es inyectiva, todos los $s_\alpha$ son distintos. Pero esto no puede ser de otra manera tenemos una inyección de $\mathrm{Ord} \to S$ donde $S$ es un conjunto.

EDIT: O, si queremos ser frugal y no mencionar las inyecciones de $\mathrm{Ord}$, podemos decir que el hecho de que el $s_\alpha$ son todos distintos contradice Hartog del Lexema.