stringtranslate.com

Conjunto contable

En matemáticas , un conjunto es contable si es finito o puede hacerse una correspondencia biunívoca con el conjunto de números naturales . [a] De manera equivalente, un conjunto es contable si existe una función inyectiva de él en los números naturales; esto significa que cada elemento del conjunto puede estar asociado a un número natural único, o que los elementos del conjunto pueden contarse uno a uno, aunque el conteo puede no terminar nunca debido a un número infinito de elementos.

En términos más técnicos, asumiendo el axioma de elección contable , un conjunto es contable si su cardinalidad (el número de elementos del conjunto) no es mayor que la de los números naturales. Un conjunto contable que no es finito se dice que es contablemente infinito .

El concepto se atribuye a Georg Cantor , quien demostró la existencia de conjuntos incontables , es decir, conjuntos que no son contables; por ejemplo el conjunto de los números reales .

Una nota sobre la terminología

Aunque los términos "contable" y "contablemente infinito" como se definen aquí son bastante comunes, la terminología no es universal. [1] Un estilo alternativo utiliza contable para significar lo que aquí se llama contablemente infinito, y como máximo contable para significar lo que aquí se llama contable. [2] [3]

Los términos enumerable [4] y numerable [5] [6] también pueden usarse, por ejemplo, refiriéndose a contable y numerablemente infinito respectivamente, [7] las definiciones varían y se debe tener cuidado con respecto a la diferencia con recursivamente enumerable . [8]

Definición

Un conjunto es contable si:

Todas estas definiciones son equivalentes.

Un conjunto es infinito contablemente si:

Un conjunto es incontable si no es contable, es decir, su cardinalidad es mayor que . [9]

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. [16] En 1878, utilizó correspondencias uno a uno para definir y comparar cardinalidades. [17] En 1883, extendió los números naturales con sus ordinales infinitos y utilizó conjuntos de ordinales para producir una infinidad de conjuntos que tienen diferentes cardinalidades infinitas. [18]

Introducción

Un conjunto es una colección de elementos y puede describirse de muchas maneras. Una forma es simplemente enumerar todos sus elementos; por ejemplo, el conjunto que consta de los números enteros 3, 4 y 5 puede denotarse como , llamada forma de lista. [19] Sin embargo, esto solo es efectivo para conjuntos pequeños; para conjuntos más grandes, esto consumiría mucho tiempo y sería propenso a errores. En lugar de enumerar cada elemento individual, 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, presumiblemente denota el conjunto de números enteros del 1 al 100. Sin embargo, incluso en este caso, todavía es posible enumerar todos los elementos, porque el número de elementos en el conjunto es finito. Si numeramos los elementos del conjunto 1, 2, y así sucesivamente, hasta , esto nos da la definición habitual de "conjuntos de tamaño ".

Aplicación biyectiva de números enteros a pares

Algunos conjuntos son infinitos ; estos conjuntos tienen más de elementos donde es cualquier entero que se pueda especificar. (No importa cuán grande sea el entero especificado , como , los conjuntos infinitos tienen más de elementos). Por ejemplo, el conjunto de números naturales, denotable por , [a] tiene infinitos elementos, y no podemos usar ningún número natural para dar su tamaño. Puede parecer natural dividir los conjuntos en diferentes clases: poner todos los conjuntos que contienen un elemento juntos; todos los conjuntos que contienen dos elementos juntos; ...; finalmente, poner juntos todos los conjuntos infinitos y considerarlos como si tuvieran el mismo tamaño. Esta visión funciona bien para conjuntos infinitos contables y era la suposición predominante antes del trabajo de Georg Cantor. Por ejemplo, hay infinitos números enteros impares, infinitos números enteros pares y también infinitos números enteros en general. Podemos considerar que todos estos conjuntos tienen el mismo "tamaño" porque podemos organizar las cosas de manera que, para cada número entero, haya un número entero par distinto: o, de manera más general, (ver imagen). Lo que hemos hecho aquí es organizar los números enteros y los números pares en una correspondencia biyectiva (o biyección ), que es una función que se aplica entre dos conjuntos de modo que cada elemento de cada conjunto corresponde a un único elemento del otro conjunto. Esta noción matemática de "tamaño", cardinalidad, es que dos conjuntos son del mismo tamaño si y solo si hay una biyección entre ellos. Llamamos a todos los conjuntos que están en correspondencia biyectiva con los números enteros infinitos contables y decimos que tienen cardinalidad .

