Conjunto contable

Un conjunto contable es un conjunto infinito cuyos elementos pueden ser numerados por números naturales . Más formalmente: un conjunto es contable si hay una biyección con un conjunto de números naturales: en otras palabras, un conjunto contable es un conjunto que es equivalente en potencia al conjunto de números naturales. En la jerarquía de alefs , la cardinalidad de un conjunto contable se denota ("alef-cero"). $X$ $X\leftrightarrow \mathbb {N}$ $\alef _{0}$

Propiedades

Un conjunto contable es el conjunto infinito "más simple" en el siguiente sentido: en cualquier conjunto infinito hay un subconjunto contable . En efecto, elegiremos aleatoriamente elementos de un conjunto infinito y les asociaremos números. Como el conjunto es infinito, para cualquier natural hay un elemento en él para comparar con el número , del cual, por el principio de inducción , se construye el subconjunto será biyectiva con . $1,\,2,\,3,\,\ldots$ $norte$ $n+1$ $\matemáticas {N}$

Además, todo subconjunto de un conjunto contable es finito o contable (no más que contable). Enumeramos los elementos del conjunto original por números naturales, lo cual es posible, ya que es contable. Para cada elemento, sabemos si se encuentra en nuestro subconjunto o no. Repasándolos en orden, si el siguiente elemento no se encuentra en el subconjunto, lo omitiremos; si miente, asígnele el siguiente número (comencemos a numerar con ). Por el principio de inducción, un subconjunto será equivalente si no es finito. Nótese que, clasificando en orden, entre los elementos ya considerados, no nos faltó ninguno. $una$ $\matemáticas {N}$

Además, una unión como máximo contable (finita o contable) de conjuntos como máximo contables es como máximo un conjunto contable . Enumeramos los elementos de los conjuntos combinados (establecer una biyección con ). Si hay un número finito de conjuntos iniciales , numeraremos los elementos — sus uniones: Es fácil ver por la inducción que se establece una biyección con . En el caso de una unión infinita, esta regla no se aplica, pero es posible una numeración similar. Se puede visualizar de la siguiente manera (sin embargo, se puede formalizar una conclusión adicional): escribamos los elementos de cada conjunto (ordenados por números) en una columna. Hagamos una tabla a partir de estos, cuyas columnas definen cada conjunto incluido en la unión, y las filas, ciertos números de cada uno de ellos. Desde la esquina superior izquierda, nos convertiremos en una serpiente para sortear toda la tabla, numerando cada celda en el camino. Por inducción, damos la vuelta a toda la tabla y la unión resultante resulta ser contable. En términos generales, la mesa en sí tendrá que ser "construida" por la misma serpiente, ya que es infinita. Los elementos de conjuntos finitos siempre se pueden asignar primero, cambiando así la numeración por algún número. $\matemáticas {N}$ $A,\,B,\,C,\,\ldots$ $norte$ $S$ $s_{1}=a_{1},\;s_{2}=b_{1},\;\ldots,\;s_{n+1}=a_{2},\;s_{n+ 2 }=b_{2},\;\ldots$ $\matemáticas {N}$

También es fácil demostrar que el producto directo de un número finito de no más que conjuntos contables no es más que contable . Considere el producto de dos conjuntos, su contabilidad se establece mediante la numeración de la tabla similar a la anterior, cuyas filas son los elementos de un conjunto y las columnas del otro. El producto de un número finito de conjuntos se divide en factores, cada uno de los cuales será el producto del conjunto multiplicador original y el producto cartesiano de dos conjuntos. Expandamos el producto final desde el final: numeremos el producto de dos conjuntos, los elementos de uno de los cuales se obtendrán numerando el producto de dos conjuntos "entrantes", los elementos de uno de los cuales se obtendrán de la misma manera . Sigamos con la recursividad, que no se cerrará, ya que hay un número finito de conjuntos. Tenga en cuenta que todos los números deberán buscarse por inducción, completando secuencialmente las placas necesarias en los lugares correctos.

