4.1: Nociones básicas de teoría de conjuntos
- Page ID
- 114134
En las matemáticas modernas, existe un área llamada Teoría de Categoría 1 que estudia las relaciones entre diferentes áreas de las matemáticas. Más precisamente, los fundadores de la teoría de categorías notaron que esencialmente los mismos teoremas y pruebas se podían encontrar en muchos campos matemáticos diferentes, con solo cambiados los nombres de las estructuras involucradas. En este tipo de situaciones, se puede hacer lo que se conoce como argumento categórico en el que se prueba el resultado deseado en abstracto, sin hacer referencia a los detalles de ningún campo en particular. En efecto, esto permite probar muchos teoremas a la vez; todo lo que necesitas para convertir una prueba categórica abstracta en una concreta relevante para un área en particular es una especie de clave o léxico para proporcionar los nombres correctos para las cosas. Ahora bien, la teoría de categorías probablemente no debería estudiarse realmente hasta que no tengas un fondo que incluya suficientes campos diferentes para que puedas darle sentido a sus correspondencias categóricas. Además, hay muchos matemáticos que se burlan de la teoría de categorías como “tonterías abstractas”. Pero, como alguien interesado en desarrollar una instalación con pruebas, debes estar pendiente de correspondencias categóricas. Si alguna vez te escuchas pronunciar algo así como “bueno, la prueba de eso va igual que la prueba del teorema (inserta aquí un nombre extraño que suena técnico)” probablemente estés notando una correspondencia categórica.
Bien, entonces la teoría de categorías no te será de mucha utilidad hasta mucho más tarde en tu carrera matemática (si acaso), y se podría argumentar que realmente no ahorra tanto esfuerzo. ¿Por qué no hacer simplemente dos o tres pruebas diferentes en lugar de aprender un campo completamente nuevo para que podamos combinarlas en una sola? Sin embargo, la teoría de categorías se está mencionando aquí al inicio del capítulo sobre conjuntos. ¿Por qué?
Estamos a punto de ver nuestro primer ejemplo de una correspondencia categórica. La lógica y la teoría de conjuntos son aspectos diferentes de una misma cosa. Para describir un conjunto la gente suele citar a Kurt Gödel — “Un conjunto es un Many que se permite ser considerado como un Uno”. (Obsérvese cómo el intento de definir lo que es realmente un concepto elemental e indefinible termina sonando bastante místico). Un enfoque más práctico es pensar en un conjunto como la colección de cosas que hacen cierta frase abierta cierta verdad. 2 [11]
Recordemos que en Lógica los conceptos atómicos eran “verdadero”, “falso”, “oración” y “declaración”. En la teoría de conjuntos, son “set”, “element” y “membership”. Estos conceptos (más o menos) se corresponden entre sí. En la mayoría de los libros, un conjunto se denota ya sea usando la letra\(M\) (que significa la palabra alemana “menge”) o letras romanas mayúsculas del alfabeto temprano —\(A\)\(B\)\(C\),,, etcétera. Aquí, a menudo enfatizaremos la conexión entre conjuntos y oraciones abiertas en Lógica usando una notación de subíndice. Se\(P(x)\) denotará el conjunto que corresponde a la sentencia abierta\(S_P\), llamamos conjunto\(S_P\) de verdad de\(P(x)\).
\(S_P = \{x | P(x)\}\)
Por otro lado, cuando tenemos un conjunto dado en ausencia de cualquier oración abierta, estaremos encantados de usar el alfabeto temprano, la convención de letras mayúsculas romanas — o francamente, ¡cualquier otra letra que nos apetezca! Siempre que tenemos un conjunto\(A\) dado, es fácil afirmar una oración lógica abierta que le correspondería. La pregunta de membresía:\(M_A(x) =\) “¿Está\(x\) en el set\(A\)?” O, de manera más sucinta,\(M_A(x) = “x ∈ A”\). Así, el concepto atómico “verdadero” de la Lógica corresponde a la respuesta “sí” a la pregunta de pertenencia en la teoría de conjuntos (y por supuesto “falso” corresponde a “no”).
Hay muchos temas fundamentales interesantes que vamos a evitar en nuestro desarrollo actual de la teoría de conjuntos. Por ejemplo, recordemos que en Lógica siempre trabajamos dentro de algún “universo de discurso”. Como consecuencia del enfoque que estamos tomando ahora, todo nuestro trabajo teórico conjunto se realizará dentro de algún conjunto desconocido “universal”. Los intentos de especificar (a priori) un conjunto universal para hacer matemáticas en su interior están condenados al fracaso. En los primeros días del siglo XX intentaron al menos conseguir que la teoría de conjuntos se pusiera firme definiendo el conjunto universal como “el conjunto de todos los conjuntos” —una idea que suena inocua y que tuvo consecuencias graciosas (lo investigaremos en la Sección 4.5).
En Lógica teníamos “frases” y “declaraciones”, estas últimas se distinguieron por tener valores de verdad definidos. Lo que corresponde en la teoría de conjuntos es que los conjuntos tienen la propiedad de que siempre podemos decir si un objeto dado está o no en ellos. Si alguna vez se hace necesario hablar de “sets” donde no estamos realmente seguros de lo que hay en ellos usaremos el término colección.
Se debe pensar en un conjunto como una colección desordenada de cosas, así\(\{\text{popover }, 1, \text{ froggy}\}\) y\(\{1, \text{ froggy}, \text{ popover}\}\) son dos formas de representar el mismo conjunto. Además, un conjunto contiene, o no contiene, un elemento dado. No tiene sentido tener un elemento en un conjunto varias veces. Por convención, si un elemento se enumera más de una vez cuando se enumera un conjunto ignoramos las repeticiones. Entonces, los sets\(\{1, 1\}\) y\(\{1\}\) son realmente lo mismo. Si se necesita la noción de un conjunto que contenga múltiples instancias de sus elementos existe un concepto conocido como multiconjunto que se estudia en Combinatoria. En un multiset, cada elemento está precedido por un llamado número de repetición que puede ser el símbolo especial\(∞\) (indicando un número ilimitado de repeticiones). El concepto multiset es útil a la hora de estudiar acertijos como “¿De cuántas formas se pueden reorganizar las letras de MISSISSIS?” porque las letras en MISSISSIS se pueden expresar como el multiset\(\{1 · M, 4 · I, 2 · P, 4 · S\}\). Con excepción del siguiente ejercicio, en lo que resta de este capítulo solo nos ocuparemos de conjuntos, nunca multiconjuntos
(¡No para los tímidos!) ¿De cuántas formas se pueden arreglar las letras de MISSIPISSIS?
Si un científico informático estuviera buscando una estructura de datos para implementar la noción de “conjunto”, querría una lista ordenada donde de alguna manera no se permitieran repeticiones de una entrada. Ya hemos señalado que un conjunto debe considerarse como una colección desordenada, y sin embargo se ha afirmado que una lista ordenada sería el vehículo adecuado para representar un conjunto en una computadora. ¿Por qué? Una razón es que nos gustaría poder decir (rápidamente) si dos conjuntos son iguales o no. Si los elementos han sido preordenados es más fácil.
Considera la dificultad para decidir si los dos conjuntos siguientes son iguales.
\(S_1 = \{♠, 1, e, π, ♦, A, Ω, h, ⊕, \epsilon\}\)
\(S_2 = \{A, 1, \epsilon, π, e, s, ⊕, ♠, Ω, ♦\}\)
Si en cambio los comparamos después de haber sido ordenados, el trabajo es mucho más fácil.
\(S_1 = \{1, A, ♦, e, \epsilon, h, Ω, ⊕, π, ♠\}\)
\(S_2 = \{1, A, ♦, e, \epsilon, Ω, ⊕, π, s, ♠\}\)
Este negocio sobre pedidos versus desordenados surge con bastante frecuencia, por lo que vale la pena invertir unos momentos para averiguar cómo funciona. Si se nos entrega una colección de cosas que es inherentemente desordenada generalmente las ponemos en un orden que nos agrada. Considera recibir cinco cartas del crupier en un juego de cartas, o extraer siete letras de la bolsa en una partida de Scrabble. Si, por otro lado, recibimos una colección donde el pedido es importante, ciertamente no podemos reorganizarlos. ¡Imagina a alguien recibiendo el número de teléfono de una otra atractiva pero anotándolo con los dígitos ordenados en orden creciente!
Considera un universo que consiste solo en los primeros números\(5\) naturales\(U = \{1, 2, 3, 4, 5\}\). ¿Cuántos conjuntos diferentes que tienen\(4\) elementos hay en este universo? ¿Cuántas colecciones ordenadas diferentes de\(4\) elementos hay?
El último ejercicio sugiere una pregunta interesante. Si tienes un conjunto universal de algún tamaño fijo (finito), ¿cuántos conjuntos diferentes hay? Obviamente, no puedes tener más elementos en un conjunto de los que están en tu universo. ¿Cuál es el tamaño más pequeño posible para un conjunto? Mucha gente respondería\(1\) — ¡lo cual no es irrazonable! — después de todo, se supone que un set es una colección de cosas, y ¿es realmente posible tener una colección sin nada en ella? \(0\)Sin embargo, la respuesta estándar es, principalmente porque hace que cierta fórmula de conteo funcione muy bien. Un conjunto con un elemento se conoce como un conjunto singleton (tenga en cuenta el uso del artículo indefinido). Un conjunto sin elementos se conoce como el conjunto vacío (tenga en cuenta el artículo definido). Hay tantos singletons como elementos hay en tu universo. Sin embargo, no son lo mismo, por ejemplo\(1 \neq \{1\}\). Solo hay un conjunto vacío y se denota\(∅\) —independientemente del universo en el que estemos trabajando.
Echemos un vistazo a un pequeño ejemplo. Supongamos que tenemos un conjunto universal con\(3\) elementos, sin pérdida de generalidad,\(\{1, 2, 3\}\). Es posible construir un conjunto, cuyos elementos son todos los conjuntos posibles en este universo. Este conjunto se conoce como el conjunto de potencia del conjunto universal. En efecto, podemos construir el conjunto de potencias de cualquier conjunto\(A\) y lo denotamos con el símbolo\(\mathcal{P}(A)\). Volviendo a nuestro ejemplo tenemos
\(\mathcal{P}(\{1, 2, 3\}) = \big\{ ∅, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \big\}.\)
Encuentra los conjuntos de potencia\(\mathcal{P}(\{1, 2\})\) y\(P(\{1, 2, 3, 4\})\).
Conjetura una fórmula para el número de elementos (estos son, por supuesto, conjuntos) en\(\mathcal{P}(\{1, 2, . . . n\})\).
Pista: Si tu fórmula conjeturada es correcta deberías ver por qué estos conjuntos se nombran tal como son.
Una última cosa antes de terminar esta sección. El tamaño (también conocido como cardinalidad) de un conjunto es solo el número de elementos que contiene. Utilizamos el mismo símbolo para la cardinalidad que para el valor absoluto de una entidad numérica. Realmente nunca debería haber ninguna confusión. Si\(A\) es un conjunto entonces\(|A|\) significa que debemos contar cuántas cosas hay en\(A\). Si\(A\) no es un conjunto entonces estamos hablando del valor absoluto ordinario
Ejercicios:
¿Cuál es el conjunto de potencia\(∅\)?
- Pista
-
Si tienes el último ejercicio en el capítulo sabrías que este conjunto de poder tiene\(2^0 = 1\) elemento.
Intente iterar el operador de conjunto de potencia. ¿Qué es\(\mathcal{P}(\mathcal{P}(∅))\)? ¿Qué es\(\mathcal{P}(\mathcal{P}(\mathcal{P}(∅)))\)?
Determinar las siguientes cardinalidades.
- \(A = \{1, 2, \{3, 4, 5\}\} |A| = \underline{\;\;\;\;\;\;\;\;\;\;\;} \)
- \(B = \{\{1, 2, 3, 4, 5\}\} |B| = \underline{\;\;\;\;\;\;\;\;\;\;\;} \)
¿Qué, en Lógica, corresponde la noción\(∅\) en la teoría de conjuntos?
¿Qué, en la teoría de conjuntos, corresponde a la noción\(t\) (una tautología) en Lógica?
¿Cuál es el conjunto de verdad de la proposición\(P(x) =\) “\(3\)\(2\)divide\(x\) y divide\(x\)”?
Encuentra una frase abierta lógica tal que\(\{0, 1, 4, 9, . . .\}\) sea su conjunto de verdad.
¿Cuántos conjuntos singleton hay en el conjunto de potencia de\(\{a, b, c, d, e\}\)? ¿Conjuntos “Doubleton”?
¿Cuántos subconjuntos de\(8\) elementos hay en
\(P(\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p\})?\)
¿Cuántos conjuntos singleton hay en el conjunto de potencia de\(\{1, 2, 3, . . . n\}\)?