Conxunto numerable

En matemáticas, un conxunto é contábel ou numerábel se é finito ou se pode facer unha correspondencia un a un co conxunto de números naturais.De forma equivalente, un conxunto é contábel se existe unha función inxectiva a partir dos números naturais; isto significa que cada elemento do conxunto pode estar asociado a un número natural único, ou que os elementos do conxunto poden ser contados un a un, aínda que o reconto pode nunca rematar debido a un número infinito de elementos.

Asumindo o axioma de escolla contábel, un conxunto é contábel se a súa cardinalidade (o número de elementos do conxunto) non é maior que a dos números naturais. Un conxunto numerábel que non é finito dise que é numerabelmente infinito ou contabelmente infinito .

O concepto atribúese a Georg Cantor, quen demostrou a existencia de conxuntos non numerábeis, é dicir, conxuntos que non son contábeis; por exemplo o conxunto dos números reais.

Definición

Un conxunto ${\displaystyle S}$ é contábel se:

• A súa cardinalidade ${\displaystyle |S|}$ é menor ou igual a ${\displaystyle \aleph _{0}}$ (aleph-cero, a cardinalidade do conxunto de números naturais ${\displaystyle \mathbb {N} }$. ^[1]
• Existe unha función inxectiva de ${\displaystyle S}$ a ${\displaystyle \mathbb {N} }$.^[2][3]
• ${\displaystyle S}$ é baleiro ou existe unha función sobrexectiva de ${\displaystyle \mathbb {N} }$ a ${\displaystyle S}$. ^[3]
• Existe un mapeo bixectivo entre ${\displaystyle S}$ e un subconxunto de ${\displaystyle \mathbb {N} }$.^[4]
• ${\displaystyle S}$ é finito ( ${\displaystyle |S|<\aleph _{0}}$ ) ou contabelmente infinito. ^[5]

Todas estas definicións son equivalentes.

Un conxunto ${\displaystyle S}$ é contabelmente infinito se:

• A súa cardinalidade ${\displaystyle |S|}$ é exactamente ${\displaystyle \aleph _{0}}$.^[1]
• Hai un mapeo inxectivo e sobrexectivo (e polo tanto bixectivo) entre ${\displaystyle S}$ e ${\displaystyle \mathbb {N} }$.
• ${\displaystyle S}$ ten unha correspondencia un a un con ${\displaystyle \mathbb {N} }$.^[6]
• Os elementos de ${\displaystyle S}$ pódense ordenar nunha secuencia infinita ${\displaystyle a_{0},a_{1},a_{2},\ldots }$, onde ${\displaystyle a_{i}}$ é distinto de ${\displaystyle a_{j}}$ para ${\displaystyle i\neq j}$ e cada elemento de ${\displaystyle S}$ é listado.^[7][8]

Un conxunto é non numerábel se non é numerábel, é dicir, a súa cardinalidade é maior que ${\displaystyle \aleph _{0}}$.^[1]

Introdución

Mapa bixectivo de enteiros a números pares

Algúns conxuntos son infinitos; estes conxuntos teñen máis de ${\displaystyle n}$ elementos onde ${\displaystyle n}$ é calquera número enteiro que se poida especificar. Por exemplo, o conxunto de números naturais, que serían ${\displaystyle \{0,1,2,3,4,5,\dots \}}$,^[a] ten infinitos elementos, e non podemos usar ningún número natural para dar o seu tamaño. Por exemplo, hai infinitos enteiros impares, infinitos enteiros pares e tamén infinitos enteiros en xeral. Podemos considerar que todos estes conxuntos teñen o mesmo "tamaño" porque podemos organizar as cousas de forma que, para cada número enteiro, haxa un número dese conxunto distinto, por exemplo para os pares podemos estabelecer unha función bixectiva:$${\displaystyle \ldots \,-\!2\!\rightarrow \!-\!4,\,-\!1\!\rightarrow \!-\!2,\,0\!\rightarrow \!0,\,1\!\rightarrow \!2,\,2\!\rightarrow \!4\,\cdots }$$ou, máis xenralmente, ${\displaystyle n\rightarrow 2n}$ (ver imaxe). Esta noción matemática de "tamaño", cardinalidade, é que dous conxuntos son do mesmo tamaño se e só se hai unha bixección entre eles. Chamamos infinitos a todos os conxuntos que están en correspondencia un a un cos números enteiros e dicimos que teñen cardinalidade ${\displaystyle \aleph _{0}}$.

Georg Cantor demostrou que non todos os conxuntos infinitos son contábeis. Por exemplo, os números reais non se poden poñer en correspondencia un a un cos números naturais (números enteiros non negativos). O conxunto de números reais ten unha cardinalidade maior que o conxunto de números naturais e dise que é non numerábel.

Visión xeral formal

Por definición, un conxunto ${\displaystyle S}$ é contábel se existe unha bixección entre ${\displaystyle S}$ e un subconxunto dos números naturais ${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$.

No caso dos conxuntos infinitos, un conxunto ${\displaystyle S}$ é contabelmente infinito se hai unha bixección entre ${\displaystyle S}$ e todo ${\displaystyle \mathbb {N} }$ . Como exemplos, considere o conxunto ${\displaystyle A=\{1,2,3,\dots \}}$, o conxunto de enteiros positivos, temos a bixección ${\displaystyle n\leftrightarrow n+1}$ e para o conxunto ${\displaystyle B=\{0,2,4,6,\dots \}}$, os enteiros pares, temos a bixección ${\displaystyle n\leftrightarrow 2n}$.

Teorema:  Todo subconxunto dun conxunto contábel é contábel. ^[9]

O conxunto de todos os pares ordenados de números naturais, o produto cartesiano de dous conxuntos de números naturais, ${\displaystyle \mathbb {N} \times \mathbb {N} }$ é contabelmente infinito, como se pode ver seguindo un camiño como o da imaxe:

A función de emparellamento de Cantor asigna un número natural a cada par de números naturais

O mapeo resultante sería do seguinte xeito:$${\displaystyle 0\leftrightarrow (0,0),1\leftrightarrow (1,0),2\leftrightarrow (0,1),3\leftrightarrow (2,0),4\leftrightarrow (1,1),5\leftrightarrow (0,2),6\leftrightarrow (3,0),\ldots }$$

Teorema: O produto cartesiano de finitamente moitos conxuntos contábeis é contábel.^[10]

O conxunto de todos os números enteiros ${\displaystyle \mathbb {Z} }$ e o conxunto de todos os números racionais ${\displaystyle \mathbb {Q} }$ intuitivamente poden parecer moito máis grandes que ${\displaystyle \mathbb {N} }$. Mais desde o punto de vista da cardinalidade isto non é así, se un par é tratado como o numerador e o denominador dunha fracción (${\displaystyle a/b}$ onde ${\displaystyle a}$ e ${\displaystyle b\neq 0}$ son enteiros), entón para cada fracción positiva, podemos chegar a un número natural distinto que lle corresponda.

Teorema:  ${\displaystyle \mathbb {Z} }$ (conxunto de todos os enteiros) e ${\displaystyle \mathbb {Q} }$ (conxunto de todos os números racionais) son contábeis.^[b]

De xeito semellante, o conxunto de números alxébricos é contábel. ^[11]

Teorema: Calquera unión finita de conxuntos countábeis é contábel.^[12][13]

 Teorema: (asumindo o axioma de escolla contábel) A unión de contabelmente moitos conxuntos contábeis forma un conxunto contábel.^[14]

Enumeración dun número contábel de conxuntos contábeis

Necesitamos o axioma de escolla contábel para indexar todos os conxuntos ${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},{\textbf {d}},\dots }$ simultaneamente.

Teorema: O conxunto de todas as secuencias de números naturais é contábel.

Teorema: O conxunto de todos os subconxuntos finitos dos números naturais é contábel.

Teorema:  Sexan os conxuntos ${\displaystyle S}$ e ${\displaystyle T}$.

Se a función ${\displaystyle f:S\to T}$ é inxectiva e ${\displaystyle T}$ é contábel, daquela ${\displaystyle S}$ é contábel.

Se a función ${\displaystyle g:S\to T}$ é sobrexectiva e ${\displaystyle S}$ é contábel, daquela ${\displaystyle T}$ é contábel.

Isto segue das definicións de conxunto contábel como funcións inxectivas/sobrexectivas.

O teorema de Cantor afirma que se ${\displaystyle A}$ é un conxunto e ${\displaystyle {\mathcal {P}}(A)}$ é o seu conxunto de partes, é dicir, o conxunto de todos os subconxuntos de ${\displaystyle A}$, entón non hai función sobrexectiva de ${\displaystyle A}$ a ${\displaystyle {\mathcal {P}}(A)}$. Unha demostración dáse no artigo Teorema de Cantor. Como consecuencia inmediata disto e do teorema básico anterior temos:  Proposición: O conxunto ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ non é contábel; isto é, e non numerábel.

O conxunto dos números reais é non numerábel, ^[c] e tamén o é o conxunto de todas as secuencias infinitas de números naturais.

Orde total

Os conxuntos contábeis pódense ordenar totalmente de varias maneiras, por exemplo:

• Ben ordenado (ver tamén número ordinal):
  • A orde habitual dos números naturais (0, 1, 2, 3, 4, 5, ...)
  • Os enteiros na orde (0, 1, 2, 3, ...; −1, −2, −3, ...)
• Outros (non ben ordenados):
  • A orde habitual dos números enteiros (..., −3, −2, −1, 0, 1, 2, 3, ...)
  • A orde habitual dos números racionais (Non se pode escribir explicitamente como unha lista ordenada!)

Nos dous exemplos de ordes ben ordenadas, calquera subconxunto ten un elemento menor; mais en ambos os dous exemplos de non ben ordenados, algúns subconxuntos non teñen un elemento menor. Esta é a definición clave que determina se unha orde total tamén é unha orde ben ordenada.