Epistemowikia Revista «Hiperenciclopédica» de Divulgación del Saber Segunda Época, Año VII Vol. 6, Núm. 4: de octubre a diciembre de 2012 (en curso)	Epistemowikia es parte de CALA → ALA | Communitas | Evolvere Editio | Epistemowikia | Exercitatio | Fictor | Flor

Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

De Epistemowikia

Preliminares. Conjuntos finitos

Dado un conjunto A, el hecho de ser a un elemento de A se nota a∊A, y se lee «a pertenece al conjunto A», o bien, «a es elemento de A». Podemos definir un conjunto de dos formas: por extensión, enumerando todos sus elementos, y por comprensión, definiendo todos sus elementos mediante las propiedades que los caracterizan. Si un conjunto es finito, lo podemos definir fácilmente enumerando todos sus elementos, pero si es infinito es imposible hacer ésto. En este último caso, se recurre a la definición por comprensión, la cuál podemos hacerla de dos maneras, lo más fácil sería indicar el esquema que siguen esos elementos (por ejemplo, es fácil darse cuenta que A = {2, 4, 6, 8, 10, 12, ...} es el conjunto de los números pares), no obstante el problema surge cuando el que lo lee no se da cuenta de la relación. Es mejor escribir la propiedad que los caracteriza, así, A = {x : x es natural y par}, o bien, A = {x ∊ ℕ : ∃ y∊ℕ tal que x=2y}, o bien, A = {(x∊ℕ) (∃y∊ℕ) (x=2y)}.

