Cardinalidad y conjuntos numerables

Inyectiva significa que no junta dos entradas distintas en una misma salida; sobreyectiva, que llega a todas las salidas de B. Juntas dan un emparejamiento exacto. En conjuntos finitos coincide con contar igual número de elementos.

Para conjuntos infinitos una fórmula puede describir todas las parejas sin acabar una cuenta. Debemos probar ambas propiedades para cualquier entrada o salida permitida. El dibujo solo muestra un inicio: las cinco flechas visibles no demuestran por sí solas una afirmación infinita.

Los impares positivos son parte de ℕ y faltan muchos naturales, incluido cero. Aun así acabamos de emparejarlos con todo ℕ. No hay contradicción: ser subconjunto describe pertenencia; tener igual cardinal describe si existe una biyección.

También escribimos |A|≤|B| cuando hay una inyección de A a B. La inclusión de un subconjunto en su conjunto es una inyección. Pero inclusión estricta y desigualdad estricta de cardinales son cosas distintas en el infinito; tampoco todos los infinitos resultan del mismo tamaño.

En esta página numerable significa finito o numerablemente infinito. Por tanto incluye el conjunto vacío. Otras fuentes reservan la palabra solo para conjuntos infinitos: conviene declarar la convención antes de aplicar un teorema.

Una enumeración que cubre un conjunto puede repetir elementos. Para una biyección con ℕ no admitimos repeticiones. Si el conjunto enumerado es infinito, conservar solo la primera aparición de cada elemento produce una lista infinita sin duplicados; cada elemento original tiene que aparecer en una posición finita.

Empezamos 0,1,−1,2,−2,3,−3,… . Listar todos los positivos antes de comenzar los negativos nunca llegaría al primer negativo. Alternar garantiza un lugar finito para cada signo y magnitud.

Posiciones impares positivas dan enteros positivos; pares positivas, negativos. Los tres grupos no se solapan y cada entero tiene una única posición.

En ℕ×ℕ cada objeto es un par ordenado (a,b). No enumeramos una fila infinita antes de pasar a la siguiente. Ordenamos por la suma a+b: para suma s, los pares son (0,s),(1,s−1),…,(s,0). Son s+1 pares, una cantidad finita.

Visitamos las sumas cero, uno, dos y así sucesivamente. Cualquier (a,b) pertenece a la diagonal finita de suma a+b, alcanzada después de finitas diagonales finitas. La fórmula de su posición, si recorremos cada diagonal aumentando a, es s(s+1)/2+a, con s=a+b y posiciones desde cero.

Cada racional es a/b con a entero y b entero positivo.

Cada etapa es finita.

Así cada racional tiene una representación que llega en una etapa finita. Pero 1/2 y 2/4 son el mismo racional. Conservamos solo su primera aparición, o exigimos fracciones irreducibles con denominador positivo. Queda una enumeración de ℚ sin repeticiones; es infinita porque ya contiene todos los enteros.

Un subconjunto S de un conjunto numerable también es numerable. En una enumeración sin repeticiones del conjunto original, conservamos los elementos que pertenecen a S. Si quedan infinitos, sus posiciones originales forman una sucesión creciente; cada elemento seleccionado conserva una posición finita en la nueva lista.

Para dos conjuntos intercalamos a₀,b₀,a₁,b₁,… y quitamos duplicados. Para una familia de listas ya dadas, recorremos por diagonales el par índice de lista, posición interna. La condición listas ya dadas evita suponer sin explicación que conocemos una enumeración simultánea de una familia arbitraria.

Supongamos que r₀,r₁,… enumera todos los reales de (0,1). Escribimos cada uno con la expansión decimal que no acaba en una cola infinita de nueves. Construimos d: su cifra de posición n+1 será dos si la cifra correspondiente de rₙ es uno, y uno en cualquier otro caso.

Para cada n, d difiere de rₙ en esa posición diagonal. d está entre cero y uno y usa solo unos y doses, así que no hay ambigüedad de representación por colas de ceros o nueves. No coincide con ninguna fila, aunque la lista sea infinita.

Esto contradice que cubriera (0,1); por tanto ese intervalo y ℝ no son numerables.

Cada f(a) es un subconjunto, de modo que la pregunta a∈f(a) tiene sentido. D también es un subconjunto de A, así que es un elemento de P(A).

Si algún d de A tuviera f(d)=D, por definición d∈D sería equivalente a d∉f(d), es decir d∉D: imposible. Por tanto D queda fuera de la imagen de cualquier f. Ninguna f es sobreyectiva. Como a↦{a} sí es inyectiva de A a P(A), el cardinal del conjunto potencia es estrictamente mayor.

Esto incluye conjuntos finitos e infinitos.

ℚ es denso: cualquier intervalo real abierto contiene racionales. Aun así es numerable. En cambio (0,1) no es numerable. No podemos inferir tamaño cardinal solo de ver puntos repartidos por una recta o de poder aproximar otros números.

Tampoco la longitud decide cardinalidad. Una función afín invertible empareja intervalos abiertos de longitudes diferentes. Una biyección puede estirar, comprimir o cambiar distancias; solo exige una pareja única para cada elemento de ambos conjuntos.