Algebra af delene af et sæt

I sætteori har sættet af dele af et sæt , udstyret med operationerne i kryds , union og passage til komplementet , en boolsk algebrastruktur . Andre operationer kan udledes heraf, såsom den indstillede forskel og den symmetriske forskel ...

Den algebra af sæt studeret aritmetiske af disse operationer (se " Operation ensemblist " for operationer, der ikke forlader permanent alle dele af en helhed).

Inklusion og lighed

I hele artiklen, sættene anses alle formodes at indgå i et givent sæt U . Integration er en (delvis) ordre forhold bemærkede ”⊂” eller ”⊆”, og defineret på sættet af dele af U , bemærkede P ( U ), ved:

A ⊂ B hvis og kun hvis ∀ x ∈ U ( x ∈ A ⇒ x ∈ B ).

Lighed er defineret ved ekstensionalitet, to sæt er ens, når de har de samme elementer, det vil sige at:

A = B hvis og kun hvis ∀ x ∈ U ( x ∈ A ⇔ x ∈ B ).

eller

A = B hvis og kun hvis A ⊂ B og B ⊂ A .

Følgende egenskaber svarer derfor for ligestillingerne til ækvivalenser i propositionel beregning, hvorfra de udledes. De kan visualiseres med Venn-diagrammer , en skematisk måde at beskrive alle mulige tilfælde for, at et element tilhører et endeligt (og tilstrækkeligt reduceret) antal sæt, og som derfor også kan give mulighed for at beskrive bevis lighed eller inkludering.

Tilsvarende indeslutninger koger ned til implikationer.

Møde og kryds

Kombination af to sæt

Den union sæt af A og B , bemærkede " A U B " (læs " A union B "), er det sæt af elementer, som tilhører A eller B :

{\ displaystyle A \ cup B = \ {x \ in \ mathrm {U} \ mid (x \ in A) \ lor (x \ in B) \}}

hvilket betyder :

x ∈ A ∪ B hvis og kun hvis x ∈ A eller x ∈ B . Ejendomme

Sættet U leveret med unionen har følgende egenskaber (for alle undergrupper A , B , C af U ):

(associativitet): resultatet af sammenføjning af flere sæt afhænger ikke af rækkefølgen, hvor sammenføjningsoperationer udføres:

(A \ kop B) \ kop C = A \ kop (B \ kop C)

og vi betegner med A ∪ B ∪ C dette sæt;

(kommutativitet): foreningen af to sæt afhænger ikke af rækkefølgen, i hvilken disse to sæt tages:

A \ kop B = B \ kop A

;

(idempotence): genforening af ethvert sæt med sig selv giver dette sæt igen:

A \ kop A = A

;

Ø er neutral : foreningen af det tomme sæt med ethvert sæt giver dette sæt igen:

A \ cup \ varnothing = A

;

U er absorberende: U ∪ A = U .

Sættet A ∪ B er den øvre grænse for inkludering af de to sæt A og B , dvs. det indeholder A og B , og det er indeholdt i ethvert sæt, der indeholder A og B :

A ⊂ A ∪ B , B ⊂ A ∪ B og ∀ C [( A ⊂ C og B ⊂ C ) ⇒ A ∪ B ⊂ C ].

Derfor er inkludering defineret fra mødet:

A ⊂ B hvis og kun hvis A ∪ B = B .

Skæringspunkt mellem to sæt

Den skæringspunktet sæt af A og B , betegnet ” A ∩ B ” (læs ” A inter B ”) er det sæt af elementer af A , der også elementer af B , nemlig:

{\ displaystyle A \ cap B = \ {x \ in \ mathrm {U} \ mid (x \ in A) \ land (x \ in B) \}}

hvilket betyder :

x ∈ A ∩ B hvis og kun hvis x ∈ A og x ∈ B .

To sæt, der ikke har noget element til fælles, dvs. deres skæringspunkt er tom, siges at være adskilt .

Ejendomme

Krydsets egenskaber svarer til fagforeningens. Vi siger, at de er dobbelte af disse, fordi vi opnår dem ved at erstatte foreningstegnet med skæringspunktet og om nødvendigt ved at udveksle ∅ og U , inklusionen og dens gensidige. For alle undergrupper A , B , C af U har vi følgende egenskaber:

