Halmazok, halmazműveletek. Matematikai és nem matematikai tartalmú halmazba rendezések.
Gyakorló feladatok (vö. Kiss 1996: 19-25; Monostory 2006: 7-10; Lavrov-Maximova 1987: 11-14):
Írjuk fel az A={a,b,c} halmaz összes részhalmazát, azaz a 2A hatványhalmaz elemeit! Számoljuk össze, hogy hány ilyen részhalmaz van?
Legyen az alaphalmaz
I = {n∈ℕ | n≤15}, továbbá
A = {n∈I | 2|n},
B = {n∈I | 3|n},
C = {n∈I | 4|n},
D = {n∈I | 6|n}.
Adja meg az A, B, C és D halmazokat úgy, hogy felsorolja az elemeiket!
Készítsen Venn-diagramot, és töltse ki az A, B, C és D halmazok elemeivel a megfelelő részhalmazokat jelölő alakzatokat!
Az A, B, C és D halmazok ismeretében sorolja fel az alábbi halmazok elemeit, és adja meg a halmazokat formálisan is!
(a1) A∩B = {x∈I | x∈A ∧ x∈B} (ahol ∧ az "és" (konjunkció) logikai művelet jele)
Első megoldás:
soroljuk fel az I halmaz elemeit, húzzuk alá az A halmaz elemeit és húzzunk vonalat a B halmaz elemei felé ("húzzuk felé" a B halmaz elemeit). Az A∩B elemeit azok az aláhúzott elemek adják meg, amelyek felett is vonal található (amelyek "feléhúzottak" is).
{0,
1,
2,
3,
4,
5,
6,
...}
Második megoldás:
soroljuk fel az I halmaz elemeit, és húzzuk át '/' jellel azokat az elemeket, amelyek nem tartoznak az A halmazba. Utána húzzuk át '\' jellel azokat az elemeket, amelyek nem tartoznak a B halmazba. Az A∩B elemeit azok az elemek adják meg, amelyeket nem húztunk át sem a '/' jellel, sem a '\' jellel.
{0,
1/\,
2\,
3/,
4\,
5/\,
6, ...}
(a2) A∩C (Hasonlítsa össze az A és C halmazokkal!)
(a3) A∩D (Hasonlítsa össze az A és D halmazokkal!)
(b1) B∩C
(b2) B∩D (Hasonlítsa össze a B és D halmazokkal!)
(c1) A∪B
(c2) A∪C (Hasonlítsa össze az A és C halmazokkal!)
(c3) A∪D (Hasonlítsa össze az A és D halmazokkal!)
(d1) B∪C
(d2) B∪D (Hasonlítsa össze a B és D halmazokkal!)
(e1) A∖C
(e2) C∖A
(f1) D∖B
(f1) B∖D
Tippek a Venn-diagram elkészítéséhez:
(1) körökkel (14 különböző terület a számok elhelyezésére; de egyrészt a piros és zöld köröknek nincs olyan közös részük, amely ne tartozna vagy a sárga, vagy a kék körhöz, ill. mindkettőhöz; másrészt a kék és sárga köröknek nincs olyan közös részük, amely ne tartozna vagy a piros, vagy a zöld körhöz, ill. mindkettőhöz)
Ábrázoljuk, hogy az I alaphalmaz négy részhalmaza (A, B, C és D) esetén egy tetszőleges x∈I elem milyen részhalmazokba tartozhat bele! A táblázat A, B, C vagy D oszlopában a '0' és '1' értékek azt jelzik, hogy egy elem az oszlophoz tartozó részhalmaznak az eleme-e vagy sem. A táblázat utolsó oszlopában pedig az I halmaznak azokat az elemeit tüntettük fel, amelyek egy adott sorhoz tartoznak.
| A (2|x) | B (3|x) | C (4|x) | D (6|x) | x |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1, 5, 7, 11, 13 |
| 0 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 3, 9, 15 |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | 2, 10, 14 |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 4, 8 |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 6 |
| 1 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 1 | 0, 12 |
Magyarázzuk meg, hogy egyes sorokban az utolsó oszlopban miért nem szerepelnek számok!
Például a harmadik sorban x∉A és x∈D szerepel. Mivel D a hattal, A a kettővel osztható I-beli számokat tartalmazza, D⊆A teljesül. Azonban ha x∈D, akkor D⊆A miatt x∈A teljesül, de ez x∉A miatt ellentmondáshoz vezet.
Keressük meg a táblázatban azokat a sorokat, amelyek a fenti Venn-diagramban nem jelennek meg külön alakzatként!
(2) ellipszisekkel
(3) aszimmetrikus alakzatokkal
Legyen az alaphalmaz
I = {n∈ℕ | n≤15}, továbbá
A = {"6 pozitív osztói"},
B = {"10 pozitív osztói"},
C = {"15 pozitív osztói"}.
Adja meg az A, B és C halmazokat formálisan is, továbbá adja meg a halmazokat úgy is, hogy felsorolja az elemeiket!
Például az A⊆I halmaz esetén:
A = {x∈I | x|6} vagy
A = {x∈I | ∃q (q*x=6)}
A = {1,2,3,6}
Az A, B és C halmazok ismeretében sorolja fel az alábbi halmazok elemeit, és adja meg a halmazokat formálisan is!
(a) A∩B
(b1) A∪B
(b2) A∪C
(b3) B∪C
(c) (A∩B)∪C
(d) (A∪C)∩(B∪C)
(e1) A
(e2) B
(e3) C
(f) A∪B∪C
(g1) A∩B (Hasonlítsa össze az A∖B halmazzal!)
(g2) A∩B
(h1) A∖B (Hasonlítsa össze az A∩B halmazzal!)
(h2) B∖A
(i) (A∖B)∩(B∖A)
(j) (A∖B)∪(B∖A) (szimmetrikus differencia)
(k) (A∪B)∖(A∩B) (szimmetrikus differencia)
Halmazelméleti azonosságok
Bizonyítsa be a halmazműveletekre vonatkozó azonosságok⇒ alapján, hogy tetszőleges A, B, C halmazokra mindig teljesülnek az alábbi azonosságok.
(Tipp: a halmazok különbségét írja át az
A∖B = A∩B
azonosság alapján, és utána alkalmazza az unió, metszet és komplementerképzésre vonatkozó azonosságokat!)
Bizonyítás után értelmezze egy adott I halmazon az azonosságok jelentését!
(Például 'I' legyen a tanulók halmaza, 'A' a lányok halmaza, 'B' a szemüveges tanulók halmaza stb.)
(a) A∖B = A∪B
A feladat megoldásakor kiindulunk a bizonyítandó azonosság bal oldalából, és levezetéssel eljutunk az azonosság jobb oldalához:
| Átalakítandó kifejezés | Átalakítás |
|---|---|
| A∖B = | A∖B → A∩B |
| A∩B = |
B → C A∩B → A∩C A∩C → A∪C (de Morgan) A∪C → A∪B |
| A∪B = | B → B |
| A∪B (q.e.d.) |
Ha 'I' a tanulók halmaza, 'A' a lányok halmaza, 'B' pedig a szemüveges tanulók halmaza, akkor
A∖B ⇋ "a nem szemüveges lányok halmaza"
A∖B ⇋ "a szemüveges lányok és a fiúk halmaza"
és
A∪B ⇋ "a fiúk és a szemüveges tanulók halmaza" (a mondatban az 'és' a logikai 'vagy' műveletet jelenti!)
A feladat megoldható a következőképpen is. Vegyünk fel egy táblázatot, amelyben egy tetszőleges x∈I elemre egy adott oszlopban az '1' érték jelentse azt, hogy 'x' eleme az oszlopnak megfeleltetett halmaznak (és '0' azt, hogy nem).
| A | B | A∖B | A∖B | A | A∪B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
Figyeljük meg, hogy az A∖B és az A∪B oszlopok soraiban ugyanazok az értékek szerepelnek, vagyis a két kifejezés ugyanazokat az x∈I elemeket tartalmazza.
(b1) A∖(A∩B) = A∖B
(b2) A∖(A∖B) = A∖B
(c1) A∪(B∖A) = A∪B
(c2) A∪(B∖A) = A∖B
(c3) (A∩B)∪(A∖B) = A
(d) A∩(B∖A) = ∅
(e) (A∪B)∖B = A∖B
(f) (A∖B)∖C = A∖(B∪C) = (A∖C)∖(B∖C)
(g) A∖(B∖C) = (A∖B)∪(A∩C)
(h) (A∩B)∖C = (A∩B)∖(A∩C) = A∩(B∖C)
(i) (A∪B)∖C = (A∖C)∪(B∖C)
A feladat megoldásakor kiindulunk a bizonyítandó azonosság jobb oldalából, és levezetéssel eljutunk az azonosság bal oldalához:
(A∖C)∪(B∖C) =
(A∩C)∪(B∩C) =
(A∪B)∩C =
(A∪B)∖C (q.e.d.)
Megjegyzés: ha nem vesszük észre, hogy a harmadik lépésben C kiemelhető, akkor a disztributivitás és az abszorpció többszöri alkalmazásával is ugyanezt kapjuk:
(A∩C)∪(B∩C) = [(A∩C)∪B]∩[(A∩C)∪C] = [(A∪B)∩(C∪B)]∩[(A∪C)∩(C∪C)] = [(A∪B)∩(C∪B)]∩[(A∪C)∩C] = [(A∪B)∩(C∪B)]∩C = (A∪B)∩[(C∪B)∩C] = (A∪B)∩C = (A∪B)∖C (q.e.d.)
(j) A∖(B∪C) = (A∖B)∩(A∖C) = (A∖B)∖C
(k) A∖(B∩C) = (A∖B)∪(A∖C)
(l) (A∖B)∪B = A∪B
(m.1) A∖(A∖B) = A∩B
(m.2) A∖(A∖B) = A∖B
(n) (A∪B)∩(A∪B) = (A∩B)∪(A∩B)
(o) A=(A∩B)∪(A∖B)
(p) A∪B=(A∖B)∪(A∩B)∪(B∖A)
Induljunk ki a bizonyítandó azonosság jobb oldalából:
(A∖B)∪(A∩B)∪(B∖A)
=
(A∩B)∪(A∩B)∪(B∩A)
Alkalmazzuk az únióképzés idempotenciáját kifejező A∪A=A azonosságot az (A∩B) tagra:
(A∩B)∪(A∩B)∪(B∩A)
=
(A∩B)∪(A∩B)∪(A∩B)∪(B∩A)
Zárójelezzük a kapott kifejezést és alkalmazzuk a harmadik tagra a metszetképzés kommutativitását kifejező (A∩B)=(B∩A) azonosságot:
(A∩B)∪(A∩B)∪(A∩B)∪(B∩A)
=
[(A∩B)∪(A∩B)]∪[(B∩A)∪(B∩A)]
A szögletes zárójelekben szereplő kifejezésekben emeljük ki A-t, ill. B-t:
[(A∩B)∪(A∩B)]∪[(B∩A)∪(B∩A)]
=
[(A∩(B∪B)]∪[(B∩(A∪A)]
Mivel
B∪B=A∪A=I
ezért a kapott kifejezés leegyszerűsödik:
[(A∩(B∪B)]∪[(B∩(A∪A)]
=
[(A∩I)]∪[(B∩I)]
Mivel pedig A∩I=A és B∩I=B teljesül, ezért megkapjuk az igazolandó azonosság bal oldalát:
[(A∩I)]∪[(B∩I)] = A∪B (q.e.d.)
Megjegyzés: ha nem vesszük észre az idempotencia alkalmazásával lehetővé váló a kétszeres kiemelés lehetőségét, egy lehetséges megoldás a következő lehet:
(A∩B)∪(B∩A)∪(A∩B)
= (asszociativitás, zárójelezés)
((A∩B)∪(B∩A))
∪ (A∩B)
= (disztributivitás, helyettesítés, pótlás)
(((A∩B)∪B)
∩ ((A∩B)∪A))
∪ (A∩B)
= (kommutativitás, helyettesítés, pótlás)
((B∪(A∩B))
∩ (A∪(A∩B)))
∪ (A∩B)
= (disztributivitás, helyettesítés, pótlás)
(((B∪A)
∩ (B∪B))
∩ ((A∪A)
∩ (A∪B)))
∪ (A∩B)
= (A∪A=I, helyettesítés, pótlás)
(((B∪A)∩I)
∩ ((A∪A)
∩ (A∪B)))
∪ (A∩B)
= (A∪A=I ⇔ A∪A=I, pótlás)
(((B∪A)∩I)
∩ (I∩(A∪B)))
∪ (A∩B)
= (A∩I=A, helyettesítés, pótlás)
((B∪A)
∩ (I∩(A∪B)))
∪ (A∩B)
= (A∩I=A ⇔ I∩A=A, helyettesítés, pótlás)
((B∪A)
∩ (A∪B))
∪ (A∩B)
= (kommutativitás, pótlás)
((A∪B)
∩ (A∪B))
∪ (A∩B)
= (kommutativitás, helyettesítés, pótlás)
(A∩B) ∪
((A∪B)
∩ (A∪B))
= (disztributivitás, helyettesítés)
((A∩B)∪(A∪B))
∩ ((A∩B)∪(A∪B))
= (de Morgan szabály, helyettesítés, pótlás)
((A∩B)∪(A∪B))
∩ ((A∩B)∪(A∩B))
= (A∪A=I, helyettesítés, pótlás)
((A∩B)∪(A∪B))
∩ I
= (A∩I=A, helyettesítés)
((A∩B)∪(A∪B))
= (asszociativitás, helyettesítés)
(((A∩B)∪A)
∪ B)
= (kommutativitás, helyettesítés,⇒ pótlás)
((A∪(A∩B))
∪ B)
= (abszorpció, pótlás⇒)
((A)
∪ B)
= (felesleges zárójelek elhagyása)
A∪B (q.e.d.)
Vegyük észre, hogy a most levezetett azonosság bal oldala kifejezhető a szimmetrikus differenciával:⇒
(A∩B)∪(B∩A)∪(A∩B)
=
(AΔB)∪(A∩B)
= A∪B
Melyek azok a halmazok, amelyekre A∖B=B∖A teljesül? (tipp: először igazolja, hogy A∖B és B∖A diszjunktak, majd azt, hogy A∖B=B∖A=∅, végül azt, hogy A=B teljesül. Az utolsó lépéshez például fel lehet használni az A=(A∩B)∪(A∖B) azonosságot.)
Kiegészítő anyag
Bizonyítsa be a halmazműveletek definíciója alapján, hogy tetszőleges A, B, C, D halmazokra teljesülnek az alábbi összefüggések, ill. azonosságok: (tipp: használja fel a részhalmaz reláció antiszimmetriáját⇒ az azonosságok bal- és jobboldalán szereplő kifejezések egyenlőségének bizonyításához!)
Emlékeztető: ∧ ⇋ "és", ∨ ⇋ "vagy", ⌝ ⇋ "nem"; ⊃ ⇋ "...ból következik, hogy..." (logikai kifejezésekben); ∀x ⇋ "bármely / minden x-re teljesül, hogy ...", ∃x ⇋ "létezik / van olyan x, amelyre teljesül, hogy ..."; ⇒ ⇋ "...ból következik, hogy..." (levezetésekben); ⇔ ⇋ "... pontosan akkor, ha ..." vagy "... akkor és csak akkor, ha ..."
Halmazelméleti szimbólumok:
A⊆B minden x∈I-re x∈A ⇒ x∈B⇒ A∪B A∪B = {x∈I | x∈A ∨ x∈B}⇒ minden x∈I-re x∈(A∪B) ⇔ x∈A ∨ x∈B A∩B A∩B = {x∈I | x∈A ∧ x∈B}⇒ minden x∈I-re x∈(A∩B) ⇔ x∈A ∧ x∈B A A = {x∈I | x∉A}⇒
x∉A ⇋ ⌝(x∈A)minden x∈I-re x∈A ⇔ x∉A A∖B A∖B = A∩B = {x∈I | x∈A ∧ x∉B}⇒ minden x∈I-re x∈A∖B ⇔ x∈A ∧ x∉B Fontosabb következtetési szabályok:
Legyenek A, B⊆I tetszőleges halmazok, a∈I tetszőleges halmazelem (∀a∈I (...)).
– részhalmaz reláció felbontása: a∈A, A⊆B ⇒ a∈B
– részhalmaz reláció bizonyítása: (a∈A ⇒ ... ⇒ a∈B) ⇒ A⊆B
– halmazok egyenlőségének bizonyítása: A⊆B ∧ B⊆A ⇒ A=B
– metszet felbontása: a∈(A∩B) ⇒ a∈A ∧ a∈B
– metszet visszaírása: (a∈A ∧ a∈B) ⇒ a∈A∩B
– unió felbontása: a∈(A∪B) ⇒ a∈A ∨ a∈B
– unió visszaírása: (a∈A ∨ a∈B) ⇒ a∈A∪BLegyenek A, B, C tetszőleges állítások.
– a szűkítés szabálya: A ∧ B ⇒ A
(pl. ha "kiváló" ⇋ "szorgalmas és okos", akkor "Janka kiváló" ⇒ "Janka szorgalmas")
– a bővítés szabálya: A ⇒ A ∨ B
(pl. ha "tehetséges" ⇋ "szorgalmas vagy okos", akkor "Janka szorgalmas" ⇒ "Janka tehetséges")
– esetegyesítés: (A ⇒ B) és (A ⇒ C) teljesüléséből (A ⇒ B ∧ C) következik
– esetszétválasztás, esetelemzés: (A ⇒ C) és (B ⇒ C) teljesüléséből (A ∨ B ⇒ C) következik
(pl. ha "tehetséges" ⇋ "szorgalmas vagy okos", és bizonyítjuk, hogy
–– "aki szorgalmas, az bekerül az egyetemre" és
–– "aki okos, az bekerül az egyetemre" akkor ezekből az állításokból
–– "aki tehetséges, az bekerül az egyetemre" következik)
– logikai ekvivalencia bizonyítása: (A ⇒ B) és (B ⇒ A) teljesüléséből (A ⇔ B) következikPélda: az A⊆B ⇔ A=A∩B összefüggés bizonyítása⇒ az előadás anyagában megtalálható
(a) A⊆A (a részhalmaz reláció reflexivitása); A⊆A∪B (tetszőleges B⊆I halmazra)
Legyen x∈A tetszőleges elem, ahol 'A' a reláció bal oldalán szereplő halmaz. Ez nyilvánvalóan eleme a reláció jobb oldalán szereplő A-nak is, tehát a részhalmaz reláció definíciója⇒ alapján A⊆A teljesül. A bizonyításból látszik, hogy ha a jobb oldalon szereplő 'A' halmazhoz tetszőleges elemeket hozzáadunk, a reláció ugyanúgy fennáll, azaz A⊆A∪B is teljesül tetszőleges 'B' halmazra (vö. a (c2) feladattal).
A probléma egy konkrét feladatba ágyazása a következő:
Egy osztályban Petike kölcsönadja a kedvenc ceruzáját (c) Julcsinak. Julcsi beteszi a tolltartójába, a "tollai halmazába" (A; és innentől c∈A teljesül). Az óra végén Julcsi azt mondja, hogy nincs nála a ceruza. Petike szól a tanítónéninek. Hol fogja a tanító néni keresni a ceruzát? Megoldás: Julcsi tolltartójában (mert tudja, hogy minden 'x' ceruzára, tollra stb., amely Julcsinál van, x∈A teljesül).
A tanító néni tehát jól tudja, hogy minden olyan 'x' ceruzát, amelyet Julcsi beletett a tolltartóba (x∈A), a tolltartóban fogunk megtalálni (x∈A). Ezt formálisan úgy tudjuk kifejezni, hogy A⊆A teljesül.
(b) ha A⊆B és B⊆C teljesül, akkor A⊆C is teljesül (a részhalmaz reláció tranzitivitása)
Julcsinak nagyon tetszett a ceruza, ezért betette a tolltartót (A) a táskájába (B), azt pedig szünetben az osztályban levő szekrénybe (C). Vajon így megtalálja-e a ceruzát a tanító néni?
(c) A∩B⊆A (→c1), A⊆A∪B (→c2) és A∩B⊆A∪B (→c3)
(c1) A∩B⊆A (és nyilvánvalóan A∩B⊆B) (tipp: használja fel a minden x∈I elem esetén teljesülő x∈A ∧ x∈B ⇒ x∈A⇒ (ill. x∈A ∧ x∈B ⇒ x∈B) logikai törvényeket a bizonyításhoz!)
Legyen x∈I tetszőleges halmazelem, amely eleme az A és B halmazok metszetének (x∈A∩B). Erre teljesül, hogy 'x' eleme az 'A' halmaznak (x∈A), valamint a 'B' halmaznak is (x∈B).
Ha pedig a C=A∩B halmaz minden 'x' elemére teljesül, hogy eleme az 'A' halmaznak, akkor a C halmaz része az A halmaznak, vagyis C⊆A teljesül (és hasonlóan teljesül C⊆B is).
Tehát az A és B halmazok metszete része az A halmaznak (A∩B⊆A).
A∩B⊆A esetén a bizonyítás lépései formálisan leírva:
x∈A∩B ⇒ x∈A ∧ x∈B ⇒ x∈A
tehát A∩B⊆A teljesül (q.e.d.)
(c2) A⊆A∪B (és nyilvánvalóan B⊆A∪B) (tipp: használja fel a minden x∈I elem esetén teljesülő x∈A ⇒ x∈A ∨ x∈B⇒ (ill. x∈B ⇒ x∈A ∨ x∈B) logikai törvényeket a bizonyításhoz!)
A⊆A∪B esetén a bizonyítás lépései formálisan leírva:
x∈A ⇒ x∈A ∨ x∈B ⇒ x∈A∪B
tehát A⊆A∪B teljesül (q.e.d.)
(c3) A∩B⊆A∪B
(d) ha A⊆B, akkor A⊆A∩B (→d1) és A∪B⊆B (→d2) teljesül; ha A⊆A∩B akkor A⊆B (→d3) teljesül
(d1) ha A⊆B, akkor A⊆A∩B
(d2) ha A⊆B, akkor A∪B⊆B
A bizonyítás lépései formálisan leírva:
x∈A∪B ⇒ x∈A ∨ x∈B
x∈A ∧ A⊆B ⇒ x∈B
x∈B ⇒ x∈B
x∈A ∨ x∈B ⇒ x∈B
tehát A∪B⊆B teljesül (q.e.d.)
Vegyük észre, hogy a bizonyításban a logikai "vagy" műveletet tartalmazó x∈A ∨ x∈B logikai kifejezés két eset vizsgálatát tette szükségessé (x∈A és x∈B). Mivel mindkét esetben ugyanazt a konklúziót kaptuk (x∈B), ezért levonhattuk az x∈A ∨ x∈B ⇒ x∈B következtetést. (Az alkalmazott logikai eljárást esetszétválasztásnak vagy esetelemzésnek⇒ nevezzük.)
(d3) ha A⊆A∩B, akkor A⊆B
(e) ha A⊆B és C⊆D teljesül, akkor A∩C⊆B∩D (→e1) és A∪C⊆B∪D (→e2) teljesül
(e1) ha A⊆B és C⊆D, akkor A∩C⊆B∩D
A bizonyítás lépései formálisan leírva:
x∈A∩C ⇒ x∈A ∧ x∈C
x∈A ∧ x∈C ⇒ x∈A
x∈A ∧ A⊆B ⇒ x∈B
x∈A ∧ x∈C ⇒ x∈C
x∈C ∧ C⊆D ⇒ x∈D
x∈A ∧ x∈C ⇒ x∈B ∧ x∈D
x∈B ∧ x∈D ⇒ x∈B∩D
tehát A∩C⊆B∩D teljesül (q.e.d.)
(e2) ha A⊆B és C⊆D, akkor A∪C⊆B∪D
A bizonyítás lépései formálisan leírva:
x∈A∪C ⇒
x∈A ∨ x∈C
x∈A ∧ A⊆B ⇒ x∈B ⇒
x∈B ∨ x∈D
x∈C ∧ C⊆D ⇒ x∈D ⇒ x∈D ∨ x∈B ⇒
x∈B ∨ x∈D
x∈A ∨ x∈C
⇒
x∈B ∨ x∈D
x∈B ∨ x∈D ⇒
x∈B∪D
tehát A∪C⊆B∪D teljesül (q.e.d.)
(e/1) [kieg.]
tetszőleges P, Q és C halmazok esetén,
ha C⊆P és C⊆Q teljesül, akkor C⊆P∩Q (két halmaz metszete tartalmaz minden olyan halmazt, amely a halmazok közös elemeiből áll; a metszet a "legnagyobb" ilyen tulajdonságú halmaz, a P és Q halmazok ún. legnagyobb alsó korlátja vagy infimuma)
Speciálisan, tetszőleges P, Q, C és C' halmazok esetén, ha P∪Q⊆C és P∪Q⊆C' teljesül, akkor P∪Q⊆C∩C' is teljesül (vagyis létezik olyan D=C∩C' halmaz, amelyre P∪Q⊆D, D⊆C és D⊆C' teljesül).
(e/2) [kieg.]
tetszőleges P, Q és C halmazok esetén,
ha P⊆C és Q⊆C teljesül, akkor P∪Q⊆C (két halmaz uniója minden olyan halmaznak része, amely egyszerre tartalmazza mindkét halmaz elemeit; az unió a "legkisebb" ilyen tulajdonságú halmaz, a P és Q halmazok ún. legkisebb felső korlátja vagy szuprémuma)
(f) a metszetképzés és az unióképzés abszorpciója⇒
(f1) A∩(A∪B)=A
A bizonyítás lépései formálisan leírva:
(1) x∈A∩(A∪B) ⇒
x∈A ∧ (x∈A ∨ x∈B) ⇒
x∈A
tehát A∩(A∪B)⊆A teljesül;
(2) x∈A ⇒
x∈A ∨ x∈B ⇒
x∈A ∧ (x∈A ∨ x∈B) ⇒
x∈A∩(A∪B) ⇒
tehát A⊆A∩(A∪B) teljesül;
(3) (1) és (2) alapján (A∩(A∪B)⊆A) ∧ (A⊆A∩(A∪B)) ⇒ A=A∩(A∪B) teljesül (q. e. d.)
(f2) A∪(A∩B)=A
A bizonyítás lépései formálisan leírva:
(1) x∈A∪(A∩B) ⇒
x∈A ∨ (x∈A ∧ x∈B) ⇒
x∈A ⇒ x∈A
x∈A ∧ x∈B ⇒ x∈A
x∈A ∨ (x∈A ∧ x∈B) ⇒ x∈A
tehát A∪(A∩B)⊆A teljesül;
(2) x∈A ⇒
x∈A ∨ (x∈A ∧ x∈B) ⇒
x∈A∪(A∩B)
tehát A⊆A∪(A∩B) teljesül;
(3) (1) és (2) alapján (A∪(A∩B)⊆A) ∧ (A⊆A∪(A∩B)) ⇒ A=A∪(A∩B) teljesül (q. e. d.)
(g) [kieg.] tetszőleges A és B halmazok esetén A=(A∩B)∪(A∩B) teljesül (egy halmaz felbontása diszjunkt komponensekre) (mivel A∖B=A∩B, ezért az 'A' halmaz fenti felbontása A=(A∩B)∪(A∖B) alakban is írható)
A bizonyítás lépései formálisan leírva (megjegyzés: a (2) lépésben felhasználjuk, hogy x∈I ⇔ x∈(B∪B) mindig teljesül):
(1) x∈(A∩B)∪(A∩B) ⇒
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒
x∈A ∧ x∈B ⇒ x∈A
x∈A ∧ x∈B ⇒ x∈A
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒ x∈A
tehát (A∩B)∪(A∩B)⊆A teljesül;
(2) x∈A és x∈(B∪B) ⇒
x∈A ∧ (x∈B ∨ x∈B) ⇒
x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B)
x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈B)
x∈A ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ B)
tehát A⊆(A∩B)∪(A∩B) teljesül;
(3) (1) és (2) alapján (A∩B)∪(A∩B)⊆A ∧ A⊆(A∩B)∪(A∩B) ⇒ A=(A∩B)∪(A∩B) teljesül (q. e. d.)
(h) [kieg.] a metszetképzés és az unióképzés disztributivitása⇒
Tekintsük például az
A∩(B∪C) = (A∩B)∪(A∩C)
azonosságot. Először (I.) azt bizonyítjuk, hogy A∩(B∪C) ⊆ (A∩B)∪(A∩C) teljesül, azután pedig (II.) azt bizonyítjuk, hogy (A∩B)∪(A∩C) ⊆ A∩(B∪C) teljesül. Mivel a részhalmaz reláció antiszimmetrikus, I. és II. teljesüléséből az azonosság bal és jobb oldalán szereplő kifejezések egyenlősége már következik.
(I.)
Legyen x∈A∩(B∪C) tetszőleges elem. Ekkor a metszetképzés definíciója⇒ miatt
x∈A és x∈(B∪C)
teljesül. Az unióképzés definíciója⇒ miatt
x∈(B∪C) pontosan akkor teljesül, ha
vagy x∈B, vagy x∈C
teljesül, amiből
x∈A ∧ (x∈B ∨ x∈C) következik.
Itt két eset lehetséges:⇒
(I.i.) x∈A és x∈B teljesül. Ebből a bővítés szabályát⇒ az x∈A ∧ x∈B kifejezésre alkalmazva
x∈A ∧ x∈B ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
következik.
(I.ii.) x∈A és x∈C teljesül. Ismét a bővítés szabályát⇒ alkalmazva az x∈A ∧ x∈C kifejezésre
x∈A ∧ x∈C ⇒ (x∈A ∧ x∈C) ∨ (x∈A ∧ x∈B) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
adódik.
Mivel mindkét esetben azonos következtetésre jutottunk, ezért
x∈A ∧ (x∈B ∨ x∈C) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
teljesül (I.), amiből az unióképzés⇒ és a metszetképzés definíciója⇒ miatt
x∈(A∩B)∪(A∩C)
következik. A részhalmaz reláció definíciója⇒ következtében tehát A∩(B∪C) ⊆ (A∩B)∪(A∩C) teljesül.
(II.)
Legyen x∈(A∩B)∪(A∩C) tetszőleges elem. Ekkor az unióképzés definíciója⇒ miatt
vagy x∈(A∩B),
vagy x∈(A∩C)
teljesül. Tehát most is két eset lehetséges:
(II.i.) x∈(A∩B) teljesül. Ekkor a metszetképzés definíciója⇒ miatt x∈A és x∈B teljesül. Ebből a bővítés szabályát⇒ az x∈A ∧ x∈B kifejezésre alkalmazva
x∈A ∧ x∈B ⇒ x∈A ∧ (x∈B ∨ x∈C)
következik.
(II.ii.) x∈(A∩C) teljesül. Ekkor a metszetképzés definíciója⇒ miatt x∈A és x∈C teljesül. Ismét a bővítés szabályát⇒ alkalmazva az x∈A ∧ x∈C kifejezésre
x∈A ∧ x∈C ⇒ x∈A ∧ (x∈C ∨ x∈B) ⇒ x∈A ∧ (x∈B ∨ x∈C)
adódik.
Mivel mindkét esetben azonos következtetésre jutottunk, ezért
x∈(A∧B)∨(A∧C) ⇒ x∈A ∧ (x∈B ∨ x∈C)
teljesül (II.), amiből az unióképzés⇒ és a metszetképzés definíciója⇒ miatt x∈A∩(B∪C) következik.
Emiatt a részhalmaz reláció definíciója⇒ miatt (A∩B)∪(A∩C) ⊆ A∩(B∪C) teljesül.
(III.) Összegezve a fentieket: amint azt a bizonyítás elején említettük, a részhalmaz reláció antiszimmetriája miatt I. és II. teljesüléséből az azonosság bal és jobb oldalán szereplő kifejezések egyenlősége már következik. Ezért az
A∩(B∪C) = (A∩B)∪(A∩C)
azonosság tetszőleges A, B és C halmazok esetén fennáll.
Ha a bizonyítás során felhasználjuk az "és" és "vagy" logikai műveletek disztributivitását,⇒ ebből mind az I., mind a II. pont végkövetkeztetése azonnal következik.
A következtetés logikáját például az alábbi két kijelentés szemlélteti:
(1) Láttam az utcán Katit és vagy Lenkét, vagy Zsuzsát.
(2) Láttam az utcán Katit és Lenkét, vagy Katit és Zsuzsát.
(Tegyük fel, hogy Kati és Zsuzsa egypetéjű ikrek, úgy hasonlítanak egymásra, mint két tojás. :) )
Az "és" és "vagy" logikai műveletek disztributivitása miatt a két kijelentésben ugyanazt állítjuk.
(i) [kieg.] de Morgan-féle azonosságok⇒