En matemáticas , un conjunto contable es un conjunto con la misma cardinalidad ( número de elementos) que algún subconjunto del conjunto de números naturales . Un conjunto contable es un conjunto finito o un conjunto infinito contable . Ya sea finito o infinito, los elementos de un conjunto contable siempre se pueden contar uno a la vez y, aunque es posible que el conteo nunca termine, cada elemento del conjunto está asociado con un número natural único.
Algunos autores usan conjunto contable para significar numerablemente infinito solo. [1] Para evitar esta ambigüedad, el término como máximo contable puede usarse cuando se incluyen conjuntos finitos y son numerables infinitos , enumerables , [2] o numerables [3] en caso contrario.
Georg Cantor introdujo el término conjunto contable , contrastando conjuntos que son contables con aquellos que son incontables (es decir, no numerables o no numerables [4] ). Hoy en día, los conjuntos contables forman la base de una rama de las matemáticas llamada matemáticas discretas .
Definición
Un conjunto S es contable si existe una función inyectiva f de S a los números naturales N = {0, 1, 2, 3, ... }. [ cita requerida ] [5]
Si se puede encontrar una f que también sea sobreyectiva (y por lo tanto biyectiva ), entonces S se llama infinito numerable .
En otras palabras, un conjunto es infinito numerable si tiene uno-a-uno correspondencia con el conjunto de número natural, N . En cuyo caso, la cardinalidad del conjunto se denota( aleph-null ): el primero de la serie de números aleph. [6]
Esta terminología no es universal. Algunos autores usan contable para significar lo que aquí se llama infinito numerable y no incluyen conjuntos finitos.
También se pueden dar formulaciones alternativas (equivalentes) de la definición en términos de una función biyectiva o una función sobreyectiva . [7] Véase también § Resumen formal sin detalles a continuación.
Historia
En 1874, en su primer artículo de teoría de conjuntos , Cantor demostró que el conjunto de números reales es incontable, mostrando así que no todos los conjuntos infinitos son contables. [8] En 1878, utilizó correspondencias uno a uno para definir y comparar cardinalidades. [9] En 1883, amplió los números naturales con sus ordinales infinitos y usó conjuntos de ordinales para producir una infinidad de conjuntos que tienen cardinalidades infinitas diferentes. [10]
Introducción
Un conjunto es una colección de elementos y puede describirse de muchas formas. Una forma es simplemente enumerar todos sus elementos; por ejemplo, el conjunto que consta de los números enteros 3, 4 y 5 puede denominarse {3, 4, 5}, llamado forma de lista. [11] Sin embargo, esto solo es efectivo para conjuntos pequeños; para conjuntos más grandes, esto llevaría mucho tiempo y sería propenso a errores. En lugar de enumerar todos los elementos, a veces se usa una elipsis ("...") para representar muchos elementos entre el elemento inicial y el elemento final en un conjunto, si el escritor cree que el lector puede adivinar fácilmente qué representa ... ; por ejemplo, {1, 2, 3, ..., 100} presumiblemente denota el conjunto de números enteros del 1 al 100. Incluso en este caso, sin embargo, todavía es posible enumerar todos los elementos, porque el número de elementos en el el conjunto es finito.
Algunos conjuntos son infinitos ; estos conjuntos tienen más de n elementos donde n es cualquier número entero que se pueda especificar. (No importa qué tan grande sea el entero n especificado , como n = 9 × 10 32 , los conjuntos infinitos tienen más de n elementos). Por ejemplo, el conjunto de números naturales, denotables por {0, 1, 2, 3, 4 , 5, ...}, tiene una cantidad infinita de elementos y no podemos usar ningún número natural para dar su tamaño. No obstante, resulta que los conjuntos infinitos tienen una noción bien definida de tamaño (o más propiamente, cardinalidad , el término técnico para el número de elementos en un conjunto), y no todos los conjuntos infinitos tienen la misma cardinalidad.
Para comprender lo que esto significa, primero examinamos lo que no significa. Por ejemplo, hay infinitos números enteros impares, infinitos números enteros pares y (por lo tanto) infinitos números enteros en general. Sin embargo, resulta que el número de enteros pares, que es el mismo que el número de enteros impares, también es el mismo que el número de enteros en general. Esto se debe a que podemos organizar las cosas de modo que, para cada entero, haya un entero par distinto:
Sin embargo, no todos los conjuntos infinitos tienen la misma cardinalidad. Por ejemplo, Georg Cantor (quien introdujo este concepto) demostró que los números reales no se pueden poner en correspondencia uno a uno con los números naturales (enteros no negativos) y, por lo tanto, el conjunto de números reales tiene una cardinalidad mayor que el conjunto de números naturales.
Un conjunto es contable si: (1) es finito, o (2) tiene la misma cardinalidad (tamaño) que el conjunto de números naturales (es decir, numerable). [12] De manera equivalente, un conjunto es contable si tiene la misma cardinalidad que algún subconjunto del conjunto de números naturales. De lo contrario, es incontable .
Resumen formal sin detalles
Por definición, un conjunto S es contable si existe una función inyectiva f : S → N de S a los números naturales N = {0, 1, 2, 3, ...}. Simplemente significa que cada elemento en S tiene correspondencia con un elemento diferente en N .
Puede parecer natural dividir los conjuntos en diferentes clases: juntar todos los conjuntos que contienen un elemento; todos los conjuntos que contienen dos elementos juntos; ...; finalmente, junte todos los conjuntos infinitos y considérelos del mismo tamaño. Sin embargo, esta opinión no es sostenible bajo la definición natural de tamaño.
Para elaborar esto, necesitamos el concepto de biyección . Aunque una "biyección" parece un concepto más avanzado que un número, el desarrollo habitual de las matemáticas en términos de teoría de conjuntos define funciones antes que números, ya que se basan en conjuntos mucho más simples. Aquí es donde entra el concepto de biyección: definir la correspondencia
- a ↔ 1, b ↔ 2, c ↔ 3
Dado que cada elemento de { a , b , c } está emparejado con precisamente un elemento de {1, 2, 3} y viceversa, esto define una biyección.
Ahora generalizamos esta situación; nos definimos que dos conjuntos son del mismo tamaño, si y sólo si existe una biyección entre ellos. Para todos los conjuntos finitos, esto nos da la definición habitual de "el mismo tamaño".
En cuanto al caso de los conjuntos infinitos, considere los conjuntos A = {1, 2, 3, ...}, el conjunto de enteros positivos , y B = {2, 4, 6, ...}, el conjunto de pares enteros positivos. Afirmamos que, según nuestra definición, estos conjuntos tienen el mismo tamaño y que, por lo tanto, B es numerablemente infinito. Recuerde que para probar esto, necesitamos exhibir una biyección entre ellos. Esto se puede lograr usando la asignación n ↔ 2 n , de modo que
- 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....
Como en el ejemplo anterior, cada elemento de A se ha emparejado con precisamente un elemento de B, y viceversa. De ahí que tengan el mismo tamaño. Este es un ejemplo de un conjunto del mismo tamaño que uno de sus subconjuntos propios , lo cual es imposible para conjuntos finitos.
Asimismo, el conjunto de todos los pares ordenados de números naturales (el producto cartesiano de dos conjuntos de números naturales, N × N ) es numerablemente infinito, como se puede ver siguiendo un camino como el de la imagen:
El mapeo resultante procede de la siguiente manera:
- 0 ↔ (0, 0), 1 ↔ (1, 0), 2 ↔ (0, 1), 3 ↔ (2, 0), 4 ↔ (1, 1), 5 ↔ (0, 2), 6 ↔ (3, 0), ....
Este mapeo cubre todos esos pares ordenados.
Si un par se trata como el numerador y denominador de una fracción vulgar (una fracción en forma de a / b donde a y b ≠ 0 son números enteros), entonces para cada fracción positiva, podemos obtener un número natural distinto correspondiente lo. Esta representación también incluye los números naturales, ya que cada número natural es también una fracción N / 1. Entonces podemos concluir que hay exactamente tantos números racionales positivos como enteros positivos. Esto también es cierto para todos los números racionales, como se puede ver a continuación.
A veces, más de un mapeo es útil: un conjunto A que se muestra como contable es uno a uno mapeado (inyección) a otro conjunto B, entonces A se demuestra como contable si B es uno a uno mapeado al conjunto de números naturales. Por ejemplo, el conjunto de números racionales positivos se puede asignar fácilmente uno a uno al conjunto de pares de números naturales (2-tuplas) porque p / q se asigna a ( p , q ). Dado que el conjunto de pares de números naturales se asigna uno a uno (en realidad, correspondencia o biyección uno a uno) al conjunto de números naturales como se muestra arriba, el conjunto de números racionales positivos se demuestra como contable.
Teorema: El producto cartesiano de un número finito de conjuntos contables es contable.
Esta forma de mapeo triangular se generaliza recursivamente a n - tuplas de números naturales, es decir, ( a 1 , a 2 , a 3 , ..., a n ) donde a i y n son números naturales, al mapear repetidamente los dos primeros elementos de una n- tupla a un número natural. Por ejemplo, (0, 2, 3) se puede escribir como ((0, 2), 3). Luego (0, 2) se asigna a 5, por lo que ((0, 2), 3) se asigna a (5, 3), luego (5, 3) se asigna a 39. Dado que una 2-tupla diferente, es un par como ( a , b ), se asigna a un número natural diferente, una diferencia entre dos n-tuplas por un solo elemento es suficiente para garantizar que las n-tuplas se asignan a diferentes números naturales. Entonces, se prueba una inyección del conjunto de n tuplas al conjunto de números naturales N. Para el conjunto de n-tuplas formado por el producto cartesiano de un número finito de conjuntos diferentes, cada elemento en cada tupla tiene la correspondencia con un número natural, por lo que cada tupla se puede escribir en números naturales y luego se aplica la misma lógica para demostrar el teorema .
El siguiente teorema se refiere a subconjuntos infinitos de conjuntos infinitos numerables.
Teorema: Cada subconjunto de un conjunto contable es contable. En particular, cada subconjunto infinito de un conjunto infinito numerable es infinito numerable. [13]
Por ejemplo, el conjunto de números primos es contable, mediante la asignación de la n -ésima número primo a n :
- 2 mapas a 1
- 3 mapas a 2
- 5 mapas a 3
- 7 mapas a 4
- 11 mapas a 5
- 13 mapas a 6
- 17 mapas a 7
- 19 mapas a 8
- 23 mapas a 9
- ...
También hay conjuntos que son "naturalmente mayor que" N . Por ejemplo, Z el conjunto de todos los números enteros o Q , el conjunto de todos los números racionales , que intuitivamente puede parecer mucho más grande que N . Pero las apariencias engañan, porque afirmamos:
Teorema: Z (el conjunto de todos los números enteros) y Q (el conjunto de todos los números racionales) son contables.
De manera similar, el conjunto de números algebraicos es contable. [14]
Estos hechos se derivan fácilmente de un resultado que muchas personas encuentran poco intuitivo.
Teorema: cualquier unión finita de conjuntos contables es contable.
Con la previsión de saber que hay innumerables conjuntos, podemos preguntarnos si este último resultado puede llevarse más lejos. La respuesta es "sí" y "no", podemos extenderla, pero necesitamos asumir un nuevo axioma para hacerlo.
Teorema: (Suponiendo el axioma de elección contable ) La unión de muchos conjuntos contables es contable.
Por ejemplo, dados conjuntos contables a , b , c , ...
Usando una variante de la enumeración triangular que vimos arriba:
- a 0 se asigna a 0
- a 1 se asigna a 1
- b 0 se asigna a 2
- a 2 mapas a 3
- b 1 se asigna a 4
- c 0 se asigna a 5
- a 3 mapas a 6
- b 2 se asigna a 7
- c 1 se asigna a 8
- d 0 se asigna a 9
- a 4 mapas a 10
- ...
Esto solo funciona si los conjuntos a , b , c , ... son disjuntos . De lo contrario, la unión es aún menor y, por lo tanto, también es contable mediante un teorema anterior.
Necesitamos el axioma de elección contable para indexar todos los conjuntos a , b , c , ... simultáneamente.
Teorema: El conjunto de todas las secuencias de números naturales de longitud finita es contable.
Este conjunto es la unión de las secuencias de longitud 1, las secuencias de longitud 2, las secuencias de longitud 3, cada una de las cuales es un conjunto contable (producto cartesiano finito). Entonces estamos hablando de una unión contable de conjuntos contables, que es contable por el teorema anterior.
Teorema: El conjunto de todos los subconjuntos finitos de los números naturales es contable.
Los elementos de cualquier subconjunto finito se pueden ordenar en una secuencia finita. Solo hay un número numerable de secuencias finitas, por lo que también hay un número numerable de subconjuntos finitos.
El siguiente teorema da formulaciones equivalentes en términos de una función biyectiva o una función sobreyectiva . Una prueba de este resultado se puede encontrar en el texto de Lang. [3]
Teorema (básico): Sea S un conjunto. Las siguientes declaraciones son equivalentes:
- S es contable, es decir, existe una función inyectiva f : S → N .
- Cualquiera de S está vacío o existe una función sobreyectiva g : N → S .
- Cualquiera de S es finita o existe una biyección h : N → S .
Corolario: Sean S y T conjuntos.
- Si la función f : S → T es inyectiva y T es contable, entonces S es contable.
- Si la función g : S → T es sobreyectiva y S es contable, entonces T es contable.
El teorema de Cantor afirma que si A es un conjunto y P ( A ) es su conjunto de potencias , es decir, el conjunto de todos los subconjuntos de A , entonces no hay función sobreyectiva de A a P ( A ). Se da una demostración en el artículo Teorema de Cantor . Como consecuencia inmediata de esto y del Teorema básico anterior tenemos:
Proposición: El conjunto P ( N ) no es contable; es decir, es incontable .
Para una elaboración de este resultado, consulte el argumento diagonal de Cantor .
El conjunto de números reales es incontable (ver la primera prueba de incontablecimiento de Cantor ), y también lo es el conjunto de todas las secuencias infinitas de números naturales.
Algunos detalles técnicos
Las pruebas de los enunciados de la sección anterior se basan en la existencia de funciones con ciertas propiedades. Esta sección presenta las funciones que se usan comúnmente en este rol, pero no las verificaciones de que estas funciones tienen las propiedades requeridas. El teorema básico y su corolario se utilizan a menudo para simplificar demostraciones. Observe que N en ese teorema se puede reemplazar con cualquier conjunto infinito numerable.
Proposición: cualquier conjunto finito es contable.
Prueba: Sea S tal conjunto. Se deben considerar dos casos: o S está vacío o no lo está. 1.) El conjunto vacío es incluso en sí mismo un subconjunto de los números naturales, por lo que es contable. 2.) Si S es no vacío y finito, entonces, por definición de finitud, hay una biyección entre S y el conjunto {1, 2, ..., n } para algún número natural positivo n . Esta función es una inyección de S en N .
Proposición: cualquier subconjunto de un conjunto contable es contable. [15]
Prueba: la restricción de una función inyectiva a un subconjunto de su dominio sigue siendo inyectiva.
Proposición: Si S es un conjunto contable, S ∪ { x } es contable. [dieciséis]
Prueba: Si x ∈ S no hay nada que mostrar. De lo contrario, sea f : S → N una inyección. Definir g : S ∪ { x } → N por g ( x ) = 0 y g ( y ) = f ( y ) + 1 para todos y en S . Esta función g es una inyección.
Proposición: Si A y B son conjuntos contables, entonces A ∪ B es contable. [17]
Prueba: Let f : A → N y g : B → N sea inyecciones. Definir una nueva inyección h : A ∪ B → N por h ( x ) = 2 f ( x ) si x está en A y h ( x ) = 2 g ( x ) + 1 si x está en B , pero no en A .
Proposición: El producto cartesiano de dos conjuntos contables A y B es contable. [18]
Prueba: Observe que N × N es contable como consecuencia de la definición porque la función f : N × N → N dada por f ( m , n ) = 2 m 3 n es inyectiva. [19] A continuación, se deduce del teorema básico y el corolario que el producto cartesiano de dos conjuntos contables cualesquiera es contable. Esto se deduce porque si A y B son contables hay surjections f : N → A y g : N → B . Entonces
- f × g : N × N → A × B
es una sobreyección del conjunto contable N × N al conjunto A × B y el corolario implica que A × B es contable. Este resultado se generaliza al producto cartesiano de cualquier colección finita de conjuntos contables y la prueba sigue por inducción sobre el número de conjuntos en la colección.
Proposición: Los números enteros Z son contables y los números racionales Q son contables.
Prueba: Los números enteros Z son contables porque la función f : Z → N dada por f ( n ) = 2 n si n es no negativo y f ( n ) = 3 - n si n es negativo, es una función inyectiva. Los números racionales Q son contables porque la función g : Z × N → Q dada por g ( m , n ) = m / ( n + 1) es una surjection del conjunto numerable Z × N a los racionales Q .
Proposición: Los números algebraicos A son contables.
Prueba: por definición, cada número algebraico (incluidos los números complejos) es una raíz de un polinomio con coeficientes enteros. Dado un número algebraico, dejar ser un polinomio con coeficientes enteros tales que es la k- ésima raíz del polinomio, donde las raíces se ordenan por valor absoluto de pequeña a grande, luego se ordenan por argumento de pequeña a grande. Podemos definir una función de inyección (es decir, uno a uno) f : A → Q dada por, tiempo es el n -ésimo primo .
Proposición: Si A n es un conjunto contable para cada n en N, entonces la unión de todos A n también es contable. [20]
Prueba: Esto es una consecuencia del hecho de que para cada n hay una función sobreyectiva g n : N → A n y por lo tanto la función
dado por G ( n , m ) = g n ( m ) es una sobreyección. Dado que N × N es contable, el corolario implica que la unión es contable. Usamos el axioma de elección contable en esta demostración para elegir para cada n en N una sobreyección g n de la colección no vacía de sobreyecciones de N a A n .
Una prueba topológica de la incontables números reales se describe en la propiedad de intersección finita .
El modelo mínimo de teoría de conjuntos es contable
Si hay un conjunto que es un modelo estándar (ver modelo interno ) de la teoría de conjuntos ZFC, entonces hay un modelo estándar mínimo ( ver Universo construible ). El teorema de Löwenheim-Skolem se puede utilizar para demostrar que este modelo mínimo es contable. El hecho de que la noción de "incontables" tiene sentido incluso en este modelo, y en particular que este modelo M contiene elementos que son:
- subconjuntos de M , por lo tanto contables,
- pero incontable desde el punto de vista de M ,
fue visto como paradójico en los primeros días de la teoría de conjuntos, ver la paradoja de Skolem para más información.
El modelo estándar mínimo incluye todos los números algebraicos y todos los números trascendentales efectivamente computables , así como muchos otros tipos de números.
Órdenes totales
Los juegos contables se pueden pedir totalmente de varias formas, por ejemplo:
- Órdenes de pozo (ver también el número ordinal ):
- El orden habitual de los números naturales (0, 1, 2, 3, 4, 5, ...)
- Los enteros en el orden (0, 1, 2, 3, ...; −1, −2, −3, ...)
- Otros ( órdenes no bien):
- El orden habitual de los enteros (..., −3, −2, −1, 0, 1, 2, 3, ...)
- El orden habitual de los números racionales (¡no se puede escribir explícitamente como una lista ordenada!)
En ambos ejemplos de órdenes de pozo aquí, cualquier subconjunto tiene un elemento mínimo ; y en ambos ejemplos de órdenes de no pozos, algunos subconjuntos no tienen un elemento mínimo . Esta es la definición clave que determina si un pedido total también es un pedido de pozo.
Ver también
- Número de Aleph
- Contando
- La paradoja de Hilbert del Grand Hotel
- Conjunto incontable
Notas
- ↑ Rudin 1976 , Capítulo 2
- ↑ Kamke , 1950 , pág. 2
- ^ a b Lang 1993 , § 2 del Capítulo I
- ↑ Apostol 1969 , Capítulo 13.19
- ^ Dado que hay una biyección obviaentre N y N * = {1, 2, 3, ... }, no importa si uno considera 0 un número natural o no. En cualquier caso, este artículo sigue la norma ISO 31-11 y la convención estándar en lógica matemática , que toma 0 como número natural.
- ^ "Lista completa de símbolos de teoría de conjuntos" . Bóveda de matemáticas . 2020-04-11 . Consultado el 6 de septiembre de 2020 .
- ^ Halmos 1960 , p. 91, llama a S contable siexisteun mapeo biyectivo entre un subconjunto de S y N. Kamke 1950 , pág. 2, requiere una biyectiva entre S y N .
- ^ Stillwell, John C. (2010), Roads to Infinity: The Mathematics of Truth and Proof , CRC Press, p. 10, ISBN 9781439865507,
El descubrimiento de Cantor de conjuntos numerables en 1874 fue uno de los eventos más inesperados en la historia de las matemáticas. Antes de 1874, el infinito ni siquiera era considerado un tema matemático legítimo por la mayoría de la gente, por lo que no se podía haber imaginado la necesidad de distinguir entre infinitos contables e incontables.
- ^ Cantor 1878, p. 242.
- ^ Ferreirós 2007, págs. 268, 272-273.
- ^ "¿Qué son los conjuntos y la forma de la lista?" . expii . 2021-05-09.
- ^ Weisstein, Eric W. "Conjunto contable" . mathworld.wolfram.com . Consultado el 6 de septiembre de 2020 .
- ^ "9.2: Conjuntos contables" . Matemáticas LibreTexts . 2017-09-20 . Consultado el 6 de septiembre de 2020 .
- ^ Kamke 1950 , págs. 3-4
- ^ Halmos 1960 , p. 91
- ^ Avelsgaard 1990 , p. 179
- ^ Avelsgaard 1990 , p. 180
- ^ Halmos 1960 , p. 92
- ^ Avelsgaard 1990 , p. 182
- ^ Fletcher y Patty 1988 , p. 187
Referencias
- Apostol, Tom M. (junio de 1969), Cálculo multivariable y álgebra lineal con aplicaciones , Cálculo, 2 (2a ed.), Nueva York: John Wiley + Sons, ISBN 978-0-471-00007-5
- Avelsgaard, Carol (1990), Fundamentos para matemáticas avanzadas , 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 (84): 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 (2a ed. Revisada), Birkhäuser, ISBN 978-3-7643-8349-7
- Fletcher, Peter; Patty, C. Wayne (1988), Fundamentos de las matemáticas superiores , Boston: PWS-KENT Publishing Company, ISBN 0-87150-164-3
- Halmos, Paul R. (1960), Teoría de conjuntos ingenua , D. Van Nostrand Company, Inc Reimpreso por Springer-Verlag, Nueva York, 1974. ISBN 0-387-90092-6 (edición Springer-Verlag). Reimpreso por Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (edición de bolsillo).
- Kamke, Erich (1950), Teoría de conjuntos , serie Dover en matemáticas y física, Nueva York: Dover, ISBN 978-0486601410
- Lang, Serge (1993), Real and Functional Analysis , Berlín, Nueva York: Springer-Verlag, ISBN 0-387-94001-4
- Rudin, Walter (1976), Principios del análisis matemático , Nueva York: McGraw-Hill, ISBN 0-07-054235-X