Finalmente , si sumamos un conjunto finito o numerable a un conjunto infinito, entonces obtenemos un conjunto que es equivalente al original [1] . La validez del enunciado es fácil de demostrar si elegimos un subconjunto contable en el conjunto original . Así, . Adjuntar al conjunto como máximo contable no cambia su cardinalidad, por lo que para el conjunto como máximo contable es cierto: . $A$ $B$ $A=(A\setminus B)\cup B\;\leftrightarrow (A\setminus B)\cup \mathbb {N}$ $B$ $C$ $A\cup C=(A\setminus B)\cup (B\cup C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$

Tenga en cuenta que el conjunto de todos los subconjuntos finitos de un conjunto contable es contable . El conjunto de subconjuntos finitos de elementos es contable, ya que es un subconjunto del producto cartesiano de los conjuntos originales. El conjunto de todos los subconjuntos finitos es la unión de subconjuntos finitos con un cierto número de elementos (que son contables), es decir contablemente. $norte$ $norte$

Sin embargo, el conjunto de todos los subconjuntos de un conjunto contable es continuo y no contable . Mostremos el hecho en un sentido más general de que no hay biyección entre un cierto conjunto y el conjunto de todos sus subconjuntos. Supongamos lo contrario. Elegimos el conjunto de todos los elementos del conjunto original que no están asociados con conjuntos que se contienen a sí mismos. Tal, por supuesto, es un elemento del conjunto de todos los subconjuntos. No puede compararse con ningún elemento que esté en él por un lado (por definición), así como con ningún elemento que no esté en él por el otro (porque de lo contrario, tal elemento ya estaría en él). Así, el conjunto que hemos construido está vacío, pero los subconjuntos que contienen un determinado elemento son siempre más de uno; Esto significa que la correspondencia no es uno a uno. Una contradicción significa que la suposición de la existencia de una biyección es incorrecta.

Ejemplos

Son contables los conjuntos de números naturales $\matemáticas {N}$ , enteros $\matemáticas {Z}$ , números racionales $\matemáticas {Q}$ , números algebraicos ${\ estilo de visualización \ mathbb {A}}$ . Contables son objetos resultantes de procedimientos recursivos , en particular, estos son números computables , números aritméticos (como resultado, el anillo de períodos también es contable , ya que cada período es computable ). El conjunto de todas las palabras finitas sobre un alfabeto contable y el conjunto de todas las palabras sobre un alfabeto finito son contables. Cualquier objeto que se pueda definir con una comparación uno a uno con un conjunto contable es contable, por ejemplo: cualquier familia infinita de intervalos abiertos que no se intersecan en el eje real; el conjunto de todas las líneas en el plano , cada una de las cuales contiene al menos dos puntos con coordenadas racionales ; cualquier conjunto infinito de puntos en el plano, todas las distancias por pares entre elementos de los cuales son racionales.

Un conjunto incontable es un conjunto infinito que no es contable, tales, en particular, son los conjuntos de números reales $\matemáticas {R}$ , números complejos ${\ estilo de visualización \ mathbb {C}}$ , cuaterniones , números de Cayley . Por lo tanto, cualquier conjunto puede llamarse finito, contable o incontable. $\matemáticas {H}$ $\matemáticas O$

Datos interesantes

A primera vista, parece imposible establecer una correspondencia biunívoca entre, digamos , y , porque los elementos del segundo conjunto parecen ser el doble. Pero aquí estamos lidiando con nuestra percepción del concepto de infinito , como algo que no tiene fin. Puede intentar percibir este hecho en el siguiente ejemplo, absurdo en cierto sentido. $\matemáticas {N}$ $\matemáticas {Z}$

Imaginemos que se construye un hotel con infinidad de habitaciones para una reunión del consejo galáctico, y sucede que todas las habitaciones están ocupadas. En ese momento llegaron diplomáticos que necesitaban ser reubicados. Dado que hay un número contable de habitaciones de hotel y de residentes, propondremos la siguiente estrategia para el reasentamiento de los recién llegados. Movamos a los invitados de la -ésima habitación a la -ésima, viviendo en la -ésima en la -ésima, y luego en orden. En las primeras habitaciones desocupadas , de hecho, acomodaremos a los que llegaron. Sin embargo, el hotel, ya que estaba completamente ocupado, seguirá siéndolo. Resulta que no había asientos vacíos. Se encuentra una contradicción en la representación del infinito como una cierta finitud. Sin embargo, el infinito se caracteriza precisamente por la ausencia de su fin, en otras palabras, el infinito con la adición de un fin es exactamente el mismo infinito. $norte$ $una$ $(n+1)$ $2$ ${\ estilo de visualización (n + 2)}$ $norte$

Además, es posible envolver de una forma bastante elegante la prueba de la ausencia de biyección entre un determinado conjunto y el conjunto de todos sus subconjuntos. Llamemos al primero un conjunto de personas (se puede suponer que las acciones tienen lugar en la misma galaxia), y al segundo una sociedad. Supongamos que en cada sociedad hay un (y único) representante que lo representa únicamente a él. Llamemos héroes a aquellos que representan una sociedad a la que no pertenecen. Resulta que un héroe no puede representar a todos los héroes. Pero un no-héroe tampoco puede hacer esto, porque al cometer un acto tan heroico, se convertiría en un héroe. Por lo tanto, no hubo héroes en la galaxia, de lo contrario, nuestra suposición es incorrecta. Pero no todas las sociedades pueden prescindir de un héroe, por lo que nuestra suposición es ciertamente incorrecta. Resulta que no hay biyección

Notas

↑ Brudno, 1971 , pág. catorce.

Literatura

Brudno A. L. Teoría de funciones de variable real. - M. : Nauka, 1971. - 119 p.