Osammanhängande uppsättningar

Inom matematiken sägs två uppsättningar vara osammanhängande , eller osammanhängande , om de inte har några gemensamma element. På motsvarande sätt är disjunkta mängder mängder vars skärningspunkt är den tomma mängden [1] . Till exempel är {1, 2, 3} och {4, 5, 6} disjunkta uppsättningar, medan {1, 2, 3} och {3, 4, 5} inte är det.

Generaliseringar

Ovanstående definition av disjunkta uppsättningar kan utökas till vilken familj av uppsättningar som helst . En familj av mängder är parvis disjunktiv (beståndsdelar är parvis disjunktiva ) om två grupper i familjen inte har några gemensamma element [1] . Till exempel är uppsättningen av uppsättningar { {1}, {2}, {3}, ... } parvis disjunkta.

Två uppsättningar sägs vara nästan osammanhängande om deras skärningspunkt i någon mening är liten. Till exempel kan två oändliga mängder vars skärningspunkt är en ändlig mängd anses nästan osammanhängande [2] .

Inom topologi finns det olika notationer för separerade mängder med strängare villkor än ingen skärning. Till exempel sägs två uppsättningar vara separerbara när de har osammanhängande stängningar eller osammanhängande kvarter . På liknande sätt, i ett metriskt utrymme, är positivt separerade mängder mängder åtskilda av ett avstånd som inte är noll [3] .

Exempel

Korsningar

Osammanhängandet av mängder eller familjer av mängder kan uttryckas i termer av skärningspunkter .

Två uppsättningar A och B är disjunkta om och endast om deras skärningspunkt är en tom uppsättning [1] . Det följer av denna definition att varje mängd är disjunktiv med den tomma mängden, och den tomma mängden är den enda mängden som är disjunktiv till sig själv [4] .

En familj F av mängder är parvis disjunktiv om för två uppsättningar i familjen deras skärningspunkt är tom [1] . Om en familj innehåller mer än en uppsättning, följer det att skärningspunkten mellan alla uppsättningar i familjen är tom. En enstaka familj är dock per definition "parvis osammanhängande" och kan uppenbarligen ha en icke-tom korsning. Dessutom kan en familj av uppsättningar ha en tom skärningspunkt, men inte vara parvis osammanhängande [5] . Till exempel har tre uppsättningar { {1, 2}, {2, 3}, {1, 3} } en tom skärningspunkt, men de är inte parvis disjunkta. Faktum är att det inte finns två osammanhängande uppsättningar i denna uppsättning. Dessutom är den tomma familjen av uppsättningar parvis osammanhängande [6] .

En Helly-familj  är ett uppsättningssystem där endast underfamiljer med tom skärningspunkt är parvis osammanhängande. Till exempel bildar slutna intervall på den reella axeln en Helly-familj - om en familj av slutna intervall har en tom skärningspunkt och är minimal (det vill säga ingen underfamilj har en tom skärning) måste den vara parvis disjunkt [7] .

Osammanhängande fackföreningar och partitioner

En partition av en mängd X är vilken som helst uppsättning av ömsesidigt disjunkta mängder vars förening är lika med X [8] . Vilken partition som helst kan på motsvarande sätt beskrivas av en ekvivalensrelation , en binär relation som bestämmer om två element tillhör samma mängd i nedbrytningen eller inte [8] . Disjoint set-system [9] och partitionsförfining [10] är två tekniker inom datavetenskap för att effektivt hantera partitioner av en uppsättning objekt, respektive för unionsoperationen, som slår samman två uppsättningar, och förfiningsoperationen, som delar upp ett set i två. .

En osammanhängande förening kan betyda två saker. I det enklaste fallet kan detta innebära föreningen av disjunktiva mängder [11] . Men om två eller flera uppsättningar inte är disjunkta, kan deras disjunkta förening bildas genom att modifiera uppsättningarna [12] [13] . Till exempel kan två uppsättningar göras disjunkta genom att ersätta element med ordnade par av element och ett index som avgör om elementet tillhör den första eller andra uppsättningen [14] . Samma teknik kan tillämpas på familjer med fler än två uppsättningar [15] .

Se även

Anteckningar

  1. ↑ 1 2 3 4 Halmos, 1960 , sid. femton.
  2. ↑ Halbeisen, 2011 , sid. 184.
  3. ↑ Copson, 1988 , sid. 62.
  4. ↑ Oberste-Vorth, Mouzakitis, Lawrence, 2012 , sid. 59.
  5. ↑ Smith, Eggen, St. Andrew, 2010 , sid. 95.
  6. ↑ Se svaren på frågan ″Är den tomma familjen av set parvis disjunktiv?″ Arkiverad 20 oktober 2020 på Wayback Machine
  7. ↑ Bollobás, 1986 , sid. 82.
  8. ↑ 1 2 Halmos, 1960 , sid. 28.
  9. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , sid. 498–524.
  10. ↑ Paige, Tarjan, 1987 , sid. 973–989.
  11. ↑ Ferland, 2008 , sid. 45.
  12. ↑ Arbib, Kfoury, Moll, 1981 , sid. 9.
  13. ↑ I Vavilovs bok förstås disjunktiv förening endast i första meningen. För förening i den andra betydelsen används termen fri förening , fri summa eller samprodukt av mängder .
  14. ↑ Monin och Hinchey, 2003 , sid. 21.
  15. ↑ Lee, 2010 , sid. 64.

Litteratur

Länkar