Conjunto contable

Un conjunto matemático es numerable si es finito o si se puede establecer una correspondencia biunívoca con el conjunto de los números naturales . ^{[ a ]} De manera equivalente, un conjunto es numerable si existe una función inyectiva del mismo en los números naturales; esto significa que cada elemento del conjunto puede asociarse a un único número natural, o que los elementos del conjunto pueden contarse uno a uno, aunque el conteo puede no terminar nunca debido a la infinidad de elementos.

En términos más técnicos, asumiendo el axioma de elección numerable , un conjunto es numerable si su cardinalidad (el número de elementos del conjunto) no es mayor que la de los números naturales. Un conjunto numerable que no es finito se denomina numerablemente infinito ; por ejemplo, el conjunto de todos los números naturales.${\displaystyle \mathbb {N} }$o todos los números racionales${\displaystyle \mathbb {Q} }$.

El concepto se atribuye a Georg Cantor , quien demostró la existencia de conjuntos no numerables , es decir, conjuntos que no se pueden contar; por ejemplo, el conjunto de los números reales.${\displaystyle \mathbb {R} }$.

Aunque los términos «contable» e «infinito contable», tal como se definen aquí, son bastante comunes, la terminología no es universal. ^{[ 1 ]} Un estilo alternativo utiliza «contable» para referirse a lo que aquí se denomina infinito contable, y « como máximo contable» para referirse a lo que aquí se denomina «contable». ^{[ 2 ] [ 3 ]}

También se pueden usar los términos enumerable ^{[ 4 ]} y denumerable ^{[ 5 ] [ 6 ] , que se refieren a numerable e infinito numerable, respectivamente. [ 7 ]} Las definiciones varían y es necesario tener cuidado al respetar la diferencia con enumerable recursivamente . ^{[ 8 ]}

Un conjunto${\displaystyle S}$es contable si:

• Su cardinalidad${\displaystyle |S|}$es menor o igual que${\displaystyle \aleph _{0}}$( aleph-nulo ), la cardinalidad del conjunto de números naturales${\displaystyle \mathbb {N} }$. ^{[ 9 ]}
• Existe una función inyectiva de${\displaystyle S}$a${\displaystyle \mathbb {N} }$. ^{[ 10 ] [ 11 ]}
• ${\displaystyle S}$está vacío o existe una función sobreyectiva de${\displaystyle \mathbb {N} }$a${\displaystyle S}$. ^{[ 11 ]}
• Existe una correspondencia biyectiva entre${\displaystyle S}$y un subconjunto de${\displaystyle \mathbb {N} }$. ^{[ 12 ]}
• ${\displaystyle S}$es finito (${\displaystyle |S|<\aleph _{0}}$) o infinitamente numerable. ^{[ 5 ]}

Todas estas definiciones son equivalentes.

Un conjunto${\displaystyle S}$es infinitamente numerable si:

• Su cardinalidad${\displaystyle |S|}$es exactamente${\displaystyle \aleph _{0}}$. ^{[ 9 ]}
• Existe una correspondencia inyectiva y sobreyectiva (y por lo tanto biyectiva ) entre${\displaystyle S}$y${\displaystyle \mathbb {N} }$.
• ${\displaystyle S}$tiene una correspondencia individual con${\displaystyle \mathbb {N} }$. ^{[ 13 ]}
• Los elementos de${\displaystyle S}$se pueden organizar en una secuencia infinita${\displaystyle a_{0},a_{1},a_{2},\ldots }$, dónde${\displaystyle a_{i}}$es distinto de${\displaystyle a_{j}}$para${\displaystyle i\neq j}$y cada elemento de${\displaystyle S}$está listado. ^{[ 14 ] [ 15 ]}

Un conjunto es incontable si no es contable, es decir, su cardinalidad es estrictamente mayor que${\displaystyle \aleph _{0}}$. ^{[ 9 ]} Es decir, hay una inyección desde${\displaystyle \mathbb {N} }$a${\displaystyle S}$, pero ninguna inyección de${\displaystyle S}$a${\displaystyle \mathbb {N} }$. En los modelos donde falla el axioma de elección , también puede haber conjuntos que sean incomparables a${\displaystyle \mathbb {N} }$, los llamados conjuntos finitos infinitos de Dedekind .

En 1874, en su primer artículo sobre teoría de conjuntos , Cantor demostró que el conjunto de los números reales es incontable, mostrando así que no todos los conjuntos infinitos son contables. ^{[ 16 ]} En 1878, utilizó correspondencias biyectivas 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 con diferentes cardinalidades infinitas. ^{[ 18 ]}

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 formado por los enteros 3, 4 y 5 puede denotarse${\displaystyle \{3,4,5\}}$, llamado formato 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, a veces se utiliza 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 lo que representa "..."; por ejemplo,${\displaystyle \{1,2,3,\dots ,100\}}$presumiblemente denota el conjunto de 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${\displaystyle n}$, esto nos da la definición habitual de "conjuntos de tamaño${\displaystyle n}$".

