Szerkesztő:Gubbubu/Halmazelmélet/Osztályműveletek

E fejezetben néhány további módszert foglalunk össze, melyek segítségével osztályokból újabb osztályokat lehet konstruálni. Az „osztályművelet” kifejezést nem definiáljuk, de nem is alapfogalom. Extra-matematikai, informális gyűjtőfogalomnak tekintjük, ami a következőket foglalja össze:

Osztályműveletek

Definíciók

Definíció: Legyen A,B két osztály. Ezek uniójának vagy egyesítésének nevezzük azon dolgok osztályát, melyek a kettő közül legalább az egyiknek az elemei. Formulával:
A∪B := {x | x∈A ∨ x∈B} (olv. „A unió Bé” v. „A és Bé egyesítése”).
Definíció: Legyen A,B két osztály. Ezek metszetének (esetleg szorzatának) nevezzük azon dolgok osztályát, melyek mindkét osztálynak az elemei. Formulával:
A∩B := {x | x∈A ∧ x∈B} (olv. „A metszet Bé” v. „A és Bé metszete”).
Definíció: Legyen A osztály. Ennek komplementere azon dolgok osztálya, melyek A-nak nem elemei. Formulával:
c(A) := {x | x∉A} (olv. „A komplementere”).
Definíció: Legyen A,B két osztály. Ezek különbségének (esetleg differenciájának) nevezzük azon dolgok osztályát, melyek A osztálynak az elemei, de B osztálynak nem. Formulával:
A\B = A-B := {x | x∈A ∧ x∉B} (olv. „A mínusz Bé” v. „A és Bé különbsége”; mi az A-B jelölést fogjuk használni).
Definíció: Legyen A,B két osztály. Ezek szimmetrikus differenciájának (esetleg differenciájának) nevezzük azon dolgok osztályát, melyek pontosan az egyik osztálynak elemei. Formulával:
AΔB := {x | (x∈A ∧ x∉B)∨(x∉A ∧ x∈B)} = (A\B)∪(B\A) (olv. „A delta Bé”).
Definíció: Legyen A,B két osztály. Ezek direkt- vagy Descartes-szorzata azon rendezett párok osztálya, melyek első koordinátája A-ból, a második B-ből való. Formulával:
A×B := {p | (∃x∈A)(∃x∈B):(p=<a,b>)} (olv. „A szor Bé” v. „A kereszt Bé” ).

Létezés

Ha A és B osztályok, akkor a fent definiált osztályok mindegyike létezik.

Tulajdonságok

∪, ∩ és ⊆

Tétel: Ha A,B tetszőleges osztályok, akkor

A,B⊆A∪B (az unió extenzív tulajdonsága);
A∩B⊆A,B. (a metszet kontraktív tulajdonsága)

Bizonyítás: A és B minden eleme eleme A∪B-nek, hiszen utóbbi azon elemeket tartalmazza, amelyek A-ban vagy B-ben vannak, tehát pl. ha x∈A, akkor x benne van az unióban is az unió definíciója miatt. A∩B minden eleme eleme pl. A-nak, hiszen előbbi azon A-beli elemek halmaza, melyek még B-nek is elemei, hasonló okok miatt A∩B minden eleme B-nek is eleme. Q.E.D.

Tétel: Ha A,B olyan osztályok, melyekre A⊆B, akkor

A∪B = B;
A∩B = A.

Bizonyítás:

∪ és ∩

Tétel: Tetszőleges A,B,C osztályokra érvényesek a következők:

Összekapcsolás az üreshalmazzal:
1. A∪∅ = A
2. A∩∅ = ∅
Összekapcsolás az univerzális osztályjal:
1. A∪U = U
2. A∩U = A
idempotencia:
1. A∪A = A
2. A∩A = A
kommutativitás:
1. A∪B = B∪A
2. A∩B = B∩A
asszociativitás:
1. A∪B∪C := (A∪B)∪C = A∪(B∪C)
2. A∩B∩C := (A∩B)∩C = A∩(B∩C)
adszorbciós tulajdonságok:
1. A∪(A∩B) = A
2. A∩(A∪B) = A
disztributivitás:
1. (A∪B)∩(A∪C) = A∪(B∩C)
2. (A∩B)∪(A∩C) = A∩(B∪C)

Bizonyítás:

1.1. A∪∅ bármely eleme vagy az A-ból, vagy az ∅-ból való, de az utóbbiból annak üressége miatt biztos nem, tehát csak A-ból. Eszerint A∪∅⊆A. Fordítva, A⊆A∪∅ az előző tétel, az unió extenzivitása miatt (az előző tételben a B:=∅ helyettesítést alkalmazva). Ezáltal, a részhalmazság antiszimmetriája miatt, érvényes a tétel.

1.2. Az előző tétel, a metszet kontraktivitása alapján A∩∅⊆∅, és mivel ∅⊆A∩∅, mert az üres halmaz minden osztálynak részhalmaza, ezért érvényes a tétel.

2.1. Ha X egy osztály, akkor csak nem-valódi osztályokat tartalmazhat elemként, azaz halmazokat, hiszen valódi osztályok nem lehetnek más osztály elemei. Ebből következően bármely X osztályra X⊆U. Ezért (az X:= A∪U választással) A∪U⊆U. Az előző tétel (az unió extenzivitása) miatt pedig az is igaz, hogy U⊆A∪U. A két tartalmazási relációt egybevetve s a tartalmazási reláció antiszimmetriáját figyelembe véve, a tétel igazolása kész ténnyé vált.

