En matemáticas, un conjunto numerable es un conjunto o bien finito o bien del mismo tamaño que los números naturales. Más concretamente, un conjunto se dice que es numerable (o contable) cuando es finito o cuando existe una biyección entre este conjunto y el conjunto de los números naturales.

En 1874 Georg Cantor introdujo el término conjunto numerable, contrastando conjuntos que son contables con los que son incontables. Hoy en día, los conjuntos numerables forman la base de una rama de las matemáticas llamada matemática discreta.

Definición Un conjunto es contable si existe una función inyectiva desde números naturales ya que existe una obvia biyección entre y , no existe diferencia si se considera el 0 como natural o si no; en cualquier caso, este artículo toma la convención estándar de la lógica matemática, en donde se toma al a , es decir, a cada n de los naturales (dominio o conjunto de partida) le corresponde un elemento de S (imagen o conjunto de llegada) mediante una función .

Si la función llega a ser también sobreyectiva (y por lo tanto biyectiva), entonces se llama infinito numerable.

En otras palabras, un conjunto es infinito numerable si tiene correspondencia uno a uno con el conjunto de los números naturales .

Como se señaló anteriormente, esta terminología no es universal. Algunos autores utilizan contable en el sentido de lo que aquí se llama infinito numerable, y no incluyen los conjuntos finitos.

Formulaciones alternativas (equivalentes) de la definición en términos de una función biyectiva o una función sobreyectiva también se puede dar. Véase abajo.

Historia En 1874, en su primer artículo de la teoría de conjuntos, Cantor demostró que el conjunto de los números reales es incontable, mostrando entonces que no todos los conjuntos infinitos son numerables. En 1878 utilizó las correspondencias uno a uno para definir y comparar las cardinalidades.Cantor 1878, p. 242. En 1883 extendió los números naturales con sus ordinales infinitos, y usó conjuntos de ordinales para producir una infinidad de conjuntos teniendo diferentes cardinalidades infinitas.Ferreirós 2007, pp. 268, 272-273.

Origen del término La noción de numerabilidad fue introducida por Georg Cantor en un artículo de 1874,y en 1873 en su correspondencia con Dedekind. Sobre una propiedad del sistema de todos los números algebraicos realesCantor (1874) Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal de Crelle 77, p258-262 (ver el centro de numeración de Göttingen ). Disponemos del origen de esta demostración, que todavía no es la demostración más conocida que utiliza el argumento diagonal, gracias a las cartas del 7 y 9 de diciembre de 1873 de Georg Cantor a Richard Dedekind. donde establece por una parte que el conjunto de números algebraicos reales (es decir, el conjunto de los números reales que son solución de alguna ecuación polinómica con coeficientes racionales) es numerable,Demostración de Dedekind, según su correspondencia. y por otra que el conjunto de todos los números reales no lo es, a partir de lo cual deduce inmediatamente la existencia de números trascendentes o no algebraicos, redescubriendo así un resultado de Liouville.

Su origen está ligado a la concepción del infinito en matemáticas. Hasta el descubrimiento de Cantor, el infinito era el infinito potencial, la posibilidad de continuar un proceso sin detenerse nunca. La comparación de conjuntos infinitos trae consigo la noción de infinito alcanzado, actual o completo: un conjunto infinito visto como un todo, un concepto que ha sido rechazado por numerosos matemáticos (Gauss, o, en la época de Cantor, Kronecker, etc.).Véase por ejemplo Kneale and Kneale, The development of Logic Clarendon Press 1962, p 673. Para ellos, el hecho de considerar una infinidad de objetos como un todo, es decir, el concepto de conjunto infinito no tiene sentido, sino que el infinito solo puede surgir del proceso de enumeración sin repetición que nunca se detiene. Solo el infinito numerable puede tener en rigor algún sentido.

