Por qué no es este un argumento válido para la "prueba" de que el Axioma de Contables Elección?

Question

Estoy teniendo un poco de problemas para identificar el problema con este argumento:

Deje $\{A_1, A_2, \ldots, A_n, \ldots\}$ ser una secuencia de conjuntos.

Deje $X:= \{n \in \mathbb{N} : $ no es un elemento del conjunto a $A_n$ asociado a $n \}$

(1) $A_1$ no está vacío. Por lo tanto, existe un $x_1 \in A_1$

(2) Dado un $A_n$ (y un $x_n \in A_n$), tenemos que $A_{n+1}$ no está vacía y, por lo tanto, existe un $x_{n+1} \in A_{n+1}$

Así que, por inducción, $X=\mathbb{N}$ y el axioma de contables elección es "probado".

¿Dónde está el error?

Answer 1

Como se señaló en los comentarios y respuestas, el problema es que a partir de la existencia de secuencias finitas $(x_1,\dots,x_n)\in A_1\times \dots\times A_n$, no podemos concluir la existencia de una secuencia infinita $(x_1,x_2,\dots)\in A_1\times A_2\times\dots$ sin adicional de la asunción (tales como el axioma de contables de elección).

Esto ciertamente parece extraño cuando uno encuentra por primera vez, así que tal vez el siguiente puede indicar por qué hay algo sutil:

A partir de la obra de Gödel, sabemos que no es recursiva coherente, completa el conjunto de axiomas de la ampliación de primer orden de la aritmética de Peano $\mathsf{PA}$. Lo que esto significa es que si $T$ es un conjunto de axiomas para la ampliación de la Aritmética de Peano, $T$ es consistente, y no es un programa de computadora que, para cada fórmula $\phi$, nos indica si $\phi$ es un axioma de la $T$ o no, entonces hay declaraciones de $\psi$ tal que $T$ no puede probar la $\psi$, y no puede probar la $\lnot\psi$.

(Si usted tiene problemas con el uso de la Aritmética de Peano de aquí, se puede reemplazar con mucho más débil de los sistemas, tales como la aritmética de Robinson $Q$; este no es un problema.)

Ok, considere ahora la siguiente construcción, que es quizás la mejor explicado como el etiquetado de los nodos del subárbol de $2^{<\mathbb N}$, el conjunto de secuencias finitas de $0$s y $1$s.

Empezar por la fijación de una lista de $\phi_0,\phi_1,\dots$ de todas las sentencias en el lenguaje de la aritmética. Poner $\mathsf{PA}$ en el nodo inferior $\emptyset$. Dada una secuencia finita $t\in 2^{<\mathbb N}$, asumimos que tenemos asignado un conjunto consistente de axiomas $T_t$ a el nodo $t$. Este nodo tiene dos sucesores, $t^\frown(0)$, e $t^\frown(1)$. Ir a través de la lista $\phi_0,\phi_1,\dots$, hasta llegar a un $\phi_n$ tal que $T_t$ no demuestran $\phi_n$, y no demostrar $\lnot\phi_n$. Asignar a $t^\frown(0)$ la teoría con los axiomas $T_t\cup\{\phi_n\}$, e $t^\frown(1)$ la teoría con los axiomas $T_t\cup\{\lnot\phi_n\}$.

Ahora, para cada una de las $n$, hay un programa de ordenador que muestra los axiomas de la $T_s$ todos los $s$ de la longitud de la $n$ o menos. Sin embargo, esto no significa que nos podemos encontrar en un programa de ordenador que muestra los axiomas a través de cualquiera de las ramas del árbol, porque cualquier rama nos da una teoría completa, y nos estaría en contradicción con Gödel es el resultado. Pensar acerca de este ejemplo, y nota que "inducción" no ayudaría a nosotros aquí, como podemos modificar esta construcción ligeramente de modo que las teorías al final no puede ser descrito en cualquier "aritméticamente" definibles por el de la moda. Esto es mucho más generoso noción de que "recursivo", y no es suficiente todavía.

El problema es la falta de homogeneidad: a pesar de que para cada una de las $n$ no es un programa de ordenador que identifica las teorías en el nivel $n$, no hay ningún método algorítmico para la identificación de las teorías que se producen "en el final".

Similares problemas se identifican en el área de "revertir las matemáticas", donde, por ejemplo, uno de los estudios de la (complicado) contenido informativo que una rama de un árbol se puede llevar, incluso si cada nodo, o, de hecho, el árbol entero, es descrito por un proceso fácil.

