Algebra částí množiny

Vlastnosti křižovatky jsou podobné vlastnostem schůzky. Říkáme, že jsou dvojí, protože je získáme nahrazením znaménka spojení křižovatkou a v případě potřeby výměnou ∅ a U , zahrnutí a jeho vzájemnosti. U všech podskupin , B , C, z U máme následující vlastnosti:

• (asociativita): výsledek průniku několika množin nezávisí na pořadí, ve kterém jsou operace prováděny:

(NA∩B)∩VS=NA∩(B∩VS){\ displaystyle (A \ cap B) \ cap C = A \ cap (B \ cap C)}

• (komutativita): průnik dvou množin nezávisí na pořadí, ve kterém jsou tyto dvě množiny vzaty

NA∩B=B∩NA{\ displaystyle A \ cap B = B \ cap A}

• (idempotence): průsečík libovolné množiny se sebou dává tuto množinu

NA∩NA=NA{\ displaystyle A \ cap A = A}

• (Absorbent Ø): průsečík prázdné sady a jakékoli sady je prázdný

NA∩∅=∅{\ displaystyle A \ cap \ varnothing = \ varnothing}

• U je neutrální: U ∩ = .

Sada A ∩ B je dolní mez pro zahrnutí dvou sad A a B , tj. Je zahrnuta do A a B , a že obsahuje libovolnou sadu zahrnutou současně do A a B  :

• A ∩ B ⊂ A ,   A ∩ B ⊂ B   a ∀ C [( C ⊂ A a C ⊂ B ) ⇒ C ⊂ A ∩ B ].

To umožňuje tentokrát definovat zahrnutí z křižovatky:

Distribuce

Dvě operace shledání a křižovatky jsou vzájemně distribuční , to znamená, že máme následující dvě vlastnosti pro všechny množiny A , B , C  :