Georg Cantor demostró que no todos los conjuntos infinitos son numerables. Por ejemplo, los números reales no pueden ponerse en correspondencia biunívoca con los números naturales (enteros no negativos). El conjunto de los números reales tiene una cardinalidad mayor que el conjunto de los números naturales y se dice que es incontable.

Descripción formal

Por definición, un conjunto es numerable si existe una biyección entre y un subconjunto de los números naturales . Por ejemplo, defina la correspondencia Dado que cada elemento de está emparejado con precisamente un elemento de , y viceversa, esto define una biyección y muestra que es numerable. De manera similar, podemos demostrar que todos los conjuntos finitos son numerables.

En el caso de los conjuntos infinitos, un conjunto es numerablemente infinito si existe una biyección entre y todos los . Como ejemplos, considere los conjuntos , el conjunto de los números enteros positivos , y , el conjunto de los números enteros pares. Podemos demostrar que estos conjuntos son numerablemente infinitos al exhibir una biyección a los números naturales. Esto se puede lograr utilizando las asignaciones y , de modo que Todo conjunto numerablemente infinito es numerable, y todo conjunto numerable infinito es numerablemente infinito. Además, cualquier subconjunto de los números naturales es numerable, y de manera más general:

Teorema  :  Un subconjunto de un conjunto contable es contable. [20]