El contenido de los conjuntos se representa entre llaves {}, y suelen notarse con letras mayúsculas, A, B, C, ..., aunque esto no es necesario. Al número de elementos de un conjunto finito A lo llamamos cardinal de A y lo notaremos |A| (también podemos encontrarnos Card(A) ó #(A)).

La representación gráfica de conjuntos se realiza mediante líneas cerradas denominadas DIAGRAMAS DE VENN.

Inclusión e igualdad

Decir que dos conjuntos A y B son iguales (A=B) equivale a afirmar que contienen los mismos elementos. Formalmente, A=B ⇔∀x, x∊A ⇔x∊B. El orden de los elementos en un conjunto no importa; {1, 2, 3} = {3, 1, 2} aún más, la repetición de uno o más elementos no hace que los conjuntos sean distintos, {1, 2, 3} = {1, 2, 1, 3, 2}. Se denomina conjunto unitario al formado por un sólo elemento, por ejemplo {7}. También se considera el conjunto que no posee ningún elemento, el conjunto vacío y se nota ∅; este conjunto suele definirse como aquél cuyos elementos satisfacen una contradicción, por ejemplo, ∅ = {x : x≠x}.

Decimos que A es subconjunto de B, y notamos, A⊆B, si y sólo si, todo elemento de A es elemento de B. Formalmente, A⊆B ≡ (x∊A → x∊B). Leemos la relación A⊆B, «A está incluido en B»; si A⊆B pero A≠B, o sea, que al menos un elemento de B no es elemento de A, decimos que A es subconjunto estricto o propio de B, y notamos A⊂B («A está incluido estrictamente, o propiamente, en B»). Es evidente que, de A⊂B se sigue A⊆B, pero el recíproco no es cierto, por ejemplo, sea A = {Juan}, y B = {máximos acertantes en la Lotería}, y supongamos que se ha celebrado el sorteo y que Juan ∊ B; mientras que no finalice el recuento, sólo podemos asegurar que A⊆B, pues no sabemos si Juan es el único acertante, luego no podemos decir que A⊂B. No usaremos la notación ⊊, ya que significa lo mismo que ⊂.

Observación.- Sean A = {x: x∊ℕ ∧ x ≤ 10} y B = {1,3,5,7}. Claramente, B ⊂ A, de donde A⊄B. Estos símbolos también suelen escribirse al revés (en realidad se trata de relaciones de orden y de sus inversas), A ⊃ B (A incluye a B). ¡Ojo! con lo anterior: B ⊂ A no es equivalente a A⊄B, pues, B ⊂ A implica A⊄B, pero el recíproco no es cierto, por ejemplo, A = {1,2,3} ⊄ B = {4,5,6} y tampoco, B⊄A.

Las relaciones de inclusión, representadas por los símbolos ⊆ y ⊂, deben entenderse como totalmente distintas de la relación de pertenencia ∊. Por ejemplo, {2}⊆{2,3}, y también {2}⊂{2,3}, pero no es cierto {2}∊{2,3}, ni {2}∊{{2,3}}, ni {2}⊆{{2,3}}, aunque sí lo son las afirmaciones, 2∊{2,3}, {2}∊{{2},{3}} y {{2}}⊂{{2},{3}}. El conjunto vacío es subconjunto de cualquier conjunto A, pero en general no es elemento de A. Asimismo, es fácil comprender que x∊A ↔ {x}⊆A es tautología.

Podemos ahora redefinir la igualdad de dos conjuntos A y B: A = B :≡ (A ⊆ B) ∧ (B ⊆ A). Así, demostrar la igualdad de dos conjuntos, es equivalente a demostrar la doble inclusión.

Propiedades de la Inclusión

►Propiedad Reflexiva: todo conjunto A es subconjunto de sí mismo. Formalmente, ∀A, A⊂A.

►Propiedad Antisimétrica: Dados dos conjuntos cualesquiera A y B, si el primero está incluido en el segundo y también el segundo está incluido en el primero, entonces es que los dos conjuntos son iguales. Está es la propiedad en la que se basa la redefinición de igualdad de conjuntos. Formalmente, ∀A,B: A⊂B ∧ B⊂A ⇒ A=B.

►Propiedad Transitiva: para cualquiera de los conjuntos A, B y C, si todos los elementos de A están en B (A⊂B) y además todos los elementos de B están en C (B⊂C) entonces todos los elementos de A están en C y por tanto A⊂C. Formalmente, ∀A,B,C: A⊂B ∧ B⊂C ⇒ A⊂C.

Conjunto potencia

Se conoce por conjunto potencia de A (o conjunto de las partes de A), al conjunto de todos los subconjuntos de A. Lo notamos 2^A.

Teorema (cardinal del conjunto potencia).- Si |A| = n, entonces |2^A| = 2ⁿ
Dem.: En efecto, razonemos por inducción sobre n; para n=0, el único conjunto es ∅, cuyo único subconjunto es ∅, de donde, 2^∅ = {∅}, que tiene 2^|∅| = 2⁰ = 1 elementos. Supongamos que para todo conjunto con n=k elementos, el conjunto de sus partes tiene 2^k elementos. Consideremos un conjunto A con n=k+1 elementos; quitémosle uno, llamémoslo x, el conjunto restante, A\{x} tiene k elementos y su conjunto de partes 2^k. Estos 2^k elementos son todos los subconjuntos de A que no contienen a x. El número de subconjuntos de A que contienen a x es fácil hallarlo, son todos aquellos subconjuntos de A que no contienen a x, introduciendo x en ellos, o sea, también 2^k. Por tanto, PA tiene 2^k + 2^k = 2⋅ 2^k = 2^k+1 elementos. ❏

El álgebra de Boole de los subconjuntos

Se nota A∩B, y se lee «A intersección B» al conjunto A∩B = {x : x∊A ∧ x∊B}. Decir que A y B son disjuntos equivale a decir que A∩B = ∅. Se nota A∪B, y se lee «A unión B», al conjunto A∪B = {x: x∊A ∨ x∊B}.

De la definición de intersección de conjuntos se deducen las siguientes consecuencias: ∀A,B:

►(A∩B)⊂A ∧ (A∩B)⊂B

►A⊂B⇔A∩B=A

►(A∩B)⊂(A∪B)

De la definición de unión de conjuntos se deducen también las siguientes consecuencias: ∀A,B:

►A⊂(A∪B), B⊂(A∪B)

►A⊂B⇔(A∪B)=B

El conjunto A−B = {x: x∊A ∧ x∉B}, se denomina conjunto diferencia «A menos B». También se nota por A\B. Observemos que no es necesario que B ⊆ A. Pero si esto ocurre, si B∊2^A, entonces al conjunto diferencia A−B también se le conoce como complementario de B en A, y se nota ∁_AB. En este caso, al conjunto A se le denomina conjunto universal. Suele notarse por U a un conjunto universal indefinido, y a los subconjuntos de U, elementos de 2^U, por las letras normales, A, B, C, ..., mayúsculas o minúsculas. Dados A,B∊2^U, se satisface: A−B = ∁_A(A∩B) = A ∩ ∁_UB. Si tenemos claro cuál es U, podríamos utilizar otra notación para el complementario de A, que no incluyese a U.

Teorema (propiedades de la unión e intersección).- Sean A y B dos subconjuntos. Se satisfacen las propiedades siguientes:

Se conoce como diferencia simétrica de A y B, al conjunto A∆B = A\B ∪ B\A, esto es, A∆B = {x: x∊A ∧ x∉B} ∪ {x: x∊B ∧ x∉A}.

Es fácil ver que A∆B = (A∪B)\(A∩B) = (A∪B)∩(∁_UA ∪ ∁_UB). Además, la diferencia simétrica satisface las propiedades conmutativa, asociativa, elemento neutro (A ∆ ∅ = A), todo conjunto es su propio simétrico (A ∆ A = ∅) y la distributiva respecto de la intersección (A∩(B ∆ C) = (A∩B) ∆ (A∩C)).

Sea el conjunto 2^U de un conjunto universal U; en él están definidas las operaciones (ver, más adelante, el apartado "estructuras algebraicas") intersección, unión y complementación. Diremos que 2^U con estas tres operaciones y verificando las propiedades (1) ... (9) posee estructura de álgebra de Boole. Este hecho lo notamos diciendo que la cuaterna (2^U, ∩, ∪, ∁_U) es un álgebra de Boole.

Partición

Se denomina partición de un conjunto A, a todo conjunto de subconjuntos de A tales que, siendo disjuntos dos a dos, su unión es todo A. Esto es, {A₀, A₁, ..., A_n-1} es partición de A, si y sólo si:

1. ∀ i∊ℤ_n, A_i⊆A
2. ∀ i,j∊ℤ_n, si i<j entonces A_i ∩ A_j = ∅
3. A₀ ∪ A₁ ∪ ... ∪ A_n-1 = A

Si no se satisface la segunda condición, diremos que {A₀, A₁, ..., A_n-1} es un recubrimiento de A.

Dadas dos particiones, P₁ y P₂ de un conjunto A, diremos que P₁ es una partición más fina que P₂ (o que P₁ es un refinamiento de P₂) si cada conjunto de P₁ es un subconjunto de algún conjunto de P₂.

Producto cartesiano

Se llama producto cartesiano de A por B, y se nota AxB, al conjunto de pares ordenados: AxB = {(a,b) : a∊A ∧ b∊B}.

Conjuntos equipotentes

Conjuntos infinitos

David Hilbert relata la historia de un hotel con infinitas habitaciones, que según Martin Gardner populariza «se extienden hasta un espacio de dimensión superior a través de un agujero negro», numeradas de 1 en adelante; sean H = {h_n}_n∊ℕ. Un buen día, y aunque todo estaba ocupado, se pudo dar cabida a un nuevo huésped, simplemente desplazando a los inquilinos de cada habitación a la siguiente en número; en otra ocasión, pudo hacerlo con cinco nuevos huéspedes, sólo tuvo que desplazar a los ocupantes de la habitación n a la n+5 (para cualquier número de habitación n). Algo más formalmente, esto corresponde a definir la aplicación f: H → H, f(h_i) = h_i+n, con lo cuál, las 5 primeras habitaciones quedan libres, pues el huésped de la habitación uno, pasa a alojarse en la habitación 5+1, etc. Otro día se generó un problema, aparentemente mucho más complicado, llegaron infinitos nuevos huéspedes; pero también pudieron alojarse, ¿cómo?

Sencillo, desplazando, para toda habitación n, a sus ocupantes, a la habitación de número doble que la original; de este modo, quedan libres todas las habitaciones impares, que son infinitas, y se pueden alojar en ellas el número infinito de nuevos huéspedes. La aplicación, sería f*: H → H, f(h_i) = h_2i.

Observemos que f y f* son aplicaciones inyectivas, no sobreyectivas.

Para conjuntos finitos, son ciertas las siguientes afirmaciones:

Ninguna es cierta para conjuntos infinitos. Algo que caracteriza a cualquier conjunto infinito es la existencia de una biyección entre él y algún subconjunto propio suyo (caracterización biyectiva propia, o definición de conjunto infinito según Dedekind). Por ejemplo, ℕ es infinito, pues g: ℕ → ℕ_cuad, g(n) = n², es una biyección. (Por cierto, ya en 1638, Galileo Galilei refiere explícitamente esta correspondencia entre los números naturales y sus cuadrados. Aún más, parece que los estoicos (quizás Crisipo, s. III, a. C.) conjeturaban la existencia de tales correspondencias para cualquier conjunto infinito.)

Pues bien, en particular, g es inyectiva, pero, ℕ⊈ℕ_cuad. La aplicación f: H → H, f(h_i) = h_i+n, es inyectiva y no sobreyectiva, pero H ⊄ H. Y finalmente, g es biyectiva, pero ℕ ≠ ℕ_cuad.
Para conjuntos infinitos, sí son ciertas las siguientes afirmaciones:

Vemos las posibles diferentes infinidades que se pueden definir segun los autores[1]:
Diferentes infinidades
"Si tomamos como definición de conjunto infinito, que es el que permite establecer una correspondencia unívoca con cada uno de sus subconjuntos, podemos encontrar una aplicación de esta definición que permite demostrar que hay más números racionales que número naturales. Si buscamos una correspondencia unívoca entre ambos conjuntos, de forma sencilla consiste en contar las fracciones en que la suma del numerador y el denominador es 1, y luego aquellos que suman 2, y luego 3, y así sucesivamente. Dentro de cada grupo, se disponen las fracciones en orden de tamaño, omitiendo cualquier fracción que ya ha sido numerada. Esto tiene como resultado que los números racionales se numeran en un orden único:

    1/1   1/2   2/1   1/3   (2/2)   3/1   1/4   2/3   3/2   4/1

Es evidente que podemos calcular la correspondencia entre número racional y número natural, y esto es sufience para demostrar que no hay más números racionales que números naturales:

    1/1   1/2   2/1   1/3    3/1   1/4    2/3   3/2   4/1
     ↓    ↓    ↓     ↓     ↓     ↓     ↓    ↓    ↓   
     1     2     3     4      5      6     7     8    9  

Sería un error, no obstante, llegar a la conclusión, a partir de esto, que todos los conjuntos infinitos son equivalentes. De hecho, es posible demostrar que los números reales no pueden ser contados de la manera en que contábamos los números naturales y los números racionales (ver Teorema de la diagonal de Cantor).

A finales del siglo XIX, ésto originó nuevos estudios de lo que se llamó [[aritmética transfinita], y se intentó demostrar que la cardinalidad de los números reales es el próximo cardinal transfinito después de los números enteros. En 1963, se demostró que finalmente este conjetura no puede ser ni probada ni no probada; se trata de una "brecha" en las matemáticas."

El conjunto de los naturales

Planteémonos, en este momento, una definición constructiva, no axiomática, de ℕ.

Ernst Zermelo, en 1908, propone definir 0, 1, 2, 3..., como: ∅, {∅}, {{∅}}, {{{∅}}}... John von Neumann, propone que cada número natural sea el conjunto de todos los números naturales menores que él, es decir, propone definir 0, 1, 2, 3..., como: ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}...

Podemos interpretar esta idea, basándonos en la relación de equipotencia de conjuntos, de forma que el conjunto de números naturales es la clase de los cardinales de todos los conjuntos finitos, y por tanto, cualquier número natural, no es más que una potencia de un conjunto (Claro que la construcción de von Neumann genera algunos efectos laterales no deseados, aunque no son dañinos ni paradójicos, e incluso, a veces, son convenientes, en posteriores desarrollos formales. Por ejemplo, según ella, se tiene que 0 ∊ 1 ∊ 2 ∊ 3 ∊..., y que 0 ⊆ 1 ⊆ 2 ⊆ 3 ⊆...)

Observemos que 1 = {0}, 2 = {0, 1}, ..., n = {0, 1, 2, ..., n-1}, ..., es decir, todo número natural es un conjunto, formado por todos los números naturales anteriores. Para evitar confusiones, sobre todo en el orden técnico, muchos autores notan a estos conjuntos ℕ₁ = {0}, ℕ₂ = {0, 1}, ..., ℕ_n = {0, ..., n-1}, ... (aunque quizás esté más extendida la notación ℤ_n, significando lo mismo para cada subíndice).

Pero, ¿cómo definimos el conjunto de todos los números naturales, sin emplear expresiones tan imprecisas como “e igual de aquí en adelante”?

Si entendemos por sucesor de un conjunto a, y notamos a⁺ ó a+1, el conjunto a⁺ = a ∪ {a}, y definimos como conjunto inductivo a, aquél y sólo aquél tal que, ∅∊a, y ∀ x∊a, x⁺∊a, entonces, podemos definir los números naturales como aquéllos conjuntos que pertenecen a todo conjunto inductivo.

En estos términos, el principio de inducción ( consultar artículos Inferencias Deductivas e Inductivas, Problema de la inducción) para ℕ establece que ℕ es un conjunto inductivo , que es subconjunto de cualquier otro conjunto inductivo, esto es, ℕ es el menor conjunto inductivo (en el sentido de la inclusión). En otras palabras, que cualquier subconjunto inductivo de ℕ, coincide con ℕ.

En efecto, claramente, ∅∊ℕ, y si x∊ℕ, entonces, x pertenece a cualquier conjunto inductivo, por lo que x⁺ también pertenece a cualquier conjunto inductivo, así que, x⁺∊ℕ.

Equipotencia, finitud e infinitud

Conjuntos numerables

Potencia del continuo

Teorema de Cantor. Relación entre las potencias del numerable y del continuo

Por ahora, sabemos que los conjuntos ℕ, ℤ y ℚ, tienen la misma potencia, la numerable, ℵ₀. Se puede demostrar, que sus conjuntos potencia (esto es, el conjunto de todos sus subconjuntos), 2^ℕ, 2^ℤ y 2^ℚ, tienen la misma potencia, la del continuo, 2^ℵ₀, la potencia de ℝ.

Observación.- Por cierto, algo que hemos admitido, sin más, para conjuntos finitos, es la existencia del conjunto potencia. Podemos razonar que existe, proporcionando un método efectivo de construcción del mismo, que además termina en tiempo finito. Sin embargo, para conjuntos infinitos, formalmente, la situación no es obvia. De hecho, cualquier axiomática conjuntista contiene algún axioma que implica tal existencia. En el caso de la axiomática de Zermelo-Fraenkel, se concreta en el axioma del conjunto potencia: «Para todo conjunto existe su conjunto potencia», formalmente, ∀x ∃y ∀z (z∊y ↔ z ⊆ x).

Teorema.- Para todo conjunto A, |2^A| = 2^|A|
Dem.: En efecto, el número de aplicaciones que pueden definirse entre dos conjuntos, f: A → B, se calcula como las variaciones con repetición, VR_|A|,|B|, esto es, |B|^|A|. Sea ℳ(A,ℤ₂) el conjunto de todas las aplicaciones de A en ℤ₂ (={0,1}), y sea g: 2^A → ℳ(A,ℤ₂), definida por g(B) = χ_B, donde χ_B es la función característica de B, esto es, χ_B(x) = 1 si x∊B, y χ_B(x) = 0, en caso contrario. Se demuestra fácilmente que g es biyectiva. Por tanto, |2^A| es |ℤ₂|^|A|, esto es, |2^A| = 2^|A|.

Por tanto, en particular, |2^ℕ| = |2^ℤ| = |2^ℚ| = 2^ℵ₀.

Veamos ahora que este último también es la potencia del continuo.

Teorema.- |ℝ| = 2^ℵ₀
Dem.: En efecto, sabemos, por un ejemplo anterior, que [0,1] ∼ ℝ, por lo que basta demostrar que [0,1] ∼ 2^ℕ. Consideremos los números reales de [0,1], representados en el sistema binario, exigiendo que la sucesión de bits no termine en una secuencia infinita de unos, para que tal representación sea única. Sea f: [0,1] → 2^ℕ, definida por f(0,a₁a₂a₃...) = {n∊ℕ: a_n = 1}. Fácilmente se demuestra que es biyectiva. Obsérvese que la inversa es f⁻¹: 2^ℕ → [0,1], definida como f⁻¹(A) = 0,a₁a₂a₃..., donde a_n = χ_A(n). ❏

Pudiera pensarse que los únicos cardinales son ℵ₀ y 2^ℵ₀. El conocido como teorema de Cantor, demuestra, que hay infinitos cardinales mayores que el del continuo, proporcionando así una ley de formación de los mismos. En ningún momento se demuestra que sean esos los únicos cardinales existentes. De hecho, actualmente, se ignora si son o no los únicos.

Teorema (de Cantor).- Para todo conjunto A, |A| < 2^|A|
Dem.: En efecto, Para conjuntos finitos, es fácil demostrar, por ejemplo, por inducción, que (∀ n∊ℕ) (|A| = n < 2ⁿ = |2^A|). Para conjuntos infinitos, razonamos en dos fases: primero, demostramos que existe una inyección desde A, a un subconjunto propio de 2^A, por lo que |A| ≤ |2^A|; a continuación, demostramos que no existe ninguna biyección entre A y 2^A, por lo que, |A| ≠ |2^A|. Lo primero es trivial, basta tomar como subconjunto propio el conjunto de todos los subconjuntos, que tienen como único elemento, un elemento de A. Para demostrar lo segundo, razonamos por reducción al absurdo; suponemos que existe una biyección entre A y 2^A. Sea B el conjunto de todos los elementos de A, que no son elementos del subconjunto asignado a ellos por la biyección, o sea, B = {a∊A: a∉f(a)} y sea b = f⁻¹(B). El elemento b debe estar o no estar en B; si b∊B, entonces, por definición de B, b∉f(B), esto es, b∉B; por otro lado, si b∉B, entonces, por definición de B, b∊f(B), o sea, b∊B. Concluimos que no puede existir una biyección entre A y 2^A, y por tanto, |A| ≠ |2^A|. ❏

Observemos que, de este teorema, se deduce, por ejemplo, que: 2^ℵ₀ < 2^2ℵ₀.

En un más que breve resumen, en este punto, diríamos:

Aritmética para aleph0 y C

Acerca de la sucesión de infinitos

El teorema de Cantor permite afirmar la existencia de una infinidad de conjuntos infinitos:

y, por tanto, de una sucesión ℭ₀, estrictamente creciente de cardinales infinitos:

sucesión, que comienza donde «termina» la de números cardinales finitos.

Pensemos ahora en la unión de conjuntos cualesquiera con cardinales los de la sucesión anterior; el cardinal de esta unión, al que designaremos por Ω₀, es mayor que cualquiera de los cardinales ℵ₀, 2^ℵ₀, 2^2ℵ₀, ..., de modo que tendremos otra sucesión estrictamente creciente, ℭ₁, que comienza donde «termina» ℭ₀:

Consideremos ahora, la unión de conjuntos cualesquiera con cardinales los de estas dos sucesiones; el cardinal de esta unión, al que llamamos Ω₁, es mayor que cualquiera de los cardinales obtenidos anteriormente, obteniéndose una nueva sucesión, ℭ₂, estrictamente creciente, cuyo comienzo está donte «termina» ℭ₁:

Generando nuevos cardinales de forma análoga, vemos que tenemos la siguiente sucesión, ℭ, estrictamente creciente de cardinales infinitos:

Teorema.- La sucesión ℭ verifica las siguientes propiedades:

Axioma de elección

Hipótesis del continuo

Retomando el primer problema de Hilbert, en su apartado uno, y ya sea admitiendo o no el axioma de elección, lo que no se puede, en un principio, es descartar que entre ℵ₀ y 2^ℵ₀, existan cardinales diferentes de ambos, ni que, en general, tampoco existan otros cardinales entre cualesquiera dos términos sucesivos de la sucesión de cardinales infinitos C.
En 1878, Cantor conjetura que cualquier subconjunto infinito de números reales es numerable o es continuo; en otras palabras, que no existen cardinales entre ℵ₀ y 2^ℵ₀, es decir, que ℵ₁ = 2^ℵ₀, afirmación que actualmente se conoce como hipótesis del continuo (HC). En 1883, implícitamente, Cantor conjetura también que ℵ₂ = 2^ℵ₁.
La conjetura, más general, de que cualquiera que sea el número cardinal infinito c, no existen otros números cardinales entre c y 2^c, es decir, que los números cardinales son única y exclusivamente los recogidos en la sucesión ℭ, fue formulada por vez primera, por Hausdorff (1908 ) y se conoce como hipótesis general del continuo (HGC). Lo que afirma esta última conjetura es que para todos los ordinales α, 2^{ℵ _α} = ℵ_α+1.
En 1938, Kurt GÖDEL, demuestra que HGC es consistente con ZFC, o sea, que HC no puede ser refutada a partir de ZF ni de ZFC. En 1963, Paul COHEN, demuestra que incluso HC, no es decidible a partir de ellos, o sea, que a partir de los axiomas usuales de la teoría de conjuntos, ya sea con el axioma de elección o sin él, es imposible demostrar la veracidad (Cohen) o la falsedad (Gödel) de HC, ni de HGC. Estos resultados de Gödel y Cohen, se obtienen bajo la hipótesis de la consistencia de ZF.
Pero también es consistente suponer cualquiera de las igualdades, 2^ℵ₀ = ℵ₂, 2^ℵ₀ = ℵ₃, etc., es decir, no sabemos nada sobre la magnitud de 2^ℵ₀, comparada con la de los alephs. Por tanto, es consistente, con ZFC, por ejemplo, suponer que ℵ₁ < 2^ℵ₀ < 2^ℵ₁. Así que, ¿cuál es el lugar que ocupa 2^ℵ₀ en la escala de alephs?
Los resultados de Gödel y Cohen, también demuestran, siendo ZF consistente, la independencia del axioma de elección respecto de ZF, es decir, que no es decidible a partir de ellos. Pudiera argumentarse la posibilidad de admitir HC, o incluso HGC, o sus negaciones, como axioma, y extender ZF. Sin embargo, esta elevación a la categoría de axioma de una afirmación, debe ser corroborada con la experiencia y, como mínimo, debe ser suficientemente intuitiva (más intuitivo que era el postulado de las paralelas de Euclides, y sin embargo, nacieron las geometrías no euclideas). Es muchísimo más intuitivo el axioma de elección, que HC. Por ello, que no presente demasiada objeción el admitir AE como axioma.

Relación con la Teoría de la Computación

Sea cual sea el programa, desde el punto de vista de su codificación en máquina, es una mera cadena de bits, por lo que la acción del programa corresponde a calcular una función f: ℕ → ℕ. Podríamos pensar, entonces, que a toda función f: ℕ → ℕ, le correspondería un programa, que pudiera ser implementado en alguna ocasión. Sea F el conjunto de todas las funciones de ℕ en ℕ; resulta que F ∼ 2^ℕ. Es decir, existe una cantidad no numerable de tales funciones.
No obstante, actualmente, los lenguajes de programación se basan en un alfabeto finito, por lo que podemos listar todos los posibles programas escritos en tal lenguaje, primero, todos los de longitud un símbolo, luego, los de longitud dos, a continuación, los de longitud tres, etc. Parece obvio que la cantidad de programas sería numerable.
Una cantidad no numerable de funciones f: ℕ → ℕ, y una cantidad numerable de programas. Si admitimos que cualquier programa calcula una única función, entonces existen funciones no calculables por ningún programa (funciones no computables).
Incluso admitiendo la existencia de programas que calculan un número finito de funciones, que ciertamente puede haberlos, o incluso, programas que calculan un número infinito numerable de funciones (un ejemplo de ellos serán los programas universales), como la unión numerable de conjuntos numerables es numerable, la cantidad total de funciones calculables es numerable.
¿Se conocen alguna de estas funciones no computables? ¿Se conocen todas?, esto es, ¿se conoce alguna caracterización de ellas? ¿Es posible computarlas, utilizando otro lenguaje de programación, o una máquina de mayor potencia? ...
La actualidad está dominada por alfabetos finitos y programas implementados con un número finito de líneas de código. Varias son las posibles modificaciones; podríamos permitir:
a) un alfabeto infinito numerable, para lo cuál bastaría tener un símbolo, e indexarlo con un conjunto infinito numerable, por ejemplo, {ai : i∊ℕ},
b) un número infinito de líneas de código. Problemas de procesamiento y ejecución (¿secuencial?). ¿cómo escribir infinitas líneas de código? ¿y cómo computarlas? El programa (∀i) (PRINT i) tiene infinitas líneas de programa, representables (compactables) en una única. En otras palabras, es un programa infinito para el que existe un programa finitamente representable, equivalente (misma solución).

Vease también

• Ejercicios y problemas sobre cardinalidad

Referencia

[1] Autores varios (1995). "La correspondencia, el cálculo y el infinito". Enciclopedia temática GUINNESS.

Bibliografía

Diferentes infinidades (Conjuntos infinitos): La naturaleza del universo: ""La correspondencia, el cálculo y el infinito". Enciclopedia temática GUINNESS, 1995