Introducción Un conjunto es una colección de elementos, y puede ser descrito de muchas maneras. Una forma es simplemente una lista de todos sus elementos; Por ejemplo, el conjunto que consiste en los números enteros 3, 4, y 5 puede ser denotado {3, 4, 5}. Esto solo es efectivo para pequeños conjuntos, sin embargo; para conjuntos más grandes, esto podría llevar mucho tiempo y ser propenso a errores. En lugar de enumerar cada elemento, a veces se utilizan unos puntos suspensivos ("...") si el escritor cree que el lector puede adivinar fácilmente lo que falta; por ejemplo, {1, 2, 3, ..., 100} presumiblemente denota el conjunto de los enteros de 1 a 100. Incluso en este caso todavía es posible listar todos los elementos, ya que el conjunto es finito.

Algunos conjuntos son infinitos; estos conjuntos tienen más de n elementos para cualquier número entero n. Por ejemplo, el conjunto de números naturales, escrito como {0, 1, 2, 3, 4, 5, ...}, tiene un número infinito de elementos, y no podemos utilizar cualquier número normal para dar su tamaño. Sin embargo, resulta que los conjuntos infinitos tienen una idea bien definida de tamaño (o mejor dicho, de cardinalidad, que es el término técnico para el número de elementos en un conjunto), y no todos los conjuntos infinitos tienen la misma cardinalidad.

Para entender lo que esto significa, primero examinamos lo que no quiere decir. Por ejemplo, hay un número infinito de enteros impares, un número infinito de enteros pares, y (por lo tanto) un número infinito de números enteros en general. Sin embargo, resulta que el número de enteros pares, que es el mismo que el número de enteros impares, es también el mismo que el número de enteros en general. Esto se debe a que para cada entero impar, existe un homólogo, entero par: ... -2 → -4, -1 → -2, 0 → 0, 1 → 2, 2 → 4, ... En la imagen están dispuestos los números enteros y los números pares en una correspondencia uno-a-uno (o biyección), que es una función que representa dos conjuntos de tal manera que cada elemento de cada conjunto corresponde a un solo elemento en el otro conjunto.

Sin embargo, no todos los conjuntos infinitos tienen la misma cardinalidad. Por ejemplo, Georg Cantor (que introdujo este concepto) demostró que los números reales no se pueden corresponder uno-a-uno con los números naturales (enteros no negativos), y por lo tanto, el conjunto de los números reales tiene una cardinalidad mayor que el conjunto de los números naturales.

Un conjunto es numerable si: (1) es finito, o (2) si tiene la misma cardinalidad (tamaño) que el conjunto de los números naturales. De manera equivalente, un conjunto es numerable si tiene la misma cardinalidad que algún subconjunto del conjunto de los números naturales. De lo contrario, es incontable.

Formulación general sin detalles Por definición, un conjunto S es numerable si existe una función inyectiva f : S → N desde S al conjunto de los números naturales N = {0, 1, 2, 3, ...}.

Podría parecer normal dividir los conjuntos en diferentes clases: poner todos los conjuntos que contienen un elemento juntos; todos los conjuntos que contienen dos elementos juntos; ...; por último, poner juntos todos los conjuntos infinitos y considerar que tienen el mismo tamaño. Este punto de vista no es sostenible dentro de la definición natural de tamaño.

Para elaborar esto necesitamos el concepto de biyección. Aunque una biyección parece un concepto más avanzado que un número, el desarrollo habitual de las matemáticas en términos de la teoría de conjuntos define funciones antes de los números, ya que se basan en conjuntos mucho más simples. Aquí es donde el concepto de biyección interviene: define la correspondencia

a ↔ 1, b ↔ 2, c ↔ 3

Esto define una biyección, puesto que cada elemento de {a, b,c} se empareja con un preciso elemento de {1, 2, 3} , y viceversa.

Ahora se generaliza esta situación y definimos dos conjuntos del mismo tamaño si (y solo si) hay una biyección entre ellos. Para todos los conjuntos finitos esto nos da la definición usual de tamaño equivalente. ¿Qué nos dice sobre el tamaño de los conjuntos infinitos?

