stringtranslate.com

Conjuntos disjuntos

Dos conjuntos disjuntos

En la teoría de conjuntos en matemáticas y lógica formal , se dice que dos conjuntos son conjuntos disjuntos si no tienen ningún elemento en común. De manera equivalente, dos conjuntos disjuntos son conjuntos cuya intersección es el conjunto vacío . [1] Por ejemplo, {1, 2, 3} y {4, 5, 6} son conjuntos disjuntos, mientras que {1, 2, 3} y {3, 4, 5} no son disjuntos. Una colección de dos o más conjuntos se llama disjunta si dos conjuntos distintos de la colección son disjuntos.

Generalizaciones

Una colección disjunta de conjuntos

Esta definición de conjuntos disjuntos se puede extender a familias de conjuntos y a familias indexadas de conjuntos. Por definición, una colección de conjuntos se denomina familia de conjuntos (como el conjunto potencia , por ejemplo). En algunas fuentes, se trata de un conjunto de conjuntos, mientras que otras fuentes permiten que sea un multiconjunto de conjuntos, con algunos conjuntos repetidos. Una familia indexada de conjuntos es, por definición, una función con valores de conjunto (es decir, es una función que asigna un conjunto a cada elemento de su dominio) cuyo dominio se denomina su conjunto índice (y los elementos de su dominio se denominan índices ).

Existen dos definiciones sutilmente diferentes para determinar cuándo una familia de conjuntos se denomina disjunta por pares . Según una de esas definiciones, la familia es disjunta si cada dos conjuntos de la familia son idénticos o disjuntos. Esta definición permitiría que las familias de conjuntos disjuntos por pares tengan copias repetidas del mismo conjunto. Según una definición alternativa, cada dos conjuntos de la familia deben ser disjuntos; no se permiten copias repetidas. Las mismas dos definiciones se pueden aplicar a una familia indexada de conjuntos: según la primera definición, cada dos índices distintos de la familia deben nombrar conjuntos que sean disjuntos o idénticos, mientras que según la segunda, cada dos índices distintos deben nombrar conjuntos disjuntos. [2] Por ejemplo, la familia de conjuntos { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... } es disjunta según ambas definiciones, al igual que la familia { {..., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} } de las dos clases de paridad de números enteros. Sin embargo, la familia con 10 miembros tiene cinco repeticiones de cada uno de los dos conjuntos disjuntos, por lo que es disjunta por pares según la primera definición, pero no según la segunda.

Se dice que dos conjuntos son casi disjuntos si su intersección es pequeña en algún sentido. Por ejemplo, dos conjuntos infinitos cuya intersección es un conjunto finito pueden decirse que son casi disjuntos. [3]

En topología , existen varias nociones de conjuntos separados con condiciones más estrictas que la disyunción. Por ejemplo, dos conjuntos pueden considerarse separados cuando tienen clausuras disjuntas o vecindades disjuntas . De manera similar, en un espacio métrico , los conjuntos separados positivamente son conjuntos separados por una distancia distinta de cero . [4]

Intersecciones

La disyunción de dos conjuntos, o de una familia de conjuntos, puede expresarse en términos de intersecciones de pares de ellos.

Dos conjuntos A y B son disjuntos si y sólo si su intersección es el conjunto vacío . [1] De esta definición se deduce que todo conjunto es disjunto del conjunto vacío, y que el conjunto vacío es el único conjunto que es disjunto de sí mismo. [5]

Si una colección contiene al menos dos conjuntos, la condición de que la colección sea disjunta implica que la intersección de toda la colección está vacía. Sin embargo, una colección de conjuntos puede tener una intersección vacía sin ser disjunta. Además, mientras que una colección de menos de dos conjuntos es trivialmente disjunta, ya que no hay pares para comparar, la intersección de una colección de un conjunto es igual a ese conjunto, que puede no estar vacío. [2] Por ejemplo, los tres conjuntos { {1, 2}, {2, 3}, {1, 3} } tienen una intersección vacía pero no son disjuntos. De hecho, no hay dos conjuntos disjuntos en esta colección. Además, la familia vacía de conjuntos es disjunta por pares. [6]

