Una pregunta sobre el juego de poder

Question

En las pruebas que he visto hasta ahora, para mostrar que el poder establecer $2^X$ de un conjunto $X$ no puede ser en bijection a $X$, la idea común es asumir que existe una surjection $f \colon X \to 2^X$ y, a continuación, consideremos el conjunto $$ B = \{ x \X \a mediados de x \noen f(x)\} $$

A continuación, el argumento se expresa diciendo que este juego es contradictorio, porque su pre-imagen (decir $y \in X$, es decir,$f(y) = B$) satisface tanto $y \in B$$y \notin B$.

En la Wikipedia, este método se dice que ser análoga a la diagonal de Cantor argumento que se usa para mostrar que el intervalo de $(0,1)$ de los números reales entre el $0$ $1$ es incontable. Aquí asumimos que existe una enumeración. Representación de un número $x \in (0,1)$ en su única expansión decimal, se obtiene una lista de \begin{align} x_1 &= 0.a_{11}a_{12}a_{13}... \\ x_2 &= 0.a_{21}a_{22}a_{23}... \\ x_2 &= 0.a_{31}a_{32}a_{33}... \\ x_2 &=0.a_{11}a_{12}a_{13}... \\ \vdots \end{align} donde $a_{ij} \in \{0,1,\dots,9\}$ por cada $i \in \mathbb{N}$$j \in \mathbb{N}$. A continuación, se construye un elemento de $(0,1)$ que no está en esta lista. Por ejemplo, uno puede tomar el número de $x = 0.b_{1}b_{2}b_{3}\dots$ donde \begin{equation} b_i = \begin{cases} 1 & \text{if } a_{ii} = 5 \\ 5 & \text{if } a_{ii} \ne 5 \end{casos} \end{equation}

Aquí, el número de $x$ que se genera está bien definido como un elemento de $(0,1)$, y no aparece en la lista de arriba, así que hemos llegado a una contradicción.

Por otro lado, para el argumento anterior sobre el poder establecido, asumiendo $f$ existe implica el objeto de $B$ no está bien definida como un elemento de $2^X$ ya que no es la imagen de una función de $X$ para el conjunto de $\{0,1\}$ (es multi-valor, es decir, la preimagen de $B$ evalúa a$0$$1$). En otras palabras, no puedo utilizar este objeto $B$ a derivar una contradicción. Lo que puede derivar es que, si $f$ existe $B$ no es un conjunto, y si $B$ es un conjunto para cada función $f \colon 2^X \to X$, entonces no hay tal $f$ puede ser surjective.

El último es lo que las pruebas dicen ser la única opción, en otras palabras, este objeto $B$ debe ser un conjunto definido por alguna otra razón - ¿qué me estoy perdiendo?

Answer 1

El Cantor del teorema es de hecho muy cerca de la diagonal argumento.

La idea es una generalización de la siguiente concepto. Escribimos la tabla: $$\begin{array}{|c|c|c|c|c} \hline \quad & f(x_1) & f(x_2) & f(x_3) & \ldots\\\hline x_1 & 0 & 1 & 0 & \ldots\\\hline x_2 & 1 & 1 & 0 & \ldots\\\hline x_3 & 0 & 0 & 1 & \ldots\\\hline \vdots \end{array}$$ Donde $(x,f(x))$ $0$ si $x\notin f(x)$ $1$ lo contrario. La diagonal argumento es recorrer a través de la diagonal, y considerar a aquellos que han $0$ no. Recoger este conjunto, y puede, de hecho, muestran que no es $f(x)$ cualquier $x$.

Esta $B$, como se denota, o más bien su función de indicador (si usted prefiere considerar $2^X$ en lugar de $\mathcal P(X)$ por una razón u otra) existe porque nosotros lo definimos. Explícitamente nos dio una descripción de sus miembros. Los pares ordenados de la forma $\langle x,i\rangle$ donde $i=0$ si $x\in f(x)$ $1$ lo contrario.

Uno de los primeros principios de la teoría de conjuntos es la comprensión. Es un principio importante, matemáticamente y filosóficamente. Si podemos describir una colección a continuación, queremos que existe. Y mientras que la restricción de la comprensión (todos los descriptible colecciones son conjuntos) es inconsistente, cuando la teoría de conjuntos axiomática fue formulado este fue limitado en el siguiente sentido:

Si $A$ es un conjunto, y $\varphi(x,u_1,\ldots,u_n)$ es una fórmula, a continuación, para cada elección de parámetros, $p_1,\ldots,p_n$ el conjunto $\{a\in A\mid\varphi(a,p_1,\ldots,p_n)\}$ existe.

Esto se conoce como el axioma esquema de especificación como se ha mencionado en los comentarios, y también como "restringida de la comprensión" y la "separación" a veces. ¿Por qué nos ayudan? Así, si asumimos que $X$ es un conjunto, entonces hemos definido un subconjunto (desde el parámetro $f$) y por lo tanto existe. Si prefiere la versión funcional, entonces considere el conjunto a $X\times\{0,1\}$ y aplicar el mismo argumento.

Por lo tanto, hemos demostrado que la $B$ existe, y no hay surjection a partir de un conjunto en su juego de poder.