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 incontábeis (ou 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 $\mathbb {N}$.
• Existe unha función inxectiva de $S$ a $\mathbb {N}$.
• $S$ é baleiro ou existe unha función sobrexectiva de $\mathbb {N}$ a $S$.
• Existe un mapeo bixectivo entre $S$ e un subconxunto de $\mathbb {N}$.
• $S$ é finito ( $|S|<\aleph _{0}$ ) 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 $\mathbb {N}$.
• $S$ ten unha correspondencia un a un con $\mathbb {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 é incontábel se non é contábel, é dicir, a súa cardinalidade é maior que $\aleph _{0}$.

Introdución

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 \}$, 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\,\cdots$$ou, 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 é incontá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 $\mathbb {N} =\{0,1,2,\dots \}$.

No caso dos conxuntos infinitos, un conxunto $S$ é contabelmente infinito se hai unha bixección entre $S$ e todo $\mathbb {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, $\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:$$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 $\mathbb {Z}$ e o conxunto de todos os números racionais $\mathbb {Q}$ intuitivamente poden parecer moito máis grandes que $\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 ($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:  $\mathbb {Z}$ (conxunto de todos os enteiros) e $\mathbb {Q}$ (conxunto de todos os números racionais) son contábeis.

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.

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}}(\mathbb {N} )$ non é contábel; isto é, e incontábel.

O conxunto dos números reais é incontá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.

Véxase tamén

Bibliografía

• Apostol, Tom M. (June 1969). Multi-Variable Calculus and Linear Algebra with Applications. Calculus 2 (2nd ed.). New York: John Wiley + Sons. ISBN 978-0-471-00007-5. 
• Avelsgaard, Carol (1990). Foundations for Advanced Mathematics. Scott, Foresman and Company. ISBN 0-673-38152-8. 
• Cantor, Georg (1878). Ein Beitrag zur Mannigfaltigkeitslehre. Journal für die Reine und Angewandte Mathematik 1878. pp. 242–248. doi:10.1515/crelle-1878-18788413. 
• Ferreirós, José (2007). Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised ed.). Birkhäuser. ISBN 978-3-7643-8349-7. 
• Fletcher, Peter; Patty, C. Wayne (1988). Foundations of Higher Mathematics. Boston: PWS-KENT Publishing Company. ISBN 0-87150-164-3. 
• Halmos, Paul R. (1960). Naive Set Theory. D. Van Nostrand Company, Inc.  Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).
• Kamke, Erich (1950). Theory of Sets. Dover series in mathematics and physics. New York: Dover. ISBN 978-0486601410. 
• Lang, Serge (1993). Real and Functional Analysis. Berlin, New York: Springer-Verlag. ISBN 0-387-94001-4. 
• Rudin, Walter (1976). Principles of Mathematical Analysis. New York: McGraw-Hill. ISBN 0-07-054235-X. 
• Tao, Terence (2016). "Infinite sets". Analysis I. Texts and Readings in Mathematics (en inglés) 37 (Third ed.). Singapore: Springer. pp. 181–210. ISBN 978-981-10-1789-6. doi:10.1007/978-981-10-1789-6_8. 

Outros artigos

• Número Aleph
• Paradoxo de Hilbert do Gran Hotel
• Conxunto incontábel