• (distributivita průniku s ohledem na spojení: průnik spojení dvou množin s třetí množinou se rovná spojení průsečíku každé z prvních dvou množin s třetí:

NA∩(B∪VS)=(NA∩B)∪(NA∩VS){\ displaystyle A \ cap (B \ cup C) = (A \ cap B) \ cup (A \ cap C)}

• (distributivita spojení s ohledem na křižovatku): spojení křižovatky dvou množin s třetí množinou se rovná průsečíku spojení každé z prvních dvou množin s třetí:

NA∪(B∩VS)=(NA∪B)∩(NA∪VS){\ displaystyle A \ cup (B \ cap C) = (A \ cup B) \ cap (A \ cup C)}

Na každé straně první rovnosti je sada a chceme ukázat, že tyto sady jsou stejné, to znamená ukázat, že jakýkoli prvek patří k prvnímu právě tehdy, pokud patří k druhému. Poznámka: v tomto pořadí , b , c návrhů , , . Podle distributivity části s ohledem na (což můžeme ověřit na pravdivostní tabulky ) máme X{\ displaystyle x}X∈NA{\ displaystyle x \ v A}X∈B{\ displaystyle x \ v B}X∈VS{\ displaystyle x \ v C}∧{\ displaystyle \ land}∨{\ displaystyle \ lor}

na∧(b∨vs.)⇔(na∧b)∨(na∧vs.){\ Displaystyle a \ land (b \ lor c) \ Leftrightarrow (a \ land b) \ lor (a \ land c)}

což překládá přesně požadovanou ekvivalenci:

X∈[NA∩(B∪VS)]⇔X∈[(NA∩B)∪(NA∩VS)] .{\ displaystyle x \ in [A \ cap (B \ cup C)] \ Leftrightarrow x \ in [(A \ cap B) \ cup (A \ cap C)] ~.}

Demonstrace druhé rovnosti je identická, výměnou a . ∧{\ displaystyle \ land}∨{\ displaystyle \ lor}

Setkání a křižovatka: obecný případ

Je možné zobecnit shledání na konečný počet množin: k případu dvou množin se vracíme postupným binárním shledáním a asociativita shledání zajišťuje, že na pořadí nezáleží. Podobně pro křižovatku.

Je však také možné zobecnit tyto operace na ne nutně konečnou rodinu množin.

Spojení rodiny množin je definováno: (Ei)i∈Já{\ displaystyle (E_ {i}) _ {i \ v I}}

⋃i∈JáEi={X∈U∣∃ i∈JáX∈Ei}{\ displaystyle \ bigcup _ {i \ v I} E_ {i} = \ vlevo \ {x \ v \ mathrm {U} \ uprostřed \ existuje \ i \ v I \ quad x \ v E_ {i} \, \ že jo \}}

Tato definice není závislá na U . Sjednocení prázdné rodiny je prázdný celek.

Průsečík rodiny množin je definován: (Ei)i∈Já{\ displaystyle (E_ {i}) _ {i \ v I}}

⋂i∈JáEi={X∈U∣∀i∈JáX∈Ei}{\ displaystyle \ bigcap _ {i \ in I} E_ {i} = \ left \ {x \ in \ mathrm {U} \ mid \ forall i \ in I \ quad x \ in E_ {i} \ right \} }

Výše uvedená definice nezávisí na množině U, kromě případů, kdy je rodina prázdná. v druhém případě je průsečík prázdné rodiny podle definice referenční sada U , která zůstává kompatibilní s vlastnostmi průsečíku. Nemůžeme definovat „v absolutním“ (bez referenční sady) průnik prázdné rodiny.

Některé vlastnosti shledání a binární křižovatky se zobecňují na nekonečný případ. V sázce jsou nyní vlastnosti počtu predikátů (a již nejen výrokového počtu). Zejména:

• průnik a znovusjednocení rodiny závisí pouze na celém obrazu rodiny, který zobecňuje asociativitu, komutativitu a idempotenci a vyplývá přímo z definice;(Ei)i∈Já{\ displaystyle (E_ {i}) _ {i \ v I}}
• průsečík množinové rodiny ( E i ) i ∈ I je dolní mez množiny { E i | i ∈ I };
• spojení množinové rodiny ( E i ) i ∈ I je horní mez množiny { E i | i ∈ I };
• binární křižovatka je distribuována na jakémkoli shledání, stejně jako binární shledání na jakémkoli křižovatce: NA∩⋃i∈JáBi=⋃i∈Já(NA∩Bi){\ displaystyle A \ cap \ bigcup _ {i \ in I} B_ {i} = \ bigcup _ {i \ in I} (A \ cap B_ {i})}   ;    ;NA∪⋂i∈JáBi=⋂i∈Já(NA∪Bi){\ displaystyle A \ cup \ bigcap _ {i \ in I} B_ {i} = \ bigcap _ {i \ in I} (A \ cup B_ {i})}
• obecněji máme rovnost (ve které je inkluze okamžitá, ale inkluze používá axiom výběru, pokud je nekonečná), stejně jako dvojí rovnost .⋂i∈Já⋃j∈JiNAi,j=⋃F∈(∏i∈JáJi)⋂i∈JáNAi,F(i){\ displaystyle \ bigcap _ {i \ in I} {\ bigcup _ {j \ in J_ {i}} {A_ {i, j}}} = \ bigcup _ {f \ in \ left (\ prod _ {i \ in I} {J_ {i}} \ right)} {\ bigcap _ {i \ in I} {A_ {i, f (i)}}}}⊃{\ displaystyle \ supset}⊂{\ displaystyle \ podmnožina}Já{\ displaystyle I}

Komplementární

Referenční soubor U vzhledem je komplementární k podmnožiny A až U (význam ve vztahu k U ) je soubor prvků, U , které nepatří do A . Označuje se U - A , A , A c , nebo dokonce  : ∁NA{\ displaystyle \ doplněk A}

NAvs.={X∈U∣X∉NA}{\ displaystyle A ^ {\ mathrm {c}} = \ {x \ in \ mathrm {U} \ mid x \ notin A \}}

což znamená

Doplňkem A je závislý na sadě referenční U . Vyznačuje se také dvěma rovnostmi:

Přídavný kanál operace je involutive to znamená, že ( c ) c = .

De Morganovy zákony

Přepnutí na doplňkové obrátí relaci začlenění:

a proto si vyměňuje shledání a křižovatku, které jsou horní a dolní hranicí, to jsou De Morganovy zákony  :

Uspořádaná struktura, která, stejně jako množina částí U poskytovaných binárními operacemi sjednocení a křižovatky, operace předávání komplementu a dvou odlišných prvků ∅ a U , splňuje vlastnosti těchto vyjmenovaných operací až dosud se nazývá booleovská algebra .

Rozdíl a symetrický rozdíl

Rozdíl

Set rozdíl od A a B, označený jako "  \ B  " (čti "  minus B  ") je množina prvků A, které nepatří do B , a to:

NA∖B={X∈NA∣X∉B}{\ displaystyle A \ setminus B = \ {x \ v A \ mid x \ notin B \}}

Rozdíl A a B v U je definována z komplementární ∩ B C , a pak se ( ∩ B c ) c = c ∪ B .

Pokud je B zahrnuto v A , pak A \ B se také píše „  A - B  “ (přečtěte si znovu „  A minus B  “) a nazývá se doplňkem k B v A (nebo relativně k A ). Pojem komplementární nacházíme výše, který je komplementární relativně k U  :

NA∖B=NA-B=∁NAB={X∈NA∣X∉B}{\ displaystyle A \ setminus B = AB = \ doplněk _ {A} B = \ {x \ v A \ mid x \ notin B \}}

Vlastnosti rozdílu

My máme :

x ∈ A \ B právě   tehdy, když   x ∈ A a x ∉ B x ∉ A \ B právě   tehdy, když   x ∈ A ⇒ x ∈ B

a tak:

\ B = ∅ právě tehdy, když   A ⊂ B .

Vlastnosti rozdílu jsou získány z jeho definice a z vlastností spojení křižovatky a doplňku. Například první, která následuje, je řada křižovatek, zatímco druhá používá zákon De Morgan a distribučnost křižovatky na unii.

(NA∩B)∖VS=NA∩(B∖VS)=(NA∖VS)∩(B∖VS){\ displaystyle (A \ cap B) \ setminus C = A \ cap (B \ setminus C) = (A \ setminus C) \ cap (B \ setminus C)} NA∖(B∩VS)=(NA∖B)∪(NA∖VS){\ Displaystyle A \ setminus (B \ cap C) = (A \ setminus B) \ pohár (A \ setminus C)}.

Symetrický rozdíl

Symetrický rozdíl od A a B , označený jako „  Δ B  “ (čti „  delta B  “) je soubor prvků, které patří buď A nebo B , ale ne obojí současně. To je rozdíl A ∪ B a A ∩ B . Může být napsán v různých formách:

NAΔB=(NA∪B)∖(NA∩B)=(NA∖B)∪(B∖NA)=(NA∩Bvs.)∪(B∩NAvs.){\ Displaystyle A \, \ Delta \, B = (A \ cup B) \ setminus (A \ cap B) = (A \ setminus B) \ cup (B \ setminus A) = (A \ cap B ^ {\ mathrm {c}}) \ cup (B \ cap A ^ {\ mathrm {c}})}.

My máme :

x ∈ A Δ B právě   tehdy, když buď x ∈ A nebo x ∈ B (nebo exkluzivní) x ∉ A Δ B právě   tehdy, když   x ∈ A ⇔ x ∈ B

tedy symetrický rozdíl dvou sad je prázdný právě tehdy, když jsou dvě sady stejné:

Δ B = ∅ tehdy a jen tehdy, pokud   = B . Vlastnosti symetrického rozdílu

Souprava částí U opatřen symetrickým operace rozdíl je komutativní skupina , s ∅ pro neutrální prvek, a kde každá podskupina U je vlastní opačný, to znamená, že pro to vše pod -sets A , B , C, z U , máme:

• (asociativita): symetrický rozdíl tří sad nezávisí na pořadí, ve kterém jsou operace prováděny, závorky nejsou nutné:

(NAΔB)ΔVS=NAΔ(BΔVS){\ displaystyle (A \, \ Delta \, B) \, \ Delta \, C = A \, \ Delta \, (B \, \ Delta \, C)} a můžeme psát delta B delta C .

• (komutativita): symetrický rozdíl dvou sad nezávisí na pořadí, ve kterém jsou tyto sady přijímány:

NAΔB=BΔNA{\ displaystyle A \, \ Delta \, B = B \, \ Delta \, A}

• Ø je neutrální prvek: symetrický rozdíl prázdné množiny a jiné množiny dává této množině:

NAΔ∅=NA{\ displaystyle A \, \ Delta \, \ varnothing = A}

• Každá podmnožina má svůj vlastní opak: symetrický rozdíl libovolné množiny se sebou samou dává prázdnou množinu:

NAΔNA=∅{\ displaystyle A \, \ Delta \, A = \ varnothing}

Jedním z důsledků je pravidelnost: pokud A delta B = A , delta C , pak B = C .

Sada částí U za předpokladu, kromě symetrického rozdílu, s průsečíkem, je jednotný komutativní kruh , to znamená, že kromě asociativních a komutativních vlastností průniku, a že U je neutrální prvek

• Distribučnost ∩ vzhledem k Δ: průsečík množiny se symetrickým rozdílem dvou dalších množin se rovná symetrickému rozdílu průsečíků první množiny s každou z ostatních dvou:

NA∩(BΔVS)=(NA∩B)Δ(NA∩VS){\ displaystyle A \ cap (B \, \ Delta \, C) = (A \ cap B) \, \ Delta \, (A \ cap C)}.

Symetrický rozdíl, na rozdíl od sjednocení, není distribuční vzhledem k průsečíku.

Obecnou vlastností booleovských algeber je to, že operace definovaná jako symetrický rozdíl (se sjednocením průsečíkem a přechodem k doplňku) umožňuje definovat prstencovou strukturu, někdy nazývanou booleovským kruhem. Ostatní vlastnosti společné pro všechny booleovské algebry se ověřují jako:

C = U Δ   a proto   c Δ = U .

nebo ( A Δ B ) c = A c Δ B = A Δ B c .

Axiomatické aspekty

Z axiomatického hlediska se v teorii množin vše, co předchází, vyvíjí z axiomu extenzivity (rovnost dvou množin), který zaručuje zejména jedinečnost zavedených konstrukcí a schématu axiomů porozumění , které zaručuje jejich existenci , přičemž všechny zavedené množiny jsou definovány jako podmnožina dané množiny U.

Poznámky a odkazy

• Tento článek je částečně nebo zcela převzat z článku s názvem „  Nastavovací operace  “ (viz seznam autorů ) .

1. (in) Robert L. Vaught , Teorie množin: Úvod , Birkhauser ,2001, 2 nd  ed. ( 1 st  ed. 1985) ( číst on-line ) , str.  21.
2. Ale tento zápis pro nastavený rozdíl může vést k záměně s algebraickým rozdílem . Například: while .[0,1]∖[0,1]=∅{\ displaystyle [0,1] \ setminus [0,1] = \ varnothing}{X-y∣X,y∈[0,1]}=[-1,1]{\ displaystyle \ {xy \ mid x, y \ in [0,1] \} = [- 1,1]}

Podívejte se také

• Naivní teorie množin
• Nastavit algebru
• Booleova algebra (logika)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">