(associativitet): resultatet af skæringspunktet mellem flere sæt afhænger ikke af rækkefølgen, som operationerne udføres i:

(A \ cap B) \ cap C = A \ cap (B \ cap C)

og vi betegner med A ∩ B ∩ C dette sæt;

(kommutativitet): skæringspunktet mellem to sæt afhænger ikke af rækkefølgen, i hvilken disse to sæt tages

A \ cap B = B \ cap A

;

(idempotence): skæringspunktet mellem ethvert sæt og sig selv giver dette sæt

A \ cap A = A

(Ø absorberende): skæringspunktet mellem det tomme sæt og ethvert sæt er tomt

A \ cap \ varnothing = \ varnothing

;

U er neutral: U ∩ A = A .

Sættet A ∩ B er den nedre grænse for inklusionen af de to sæt A og B , dvs. det er inkluderet i A og i B , og at det indeholder ethvert sæt inkluderet på samme tid i A og i B :

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

Dette gør det muligt at definere inklusionen fra skæringspunktet denne gang:

A ⊂ B hvis og kun hvis A ∩ B = A .

Distributivitet

De to forenings- og krydsoperationer er fordelt på hinanden, det vil sige, at vi har følgende to egenskaber for alle sæt A , B , C :

(krydsets fordelingsevne i forhold til foreningen: krydset mellem foreningen af to sæt med et tredje sæt er lig med foreningen af krydset mellem hvert af de første to sæt med det tredje:

A \ cap (B \ cup C) = (A \ cap B) \ cup (A \ cap C)

;

(foreningens fordeling med hensyn til krydset): foreningen af skæringspunktet mellem to sæt med et tredje sæt er lig med skæringspunktet mellem foreningen mellem hvert af de første to sæt med det tredje:

A \ cup (B \ cap C) = (A \ cup B) \ cap (A \ cup C)

. Demonstration

På hver side af den første lighed er der et sæt, og vi vil vise, at disse sæt er ens, det vil sige at vise, at ethvert element hører til det første, hvis og kun hvis det hører til det andet. Bemærk henholdsvis en , b , c forslag , , . Ifølge distributivitet af med hensyn til (som vi kan konstatere, om sandhed tabel ) vi har $x$ $x \ i A$ $x \ i B$ $x \ i C$ $\ land$ $\ lor$

a \ land (b \ lor c) \ Leftrightarrow (a \ land b) \ lor (a \ land c)

som oversætter nøjagtigt den ønskede ækvivalens:

x \ i [A \ cap (B \ cup C)] \ Lefttrightarrow x \ i [(A \ cap B) \ cup (A \ cap C)] ~.

Demonstrationen af den anden lighed er identisk ved udveksling og . $\ land$ $\ lor$

Møde og kryds: almindelig sag

Det er muligt at generalisere genforeningen til et begrænset antal sæt: vi kommer tilbage til tilfældet med to sæt ved successiv binær genforening, og genforeningens associativitet sikrer, at ordren ikke betyder noget. Ligeledes til krydset.

Men det er også muligt at generalisere disse operationer til en ikke nødvendigvis endelig familie af sæt.

Foreningen af en familie af sæt defineres af: $(E_i) _ {i \ i I}$

{\ displaystyle \ bigcup _ {i \ i I} E_ {i} = \ venstre \ {x \ i \ mathrm {U} \ mid \ findes \ i \ i I \ quad x \ i E_ {i} \, \ ret \}}

Denne definition er ikke afhængig af U . En tom families genforening er den tomme helhed.

Skæringspunktet mellem en familie af sæt er defineret af: $(E_i) _ {i \ i I}$

{\ displaystyle \ bigcap _ {i \ in I} E_ {i} = \ left \ {x \ in \ mathrm {U} \ mid \ forall i \ in I \ quad x \ in E_ {i} \ right \} }

Ovenstående definition afhænger ikke af sæt U undtagen når familien er tom. i sidstnævnte tilfælde er skæringspunktet mellem den tomme familie pr. definition referencesættet U , som forbliver kompatibelt med krydsets egenskaber. Vi kan ikke definere "i det absolutte" (uden et referencesæt) skæringspunktet mellem en tom familie.

Nogle af egenskaberne ved genforening og binært kryds generaliserer til det uendelige tilfælde. Det er nu egenskaber ved beregningen af predikater (og ikke længere kun af den foreslåede beregning), der står på spil. Især:

skæringspunktet og genforeningen af en familie afhænger kun af hele billedet af familien, som generaliserer associativitet, kommutativitet og fritid og følger direkte fra definitionen; $(E_i) _ {i \ i I}$
skæringspunktet mellem en sætfamilie ( E i ) i ∈ I er den nedre grænse for sættet { E i | i ∈ I };
foreningen af et sæt familie ( E jeg ) jeg ∈ Jeg er den øvre grænse for mængden { E i | i ∈ I };
det binære kryds fordeles over ethvert genforening, såvel som det binære genforening over ethvert kryds: ${\ displaystyle A \ cap \ bigcup _ {i \ in I} B_ {i} = \ bigcup _ {i \ in I} (A \ cap B_ {i})}$ ; ; ${\ displaystyle A \ cup \ bigcap _ {i \ in I} B_ {i} = \ bigcap _ {i \ in I} (A \ cup B_ {i})}$
mere generelt har vi lighed (hvor inklusionen er øjeblikkelig, men inklusionen bruger det valgte aksiom, hvis det er uendeligt) såvel som dobbelt lighed . ${\ displaystyle \ bigcap _ {i \ i I} {\ bigcup _ {j \ i J_ {i}} {A_ {i, j}}} = \ bigcup _ {f \ in \ left (\ prod _ {i \ i I} {J_ {i}} \ højre)} {\ bigcap _ {i \ i I} {A_ {i, f (i)}}}}$ $\ supset$ $\ delmængde$ $jeg$

Supplerende

En reference sæt U givet, komplementære af delmængden A til U (dvs. i forhold til U ) er det sæt af elementer, U , som ikke hører til A . Det er betegnet med U - A , A , A c eller endda : $\ supplement A$

{\ displaystyle A ^ {\ mathrm {c}} = \ {x \ in \ mathrm {U} \ mid x \ notin A \}}

hvilket betyder

x ∈ A c hvis og kun hvis x ∈ U og x ∉ A .

Den supplement af A afhænger af det sæt af henvisningen U . Det er også kendetegnet ved de to ligheder:

A ∩ A c = ∅ og A ∪ A c = U .

Den yderligere passage operation er involutive dvs. ( A c ) c = A .

De Morgans love

Skiftet til det komplementære vender inklusionsrelationen:

A ⊂ B hvis og kun hvis B c ⊂ A c

og derfor udveksler det genforeningen og krydset, som er den øvre og nedre grænse, disse er De Morgans love :

( A ∩ B ) c = A c ∪ B c ; ( A ∪ B ) c = A c ∩ B c .

En ordnet struktur, der i lighed med det sæt af de dele af U, der er forsynet med binære operationer af genforening og skæringspunkt, af operationen ved at passere til komplementet og af de to fremtrædende elementer ∅ og U , opfylder egenskaberne ved disse operationer, der er opregnet 'nu kaldes boolsk algebra .

Forskel og symmetrisk forskel

Forskel

Den indstillede forskel af A og B betegnes " A \ B " (læs " A minus B ") er det sæt af elementer af A , som ikke hører til B , nemlig:

A \ setminus B = \ {x \ i A \ mid x \ notin B \}

Forskellen på A og B i U defineres fra den komplementære A ∩ B c , og derefter ( A ∩ B c ) c = A c ∪ B .

Hvis B er inkluderet i A , så er A \ B også skrevet " A - B " (læs igen " A minus B ") og kaldes komplementær til B i A (eller relativt til A ). Vi finder forestillingen om komplementær ovenfor, som er den komplementære relativt til U :

{\ displaystyle A \ setminus B = AB = \ supplement _ {A} B = \ {x \ i A \ mid x \ notin B \}}

. Forskelens egenskaber

Vi har :

x ∈ A \ B hvis og kun hvis x ∈ A og x ∉ B x ∉ A \ B hvis og kun hvis x ∈ A ⇒ x ∈ B

også :

En \ B = ∅ hvis og kun hvis A ⊂ B .

Forskellens egenskaber opnås fra dens definition og fra egenskaberne af krydset og komplementet. For eksempel er det første, der følger, en række skæringspunkter, mens den anden bruger en De Morgan-lov og krydsets fordelingsevne på unionen.

(A \ cap B) \ setminus C = A \ cap (B \ setminus C) = (A \ setminus C) \ cap (B \ setminus C)

A \ setminus (B \ cap C) = (A \ setminus B) \ cup (A \ setminus C)

Symmetrisk forskel

Den symmetriske forskel på A og B , betegnet " A A B " (læs " A delta B ") er det sæt af elementer, der hører til A eller B , men ikke til begge på samme tid. Det er forskellen på A ∪ B og A ∩ B . Det kan skrives i forskellige former:

{\ 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}})}

