Conjuntos disjuntos

En matemáticas , se dice que dos conjuntos son disjuntos , o disjuntos , si no tienen elementos en común. De manera equivalente, los 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.

Generalizaciones

La definición anterior de conjuntos disjuntos se puede extender a cualquier familia de conjuntos . Una familia de conjuntos es disyuntiva por pares (los elementos son disjuntos por pares ) si dos conjuntos cualesquiera de la familia no tienen elementos en común [1] . Por ejemplo, el conjunto de conjuntos { {1}, {2}, {3}, ... } es disjunto por pares.

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 considerarse casi disjuntos [2] .

En topología , hay varias notaciones para conjuntos separados con condiciones más estrictas que ninguna intersección. Por ejemplo, se dice que dos conjuntos son separables cuando tienen cierres disjuntos o vecindades disjuntas . De manera similar, en un espacio métrico, los conjuntos separados positivamente son ​​conjuntos separados por una distancia distinta de cero [3] .

Ejemplos

Cruces

La disyunción de conjuntos o familias de conjuntos se puede expresar en términos de intersecciones .

Dos conjuntos A y B son disjuntos si y solo si su intersección es un conjunto vacío [1] . De esta definición se sigue que cualquier conjunto es disyuntivo con el conjunto vacío, y el conjunto vacío es el único conjunto que es disyuntivo consigo mismo [4] .

Una familia F de conjuntos es disyuntiva por pares si para dos conjuntos cualesquiera de la familia su intersección está vacía [1] . Si una familia contiene más de un conjunto, se deduce que la intersección de todos los conjuntos de la familia está vacía. Sin embargo, una familia de un solo conjunto es, por definición, "disjunta por pares" y obviamente puede tener una intersección no vacía. Además, una familia de conjuntos puede tener una intersección vacía, pero no ser disjuntos por pares [5] . Por ejemplo, tres conjuntos {{1, 2}, {2, 3}, {1, 3} } tienen una intersección vacía, pero no son pares disjuntos. De hecho, no hay dos conjuntos disjuntos en este conjunto. Además, la familia vacía de conjuntos es disjunta por parejas [6] .

Una familia Helly  es un sistema de conjuntos en el que solo las subfamilias con intersección vacía son disjuntas por pares. Por ejemplo, los intervalos cerrados en el eje real forman una familia Helly: si una familia de intervalos cerrados tiene una intersección vacía y es mínima (es decir, ninguna subfamilia 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 conjunto de conjuntos disjuntos entre sí cuya unión es igual a X [8] . Cualquier partición puede ser equivalentemente descrita por una relación de equivalencia , una relación binaria que determina si dos elementos pertenecen al mismo conjunto en la descomposición o no [8] . Los sistemas de conjuntos disjuntos [9] y el refinamiento de particiones [10] son ​​dos técnicas en ciencias de la computación para tratar eficazmente con particiones de un conjunto de objetos, respectivamente, para la operación de unión, que fusiona dos conjuntos, y la operación de refinamiento, que divide un conjunto en dos. .

Una unión disjunta puede significar dos cosas. En el caso más simple, esto puede significar la unión de conjuntos disyuntivos [11] . Pero si dos o más conjuntos no son disjuntos, su unión disjunta puede formarse modificando los conjuntos [12] [13] . Por ejemplo, dos conjuntos se pueden separar reemplazando elementos con pares ordenados de elementos y un índice que determina si el elemento pertenece al primer o segundo conjunto [14] . La misma técnica se puede aplicar a familias con más de dos juegos [15] .

Véase también

Notas

  1. ↑ 1 2 3 4 Halmos, 1960 , pág. quince.
  2. ↑ Halbeisen, 2011 , pág. 184.
  3. ↑ Copson, 1988 , pág. 62.
  4. ↑ Oberste-Vorth, Mouzakitis, Lawrence, 2012 , pág. 59.
  5. ↑ Smith, Eggen, St. Andrés, 2010 , pág. 95.
  6. ↑ Vea las respuestas a la pregunta ″¿La familia vacía de conjuntos es disyuntiva por pares?″ Archivado el 20 de octubre de 2020 en Wayback Machine .
  7. ↑ Bollobas, 1986 , p. 82.
  8. ↑ 1 2 Halmos, 1960 , p. 28
  9. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 498–524.
  10. ↑ Paige, Tarjan, 1987 , pág. 973–989.
  11. ↑ Ferland, 2008 , pág. 45.
  12. ↑ Arbib, Kfoury, Moll, 1981 , pág. 9.
  13. ↑ En el libro de Vavilov, la unión disyuntiva se entiende solo en el primer sentido. Para unión en el segundo sentido, se utiliza el término unión libre , suma libre o coproducto de conjuntos .
  14. ↑ Monin y Hinchey, 2003 , pág. 21
  15. ↑ Lee, 2010 , pág. 64.

Literatura

Enlaces