2.2. Az előző tétel (a metszet kontraktivitása) miatt A∩U = A. Fordítva, A⊆A∩U is igaz, ugyanis ha valami eleme az A-nak, akkor vagy elem, vagy halmaz, s mindkét esetben eleme U-nak is, utóbbi definíciója miatt. A bizonyítandó tétel tehát ismét adódik a két felírt tartalmazásból és ennek antiszimmetriájából.

3.1. teljességgel tirivális (egy oolyan osztály, amely A vagy az A elemeit tartalmazza, az A elemeit fogja tartalmazni), de a fentebb igazolt állításokhoz hasonlóan a kétirányú tartalmazás módszerével is igazolható.

3.2. mint 3.1.

4.1. mint 3.1.

4.2. mint 3.1.

5. Először is egy magyarázat. Az A∪B∪C jelölést a szokásos algebrai konvencióknak megfelelően kell kiolvasni, tehát ez nem más, mint az A∪B osztály uniója a C-vel: azaz (A∪B)∪C. Az első egyenlőség tehát csak egy értelmezés, egy emlékeztető az általános iskolában tanultakra, 5.1. és 5.2. esetében is.

5.1. ha valam eleme (A∪B)∪C-nek, akkor a). a C-nek, vagy b). az A∪B-nek, tehát az A-nak vagy a B-nek. Mármost ha a). a C-nek, akkor a B∪C-nek is (az unió definíciójára vagy akár az extenzivitására hivatkozva), és akkor az A∪(B∪C)-nek is. Ha meg b). az A-nak vagy B-nek, akkor ha az A-nak, akkor (extenzivitás!) az A∪(B∪C)-nek, ha meg B-nek, akkor a B∪C-nek (extenzivitás!) és akkor az A∪(B∪C)-nek is. Eszerint akár az a)., akár a b). eset érvényes, ez a valami eleme az A∪(B∪C)-nek, ha egyszer az (A∪B)∪C-nek. Ez azt jelenti, A∪(B∪C)⊆(A∪B)∪C. Hasonló „favágással” igazolható (A∪B)∪C⊆A∪(B∪C) is. Ugyanis ha valami eleme (A∪B)∪C-nek, akkor a). C-nek, vagy b). A∪B-nek, azaz A-nak vagy B-nek; az a). esetben (extenzivitás!) B∪C-nek és így A∪(B∪C)-nek is; a b). esetben ha A-nak eleme, akkor A∪X-nek is, bármilyen osztály is X, tehát X=(B∪C)-vel A∪(B∪C)-nek is; ha meg B-nek eleme, akkor B∪C-nek is és így A∪(B∪C)-nek is. Tehát teljesül az a két tartalmazási reláció, melyek összevetése az antiszimmetria figyelembe vételével igazolja az állítást.

5.2. teljesen hasonló módon igazolható (hf.!).

Algebrai analógiák és különbségek

Figyelemre méltó és kezdők számára sok segítséget nyújthat ezen állítások algebrai interpretációja. Például 1.1. szerint az unió művelettel szemben az üres osztály úgy viselkedik, mint a nulla a közönséges számok összeadásakor, azaz „nem csinál semmit” (neutrális elem). A metszettel szemben viszont úgy viselkedik, mint a nulla a szorzáskor: „mindent eltüntet”, „mindent magává változtat” (zéruselem). 1.2 szerint az univerzális osztály „majdnem olyasmi, mint a végtelen”: „bármit hozzáadunk, maga nem változik meg.” Vagyis - a közönséges számokkal ellentétben - a halmaz-összeaádsnak, az uniónak még zéruseleme is van, ami szintén mindent „magává változtat” a művelet elvégzésekor. Nagyon egyszerű (algebrai módszerekkel, mindenféle halmaz- és osztályelmélet nélkül is) bizonyítani egyébként, hogy ha egy műveletnek van zéruseleme vagy neutrális eleme, akkor csak egy ilyen elem van az egész alaptartományban. Tehát pl. az univerzális osztályon kívül nincs más olyan osztály, hogy ha ahhoz bármit is hozzáadunk, mindig a kiinduló osztályt kapjuk. Hasonlóan az üres osztályon kívül sincs más osztály, hogy teljesüljön: bármit is hozzáadunk, mindig ezt a bármit kapjuk.

Algebrai analógia alapján érthető meg a disztributivitás jelentése is. Legyen + az unió és jelöljük a metszetképzést a közönséges számok szorzásához hasonlóan, ekkor pl. 7.2 így néz ki: (AB)+(AC) = A(B+C). 7.1. így nézne ki: (A+B)(A+C) = A+(BC). Ilyen természetesen a közönséges számok körében már nincs.

Persze már az unió zéruselemessége és a 7.2. disztributivitás is mutatja, hogy azért vigyázni kell: a halmazalgebra nem interpretálható egy az egyben számalgebraként ^[1]. Ennek legszembetűnőbb példája az idempotencia, vagyis - a számalgebra nyelvére fordítva - az a tulajdonság, hogy semmi értelme sem az unió sokszorozásának, sem a metszet sokszorozásának, azaz a „hatványozásnak”.

↑ Míg a racionális vagy valós számokhoz „hasonló” struktúrákat a matematikus (szám)testeknek nevezi, addig a halmazok algebrájénak törvényeit teljesítő struktúrákat - amelyek pl. a matematikai logikában is előfordulnak - Boole-algebráknak.

[1] Míg a racionális vagy valós számokhoz „hasonló” struktúrákat a matematikus (szám)testeknek nevezi, addig a halmazok algebrájénak törvényeit teljesítő struktúrákat - amelyek pl. a matematikai logikában is előfordulnak - Boole-algebráknak.

[1]