Vi har :

x ∈ A Δ B hvis og kun hvis enten x ∈ A eller x ∈ B (eller eksklusiv) x ∉ A Δ B hvis og kun hvis x ∈ A ⇔ x ∈ B

således er den symmetriske forskel på to sæt tom, hvis og kun hvis de to sæt er ens:

A Δ B = ∅ hvis og kun hvis A = B . Egenskaber ved symmetrisk forskel

Sættet af dele af U forsynet med den symmetriske forskeloperation er en kommutativ gruppe med ∅ for neutralt element, og hvor hver delmængde af U er sin modsatte, det vil sige for alle undersæt A , B , C af U , vi har:

(associativitet): den symmetriske forskel på tre sæt afhænger ikke af rækkefølgen, hvor operationerne udføres, parenteser er ikke nødvendige:

{\ displaystyle (A \, \ Delta \, B) \, \ Delta \, C = A \, \ Delta \, (B \, \ Delta \, C)}

og vi kan skrive en Δ B Δ C .

(kommutativitet): den symmetriske forskel på to sæt afhænger ikke af rækkefølgen, i hvilken disse sæt tages:

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

Ø er et neutralt element: den symmetriske forskel på det tomme sæt og et andet sæt giver dette sæt:

{\ displaystyle A \, \ Delta \, \ varnothing = A}