Considere los conjuntos A = {1, 2, 3, ...}, el conjunto de los enteros positivos y B = {2, 4, 6, ...}, el conjunto de los enteros positivos pares. Afirmamos que, bajo nuestra definición, estos conjuntos tienen el mismo tamaño, y que, por tanto, B es infinito numerable. Recordemos que para probar esto tenemos que probar una biyección entre ellos. Pero esto es fácil, usando n ↔ 2n , de modo que 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....

Como en el ejemplo anterior, cada elemento de A se ha emparejado con un elemento de B y viceversa. De ahí que tengan el mismo tamaño. Este es un ejemplo de un conjunto del mismo tamaño que uno de sus subconjuntos propios (algo imposible para conjuntos finitos).

Del mismo modo, el conjunto de todos los pares ordenados de los números naturales es infinito numerable, como puede verse siguiendo una trayectoria como la de la imagen: La representación resultante es: 0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (0,1), 3 ↔ (2,0), 4 ↔ (1,1), 5 ↔ (0,2), 6 ↔ (3,0) .... Esta representación abarca a todos los pares ordenados.

Curiosamente, si trata a cada par como el numerador el y denominador de una fracción vulgar, a continuación, para cada fracción positiva, podemos llegar a una cantidad distinta que corresponderá a la misma. Esta representación incluye también a los números naturales, ya que cada número natural es también una fracción N/1. Por lo tanto podemos concluir que hay exactamente tantos números racionales positivos como números enteros positivos. Esto es cierto también para todos los números racionales, como puede verse a debajo.

Teorema: El producto cartesiano de un número finito de conjuntos numerables es numerable.

A veces más de una representación es útil. Aquí es donde se representa que el conjunto que se desea mostrar es infinito numerable en otro conjunto, y luego representa este otro conjunto de los números naturales. Por ejemplo, los números racionales positivos pueden ser fácilmente asignados a (un subconjunto de) los pares de números naturales porque p/q representa a (p, q).

¿Y qué ocurre con los subconjuntos infinitos de los conjuntos numerables infinitos? ¿Tienen éstos menos elementos que N?

Teorema: Cada subconjunto de un conjunto numerable es numerable. En particular, cada subconjunto infinito de un conjunto infinito numerable es infinito numerable.

Por ejemplo, el conjunto de los números primos es contable, mediante la asignación del n-ésimo número primo a n: El 2 representa al 1 El 3 representa al 2 El 5 representa al 3 El 7 representa al 4 El 11 representa al 5 El 13 representa al 6 El 17 representa al 7 El 19 representa al 8 El 23 representa al 9 ...

¿Qué ocurre con los conjuntos que son naturalmente "mayores que" N? Por ejemplo, el conjunto de los enteros, Z, o el conjunto de los números racionales, Q, que, intuitivamente puede parecer mucho más grande que N. Pero las apariencias engañan, ya que afirmamos que:

Teorema: Z (el conjunto de todos los enteros) y Q (el conjunto de todos los números racionales) son contables.

De una manera similar, el conjunto de los números algebraicos es contable.

Teorema: Cualquier unión finita de conjuntos contables es contable. Q puede definirse como el conjunto de todas las fracciones del tipo a'/b donde a y b son números enteros, con b> 0. Esto se puede corresponder con el subconjunto de triples ordenados de números naturales (a, b, c) de tal manera que si a ≥ 0 y b > 0, a y b son coprimos, y c ∈ {0, 1} luego c = 0 si a / b ≥ 0, y c = 1 en caso contrario.

El 0 representa a (0,1,0) El 1 representa a (1,1,0) El −1 representa a (1,1,1) El 1/2 representa a (1,2,0) El −1/2 representa a (1,2,1) El 2 representa a (2,1,0) El −2 representa a (2,1,1) El 1/3 representa a (1,3,0) El −1/3 representa a (1,3,1) El 3 representa a (3,1,0) El −3 representa a (3,1,1)