Una duda tonta sobre la imposibilidad de la suryección $A\to P(A)$ ?

Question

Estoy tratando de entender un detalle menor en esta prueba:

2.21. Teorema (Cantor). Para cada conjunto $A$ , $$ A <_c \mathcal{P}(A), $$ es decir, $A \leq_c \mathcal{P}(A)$ pero $A \neq_c \mathcal{P}(A)$ ; de hecho no existe ninguna suryección $\pi \colon A \twoheadrightarrow \mathcal{P}(A)$ .

Prueba. Que $A \leq_c \mathcal{P}(A)$ se deduce del hecho de que el fu $$ (x \mapsto \{x\}) $$ que se asocia a cada miembro $x$ de $A$ su singleton $\{x\}$ es una inyección. (Cuidado: el singleton $\{x\}$ es un conjunto con un único miembro $x$ y no es el mismo objeto que $x$ (que probablemente no sea un conjunto, para empezar).

Para completar la demostración, supondremos (hacia una contradicción) que existe $$ \pi \colon A \twoheadrightarrow \mathcal{P}(A), $$ a $$ B = \{ x \in A \mid x \notin \pi(x) \}, $$ de modo que para cada $x \in A$ , $$ x \in B \iff x \notin \pi(x). $$ Ahora $B$ es un subconjunto de $A$ y $\pi$ es una suryección, por lo que debe existir alguna $b \in A$ tal que $B = \pi(b)$ ; y estableciendo $x = b$ y $\pi(b) = B$ , $$ b \in B \iff b \notin B $$

Estoy confundido con la elección de $B$ aquí. Entiendo que podría hacer un suryecto de esta manera, después de todo estamos mapeando cada $a\in A$ a un elemento de $P(A)$ que no contenga $a$ es decir: Algo así como:

$$1\to\{2,3\}\\ 2\to \{1,3\}$$

Y esto arroja esa conclusión problemática. Entendí la prueba, pero no entiendo por qué esta elección de $B$ demuestra que no hay suryección. Es decir: ¿Por qué no podríamos construir $B$ en otra forma tal que la suryección sea realizable? ¿La mera existencia de esta construcción de $B$ ¿niega la sujeción? ¿Por qué?

Answer 1

La cuestión es que si $\pi$ es suryectiva, entonces cada subconjunto de $A$ está en su rango; en particular, el $B$ de la prueba.

Answer 2

La mejor forma de formular la prueba no es por contradicción, sino por contraposición: sea $\pi\colon A\to\mathcal P(A)$ sea cualquier definimos un conjunto $B_\pi\in\mathcal P(A)$ tal que $\pi(a)\neq B_\pi$ para todos $a\in A$ . En otras palabras, demostramos que $\pi$ no es suryectiva.

Ahora bien, lo importante es tener en cuenta que la definición de $B$ depende sur $\pi$ y funciona para cualquier $\pi$ . No es sólo para funciones suryectivas; y diferentes $\pi$ producirá diferentes $B$ 's.

---

Veamos dos ejemplos:

Ejemplo I:

$A=\{0,1,2\}$ y $\pi(a)=\{a\}$ .

Entonces definimos $B$ ser $\{a\in A\mid a\notin\pi(a)\}$ que a su vez se traduce con este $\pi$ ser $B=\{a\in A\mid a\notin\{a\}\}$ . Por supuesto, este $B$ tiene que estar vacío. Pero he aquí, $\pi(0),\pi(1)$ y $\pi(2)$ son todos no vacíos. Así que $B$ no está en el rango de $\pi$ .

Ejemplo II:

$A=\Bbb N$ y $\pi(n)=\{k\mid\ n^2\mid k\}$ a saber $\pi(n)$ es el conjunto de todos aquellos $k$ tal que $n^2$ divide $k$ (en este contexto, cualquier número, incluido $0$ -se divide).

¿Qué significa la definición de $B$ nos da ahora? Es el conjunto $\{n\mid\ n^2\nmid n\}$ que es exactamente $\Bbb N\setminus\{0,1\}$ . Pero ahora nos preguntamos si hay un número $n$ tal que $n^2$ divide todos los números naturales excepto $0$ y $1$ ? Puesto que cada número divide $0$ la respuesta es fácilmente negativa; pero también argumentando a través de números primos si lo prefieres: $n^2\nmid 2$ para cualquier número natural excepto $1$ pero como $1^2\mid 1$ y $1\notin B$ es imposible que $B=\pi(1)$ Así que $B$ no es $\pi(n)$ para cualquier $n$ .

---

TL;DR

Recapitulando, $B$ se define de $\pi$ para concluir que $B$ no es a imagen y semejanza de $\pi$ . Esta definición depende de $\pi$ pero funciona para cada $\pi\colon A\to\mathcal P(A)$ .

Answer 3

La construcción de $B$ se produce después de la construcción de la suryección. Es decir, mientras exista una función de $A$ a $\mathcal{P}(A)$ podemos definir un conjunto de este tipo $B$ . No se puede "construir $B$ de otra manera" porque independientemente de qué otro conjunto construyas, $B$ seguirá existiendo si tiene una función, y por lo tanto $B$ nos da la contradicción deseada.

Answer 4

Se podría pensar en el teorema de Cantor como un "corolario" de lo que está realmente demostrado.

Proposición. Para cada conjunto $ X $ y para cada $ f:X\to \mathscr{P}\left(X\right) $ existe $ Y\in\mathscr{P}\left(X\right) $ tal que $ Y\notin \operatorname{ran}\left(f\right) $ .

Prueba. Sea $ X $ sea un conjunto arbitrario. Sea $ f:X\to\mathscr{P}\left(X\right) $ sea arbitraria. Defina $ Y:=\left\{z\in X:z\notin f\left(z\right)\right\} $ . Por contradicción, supongamos $ Y\in\operatorname{ran}\left(f\right) $ . Por lo tanto, existe $ x\in X $ tal que $ f\left(x\right)=Y $ .

(I) Supongamos $ x\in Y $ . Por lo tanto $ x\in X $ y $ x\notin f\left(x\right) $ . Porque $ f\left(x\right)=Y $ , $ x\notin Y $ ---Una contradicción.

(II) Supongamos $ x\notin Y $ . Por lo tanto $ x\notin X $ o $ x\in f\left(x\right) $ . Porque $ x\in X $ , $ x\in f\left(x\right) $ . Porque $ f\left(x\right)=Y $ , $ x\in Y $ ---Una contradicción.

Como resultado, $ Y\notin\operatorname{ran}\left(f\right) $ .

---

EDIT: Para ampliar la información:

Recall

• Una función $f:A\to B$ es suryectiva si para cada $b\in B$ existe $a\in A$ tal que $f(a)=b$ .
• El alcance de una función $f:A\to B$ es $\mathrm{ran}(f):=\{b\in B:(\exists a)[a\in A\,\wedge\, f(a)=b]\}$ .

Corolario. Para cada conjunto $X$ no existe una suryección $f:X\twoheadrightarrow \mathscr{P}(X)$ .

Prueba. Sea $X$ sea un conjunto arbitrario. Por contradicción, supongamos que existe una suryección $f:X\twoheadrightarrow \mathscr{P}(X)$ . Porque $f$ es una función de $X$ a $\mathscr{P}(X)$ existe $Y\in\mathscr{P}(X)$ tal que $Y\notin \mathrm{ran}(f)$ . Porque $f$ es suryectiva y $Y\in \mathscr{P}(X)$ existe $x\in X$ tal que $f(x)=Y$ . Por lo tanto $Y\in\mathrm{ran}(f)$ ---Una contradicción. Como resultado, no existe una suryección $f:X\twoheadrightarrow \mathscr{P}(X)$ .