1, busque de forma sucesiva a través de ai 1, ai 2, ai 3 , . . . tratando de encontrar un elemento de B. Uno lo debe encontrar finalmente ya que B ...

1, busque de forma sucesiva a través de ai 1, ai 2, ai 3 , . . . tratando de encontrar un elemento de B. Uno lo debe encontrar finalmente ya que B es infinito y {g(1), g(2) , . . . , g(k ฀ 1)} es un conjunto finito. Cuando se encuentra un elemento de B, se define como g(k). Por (1) y (2) que acabamos de ver, la función g se define para cada entero positivo. Puesto que los elementos de a1, a2, a3 , . . . son todos distintos, g es inyectiva. Por otra parte, las búsquedas para elementos de B son sucesivas: Cada uno recoge al anterior donde lo dejó. Por tanto, se obtiene cada elemento de A durante alguna búsqueda. Pero todos los elementos de B se encuentran en algún lugar en la sucesión a1, a2, a3 , . . . y así cada elemento de B finalmente se encuentra y es la imagen de algunos enteros. Por tanto g es sobreyectiva. Estas observaciones muestran que g es una correspondencia inyectiva de Z a B. Por tanto B es infinito contable y por tanto contable. Una consecuencia inmediata del teorema 7.4.3 es el siguiente corolario. Corolario 7.4.4 Cualquier conjunto con un subconjunto no contable es no contable. Demostración: Considere la siguiente redacción equivalente del teorema 7.4.3: Para todos los conjuntos S y para todos los subconjuntos A de S, si S es contable, entonces A es contable. El contrapositivo de este enunciado es lógicamente equivalente a éste y establece: Para todos los conjuntos S y para todos los subconjuntos A de S, si A es no contable entonces S es no contable. Pero esta es una frase equivalente para el corolario. Por lo que se demuestra el corolario. El corolario 7.4.4 implica que el conjunto de todos los números reales es no contable ya que el subconjunto de los números entre 0 y 1 es no contable. De hecho, como muestra el ejemplo 7.4.5, ¡el conjunto de todos los números reales tiene la misma cardinalidad que el conjunto de todos los números reales entre 0 y 1! Este hecho se explora aún más en los ejercicios 13 y 14 del final de esta sección. Ejemplo 7.4.5 La cardinalidad del conjunto de todos los números reales Demuestre que el conjunto de todos los números reales tiene la misma cardinalidad que el conjunto de números reales entre 0 y 1. Solución Sea S el intervalo abierto de números entre 0 y 1: S {x R 0 x 1}. Imagine tomar a S y colocarlo en la circunferencia, como se muestra a continuación. Ya que S no incluye ni al punto final 0 ni al 1, el punto de la parte superior de la circunferencia se omite en el dibujo. 7 8 3 4 1 2 3 8 5 8 1 4 1 8 Nota Si g(k ฀ 1) ai , entonces g(k) también podría ser definida al aplicarle el principio del buen-orden al sistema n Z n i y ai B , para los números enteros. 7.4 Cardinalidad con aplicaciones a la computabilidad 437 Se define una función F: S R como sigue: Se dibuja una recta numérica y se coloca el intervalo, S, algo ampliado y colocado en una circunferencia, tangente a la recta de arriba del punto 0. Esto se muestra a continuación. Recta numérica 0–1–2–3 1 2 3 x L F(x) Para cada punto x en la circunferencia que representa a S, dibuje una línea recta L del punto de la parte superior de la circunferencia a x. Sea F(x) el punto de intersección de L y la recta numérica. (F(x) se llama la proyección de x en la recta numérica.) Es claro de la geometría de la situación que distintos puntos de la circunferencia van a puntos distintos en la recta numérica, por lo que F es uno a uno. Además, dado cualquier punto y en la recta numérica, se puede dibujar una recta de y al punto de la parte superior de la circunferencia. Esta recta debe intersectar la circunferencia en algún punto x y, por definición y F(x). Por tanto, F es sobreyectiva. Por tanto F es una correspondencia inyectiva de S a R y por tanto S y R tienen la misma cardinalidad. Usted sabe que cada entero positivo es un número real, por lo que al colocar el ejemplo 7.4.5 junto con el teorema de Cantor (teorema 7.4.2) se muestra que el infinito del conjunto de todos los números reales es “mayor” que el infinito del conjunto de todos los enteros positivos. En el ejercicio 35, deberá demostrar que cualquier conjunto y su conjunto potencia tienen cardinalidad diferente. Ya que hay una función inyectiva de cualquier conjunto con su conjunto potencia (la función que toma cada elemento a con el conjunto singleton {a}), esto implica que la cardinalidad de cualquier conjunto es “menor que” la cardinalidad de su conjunto potencia. Como resultado, puede crear una sucesión infinita de ¡infinitos más y más grandes! Por ejemplo, podría comenzar con Z, el conjunto de todos los enteros y tomar Z, (Z), ( (Z)), ( ( (Z))) y así sucesivamente. Aplicación: cardinalidad y computabilidad El conocimiento de la contabilidad y de la no-contabilidad de ciertos conjuntos pueden utilizarse para responder una pregunta de computabilidad. Comenzamos con la demostración que un cierto conjunto es contable. Ejemplo 7.4.6 Contabilidad del conjunto de programas de computadora en un lenguaje de computadora Demuestre que el conjunto de todos los programas de computadora en un lenguaje de programación determinado es contable. Solución Este resultado es consecuencia del hecho de que cualquier programa de computadora en cualquier lenguaje se puede considerar como una cadena finita de símbolos en el alfabeto (finito) del lenguaje. Dado cualquier lenguaje de programación, sea P es el conjunto de todos los programas de computadora en el lenguaje. P será finito o infinito. Si P es finito, entonces P es contable y hemos acabado. Si P es infinito, se establece un código binario para traducir, los símbolos del alfabeto de la lengua en cadenas de 0 y de 1. (Por ejemplo, podría utilizarse el Código Estadounidense Estándar para el Intercambio de Información de siete bits, conocido como ASCII (por sus siglas en inglés para American Standard Code for Information Interchange), o el Extended Binary-Coded Decimal Interchange Code de 8 bits, conocido como EBCDIC.) Para cada programa en P, utilice el código para traducir todos los símbolos en el programa en 0 y en 1. Ordene estas cadenas de longitud, colocando la más corta antes de 438 Capítulo 7 Funciones la más larga y ordenar todas las cadenas de una longitud dada considerando cada cadena como un número binario y escriba los números en orden ascendente. Se define una función F : Z P especificando que F(n) el enésimo programa en la lista para cada n Z . Por construcción, F es inyectiva y sobreyectiva, por lo que P es infinito contable y por tanto contable. Como un simple ejemplo, suponga que los siguientes números que se muestran son todos programas en P traducidos en cadenas de bits de longitud menor o igual a 5: 10111, 11, 0010, 1011, 01, 00100, 1010, 00010. Ordenados por longitud, longitud 2: 11, 01 longitud 4: 0010, 1011, 1010 longitud 5: 10111, 00100, 00010 Y ordenando cada longitud dada por el tamaño del número binario que representan se obtiene 01 F(1) 11 F(2) 0010 F(3) 1010 F(4) 1011 F(5) 00010 F(6) 00100 F(7) 10111 F(8) Observe que cuando sólo se ven como números, haciendo caso omiso de los ceros líde- res, 0010 00010. Esto muestra la necesidad de ordenar primero las cadenas por longitud antes de ordenarlas en orden numérico ascendente. El ejemplo final de esta sección muestra que cierto conjunto es no contable y, por tanto, que debe existir una función no-computable. Ejemplo 7.4.7 La cardinalidad de un conjunto de funciones y computabilidad a. Sea T el conjunto de todas las funciones de los enteros positivos para el conjunto {0, 1, 2, 3, 4, 5. 6, 7, 8, 9}. Demuestre, que T es no contable. b. Deduzca la consecuencia que hay funciones no-computables. En concreto, demuestre que en cualquier lenguaje de programación debe haber una función F de Z a {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} con la propiedad que no se puede escribir ningún programa de computadora que se pueda escribir en lenguaje que tome valores arbitrarios como entrada y de salida a los valores correspondientes de la función. Solución a. Sea S es el conjunto de todos los números reales entre 0 y 1. Como se