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 S é *contábel* se:

* A súa cardinalidade |S| é menor ou igual a \aleph_0 (aleph-cero, a cardinalidade do conxunto de números naturais \N.  
* Existe unha función inxectiva de S a \N.
* S é baleiro ou existe unha función sobrexectiva de \N a S. 
* S é finito ( |S| ) ou contabelmente infinito. 

Todas estas definicións son equivalentes.

Un conxunto S é *contabelmente infinito* se:

* A súa cardinalidade |S| é exactamente \aleph_0.
* Hai un mapeo inxectivo e sobrexectivo (e polo tanto bixectivo) entre S e \N.
* S ten unha correspondencia un a un con \N.
* Os elementos de S pódense ordenar nunha secuencia infinita a_0, a_1, a_2, \ldots, onde a_i é distinto de a_j para i\neq j e cada elemento de S é listado.

Un conxunto é *non numerábel* se non é numerábel, é dicir, a súa cardinalidade é maior que \aleph_0.

## Introdución 
miniatura|125x125px| Mapa bixectivo de enteiros a números pares
Algúns conxuntos son *infinitos*; estes conxuntos teñen máis de n elementos onde n é calquera número enteiro que se poida especificar. Por exemplo, o conxunto de números naturais, que serían \{0, 1, 2, 3, 4, 5,\dots\},{{Efn|posto que hai unha bixección obvia entre \N e \N^*=\{1,2,3,\dots\}, non hai diferenza se consideramos o 0 como número natural ou non. Este artigo segue a convención de que o 0 é un número natural.}} 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:\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \cdotsou, máis xenralmente, 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 \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 S é *contábel* se existe unha bixección entre S e un subconxunto dos números naturais \N=\{0,1,2,\dots\}. 

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

: **Teorema:**  Todo subconxunto dun conxunto contábel é contábel. 

O conxunto de todos os pares ordenados de números naturais, o produto cartesiano de dous conxuntos de números naturais, \N\times\N é contabelmente infinito, como se pode ver seguindo un camiño como o da imaxe:
miniatura|300x300px| 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:
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.
O conxunto de todos os números enteiros \Z e o conxunto de todos os números racionais \Q intuitivamente poden parecer moito máis grandes que \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 (a/b onde a e b\neq 0 son enteiros), entón para cada fracción positiva, podemos chegar a un número natural distinto que lle corresponda.

: **Teorema:**  \Z (conxunto de todos os enteiros) e \Q (conxunto de todos os números racionais) son contábeis.{{efn|**Proba:** os enteiros \Z son contábeis porque a función f:\Z\to\N dada por f(n)=2^n se n é non-negativo e f(n)=3^{-n} se n e negativo, é unha función inxectiva. Os números racionais \Q son contábeis porque a función g:\Z\times\N\to\Q dada por g(m,n)=m/(n+1) é sobrexectiva desde o conxunto contábel \Z\times\N ata os números racionais \Q.}}

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

: **Teorema:**  Calquera unión finita de conxuntos countábeis é contábel.

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

miniatura|300x300px| Enumeración dun número contábel de conxuntos contábeis
Necesitamos o axioma de escolla contábel para indexar *todos* os conxuntos \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  S  e  T.
: Se a función  f:S \to T  é inxectiva e  T  é contábel, daquela  S  é contábel.
: Se a función  g:S \to T  é sobrexectiva e  S  é contábel, daquela T  é contábel.

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

**O teorema de Cantor** afirma que se A é un conxunto e \mathcal{P}(A) é o seu conxunto de partes, é dicir, o conxunto de todos os subconxuntos de A, entón non hai función sobrexectiva de A a \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 \mathcal{P}(\N) non é contábel; isto é, e non numerábel.

O conxunto dos números reais é non numerábel,  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*.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* 
*  Reprinted by Springer-Verlag, New York, 1974.  (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011.  (Paperback edition).
* 
* 
* 
* 

### Outros artigos 
* Número Aleph
* Paradoxo de Hilbert do Gran Hotel
* Conxunto non numerábel