En matemáticas , 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 lo son. Una colección de más de dos conjuntos se llama disjunta si dos conjuntos distintos de la colección son disjuntos.
Generalizaciones
Esta definición de conjuntos disjuntos se puede extender a una familia de conjuntos : la familia es disjunta por pares , o mutuamente disociada si cuando sea . Alternativamente, algunos autores utilizan el término disjunto para referirse también a esta noción.
Para las familias, la noción de disjuntos por pares o mutuamente disjuntos a veces se define de una manera sutilmente diferente, en el sentido de que se permiten miembros idénticos repetidos: la familia es disjunta por pares si cuando sea (cada dos conjuntos distintos en la familia son inconexos). [2] Por ejemplo, la colección de conjuntos {{0,1,2}, {3,4,5}, {6,7,8}, ...} es disjunta, al igual que el conjunto {{.. . − 2,0,2,4, ...}, {...− 3, −1,1,3,5 }} de las dos clases de paridad de enteros; la familia con 10 miembros no es disjunto (porque las clases de números pares e impares están presentes cinco veces cada una), pero es disjunto por pares de acuerdo con esta definición (ya que uno solo obtiene una intersección no vacía de dos miembros cuando los dos son iguales clase).
Se dice que dos conjuntos son conjuntos casi disjuntos si su intersección es pequeña en algún sentido. Por ejemplo, se puede decir que dos conjuntos infinitos cuya intersección es un conjunto finito son casi disjuntos. [3]
En topología , existen varias nociones de conjuntos separados con condiciones más estrictas que la desunión. Por ejemplo, se puede considerar que dos conjuntos están separados cuando tienen cierres disjuntos o vecindarios disjuntos . De manera similar, en un espacio métrico , los conjuntos separados positivamente son conjuntos separados por una distancia distinta de cero . [4]
Intersecciones
La disocia 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 solo si su intersecciónes 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 está 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 estar disjunta. Además, aunque una colección de menos de dos conjuntos es trivialmente disjunta, como 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 están separados. De hecho, no hay dos conjuntos separados 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 dentro del cual las únicas subfamilias con intersecciones vacías son las que están separadas 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 y particiones disjuntas
Una partición de un conjunto X es cualquier colección de mutuamente disjuntos conjuntos no vacíos cuya unión es X . [8] Cada partición se puede describir de manera 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 sujeto a, respectivamente, operaciones de unión que fusionan dos conjuntos u operaciones de refinamiento que dividen un conjunto en dos .
Una unión inconexa puede significar una de dos cosas. De manera más simple, puede significar la unión de conjuntos que son inconexos. [11] Pero si dos o más conjuntos aún no están 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 disociarse reemplazando cada elemento por un par ordenado del elemento y un valor binario que indica si pertenece al primer o segundo conjunto. [13] Para familias de más de dos conjuntos, se puede reemplazar de manera similar cada elemento por un par ordenado del elemento y el índice del conjunto que lo contiene. [14]
Ver también
- Teorema de separación de hiperplanos para conjuntos convexos disjuntos
- Eventos mutuamente excluyentes
- Números relativamente primos con conjuntos disjuntos de divisores primos
- Separoid
- Empaquetado de conjuntos , el problema de encontrar la subfamilia disjunta más grande de una familia de conjuntos
Referencias
- ^ a b Halmos, PR (1960), Teoría de conjuntos ingenua , Textos de pregrado en matemáticas , Springer, p. 15, ISBN 9780387900926.
- ^ a b Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), Una transición a las matemáticas avanzadas , Cengage Learning, p. 95, ISBN 978-0-495-56202-3.
- ^ Halbeisen, Lorenz J. (2011), Teoría de conjuntos combinatorios: con una suave introducción al forzamiento , monografías de Springer en matemáticas, Springer, p. 184, ISBN 9781447121732.
- ^ Copson, Edward Thomas (1988), Metric Spaces , Cambridge Tracts in Mathematics, 57 , Cambridge University Press, pág. 62, ISBN 9780521357326.
- ^ Oberste-Vorth, Ralph W .; Mouzakitis, Arístides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics , libros de texto MAA, Asociación Matemática de América, p. 59, ISBN 9780883857793.
- ^ Consulte las respuestas a la pregunta ″ ¿Es la familia vacía de conjuntos disjuntos por pares? ″
- ^ Bollobás, Béla (1986), Combinatoria: sistemas de conjuntos, hipergráficos, familias de vectores y probabilidad combinatoria , Cambridge University Press, p. 82, ISBN 9780521337038.
- ↑ a b Halmos (1960) , pág. 28.
- ^ 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.
- ^ 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.
- ^ Ferland, Kevin (2008), Matemáticas discretas: Introducción a las pruebas y la combinatoria , Cengage Learning, p. 45, ISBN 9780618415380.
- ^ Arbib, Michael A .; Kfoury, AJ; Moll, Robert N. (1981), A Basis for Theoretical Computer Science , La serie AKM en Theoretical Computer Science: Textos y monografías en informática, Springer-Verlag, p. 9, ISBN 9783540905738.
- ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Comprensión de los métodos formales , Springer, p. 21, ISBN 9781852332471.
- ^ Lee, John M. (2010), Introducción a los colectores topológicos , Textos de posgrado en matemáticas, 202 (2ª ed.), Springer, p. 64, ISBN 9781441979407.
enlaces externos
- Weisstein, Eric W. "Conjuntos disjuntos" . MathWorld .