Solución:
Voy a reemplazar algunas definiciones por otras obviamente equivalentes. El beneficio será que las pruebas sean más fáciles de entender. Estoy escribiendo pruebas muy detalladas que normalmente no encontrarías en un libro de texto de matemáticas de nivel universitario.
Definición: Por $ n in mathbb {N} $ define $[n] = {k in mathbb {N} mid k Definición: los imagen de un mapa $ f: X a Y $ es el conjunto $ mathrm {im} (f) = {y en Y mid existe x en X ,. , f (x) = y PS Definición: Un conjunto $ X $ es infinito cuando por cada $ n in mathbb {N} $ y cada mapa $ f: [n] a X $ hay algunos $ x en X $ que no están en la imagen de $ f $. Lema 1: Un conjunto infinito $ X $ contiene un elemento. Prueba. Debido a que $ X $ es infinito, hay $ x en X $ que no está en la imagen del mapa único $[0] a X $. QED. Lema 2: Si $ X $ es infinito, entonces existe un mapa $ c $ tal que $ c (n, f) en X setminus mathrm {im} (f) $ por cada $ n en mathbb {N} $ y cada $ f: [n] a X $. Prueba. Por cada $ n in mathbb {N} $ y $ f: [n] to X $ el conjunto $ X setminus mathrm {im} (f) $ contiene un elemento porque $ X $ es infinito. Según el axioma de elección, existe un mapa de elección $ c $ tal que $ c (n, f) en X setminus mathrm {im} (f) $ para todos $ n $ y $ f $. QED. Aquí hay una explicación informal del mapa $ c $. Dado un conjunto infinito $ X $ y cualquier elemento $ x_0, ldots, x_ {n-1} en X $, podemos ver la tupla $ (x_0, ldots, x_n) $ como un mapa $ f: [n] a X $ donde $ f (k) = x_k $. Mediante un ligero abuso de notación podemos escribir $ c (n, f) $ como $ c (x_0, ldots, x_ {n-1}) $. Ahora vemos que $ c $ acepta un número finito de elementos de $ X $ y devuelve un elemento en $ X $ que es diferente de todos ellos. Proposición 1: Si $ X $ es infinito, entonces existe un mapa inyectivo $ i: mathbb {N} a X $. Prueba. Por el Lema 1 hay $ x en X $ y sea $ c $ el mapa del Lema 2. Defina $ i $ por recursividad: begin {align *} i (0) & = x \ i (n) & = c (i (0), ldots, i (n-1)) qquad qquad text {para $ n geq 1 $} end {align *} Claramente, $ i $ es inyectivo porque $ i ( n) $ se elige de manera que sea diferente de $ i (0), i (1), ldots, i (n-1) $. QED. Proposición 2: Si $ X $ es infinito, entonces está en biyección con algunos adecuado subconjunto $ Y subseteq X $. Prueba. Suponga que $ X $ es infinito. Buscamos un subconjunto adecuado $ Y subseteq X $ y una biyección $ f: X a Y $. Sea $ i $ el mapa de la Proposición 1. Defina $$ Y = X setminus {i (0) } $$ y defina $ b: X a Y $ por $$ b (x) = begin { cases} x & text {if $ x not in mathrm {im} (i) $} \ i (n + 1) & text {if $ x = i (n) $ para un (único) $ n in mathbb {N} $} end {cases} $$ en palabras, $ b $ lleva $ i (0) $ a $ i (1) $, $ i (1) $ a $ i (2 ) $, y así sucesivamente, y no mueve elementos que están fuera de la imagen de $ i $. Claramente, $ b $ es inyectivo porque $ i $ lo es. Es sobreyectiva porque el único elemento que no está en la imagen de $ b $ es $ i (0) $. QED. Proposición 3: Si $ X $ es un conjunto y $ b: X a Y $ una biyección de $ X $ a una adecuado subconjunto $ Y subseteq X $, entonces hay un mapa inyectivo $ j: mathbb {N} a X $. Prueba. si $ m = 0 $ entonces $ j (0) = x $ es diferente de $ j (n) = b (j (n-1)) $ porque $ b (j (n-1)) en Y $ y $ x no en Y $. para el paso de inducción, suponga que tenemos $ j (m) = j (n) $ para unos $ 0 QED. Teorema: Un conjunto es infinito si, y solo si, es equipotente con algún subconjunto adecuado. Prueba. A la inversa, suponga que tenemos una biyección $ b: X a Y $ para un subconjunto adecuado $ Y subseteq X $. Por la Proposición 3 hay un mapa inyectivo $ j: mathbb {N} a X $. Para ver que $ X $ es infinito, considere cualquier $ n in mathbb {N} $ y $ f: [n] a X $. Hay $ n + 1 $ elementos distintos $ j (0), j (1), ldots, j (n) en X $, por lo que al menos uno de ellos no está en $ mathrm {im} (f ) $ porque $ mathrm {im} (f) $ tiene como máximo $ n $ elementos. QED. Permítanme abordar rápidamente la primera parte de la prueba, $ Rightarrow $. No es necesario que lo haga por contradicción. Puede demostrar que si $ f colon X to A $ es una biyección, donde $ A $ es un subconjunto adecuado de $ X $, entonces hay una inyección de $ Bbb N $ en $ X $, y por lo tanto $ X $ es infinito. A tu segunda pregunta, quizás hubiera sido mejor decir “construcción recursiva”, ya que muchas personas solo ven la “inducción” como un método para probar enunciados y no para construir objetos matemáticos (que dirían que es una definición recursiva). El paso inductivo dice, supongamos que $ {a_1, ldots, a_k } $ es un conjunto definido, definamos $ {a_1, ldots, a_k, a_ {k + 1} } $. Cómo lo definimos? Simplemente elegimos un elemento de $ X setminus {a_1, ldots, a_k } $. ¿Por qué podemos hacerlo? Porque $ X $ es infinito y solo eliminamos un conjunto finito de $ X $. Podría argumentar, ¿qué es $ a_ {k + 1} $? ¿Qué elemento es? Bueno, no puede precisar ese elemento, porque tiene que hacer una elección arbitraria y debe apelar al axioma de la elección. Es decir, primero arreglamos alguna “operación de caja negra” que, dado un subconjunto no vacío de $ X $, nos devolverá un elemento de ese subconjunto. Y luego usamos este cuadro negro para elegir $ a_ {k + 1} $. Entonces nadie está construyendo una biyección entre un conjunto infinito y un singleton. Construimos un conjunto infinito, luego mostramos que este conjunto es numerable. Pero eso es bastante simple porque literalmente elegimos para cada $ n $ un elemento diferente, por lo que el mapa $ k mapsto a_k $ es necesariamente una inyección.
Debido a que $ Y $ es un subconjunto adecuado, existe $ x en X setminus Y $. Definimos un mapa $ j: mathbb {N} a X $ por recursividad: begin {align *} j (0) & = x \ j (n) & = b (j (n-1)) qquad qquad text {para $ n geq 1 $} end {align *} Para probar que $ j $ es inyectivo, basta con verificar que $ j (m) neq j (n) $ para todos los $ m
Si $ X $ es infinito, entonces aplicamos la Propuesta 2 para obtener un subconjunto adecuado $ Y subseteq X $ que sea equipotente con $ X $.Utiliza Nuestro Buscador