Algunos conjuntos son infinitos ; estos conjuntos tienen más de${\displaystyle n}$elementos donde${\displaystyle n}$es cualquier número entero que se pueda especificar. (No importa cuán grande sea el número entero especificado.${\displaystyle n}$es, como por ejemplo${\displaystyle n=10^{1000}}$, los conjuntos infinitos tienen más de${\displaystyle n}$elementos.) Por ejemplo, el conjunto de los números naturales, denotable por${\displaystyle \{0,1,2,3,4,5,\dots \}}$, ^{[ a ]} ​​tiene infinitos elementos, y no podemos usar ningún número natural para dar su tamaño. Podría parecer natural dividir los conjuntos en diferentes clases: juntar todos los conjuntos que contienen un elemento; juntar todos los conjuntos que contienen dos elementos; ...; finalmente, juntar todos los conjuntos infinitos y considerarlos del mismo tamaño. Esta visión funciona bien para conjuntos infinitos numerables y era la suposición predominante antes del trabajo de Georg Cantor. Por ejemplo, hay infinitos enteros impares, infinitos enteros pares y también infinitos enteros en general. Podemos considerar que todos estos conjuntos tienen el mismo "tamaño" porque podemos ordenar las cosas de tal manera que, para cada entero, hay un entero par distinto: $${\displaystyle \ldots \,-\!2\!\rightarrow \!-\!4,\,-\!1\!\rightarrow \!-\!2,\,0\!\rightarrow \!0,\,1\!\rightarrow \!2,\,2\!\rightarrow \!4\,\cdots }$$ o, más generalmente,${\displaystyle n\rightarrow 2n}$(ver imagen). Lo que hemos hecho aquí es organizar los enteros y los enteros pares en una correspondencia uno a uno (o biyección ), que es una función que mapea entre dos conjuntos de tal manera que cada elemento de cada conjunto corresponde a un único elemento en el 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 infinitos numerables a todos los conjuntos que están en correspondencia uno a uno con los enteros y decimos que tienen cardinalidad.${\displaystyle \aleph _{0}}$.

Georg Cantor demostró que no todos los conjuntos infinitos son infinitos numerables. Por ejemplo, los números reales no pueden establecerse 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. El argumento diagonal de Cantor proporciona una demostración formal mediante una estrategia de reducción al absurdo . Parte de la suposición de que el conjunto de los números reales en el intervalo (0,1) es contable. Si esto fuera cierto, cada número real en ese intervalo podría ordenarse en una lista secuencial ( _s₁ , _s₂ , _s₃ , ...) donde cada número se representa como una expansión decimal infinita. Esta lista estructurada es la base para construir un número real específico que lógicamente está garantizado que falta en la secuencia, invalidando así la premisa inicial de la numerabilidad.

La contradicción se forma al definir este nuevo número real,${\displaystyle x}$, donde cada${\displaystyle n}$El -ésimo dígito decimal se elige específicamente para que sea diferente del${\displaystyle n}$-ésimo dígito del${\displaystyle n}$-ésimo número en la lista. Al asegurar que cada dígito${\displaystyle x_{n}}$no es igual a${\displaystyle d_{n}}$(evitando el 0 o el 9 para prevenir ambigüedades con decimales periódicos), el número resultante${\displaystyle x}$es distinto de cada elemento de la secuencia por al menos una cifra decimal. Dado que${\displaystyle x}$Si es un número real entre 0 y 1 que no aparece en la lista que se supone completa, se deduce que no puede existir una biyección entre los números naturales y los números reales. ^{[ 20 ]}