El punto de contables de la elección es que el mismo problema puede ser llevado hasta el extremo. En los ejemplos anteriores, hemos recursiva de la información en cada finito etapa, y no recursivo descripción al final. Contables de elección es necesario debido a que si se elimina el requisito de que la información en cada finito etapa es "recursivo", estamos, de hecho, pueden no tener "definible" el camino de la identificación de la información al final. Tanto que, de hecho, podríamos tener todo un universo de la teoría de conjuntos en donde la información no está presente. La manera de pensar acerca de esto es que la información puede estar tan complicada que incluso el hecho de tener disponibles todos los definability presentes en un modelo de $\mathsf{ZF}$ teoría de conjuntos puede no ser suficiente para identificarlo.

Answer 2

Inducciones a dar cada caso finito , pero no es el caso infinito. La inducción no es "continuo" en este aspecto.

Sí, $X=\Bbb N$ y a partir de esto se desprende el hecho de que cada finito subcolección admite una función de elección no implica que en realidad se puede elegir entre una infinidad de conjuntos a la vez.

Permítanme darles un ridículo analógica a su argumento, es ridículo, así que usted puede encontrar fácilmente el error allí, y tengo la esperanza de que le ayudará a ver su propio error así:

"Teorema". El conjunto de los números naturales es infinito.

La "prueba". Deje $X=\{n\in\mathbb N\mid\text{The set }\{k<n\mid k\in\Bbb N\}\text{ is finite}\}$; claramente $0\in X$, y si $n\in X$$n+1\in X$.

Por lo tanto, $X=\mathbb N$ $\Bbb N$ es finito como quería. $\square\!\!\!\small?$

Es bastante obvio lo que hice mal aquí, me mostró que cada segmento inicial es finito, pero no que toda la colección es finito.

Vamos a empujar esta un paso adelante, aquí es un mal argumento que sigue de manera similar, pero su prueba es un poco menos exagerada que la de arriba:

"Teorema". El juego de poder de $\Bbb N$ es contable.

La "prueba". Escribir $\Bbb N=\bigcup [k]$ donde $[k]=\{0,\ldots,k-1\}$. A continuación, para cada $k$, $\mathcal P([k])$ es finito. Por lo tanto, $\mathcal P(\Bbb N)=\bigcup\mathcal P([k])$ es una contables de la unión de conjuntos finitos, y por lo que es contable. $\square\!\!\!\small?$

Aquí también hemos demostrado que la inducción por que cada segmento inicial tiene un número finito de juego de poder, pero hemos cometido un error al concluir que el juego de poder de $\Bbb N$ es de esta unión, que si se mira de cerca, ni siquiera contiene $\Bbb N$ sí. El error aquí es que asumimos que la inducción lleva a través del límite de la etapa, es decir, que asumen erróneamente que $\sup\{2^n\mid n\in\mathbb N\}=2^{\sup\{n\mid n\in\mathbb N\}}$.

Answer 3

En el mejor de los que muestran que para todos los $N\in\mathbb N$, hay un mapa de $f_N\colon \{a,\ldots,N\}\to\bigcup_n A_n$$f_N(n)\in A_n$. Es decir, dada $f_N$ que se extienden de este a $f_{N+1}$ utilizando un único elemento $x_{n+1}\in A_{N+1}$.

Lo que realmente necesitamos, sin embargo, sería un $f_\omega$. Usted no puede salir de esta trampa, simplemente dejando $f_\omega(n):=f_n(n)$ porque no tiene todas las $f_n$ disponibles a la vez.

Answer 4

Es cierto que en cada una de las $n$th etapa, hay un elemento en $A_n$. El problema es, ¿cómo podemos elegir qué elemento de $A_n$ a llamar "$x_n$"? Contables opción nos permite salir de este problema, pero ya que estamos tratando de demostrar es que no podemos utilizar.

Su argumento inductivo realmente sólo muestra que, para cualquier $n$, podemos encontrar una $n$-tupla en $A_1\times\dots\times A_n.$ Lo hace no dejar que nos "proceder hasta el infinito", como usted está tratando de hacer. Es decir, lo que hemos demostrado aquí es el Teorema de finitud de la elección, mostrando que es bueno hacer arbitrarias decisiones a partir de un número finito no vacío de conjuntos.

Answer 5

Para evitar Elección, usted necesita tener una manera definitiva de la elección de un elemento de cada conjunto. Por ejemplo, si cada una de las $A_n$ es un par de zapatos, usted siempre puede optar por la izquierda.

Un típico caso es cuando cada una de las $A_n$ tiene un miembro distinguido como un único mínimo que usted puede elegir. Por ejemplo, la Categoría de Baire Teorema para una completa SEPARABLE espacio métrico puede ser demostrado mediante un truco como este.