I mengdeteorien har settet med deler av et sett , utstyrt med operasjonene ved kryss , forening og passering til komplementet , en boolsk algebrastruktur . Andre operasjoner kan trekkes fra dette, for eksempel den innstilte forskjellen og den symmetriske forskjellen ...
Den algebra sett studert aritmetiske av disse operasjonene (se " Operasjon ensemblist " for operasjoner som ikke forlater permanente alle deler av en helhet).
Gjennom artikkelen, sett anses alle ment å bli inkludert i et gitt sett U . Inkluderingen er en (delvis) rekkefølge relasjon bemerket "⊂" eller "⊆", og definert på settet med deler av U , bemerket P ( U ), av:
A ⊂ B hvis og bare hvis ∀ x ∈ U ( x ∈ A ⇒ x ∈ B ).Likhet er definert av utvidelse, to sett er like når de har de samme elementene, det vil si at:
A = B hvis og bare hvis ∀ x ∈ U ( x ∈ A ⇔ x ∈ B ).eller
A = B hvis og bare hvis A ⊂ B og B ⊂ A .Følgende egenskaper tilsvarer derfor, for likhetene, ekvivalenser i proposisjonskalkulator som de er trukket fra. De kan visualiseres med Venn-diagrammer , en skjematisk måte å beskrive alle mulige tilfeller for medlemskap av et element til et endelig (og tilstrekkelig redusert) antall sett, og som derfor også kan tillate å beskrive demonstrasjoner likhet eller inkludering.
Tilsvarende inneslutninger koker ned til implikasjoner.
Den union sett av A og B , betegnet " A U B " (les " A union B "), er det sett av elementer som hører til A eller B :
som betyr :
x ∈ A ∪ B hvis og bare hvis x ∈ A eller x ∈ B . EiendommerSettet U som følger med unionen har følgende egenskaper (for alle delmengder A , B , C av U ):
Settet A ∪ B er den øvre grensen for inkludering av de to settene A og B , dvs. det inneholder A og B , og det er inneholdt i ethvert sett som inneholder A og B :
Derfor er inkludering definert fra møtet:
A ⊂ B hvis og bare hvis A ∪ B = B .Den kryss sett av A og B , betegnet “ A ∩ B ” (les “ A inter B ”) er settet av elementer av A som også er elementer av B , nemlig:
som betyr :
x ∈ A ∩ B hvis og bare hvis x ∈ A og x ∈ B .To sett som ikke har noe felles element, dvs. skjæringspunktet er tomt, sies å være usammenhengende .
EiendommerKryssets egenskaper ligner på møtet. Vi sier at de er doble av disse, fordi vi oppnår dem ved å erstatte tegnet på union med krysset, og om nødvendig ved å utveksle ∅ og U , inkluderingen og dens gjensidige. For alle delmengder A , B , C av U har vi følgende egenskaper:
Settet A ∩ B er den nedre grensen for inkludering av de to settene A og B , dvs. det er inkludert i A og i B , og at det inneholder et sett som er inkludert samtidig i A og B :
Dette gjør at inkluderingen kan defineres fra skjæringspunktet denne gangen:
A ⊂ B hvis og bare hvis A ∩ B = A .De to operasjonene av gjenforening og skjæringspunkt er distribuerende i forhold til hverandre, det vil si at vi har følgende to egenskaper, for alle sett A , B , C :
På hver side av den første likheten er det et sett, og vi vil vise at disse settene er like, det vil si å vise at ethvert element tilhører det første hvis og bare hvis det tilhører det andre. Merk henholdsvis en , b , c forslag , , . Ifølge distributivity av med hensyn til (som vi kan bekrefte på en sannhet tabell ) har vi
som oversetter nøyaktig ønsket ekvivalens:
Demonstrasjonen av den andre likheten er identisk, ved å utveksle og .
Det er mulig å generalisere gjenforeningen til et endelig antall sett: vi kommer tilbake til saken med to sett ved påfølgende binær gjenforening, og assosiativiteten til gjenforeningen sørger for at rekkefølgen ikke betyr noe. Likeledes for krysset.
Men det er også mulig å generalisere disse operasjonene til en ikke nødvendigvis endelig familie av sett.
Foreningen av en familie av sett er definert av:
.Denne definisjonen er ikke avhengig av U . Gjenforeningen til en tom familie er den tomme helheten.
Skjæringspunktet mellom en familie av sett er definert av:
.Definisjonen ovenfor avhenger ikke av settet U unntatt når familien er tom. i sistnevnte tilfelle er skjæringspunktet til den tomme familien per definisjon referansesettet U , som forblir kompatibelt med egenskapene til krysset. Vi kan ikke definere "i det absolutte" (uten et referansesett) skjæringspunktet til en tom familie.
Noen av egenskapene til gjenforening og binært skjæringspunkt generaliserer til det uendelige tilfellet. Det er nå egenskapene til beregningen av predikater (og ikke lenger bare for den foreslåtte beregningen) som står på spill. Spesielt:
En referanse sett U gitt, den komplementære av delmengden A til U (det vil si med hensyn på U ) er det settet med elementer U som ikke hører til en . Det er betegnet med U - A , A , A c , eller til og med :
som betyr
x ∈ A c hvis og bare hvis x ∈ u og x ∉ A .Komplementet av A er avhengig av settet med referanse U . Det er også preget av de to likhetene:
En ∩ A c = ∅ og A ∪ A c = U .Den ytterligere passasje operasjon er involutiv det vil si ( A c ) c = A .
Byttet til det komplementære reverserer inkluderingsforholdet:
A ⊂ B hvis og bare hvis B c ⊂ A cog derfor bytter det gjenforeningen og krysset, som er øvre og nedre grense, dette er De Morgans lover :
( A ∩ B ) c = A c ∪ B c ; ( A ∪ B ) c = A c ∩ B c .En ordnet struktur som, i likhet med settet til delene av U forsynt med binære operasjoner av gjenforening og skjæringspunkt, av operasjonen for å passere til komplementet, og av de to fremtredende elementene ∅ og U , tilfredsstiller egenskapene til disse operasjonene som er oppregnet til 'nå kalles boolsk algebra .
Den sett forskjell på A og B betegnes " A \ B " (les " A minus B ") er det sett av elementer i A som ikke tilhører B , nemlig:
.Forskjellen på A og B i U er definert fra den komplementære A ∩ B c , og deretter ( A ∩ B c ) c = A c ∪ B .
Hvis B er inkludert i A , blir A \ B også skrevet " A - B " (les igjen " A minus B "), og kalles komplementær til B i A (eller relativt til A ). Vi finner forestillingen om komplementær ovenfor, som er den komplementære relativt til U :
. Egenskapene til forskjellenVi har :
x ∈ A \ B hvis og bare hvis x ∈ A og x ∉ B x ∉ A \ B hvis og bare hvis x ∈ A ⇒ x ∈ Bog så :
A \ B = ∅ hvis og bare hvis A ⊂ B .Egenskapene til forskjellen er hentet fra dens definisjon og fra de foreningen av krysset og komplementet. For eksempel er det første som følger en serie med kryss, mens det andre bruker en De Morgan-lov og distribusjon av krysset på unionen.
.
Den symmetriske forskjellen på A og B , betegnet " A A B " (les " A delta B ") er settet med elementer som tilhører enten A eller B , men ikke til begge samtidig. Det er forskjellen på A ∪ B og A ∩ B . Det kan skrives i forskjellige former:
.Vi har :
x ∈ A Δ B hvis og bare hvis enten x ∈ A eller x ∈ B (eller eksklusiv) x ∉ A Δ B hvis og bare hvis x ∈ A ⇔ x ∈ Bdermed er den symmetriske forskjellen på to sett tom hvis og bare hvis de to settene er like:
A Δ B = ∅ hvis og bare hvis A = B . Egenskaper av symmetrisk forskjellSett med deler av U forsynt med funksjonen av symmetrisk forskjell er en kommutativ gruppe , med ∅ for nøytralt element, og der hver delmengde av U er sin egen motsats, det vil si for alle under-sett A , B , C av U har vi:
En konsekvens er regulariteten: Hvis A Δ B = A Δ C , deretter B = C .
Settet med deler av U , i tillegg til den symmetriske forskjellen, med skjæringspunktet, er en enhetlig kommutativ ring , det vil si at i tillegg til assosiativitets- og kommutativitetsegenskapene til krysset, og at U er et nøytralt element
Den symmetriske forskjellen, i motsetning til unionen, er ikke distribuerende med hensyn til krysset.
Det er en generell egenskap for boolske algebraer at en operasjon definert som den symmetriske forskjellen (med foreningen skjæringspunktet og overgangen til komplementet) gjør det mulig å definere en ringstruktur, noen ganger kalt en boolsk ring. Andre egenskaper, som er felles for alle boolske algebraer, er bekreftet som:
A c = U Δ A og derfor A c Δ A = U .eller ( A Δ B ) c = A c Δ B = A Δ B c .
Fra et aksiomatisk synspunkt, i sett teorien alt som står foran utvikler seg fra aksiom extensionality (likestilling av to sett), som garanterer spesielt det unike konstruksjonene innført, og av ordningen med aksiomer i forståelse , som garanterer deres eksistens , hvor alle introduserte sett blir definert som et delsett av et gitt sett U.