Bienvenido a el agujero de gusano.
Un conjunto que tiene un countably infinito subconjunto se denomina Dedekind Infinito. No es demostrable dentro de Zermelo-Fraenkel de la teoría de conjuntos (ZF) que todo conjunto infinito es Dedekind finito. Esto fue demostrado por Paul Cohen, quien expuso un modelo de ZF en el que hay un infinito, Dedekind-conjunto finito de números reales. Ver Asaf la respuesta a mi pregunta por las implicaciones de esta declaración en el análisis.
Usted no necesita ninguna forma de que el axioma de elección para demostrar que el infinito es igual a Dedekind infinito, en el sentido de que se pueden construir modelos de ZF en el que todos los conjuntos infinitos tienen countably infinitos subconjuntos pero no hay forma de que el axioma de elección se mantiene. Sin embargo, si tenemos alguna forma de que el axioma de elección, incluso de una forma débil, entonces podemos probar su declaración.
Me explico. El axioma de elección a los estados que, dado cualquier colección de $(A_i\;\colon\; i\in I)$ de conjuntos no vacíos, indexado por algunos de $I$, existe una función de elección de escoger, para cada una de las $i\in I$, un elemento $a_i\in A_i$. En otras palabras, tenemos una función de $f\colon I\to\bigcup_iA_i$ tal que $f(i)\in A_i$ por cada $i$.
Un conocido (pero no es fácil de probar) consecuencia del axioma de elección es la buena ordenación teorema: dado cualquier conjunto $A$, podemos ordenar los elementos de $A$ de tal manera que cualquier subconjunto no vacío de a $A$ tiene al menos un elemento en virtud de la orden. De hecho, el buen orden teorema es equivalente al axioma de elección, ya que, dado $(A_i\;\colon\;i\in I)$, podemos definir a la $f(i)$ a ser el menor elemento de a $A_i$, en este orden, lo que nos da una función de elección.
Con esta forma de el axioma de elección, uno puede demostrar su declaración como sigue: dada su conjunto $S$, en orden de acuerdo a la buena ordenación teorema. A continuación, vamos a $a_0$ ser el menor elemento de a $S$, vamos a $a_1$ ser el menor elemento de a $S\setminus\{a_0\}$ y así sucesivamente. Este proceso nunca va a terminar; de lo contrario, $S$ sería igual a $\{a_0,\dots,a_n\}$ algunos $n$ y por lo tanto sería finito.
Eso es todo bien y bueno, pero el buen orden es el teorema de no-obvio teorema de la teoría de conjuntos, y, ciertamente, no está implícito en su argumento. No deberíamos necesitar usarla para probar esta afirmación.
Afortunadamente, hay otra manera, y que en realidad implica una estricta forma más débil del axioma de elección. El axioma de contables de elección es el mismo que el axioma de elección, excepto que se requiere el conjunto de $I$ a ser contable. Hay modelos de la teoría de conjuntos en la que el axioma de elección falla, pero aún se mantiene siempre que el conjunto de índices es contable, así contables elección es estrictamente más débil que la selección completa.
He aquí cómo podemos demostrar su declaración utilizando sólo contables elección. Deje $S$ ser un conjunto infinito. A continuación, para cada una de las $n=0,1,2,\dots$, vamos a $S_n$ el conjunto de los subconjuntos de a $S$ del tamaño de la $2^n$.
Podemos mostrar que cada una de las $S_n$ no está vacía el uso de su argumento (tenga en cuenta que el axioma de elección no es necesaria para una colección finita de conjuntos, ya que se puede proceder por inducción): inductivamente recoger elementos $a_1,\dots,a_{2^n}$$S$; desde $S$ es infinito, este proceso no va a terminar y ya que estamos eligiendo sólo un número finito de elementos, no hay chunga conjunto-la teoría de los problemas.
Ahora, hay countably muchos $S_n$, por lo que el axioma de contables elección nos dice que hay una secuencia $A_0,A_1,A_2,\dots$ de los subconjuntos de a $S$ tal que $A_n$ tiene el tamaño de $2^n$ por cada $n$.
Ahora, para cada una de las $n$, vamos a $B_n$ el conjunto de elementos de $A_n$ que no están contenidas en $A_1\cup\dots\cup A_{n-1}$. Desde $A_n$ tiene el tamaño de $2^n$, e $A_1,\dots,A_{n-1}$ tienen en la mayoría de $1+2+4+\dots+2^{n-1}=2^n-1$ elementos distintos entre ellos, $B_n$ no puede ser vacío. Por el axioma de contables elección de nuevo, podemos elegir una secuencia $s_0,s_1,\dots$ con cada una de las $s_n\in B_n$. En particular, el $s_n$ son distintos. Hemos encontrado un countably infinito subconjunto de $S$.