Una familia Helly es un sistema de conjuntos en el que las únicas subfamilias con intersecciones vacías son aquellas que son disjuntas por pares. Por ejemplo, los intervalos cerrados de los números reales forman una familia Helly: si una familia de intervalos cerrados tiene una intersección vacía y es mínima (es decir, ninguna subfamilia de la familia tiene una intersección vacía), debe ser disjunta por pares. [7]

Uniones disjuntas y particiones

Una partición de un conjunto X es cualquier colección de conjuntos no vacíos mutuamente disjuntos cuya unión es X. [8] Cada partición puede describirse de forma equivalente mediante una relación de equivalencia , una relación binaria que describe si dos elementos pertenecen al mismo conjunto en la partición. [ 8] Las estructuras de datos de conjuntos disjuntos [9] y el refinamiento de particiones [10] son ​​dos técnicas en informática para mantener de manera eficiente las particiones de un conjunto sujetas, respectivamente, a operaciones de unión que fusionan dos conjuntos u operaciones de refinamiento que dividen un conjunto en dos.

Una unión disjunta puede significar una de dos cosas. En términos más simples, puede significar la unión de conjuntos que son disjuntos. [11] Pero si dos o más conjuntos no son ya disjuntos, su unión disjunta puede formarse modificando los conjuntos para hacerlos disjuntos antes de formar la unión de los conjuntos modificados. [12] Por ejemplo, dos conjuntos pueden hacerse disjuntos reemplazando cada elemento por un par ordenado del elemento y un valor binario que indique si pertenece al primer o segundo conjunto. [13] Para familias de más de dos conjuntos, uno puede reemplazar de manera similar cada elemento por un par ordenado del elemento y el índice del conjunto que lo contiene. [14]

Véase también

Referencias

  1. ^ ab Halmos, PR (1960), Teoría de conjuntos ingenua, Textos de pregrado en matemáticas , Springer, pág. 15, ISBN 9780387900926.
  2. ^ ab Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), Una transición a las matemáticas avanzadas, Cengage Learning, pág. 95, ISBN 978-0-495-56202-3.
  3. ^ Halbeisen, Lorenz J. (2011), Teoría de conjuntos combinatorios: con una introducción sencilla al forzamiento, Monografías de Springer sobre matemáticas, Springer, pág. 184, ISBN 9781447121732.
  4. ^ Copson, Edward Thomas (1988), Espacios métricos, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, pág. 62, ISBN 9780521357326.
  5. ^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, libros de texto de la MAA, Asociación Matemática de Estados Unidos, pág. 59, ISBN 9780883857793.
  6. ^ "¿La familia vacía de conjuntos es disjunta por pares?". Mathematics Stack Exchange . Consultado el 10 de octubre de 2024 .
  7. ^ Bollobás, Béla (1986), Combinatoria: sistemas de conjuntos, hipergrafos, familias de vectores y probabilidad combinatoria, Cambridge University Press, pág. 82, ISBN 9780521337038.
  8. ^ desde Halmos (1960), pág. 28.
  9. ^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Capítulo 21: Estructuras de datos para conjuntos disjuntos", Introducción a los algoritmos (segunda edición), MIT Press, págs. 498–524, ISBN 0-262-03293-7.
  10. ^ Paige, Robert; Tarjan, Robert E. (1987), "Tres algoritmos de refinamiento de particiones", SIAM Journal on Computing , 16 (6): 973–989, doi :10.1137/0216062, MR  0917035, S2CID  33265037.
  11. ^ Ferland, Kevin (2008), Matemáticas discretas: Introducción a las pruebas y la combinatoria, Cengage Learning, pág. 45, ISBN 9780618415380.
  12. ^ Arbib, Michael A.; Kfoury, AJ; Moll, Robert N. (1981), Una base para la informática teórica , La serie AKM en informática teórica: Textos y monografías en informática, Springer-Verlag, pág. 9, ISBN 9783540905738.
  13. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Comprensión de los métodos formales, Springer, pág. 21, ISBN 9781852332471.
  14. ^ Lee, John M. (2010), Introducción a las variedades topológicas , Textos de posgrado en matemáticas, vol. 202 (2.ª ed.), Springer, pág. 64, ISBN 9781441979407.

Enlaces externos