Hver delmængde er sin modsatte: den symmetriske forskel på ethvert sæt med sig selv giver det tomme sæt:

{\ displaystyle A \, \ Delta \, A = \ varnothing}

En konsekvens er gyldigheden: hvis A Δ B = A Δ C , derpå B = C .

Sættet af dele af U tilvejebragt, ud over den symmetriske forskel, med skæringspunktet, er en enhedskommutativ ring , det vil sige, at ud over associationsegenskaber og kommutativitetsegenskaber for skæringspunktet, og at U er et neutralt element

Distributivitet af ∩ i forhold til Δ: skæringspunktet mellem et sæt og den symmetriske forskel på to andre sæt er lig med den symmetriske forskel i skæringspunkterne i det første sæt med hvert af de to andre sæt:

{\ displaystyle A \ cap (B \, \ Delta \, C) = (A \ cap B) \, \ Delta \, (A \ cap C)}

Den symmetriske forskel er i modsætning til unionen ikke distribuerende med hensyn til krydset.

Det er en generel egenskab ved boolske algebraer, at en operation defineret som den symmetriske forskel (med foreningen krydset og passagen til komplementet) gør det muligt at definere en ringstruktur, undertiden kaldet en boolsk ring. Andre egenskaber, der er fælles for alle boolske algebraer, er verificeret som:

En c = U Δ A og derfor A c Δ A = U .

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

Axiomatiske aspekter

Fra et aksiomatisk synspunkt udvikler alt i set- teorien alt, hvad der foregår ud fra aksiomet af ekstensionalitet (lighed med to sæt), hvilket især garanterer det unikke ved de indførte konstruktioner og ordningen med forståelsesaksiomer , som garanterer deres eksistens hvor alle de indførte sæt defineres som en delmængde af et givet sæt U.

Noter og referencer

Denne artikel er helt eller delvist taget fra artiklen " Set-up operation " (se listen over forfattere ) .

(i) Robert L. Vaught , Set Teori: An Introduction , Birkhauser ,2001, 2 nd ed. ( 1 st ed. 1985) ( læses online ) , s. 21.
Men denne notation for den indstillede forskel kan føre til forveksling med den algebraiske forskel . For eksempel: mens . ${\ displaystyle [0,1] \ setminus [0,1] = \ varnothing}$ ${\ displaystyle \ {xy \ mid x, y \ in [0,1] \} = [- 1,1]}$

Se også