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, é 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}$ . ^[1]
Existe unha función inxectiva de $S$ a $\mathbb {N}$ .^[2]^[3]
$S$ é baleiro ou existe unha función sobrexectiva de $\mathbb {N}$ a $S$ . ^[3]
Existe un mapeo bixectivo entre $S$ e un subconxunto de $\mathbb {N}$ .^[4]
$S$ é finito ( $|S|<\aleph _{0}$ ) ou contabelmente infinito. ^[5]

Todas estas definicións son equivalentes.

Un conxunto $S$ é contabelmente infinito se:

A súa cardinalidade $|S|$ é exactamente $\aleph _{0}$ .^[1]
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}$ .^[6]
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.^[7]^[8]

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

Introdución

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 \}$ ,^[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: $\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. ^[9]

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:

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.^[10]

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.^[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 ${\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, ^[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.

Notas

↑ ^1,0 ^1,1 ^1,2 Yaqub, Aladdin M. (24 October 2014). An Introduction to Metalogic (en inglés). Broadview Press. ISBN 978-1-4604-0244-3.
↑ Singh, Tej Bahadur (17 May 2019). Introduction to Topology (en inglés). Springer. p. 422. ISBN 978-981-13-6954-4.
↑ ^3,0 ^3,1 Katzourakis, Nikolaos; Varvaruca, Eugen (2 January 2018). An Illustrative Introduction to Modern Analysis (en inglés). CRC Press. ISBN 978-1-351-76532-9.
↑ Halmos 1960
↑ Lang 1993
↑ Kamke 1950
↑ Dlab, Vlastimil; Williams, Kenneth S. (9 June 2020). Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics (en inglés). World Scientific. p. 8. ISBN 978-981-12-1999-3.
↑ Tao 2016, p. 182
↑ Halmos 1960, p. 91
↑ Halmos 1960, p. 92
↑ Kamke 1950
↑ Avelsgaard 1990, p. 180
↑ Fletcher & Patty 1988, p. 187
↑ Hrbacek, Karel; Jech, Thomas (22 June 1999). Introduction to Set Theory, Third Edition, Revised and Expanded (en inglés). CRC Press. p. 141. ISBN 978-0-8247-7915-3.

↑ posto que hai unha bixección obvia entre $\mathbb {N}$ e $\mathbb {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.
↑ Proba: os enteiros $\mathbb {Z}$ son contábeis porque a función $f:\mathbb {Z} \to \mathbb {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 $\mathbb {Q}$ son contábeis porque a función $g:\mathbb {Z} \times \mathbb {N} \to \mathbb {Q}$ dada por $g(m,n)=m/(n 1)$ é sobrexectiva desde o conxunto contábel $\mathbb {Z} \times \mathbb {N}$ ata os números racionais $\mathbb {Q}$ .
↑ Vexa en:Cantor's first uncountability proof, e tamén en:Finite intersection property#Applications para unha proba topolóxica.

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

[Yaqub-1] 1,0 ^1,1 ^1,2 Yaqub, Aladdin M. (24 October 2014). An Introduction to Metalogic (en inglés). Broadview Press. ISBN 978-1-4604-0244-3.

[Singh-2] Singh, Tej Bahadur (17 May 2019). Introduction to Topology (en inglés). Springer. p. 422. ISBN 978-981-13-6954-4.

[Katzourakis-3] 3,0 ^3,1 Katzourakis, Nikolaos; Varvaruca, Eugen (2 January 2018). An Illustrative Introduction to Modern Analysis (en inglés). CRC Press. ISBN 978-1-351-76532-9.

[4] Halmos 1960

[Lang-5] Lang 1993

[6] Kamke 1950

[7] Dlab, Vlastimil; Williams, Kenneth S. (9 June 2020). Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics (en inglés). World Scientific. p. 8. ISBN 978-981-12-1999-3.

[8] Tao 2016, p. 182

[10] Halmos 1960, p. 91

[11] Halmos 1960, p. 92

[13] Kamke 1950

[14] Avelsgaard 1990, p. 180

[15] Fletcher & Patty 1988, p. 187

[16] Hrbacek, Karel; Jech, Thomas (22 June 1999). Introduction to Set Theory, Third Edition, Revised and Expanded (en inglés). CRC Press. p. 141. ISBN 978-0-8247-7915-3.

[9] sto que hai unha bixección obvia entre $\mathbb {N}$ e $\mathbb {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.

[12] Proba: os enteiros $\mathbb {Z}$ son contábeis porque a función $f:\mathbb {Z} \to \mathbb {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 $\mathbb {Q}$ son contábeis porque a función $g:\mathbb {Z} \times \mathbb {N} \to \mathbb {Q}$ dada por $g(m,n)=m/(n 1)$ é sobrexectiva desde o conxunto contábel $\mathbb {Z} \times \mathbb {N}$ ata os números racionais $\mathbb {Q}$ .

[17] Vexa en:Cantor's first uncountability proof, e tamén en:Finite intersection property#Applications para unha proba topolóxica.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[a]

[9]

[10]

[b]

[11]

[12]

[13]

[14]

[c]