Por definición, un conjunto${\displaystyle S}$es contable si existe una biyección entre${\displaystyle S}$y un subconjunto de los números naturales${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$. Por ejemplo, defina la correspondencia $${\displaystyle a\leftrightarrow 1,\ b\leftrightarrow 2,\ c\leftrightarrow 3}$$ Dado que cada elemento de${\displaystyle S=\{a,b,c\}}$está emparejado con precisamente un elemento de${\displaystyle \{1,2,3\}}$y viceversa, esto define una biyección y muestra que${\displaystyle S}$es numerable. De manera similar, podemos demostrar que todos los conjuntos finitos son numerables.

En cuanto al caso de conjuntos infinitos, un conjunto${\displaystyle S}$es infinitamente numerable si existe una biyección entre${\displaystyle S}$y todo de${\displaystyle \mathbb {N} }$Como ejemplos, consideremos los conjuntos${\displaystyle A=\{1,2,3,\dots \}}$, el conjunto de enteros positivos y${\displaystyle B=\{0,2,4,6,\dots \}}$, el conjunto de los enteros pares. Podemos demostrar que estos conjuntos son infinitos numerables mostrando una biyección a los números naturales. Esto se puede lograr utilizando las asignaciones${\displaystyle n\leftrightarrow n+1}$y${\displaystyle n\leftrightarrow 2n}$, de modo que $${\displaystyle {\begin{matrix}0\leftrightarrow 1,&1\leftrightarrow 2,&2\leftrightarrow 3,&3\leftrightarrow 4,&4\leftrightarrow 5,&\ldots \\[6pt]0\leftrightarrow 0,&1\leftrightarrow 2,&2\leftrightarrow 4,&3\leftrightarrow 6,&4\leftrightarrow 8,&\ldots \end{matrix}}}$$ Todo conjunto infinito numerable es numerable, y todo conjunto infinito numerable es infinito numerable. Además, cualquier subconjunto de los números naturales es numerable, y de forma más general:

El conjunto de todos los pares ordenados de números naturales (el producto cartesiano de dos conjuntos de números naturales,${\displaystyle \mathbb {N} \times \mathbb {N} }$) es infinitamente numerable, como se puede ver siguiendo un camino como el de la imagen:

El mapeo resultante se desarrolla de la siguiente manera:

$${\displaystyle 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 }$$ Este mapeo abarca todos esos pares ordenados.

Esta forma de mapeo triangular se generaliza recursivamente a${\displaystyle n}$- tuplas de números naturales, es decir,${\displaystyle (a_{1},a_{2},a_{3},\dots ,a_{n})}$dónde${\displaystyle a_{i}}$y${\displaystyle n}$son números naturales, al mapear repetidamente los dos primeros elementos de un${\displaystyle n}$-tupla a un número natural. Por ejemplo,${\displaystyle (0,2,3)}$se puede escribir como${\displaystyle ((0,2),3)}$. Entonces${\displaystyle (0,2)}$mapas a 5 así que${\displaystyle ((0,2),3)}$mapas a${\displaystyle (5,3)}$, entonces${\displaystyle (5,3)}$se asigna a 39. Dado que es una 2-tupla diferente, es decir, un par como${\displaystyle (a,b)}$, se asigna 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 asignen a números naturales diferentes. Por lo tanto, una inyección del conjunto de${\displaystyle n}$tuplas al conjunto de números naturales${\displaystyle \mathbb {N} }$Se demuestra. Para el conjunto de${\displaystyle n}$-tuplas formadas por el producto cartesiano de un número finito de conjuntos diferentes, cada elemento de 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 conjunto de todos los números enteros${\displaystyle \mathbb {Z} }$y el conjunto de todos los números racionales${\displaystyle \mathbb {Q} }$Puede parecer intuitivamente mucho más grande que${\displaystyle \mathbb {N} }$. Pero las apariencias pueden engañar. Si un par se trata como el numerador y el denominador de una fracción vulgar (una fracción en la forma de${\displaystyle a/b}$dónde${\displaystyle a}$y${\displaystyle b\neq 0}$son enteros), entonces para cada fracción positiva, podemos encontrar un número natural distinto que le corresponda. Esta representación también incluye los números naturales, ya que cada número natural${\displaystyle n}$también es una fracción${\displaystyle n/1}$Por lo tanto, podemos concluir que hay exactamente la misma cantidad de números racionales positivos que de enteros positivos. Esto también es cierto para todos los números racionales, como se puede observar a continuación.

De manera similar, el conjunto de números algebraicos es contable. ^{[ 24 ] [ d ]}

A veces, más de una asignación es útil: si un conjunto${\displaystyle A}$Para ser mostrado como contable se asigna uno a uno (inyección) a otro conjunto.${\displaystyle B}$, entonces${\displaystyle A}$se demuestra que es contable si${\displaystyle B}$se corresponde uno a uno con el conjunto de los números naturales. Por ejemplo, el conjunto de los números racionales positivos se puede corresponder fácilmente uno a uno con el conjunto de pares de números naturales (2-tuplas) porque${\displaystyle p/q}$mapas a${\displaystyle (p,q)}$Dado que el conjunto de pares de números naturales se corresponde biyectivamente (en realidad, existe una correspondencia biyectiva) con el conjunto de números naturales como se muestra arriba, se demuestra que el conjunto de números racionales positivos es numerable.

Sabiendo de antemano que existen conjuntos no numerables, podemos preguntarnos si este último resultado se puede extender aún más. La respuesta es "sí" y "no"; podemos extenderlo, pero para ello necesitamos asumir un nuevo axioma.

Por ejemplo, dados conjuntos numerables${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$Primero asignamos a cada elemento de cada conjunto una tupla, luego asignamos a cada tupla un índice utilizando una variante de la enumeración triangular que vimos anteriormente: $${\displaystyle {\begin{array}{c|c|c }{\text{Index}}&{\text{Tuple}}&{\text{Element}}\\\hline 0&(0,0)&{\textbf {a}}_{0}\\1&(0,1)&{\textbf {a}}_{1}\\2&(1,0)&{\textbf {b}}_{0}\\3&(0,2)&{\textbf {a}}_{2}\\4&(1,1)&{\textbf {b}}_{1}\\5&(2,0)&{\textbf {c}}_{0}\\6&(0,3)&{\textbf {a}}_{3}\\7&(1,2)&{\textbf {b}}_{2}\\8&(2,1)&{\textbf {c}}_{1}\\9&(3,0)&{\textbf {d}}_{0}\\10&(0,4)&{\textbf {a}}_{4}\\\vdots &&\end{array}}}$$

Necesitamos el axioma de elección numerable para indexar todos los conjuntos.${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$simultáneamente.

Este conjunto es la unión de las secuencias de longitud 1, las de longitud 2, las de longitud 3, y así sucesivamente, cada una de las cuales es un conjunto numerable (producto cartesiano finito). Por lo tanto, el conjunto es una unión numerable de conjuntos numerables, que es numerable según el teorema anterior.

Los elementos de cualquier subconjunto finito pueden ordenarse en una secuencia finita. Solo existen una cantidad numerable de secuencias finitas, por lo que también solo existen una cantidad numerable de subconjuntos finitos.

Estas se derivan de las definiciones de conjunto numerable como funciones inyectivas/sobreyectivas. ^{[ g ]}

El teorema de Cantor afirma que si${\displaystyle A}$es un conjunto y${\displaystyle {\mathcal {P}}(A)}$es su conjunto potencia , es decir, el conjunto de todos los subconjuntos de${\displaystyle A}$, entonces no hay ninguna función sobreyectiva de${\displaystyle A}$a${\displaystyle {\mathcal {P}}(A)}$En el artículo «Teorema de Cantor» se ofrece una demostración . Como consecuencia inmediata de esto y del Teorema Básico anterior, tenemos:

Para una explicación más detallada de este resultado, véase el argumento diagonal de Cantor .

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

Si existe un conjunto que sea un modelo estándar (véase modelo interno ) de la teoría de conjuntos ZFC, entonces existe un modelo estándar mínimo (véase universo constructible ). El teorema de Löwenheim-Skolem puede utilizarse para demostrar que este modelo mínimo es numerable. El hecho de que la noción de "incontable" tenga sentido incluso en este modelo, y en particular que este modelo M contenga elementos que sean:

• subconjuntos de M , por lo tanto, numerables,
• pero incontable desde el punto de vista de M ,

Esto se consideraba paradójico en los inicios de la teoría de conjuntos; para más información, véase la paradoja de Skolem .

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.

Los conjuntos numerables pueden ordenarse totalmente de diversas maneras, por ejemplo:

• Órdenes de pozo (véase también número ordinal ):
  • El orden habitual de los números naturales (0, 1, 2, 3, 4, 5, ...)
  • Los números enteros en el orden (0, 1, 2, 3, ...; −1, −2, −3, ...)
• Otros ( pedidos no bien hechos):
  • 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 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 es también un orden bien definido.

• Número Aleph
• Cálculo
• La paradoja de Hilbert del Gran Hotel
• Conjunto incontable

• Apostol, Tom M. (junio de 1969), Cálculo multivariable y álgebra lineal con aplicaciones , vol.  2 (2.ª  ed.), Nueva York: John Wiley + Sons, ISBN 978-0-471-00007-5
• Avelsgaard, Carol (1990), Fundamentos de 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 , S2CID 123695365 
• Ferreirós, José (2007), Laberinto del pensamiento: Historia de la teoría de conjuntos y su papel en el pensamiento matemático (2.ª  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 ingenua de conjuntos , D. Van Nostrand Company, IncReimpreso por Springer-Verlag, Nueva York, 1974. ISBN 0-387-90092-6(Edición de 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{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Lang, Serge (1993), Análisis real y funcional , Berlín, Nueva York: Springer-Verlag, ISBN 0-387-94001-4
• Rudin, Walter (1976), Principios de análisis matemático , Nueva York: McGraw-Hill, ISBN 0-07-054235-X
• Tao, Terence (2016). «Conjuntos infinitos» . Análisis I. Textos y lecturas en matemáticas. Vol.  37 (Tercera  ed.). Singapur: Springer. pp. 181–210 . doi : 10.1007/978-981-10-1789-6_8 . ISBN  978-981-10-1789-6.