El conjunto de todos los pares ordenados de números naturales (el producto cartesiano de dos conjuntos de números naturales, es infinito contable, como se puede ver siguiendo un camino como el de la imagen:

La función de emparejamiento de Cantor asigna un número natural a cada par de números naturales.

El mapeo resultante procede de la siguiente manera:

Este mapeo cubre todos estos pares ordenados.

Esta forma de mapeo triangular se generaliza recursivamente a - tuplas de números naturales, es decir, donde y son números naturales, al mapear repetidamente los primeros dos elementos de una - tupla a un número natural. Por ejemplo, se puede escribir como . Luego se mapea a 5 por lo que se mapea a , luego se mapea a 39. Dado que una 2-tupla diferente, es decir, un par como , se mapea a un número natural diferente, una diferencia entre dos n-tuplas por un solo elemento es suficiente para asegurar que las n-tuplas se mapeen a diferentes números naturales. Entonces, se prueba una inyección del conjunto de - tuplas al conjunto de números naturales . Para el conjunto de - tuplas hecho 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 luego se aplica la misma lógica para probar el teorema.

Teorema  :  El producto cartesiano de un número finito de conjuntos numerables es numerable. [21] [b]

El conjunto de todos los números enteros y el conjunto de todos los números racionales pueden parecer intuitivamente mucho mayores que . Pero las apariencias engañan. Si un par se trata como numerador y denominador de una fracción vulgar (una fracción en la forma de donde y son números enteros), entonces para cada fracción positiva, podemos obtener un número natural distinto que le corresponde. Esta representación también incluye los números naturales, ya que cada número natural es también una fracción . Por lo tanto, 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.

Teorema  —  (el conjunto de todos los números enteros) y (el conjunto de todos los números racionales) son contables. [c]

De manera similar, el conjunto de números algebraicos es contable. [23] [d]

A veces es útil más de una aplicación: un conjunto que se va a mostrar como contable se asigna uno a uno (inyección) a otro conjunto , luego se demuestra que es contable si se asigna uno a uno 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 se asigna a . Dado que el conjunto de pares de números naturales se asigna uno a uno (en realidad, correspondencia uno a uno o biyección) al conjunto de números naturales como se muestra arriba, el conjunto de números racionales positivos se demuestra que es contable.

Teorema  —  Toda unión finita de conjuntos numerables es numerable. [24] [25] [e]

Con la previsión de saber que hay conjuntos incontables, podemos preguntarnos si este último resultado puede llevarse más lejos. La respuesta es "sí" y "no", podemos extenderlo, pero para ello necesitamos suponer un nuevo axioma.

Teorema  —  (Suponiendo el axioma de elección contable ) La unión de un número contable de conjuntos contables es contable. [f]

Enumeración para un número contable de conjuntos contables

Por ejemplo, dados conjuntos contables , primero asignamos a cada elemento de cada conjunto una tupla, luego asignamos a cada tupla un índice usando una variante de la enumeración triangular que vimos arriba:

Necesitamos el axioma de elección contable para indexar todos los conjuntos 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, de longitud 2 y de longitud 3, cada una de las cuales es un conjunto numerable (producto cartesiano finito). Por lo tanto, estamos hablando de una unión numerable de conjuntos numerables, que es numerable según 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 una cantidad contable de secuencias finitas, por lo que también hay una cantidad contable de subconjuntos finitos.

Teorema  —  Sean y conjuntos.

  1. Si la función es inyectiva y es contable entonces es contable.
  2. Si la función es sobreyectiva y es contable entonces es contable.

Estos se desprenden de las definiciones de conjunto contable como funciones inyectivas/sobreyectivas. [g]

El teorema de Cantor afirma que sies un conjunto yes su conjunto potencia , es decir, el conjunto de todos los subconjuntos de, entonces no existe ninguna función sobreyectiva dea. Se ofrece una prueba en el artículo Teorema de Cantor . Como consecuencia inmediata de esto y del Teorema Básico anterior tenemos:

Proposición  —  El conjunto no es contable; es decir, es incontable .

Para una elaboración de este resultado véase el argumento diagonal de Cantor .

El conjunto de números reales es incontable, [h] y también lo es el conjunto de todas las secuencias infinitas de números naturales.

El modelo mínimo de la teoría de conjuntos es contable

Si existe un conjunto que es un modelo estándar (ver modelo interno ) de la teoría de conjuntos ZFC, entonces existe 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 numerable. El hecho de que la noción de "incontabilidad" tenga sentido incluso en este modelo, y en particular que este modelo M contenga elementos que son:

Fue visto como paradójico en los primeros días de la teoría de conjuntos; véase 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.

Pedidos totales

Los conjuntos contables se pueden ordenar totalmente de varias maneras, por ejemplo:

En ambos ejemplos de órdenes bien definidos, cualquier subconjunto tiene un elemento mínimo ; y en ambos ejemplos de órdenes no bien definidos, algunos subconjuntos no tienen un elemento mínimo . Esta es la definición clave que determina si un orden total también es un orden bien definido.

Véase también

Notas

  1. ^ ab Dado que existe una biyección obvia entre y , no hay diferencia si se considera que 0 es 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 considera que 0 es un número natural.
  2. ^ Prueba: Obsérvese que es contable como consecuencia de la definición porque la función dada por es inyectiva. [22] Entonces se sigue que el producto cartesiano de dos conjuntos contables cualesquiera es contable, porque si y son dos conjuntos contables hay sobreyecciones y . Por lo tanto es una sobreyección del conjunto contable al conjunto y el Corolario implica que es contable. Este resultado se generaliza al producto cartesiano de cualquier colección finita de conjuntos contables y la prueba se sigue por inducción sobre el número de conjuntos en la colección.
  3. ^ Demostración: Los números enteros son contables porque la función dada por si es no negativa y si es negativa, es una función inyectiva. Los números racionales son contables porque la función dada por es una sobreyección del conjunto contable a los racionales .
  4. ^ Demostración: 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 , sea un polinomio con coeficientes enteros tal que es la raíz -ésima del polinomio, donde las raíces se ordenan por valor absoluto de menor a mayor, luego se ordenan por argumento de menor a mayor. Podemos definir una función de inyección (es decir, uno a uno) dada por , donde es el primo -ésimo .
  5. ^ Demostración: Si es un conjunto numerable para cada uno de , entonces para cada uno existe una función sobreyectiva y, por lo tanto, la función dada por es una sobreyección. Como es numerable, la unión es numerable.
  6. ^ Prueba : Como en el caso finito, pero y usamos el axioma de elección contable para elegir para cada uno en una sobreyección de la colección no vacía de sobreyecciones de a . [26] Nótese que dado que estamos considerando la sobreyección , en lugar de una inyección, no hay ningún requisito de que los conjuntos sean disjuntos.
  7. ^ Demostración : Para (1) observe que si es contable existe una función inyectiva . Entonces, si es inyectiva la composición es inyectiva, por lo que es contable. Para (2) observe que si es contable, o bien está vacía o existe una función sobreyectiva . Entonces, si es sobreyectiva, o bien y están vacías, o bien la composición es sobreyectiva. En cualquier caso es contable.
  8. ^ Véase la primera prueba de incontabilidad de Cantor y también la Propiedad de intersección finita#Aplicaciones para una prueba topológica.

Citas

  1. ^ Manetti, Marco (19 de junio de 2015). Topología. Saltador. pag. 26.ISBN​ 978-3-319-16958-3.
  2. ^ Rudin 1976, Capítulo 2
  3. ^ Tao 2016, pág. 181
  4. ^ Kamke 1950, pág. 2
  5. ^ ab Lang 1993, §2 del Capítulo I
  6. ^ Apostol 1969, p. 23, Capítulo 1.14
  7. ^ Thierry, Vialar (4 de abril de 2017). Manual de matemáticas. BoD - Libros a pedido. p. 24. ISBN 978-2-9551990-1-5.
  8. ^ Mukherjee, Subir Kumar (2009). Primer curso de análisis real. Academic Publishers. pág. 22. ISBN 978-81-89781-90-3.
  9. ^ abc Yaqub, Aladdin M. (24 de octubre de 2014). Introducción a la metalógica. Broadview Press. ISBN 978-1-4604-0244-3.
  10. ^ Singh, Tej Bahadur (17 de mayo de 2019). Introducción a la topología. Springer. pág. 422. ISBN 978-981-13-6954-4.
  11. ^ ab Katzourakis, Nikolaos; Varvaruca, Eugen (2 de enero de 2018). Una introducción ilustrativa al análisis moderno. CRC Press. ISBN 978-1-351-76532-9.
  12. ^ Halmos 1960, pág. 91
  13. ^ Kamke 1950, pág. 2
  14. ^ Dlab, Vlastimil; Williams, Kenneth S. (9 de junio de 2020). Invitación al álgebra: un compendio de recursos para profesores, estudiantes universitarios avanzados y estudiantes de posgrado en matemáticas. World Scientific. pág. 8. ISBN 978-981-12-1999-3.
  15. ^ Tao 2016, pág. 182
  16. ^ Stillwell, John C. (2010), Caminos hacia el infinito: las matemáticas de la verdad y la prueba, CRC Press, pág. 10, ISBN 9781439865507El descubrimiento de los conjuntos incontables por parte de Cantor en 1874 fue uno de los acontecimientos más inesperados en la historia de las matemáticas. Antes de 1874, la mayoría de la gente ni siquiera consideraba el infinito un tema matemático legítimo, por lo que ni siquiera se podía imaginar la necesidad de distinguir entre infinitos contables e incontables.
  17. ^ Cantor 1878, pág. 242.
  18. ^ Ferreirós 2007, págs. 268, 272-273.
  19. ^ "¿Qué son los sets y la forma de la plantilla?". expii . 2021-05-09. Archivado desde el original el 2020-09-18.
  20. ^ Halmos 1960, pág. 91
  21. ^ Halmos 1960, pág. 92
  22. ^ Avelsgaard 1990, pág. 182
  23. ^ Kamke 1950, págs. 3-4
  24. ^ Avelsgaard 1990, pág. 180
  25. ^ Fletcher y Patty 1988, pág. 187
  26. ^ Hrbacek, Karel; Jech, Thomas (22 de junio de 1999). Introducción a la teoría de conjuntos, tercera edición, revisada y ampliada. CRC Press. pág. 141. ISBN 978-0-8247-7915-3.

Referencias