Matematika 1


Tartalom, témakörök

  1. Halmazok, halmazműveletek. Matematikai és nem matematikai tartalmú halmazba rendezések. (Kopasz 1996: 21-24; Borsodi-Göndöcs 1970: 9-48)
  2. Relációk fogalma, megadási módjai, tulajdonságai. (Vajda 1996: 30-42; Borsodi-Göndöcs 1970: 48-61)
  3. Az ekvivalenciareláció és a rendezési relációk. (Vajda 1996: 40-41; Borsodi-Göndöcs 1970: 58-60)
  4. ...

1.1. Halmazok, halmazok megadása

A különböző objektumok (dolgok, tárgyak, fogalmak stb.) bizonyos összességét halmaznak nevezzük. A halmaz és a halmazelem fogalmát alapfogalomnak tekintjük és nem definiáljuk. (vö. Kopasz 1996: 21)

A halmazokat rendszerint nagybetűkkel jelöljük, a halmazok elemeit pedig rendszerint kisbetűkkel. Azt, hogy a 'p' dolog (tárgy, fogalom stb.) az 'I' halmaz eleme, p ∈ I módon jelöljük. Ezt formálisan
p ∈ I ⇋ "p eleme az I halmaznak"
módon írhatjuk le.
Azt, hogy egy 'q' dolog nem eleme az I halmaznak, q ∉ I módon jelöljük. Ezt formálisan
q ∉ I ⇋ "q nem eleme az I halmaznak"
módon írhatjuk le.

Egy halmaz elemei mindig különbözők.

Egy probléma tárgyalása során mindig megadunk egy alaphalmazt (Kopasz 1996: 21). Egy halmazt akkor tekintünk adottnak (vagy meghatározottnak), ha bármely objektumról eldönthető, hogy eleme-e a halmaznak vagy sem (Bonifert-Kovácsné Győri 1987: 5).

A halmazok megadása többféleképpen lehetséges:

Példák halmazok megadására az elemek felsorolásával:

Ha halmazokat az elemek jellemzésével adunk meg, az elemeket közösen jellemző tulajdonságokat a  |  jel után soroljuk fel, vesszővel elválasztva. Jegyezzük meg, hogy
    – egyes esetekben az alaphalmazba tartozást még a  |  elválasztójel előtt megadjuk;
    – az elválasztó jel után az elemek tulajdonságait megadhatjuk szövegesen (ún. leíró megadási mód révén), formálisan (matematikai szimbólumokat használva), vagy a kettő kombinálásával.

Példák halmazok megadására a halmazelemek jellemző tulajdonságának (vagy tulajdonságainak) a megadásával:

A halmazok ábrázolása ún. Venn-diagrammal történhet (Bonifert-Kovácsné Győri 1987: 6), amely a halmazok elemeit és az ezeket tartalmazó részhalmazokat szemléltető (rendszerint színes) ábra. A Venn-diagram konstruálásakor

A Venn-diagram használatára tekintsük az alábbi példát.

Legyen az ábrázolandó halmaz
      H = {1,2,4,5,6,7}
és tételezzük fel, hogy a 'H ' halmaz elemei meghatározott tulajdonságokkal rendelkeznek. Csoportosítsuk a közös tulajdonsággal rendelkező elemeket az A, B és C halmazokba:
      A = {1, 2, 5}
      B = {1, 6}
      C = {4, 7}
A H, valamint az A, B és C halmazokat a következőképpen ábrázolhatjuk Venn-diagramon:

halmazok ábrázolása Venn-diagramon

Feladat: keressünk olyan tulajdonságokat, amelyek alapján az A, B és C halmazok megadhatóak! (tipp: legyen az alaphalmaz a törpék halmaza, és tegyük fel azt a kérdést, hogy milyen gyümölcsöket szeret a hét törpe? pl. A = {"azok a törpék, akik szeretik az epret"} stb., valamint "az első törpe ('1') szereti az epret" stb.)


1.2. Halmaz, részhalmaz, hatványhalmaz

Azt a halmazt, amelynek egyetlen eleme sincs, üres halmaznak nevezzük, és ∅ vagy {} módon jelöljük.

Az 'A' halmaz részhalmaza a 'B' halmaznak, ha az 'A' halmaz minden eleme eleme a 'B' halmaznak is:
A⊆B ⇋ "minden a∈A esetén a∈B teljesül"

Két halmaz egyenlő, ha az elemeik megegyeznek:
A=B ⇋ "minden a∈A esetén a∈B, és minden b∈B esetén b∈A teljesül", azaz
A=B ⇋ A⊆B és B⊆A

Emeljük ki, hogy ha az 'A' és 'B' halmazokra A⊆B és B⊆A egyszerre teljesül, akkor abból a fenti definíció szerint A=B következik. Az ilyen típusú relációkat antiszimmetrikus relációknak nevezzük.

Ennek megfelelően az A és B halmazok különbözőek (nem egyenlők, A≠B), ha van olyan 'x' elem, amelyik csak az egyik halmaznak az eleme (azaz vagy x∈A és x∉B, vagy x∈B és x∉A teljesül).

Az 'A' halmaz részhalmazai:

Az 'A' halmaz hatványhalmaza az 'A' halmaz összes részhalmazának halmaza (azaz az üreshalmaz, az 'A' halmaz valódi részhalmazai, és maga az 'A' halmaz):
2A ⇋ {X | X⊆A}

Az 'A' halmaz hatványhalmazát P(A) módon is szokás jelölni.

Ha az 'A' halmaz véges és elemeinek száma |A|=n (n≥0), akkor a 2A halványhalmaz is véges és elemeinek száma |2A|=2n.

Ha |A|=n, akkor rendezzük egy n elemű sorozatba az 'A' halmaz elemeit (azaz lássuk el őket sorszámokkal), és feleltessük meg a {0,1} jelekből álló
B=(b1, b2, ..., bn)
bináris jelsorozatot (bi∈{0,1}, 1<=i<=n) az 'A' halmaz egyes elemeinek és részhalmazainak a következőképpen:
egy tetszőleges R⊆A részhalmaznak az 'A' halmaz i-dik eleme pontosan akkor eleme, ha bi=1 (bi∈{0,1}, 1<=i<=n).
Világos, hogy a csupa 0-ból álló jelsorozat az üreshalmaznak (∅), a csupa 1-ből álló jelsorozat pedig magának az 'A' halmaznak felel meg. Mivel pedig minden különböző jelsorozatnak különböző R⊆A részhalmaz felel meg, az 'A' halmaz összes részhalmazának száma megegyezik az összes különböző B jelsorozat számával. Ennek értéke két különböző elem n-ed rendű ismétléses variációja, azaz 2n.


1.3. Műveletek halmazokkal

Legyen 'I' egy halmaz, amelynek az elemeit a továbbiakban vizsgálni akarjuk (például egy osztály tanulóinak a halmaza, a természetes számok halmaza stb.). Az előzőek alapján nevezzük az 'I' halmazt alaphalmaznak.

Az 'I' alaphalmaz elemeiből álló tetszőleges 'A' halmaz esetén A⊆I teljesül.

Legyen A⊆I és B⊆I két tetszőleges halmaz. Az 'A' és 'B' halmazok között a következő műveleteket értelmezzük:

Jegyezzük meg, hogy mindegyik fenti halmazművelet eredménye egy I-beli halmaz, vagyis A∪B⊆I, A∩B⊆I, A⊆I, AB⊆I és AΔB⊆I teljesül.

A fenti műveletekkel kifejezhető az is, hogy az 'A' halmaz a 'B' halmaz részhalmaza. A definíció alapján belátható, hogy A⊆B pontosan akkor teljesül, ha
   A = A∩B
teljesül (azaz A minden eleme egyúttal eleme B-nek is). Ugyanez kifejezhető
   A∪B = B
formában is.

A különbség (differencia) segítségével az A⊆B összefüggés
   AB = A∩B = ∅
módon is kifejezhető. Ezt komplementálva az ekvivalens
   A∪B = I
összefüggéshez jutunk.

(1) Tegyük fel, hogy A⊆B teljesül. Ekkor egyrészt A⊆A miatt A⊆A∩B teljesül, másrészt a metszetképzés definíciója miatt A∩B⊆A mindig teljesül. Ebből viszont A=A∩B következik (szükséges feltétel).
(2) Tegyük fel, hogy A=A∩B teljesül. Ekkor az egyenlőség definíciója miatt minden x∈A elem esetén x∈A∩B teljesül, ebből viszont a metszetképzés definíciója miatt x∈B teljesül. De ez a részhalmaz definíciója miatt éppen A⊆B teljesülését jelenti (elégséges feltétel).

A bizonyítás lépései formálisan leírva (∧ ⇋ "és", ∨ ⇋ "vagy"):
  • tegyük fel, hogy A⊆B
    • x∈A ∧ A⊆B ⇒ x∈B
      • x∈A ∧ x∈B ⇒ x∈(A∩B)
      • A⊆(A∩B)
    • x∈(A∩B)x∈A ∧ x∈B
      • (A∩B)⊆A
    • A⊆(A∩B) ∧ (A∩B)⊆A ⇒ A=A∩B
  • tegyük fel, hogy (A∩B)=A
    • x∈A ∧ A=(A∩B) ⇒ x∈(A∩B)
      • x∈(A∩B) ⇒ x∈A ∧ x∈B
      • A⊆B
  • (A⊆B ⇒ (A∩B)=A) ∧ ((A∩B)=A ⇒ A⊆B) ⇒ (A⊆B ⇔ (A∩B)=A)

1.4. A halmazműveletek főbb tulajdonságai

Legyen az 'I' halmaz alaphalmaz (ún. teljes halmaz), az A, B, C⊆I halmazok pedig az alaphalmaz tetszőleges részhalmazai. Ekkor teljesülnek az alábbi azonosságok:

  • kettős komplementálás:
    • A = A
  • a metszetképzés idempotenciája:
    • A∩A=A
  • a metszetképzés kommutativitása:
    • A∩B=B∩A
  • a metszetképzés asszociativitása:
    • (A∩B)∩C=A∩(B∩C)
      (Megjegyzés: a metszetképzés asszociativitása miatt egyszerűen A∩B∩C is írható. A kifejezés kiértékelése történhet pl. balról jobbra.)
  • metszetképzés a teljes halmazzal és az üreshalmazzal:
    • A∩I=A
    • A∩∅=∅
  • az unióképzés idempotenciája:
    • A∪A=A
  • az unióképzés kommutativitása:
    • A∪B=B∪A
  • az unióképzés asszociativitása:
    • (A∪B)∪C=A∪(B∪C)
      (Megjegyzés: az unióképzés asszociativitása miatt egyszerűen A∪B∪C is írható. A kifejezés kiértékelése történhet pl. balról jobbra.)
  • unióképzés a teljes halmazzal és az üreshalmazzal:
    • A∪I=I
    • A∪∅=A
  • disztributivitás:
    • A∩(B∪C) = (A∩B)∪(A∩C)
    • A∪(B∩C) = (A∪B)∩(A∪C)
  • abszorpció (elnyelés; elimináció):
    • A∩(A∪B) = A
    • A∪(A∩B) = A
  • de Morgan-féle azonosságok:
    • (A∩B) = AB
    • (A∪B) = AB
  • műveletek a halmaz és komplementere között:
    • A∩A=∅
    • A∪A=I
  • a teljes halmaz és az üreshalmaz komplementer halmaza:
    • I=∅
    • =I

A fenti azonosságokat átalakíthatjuk úgy, hogy eredményül érvényes azonosságokat kapunk (vö. Ruzsa 1968: 458-459):

Például igazoljuk az alábbi azonosságot úgy, hogy kiindulunk a bal oldali kifejezésből, és ekvivalens átalakításokkal (⇔) eljutunk a jobb oldali kifejezéshez:
(A∩B)∪(B∩A)∪(A∩B) = A∪B
(A∩B)∪(B∩A)∪(A∩B) ⇔ (asszociativitás, helyettesítés, pótlá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)(AB))) ∪ (A∩B) ⇔ (A∪A=I, helyettesítés, pótlás)
(((B∪A)∩I)((A∪A)(AB))) ∪ (A∩B) ⇔ (A∪A=I ⇔ A∪A=I, pótlás)
(((B∪A)∩I)(I∩(AB))) ∪ (A∩B) ⇔ (A∩I=A, helyettesítés, pótlás)
((B∪A)(I∩(AB))) ∪ (A∩B) ⇔ (A∩I=A ⇔ I∩A=A, helyettesítés, pótlás)
((B∪A)(AB)) ∪ (A∩B) ⇔ (kommutativitás, pótlás)
((A∪B)(AB)) ∪ (A∩B) ⇔ (kommutativitás, helyettesítés, pótlás)
(A∩B) ∪ ((A∪B)(AB)) ⇔ (disztributivitás, helyettesítés, pótlás)
((A∩B)∪(A∪B))((A∩B)∪(AB)) ⇔ (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, pótlás)
((A∩B)∪(A∪B)) ⇔ (asszociativitás, helyettesítés, pótlá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. = ezt akartuk bizonyítani)
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

Egy kifejezés duálisán azt a kifejezést értjük, amely az eredeti kifejezésből úgy keletkezik, hogy bizonyos műveleti jeleket és egyéb szimbólumokat kicserélünk az alábbiak szerint:

A fenti azonosságok mindegyikére érvényes a dualitás törvénye: ha egy azonosság mindkét oldalát "dualizáljuk" (azaz mindkét oldalon az ott szereplő kifejezés helyére a kifejezés duálisát írjuk), szintén azonossághoz jutunk.

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! 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!

Tippek a Venn-diagram elkészítéséhez:
(1) körökkel

négy halmaz ábrázolása Venn-diagramon

(2) ellipszisekkel

négy halmaz ábrázolása Venn-diagramon

(3) aszimmetrikus alakzatokkal

négy halmaz ábrázolása Venn-diagramon

A megadott A, B, C és D halmazok ismeretében sorolja fel az alábbi halmazok elemeit:

(a) A∩B

(b) A∩C

(c) B∪D

(e) A∖C

(f) D∖B

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! Ezután sorolja fel az alábbi halmazok elemeit:

(a) A∩B

(b) A∪B, A∪C és B∪C

(c) (A∩B)∪C

(d) (A∪C)∩(B∪C)

(e) A, B és C

(f) AB

(g) ABC

(h) A∖B és B∖A

(i) (A∖B)∩(B∖A)

(j) (A∖B)∪(B∖A) (szimmetrikus differencia)

(k) (A∪B)∖(A∩B) (szimmetrikus differencia)

Bizonyítsa be a halmazműveletek definíciója alapján, hogy tetszőleges A, B, C, D halmazokra teljesülnek az alábbi 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"; ⇋ "...ból következik, hogy..."; ⇋ "... pontosan akkor, ha ..." vagy "... akkor és csak akkor, ha ...")

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}
minden x∈I-re x∈A ⇔ x∉A
AB AB = A∩B = {x∈I | x∈A ∧ x∉B}
minden x∈I-re x∈AB ⇔ x∈A ∧ x∉B

(4.a) A⊆A (a részhalmaz reláció reflexivitása)

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ö. az (e) feladattal).

A bizonyítás lépései formálisan leírva (b.o. = "bal oldal"; j.o. = "jobb oldal"):
  • x∈A [b.o.] ⇒
    • x∈A [j.o.] ⇒
    • A⊆A

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 (innentől c∈A), de az óra végén 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 c∈A).
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.

(4.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?

(4.c) A∩B⊆A (→c1), A⊆A∪B (→c2) és A∩B⊆A∪B (→c3)

(c1) A∩B⊆A és 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!)

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 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

(4.d) ha A⊆B, akkor A⊆A∩B (→d1) és A∪B⊆B (→d2) 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.)

(4.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

(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.)

(4.f) 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. Tehát két eset lehetséges:
        (I.i.) x∈A és x∈B teljesül. Ekkor a metszetképzés definíciója miatt x∈(A∩B) teljesül.
        (I.ii.) x∈A és x∈C teljesül. Ekkor a metszetképzés definíciója miatt x∈(A∩C) teljesül.
    Tehát x∈A∩(B∪C) esetén (I.) vagy x∈(A∩B) (I.i.) vagy x∈(A∩C) (I.ii.) teljesül, amiből az unióké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.
        (II.ii.) x∈(A∩C) teljesül. Ekkor a metszetképzés definíciója miatt x∈A és x∈C teljesül.
    Tehát x∈(A∩B)∪(A∩C) (II.) esetén vagy x∈A és x∈B (II.i.), vagy x∈A és x∈C (II.ii.) teljesül, ami ugyanazt jelenti ("ekvivalens" azzal), hogy x∈A és vagy x∈B vagy x∈C teljesül.* Emiatt x∈(A∩B)∪(A∩C) teljesüléséből az unióképzés definíciója miatt x∈A és x∈B∪C, a metszetképzés definíciója miatt pedig x∈A∩(B∪C) következik. Ebből viszont a részhalmaz reláció definíciója következtében (A∩B)∪(A∩C) ⊆ A∩(B∪C) teljesül.
    Ö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.

A bizonyítás lépései formálisan leírva:
  • x∈A∩(B∪C)
    • x∈A ∧ x∈(B∪C) ⇒
    • x∈A ∧ (x∈B ∨ x∈C) ⇒
    • (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒
    • (x∈A∩B) ∨ (x∈A∩C) ⇒
    • x∈(A∩B)∪(A∩C)
  • x∈(A∩B)∪(A∩C)
    • x∈(A∩B) ∨ x∈(A∩C) ⇒
    • (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒
    • x∈A ∧ (x∈B ∨ x∈C) ⇒
    • x∈A ∧ x∈(B∪C) ⇒
    • x∈A∩(B∪C)
  • A∩(B∪C)⊆(A∩B)∪(A∩C) ∧ (A∩B)∪(A∩C)⊆A∩(B∪C) ⇒
    • A∩(B∪C) = (A∩B)∪(A∩C)

A bizonyítás során felhasználtuk az "és" és "vagy" logikai műveletek disztributivitását. 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.

(4.g) a metszetképzés és az unióképzés abszorpciója

(4.h) de Morgan-féle 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 AB = A∩B azonosság alapján, és utána alkalmazza az unió, metszet és komplementerképzésre vonatkozó azonosságokat!)

(a) AB = A∪B

(b) A(A∩B) = AB

(c) A∪B = A∪(BA)

(d) A∩(BA) = ∅

(e) (A∪B)B = AB

(f) (AB)C = A(B∪C) = (AC)(BC)

(g) A(BC) = (AB)∪(A∩C)

(h) (A∩B)C = (A∩B)(A∩C) = A∩(BC)

(i) (A∪B)C = (AC)∪(BC)

(j) A(B∪C) = (AB)∩(AC) = (AB)C

(k) A(B∩C) = (AB)∪(AC)

(l) (AB)∪B = A∪B

(m) A(AB) = A∩B

(n) (A∪B)∩(A∪B) = (A∩B)∪(AB)

Melyek azok a halmazok, amelyekre AB=BA teljesül? (tipp: először igazolja, hogy AB és BA diszjunktak, majd azt, hogy AB=BA=∅, végül azt, hogy A=B teljesül.)


2.1. Descartes-féle szorzat

Legyen A és B két tetszőleges halmaz, a∈A és b∈B. Ekkor (a,b)-t az 'a' és 'b' elemekből képzett rendezett párnak nevezzük, ahol
– 'a' az (a,b) rendezett pár első komponense vagy tagja,
– 'b' pedig az (a,b) rendezett pár második komponense vagy tagja.

Legyenek (a,b) és (c,d) rendezett párok. Ekkor (a,b)=(c,d) akkor és csak akkor teljesül, ha a=c és b=d teljesül, azaz a rendezett párok megfelelő komponensei egyenlők.

Legyen 'A' és 'B' két tetszőleges halmaz. Ekkor az 'A' és 'B' halmazok elemeiből képzett rendezett párok halmazát, azaz az
AΧB = { (a,b) | a∈A, b∈B}
halmazt az 'A' és 'B' halmazok Descartes-féle szorzatának vagy direkt szorzatának nevezzük.

Ha az 'A' és 'B' halmazok végesek, valamint |A|=n, |B|=m (n, m∈ℕ+), akkor |AΧB|=n*m, vagyis az 'A' és 'B' halmazok direkt szorzatának elemszáma a direkt szorzat tényezőit alkotó halmazok elemszámának szorzata.


Például legyen

A = {"fehér", "piros", "kék", "zöld", "fekete"} és
B = {"Audi", "Mercedes", "Ford"}.

Az 'A' és 'B' halmazok direkt szorzata:

AΧB = {("fehér","Audi"), ("piros","Audi"), ("kék","Audi"), ..., ("fehér","Mercedes"), ("piros","Mercedes"), ("kék","Mercedes"), ..., ("kék","Ford"), ("zöld","Ford"), ("fekete","Ford")}

Mivel |A|=5 és |B|=3, emiatt |AΧB|=5*3=15.

Az AΧB direkt szorzatot ábrázolhatjuk egy 5x3-as mátrix (táblázat) formájában (a táblázat fejsorát és fejoszlopát csak a jobb megértés kedvéért ábrázoltuk):

Audi Mercedes Ford
fehér (fehér, Audi) (fehér, Mercedes) (fehér, Ford)
piros (piros, Audi) (piros, Mercedes) (piros, Ford)
kék (kék, Audi) (kék, Mercedes) (kék, Ford)
zöld (zöld, Audi) (zöld, Mercedes) (zöld, Ford)
fekete (fekete, Audi) (fekete, Mercedes) (fekete, Ford)

Az AΧB direkt szorzatot ábrázolhatjuk egy 15x2-as táblázat formájában is:

Szín Autómárka
fehér Audi
piros Audi
kék Audi
... ...
fehér Mercedes
piros Mercedes
kék Mercedes
... ...
kék Ford
zöld Ford
fekete Ford

2.2. Relációk

Legyen 'A' és 'B' két tetszőleges halmaz. Ekkor az AΧB Descartes-szorzat bármely
ρ ⊆ AΧB
részhalmazát az 'A' és 'B' halmazok közötti relációnak vagy megfeleltetésnek nevezzük. Ha A=B teljesül, homogén relációról, ha pedig A≠B teljesül, inhomogén relációról beszélünk. (Egyes szerzők a homogén relációk esetében használják a 'reláció' megnevezést, és az inhomogén relációkat nevezik megfeleltetéseknek.)

Ha 'A' és 'B' véges halmazok, akkor elvileg közöttük annyi különböző megfeleltetés létesíthető, ahány lehetséges (különböző) részhalmaza van az AΧB direkt szorzatnak. Ez a direkt szorzat hatványhalmazának elemszáma, vagyis ha |A|=n és |B|=m (n, m∈ℕ+), akkor a lehetséges megfeleltetések száma 2n*m.

Ha A=B, akkor a 'ρ' relációt az A-n értelmezett kétváltozós vagy binér relációnak nevezzük; a továbbiakban kétváltozós vagy binér reláció alatt mindig homogén relációt értünk.

Ha (a,b)∈ρ teljesül, akkor az 'a' és 'b' elemek relációban vannak egymással. Ezt ρ(a,b) vagy (a ρ b) módon jelöljük. Példák:


Példaként tekintsük a következő halmazokat:

   A = {"fehér", "piros", "kék", "zöld", "fekete"} és
   B = {"Audi", "Mercedes", "Ford"}.

A színek halmazának (A) és a autómárkák halmazának (B) direkt szorzatán adjunk meg egy
   ξ⊆AΧB
relációt pl. a következőképpen:

ξ = {("fehér","Audi"), ("kék","Audi"), ("fehér","Mercedes"), ("piros","Ford")}

Értelmezzük a ξ relációt a következőképpen:
ξ(x,y) ⇋ "az 'x' színű autóból jelenleg 'y' márkájú autó van raktáron"

A ξ reláció ismeretében például feltehetjük az alábbi kérdést: ha fehér színű autót szeretnénk, milyen márkák vannak jelenleg raktáron? A választ az alábbi halmaz elemei adják meg:
{y∈B | ξ("fehér",y)}

A ξ relációt ábrázolhatjuk például nyíldiagrammal:

színek és autómárkák kapcsolata (nyíldiagram)

A ξ relációt ábrázolhatjuk egy "rács" segítségével is:

színek és autómárkák kapcsolata (rács)

A fenti ábra 90 fokkal elforgatva: színek és autómárkák kapcsolata (rács)

Az AΧB direkt szorzatot ábrázoló egy 5x3-as mátrixban (vagy táblázatban) jelöljük be azokat az elempárokat, amelyek a ξ reláció elemei:

Mercedes Ford Audi
fehér (fehér, Mercedes) (fehér, Ford) (fehér, Audi)
piros (piros, Mercedes) (piros, Ford) (piros, Audi)
zöld (zöld, Mercedes) (zöld, Ford) (zöld, Audi)
kék (kék, Mercedes) (kék, Ford) (kék, Audi)
fekete (fekete, Mercedes) (fekete, Ford) (fekete, Audi)

Egy másik példaként tekintsük a következő halmazokat:

   A = {gyümölcsök nevei} és
   B = {1,2,3,...,67}.

A gyümölcsnevek halmazának (A) és az 1 és 67 közötti természetes számok halmazának (B⊆ℕ) direkt szorzatán adjunk meg egy
   η⊆AΧB
relációt a következőképpen:

η(a,n) ⇋ "az 'a' gyümölcsnév hossza pontosan 'n' darab betű"

Döntsük el, hogy az alábbi állítás igaz-e:

η("alma",4)    


Lássunk egy példát binér relációra. Legyen
   A = {1, 2, 3, 4, 5, 6}
és értelmezzük a
   γ⊆AΧA
binér relációt a következőképpen:
   γ = {(1,2), (1,4), (2,4), (2,5), (3,6), (4,5), (5,4), (5,5)}

A γ binér relációt ábrázolhatjuk egy irányított gráffal, ahol a gráf csúcsai (vagy csomópontjai) az 'A' halmaz elemeinek felelnek meg, és az a∈A pontból a b∈A pontba mutató irányított élt (nyilat) akkor és csak akkor ábrázoljuk, ha (a,b)∈γ teljesül.

Ennek megfelelően a γ relációt ábrázoló gráf a következő:

példa irányított gráfra

Feladat: próbáljunk meg olyan modelleket konstruálni, amelyekben a fenti relációhoz jelentést rendelünk!


Lássunk egy további példát egy binér relációra. Legyen az 'A' halmaz a gyümölcsnevek halmaza, azaz
   A = {gyümölcsök nevei}.

A gyümölcsnevek halmazának (A) önmagával vett direkt szorzatán adjunk meg egy
   θ⊆AΧA
relációt a következőképpen:

θ(a,b) ⇋ "az 'a' és 'b' gyümölcsnevek hossza megegyezik"

Ekkor például
   θ("alma","alma"), azaz ("alma","alma")∈θ,
   θ("barack","szilva"), azaz ("barack","szilva")∈θ,
   θ("szilva","barack"), azaz ("szilva","barack")∈θ.

Ezzel szemben például
   ("alma","citrom")∉θ és
   ("dinnye","dió")∉θ.

A θ relációt véges 'A' halmaz esetén ábrázolhatjuk például irányított gráf formájában. Értelmezzük a θ relációt az

A={"alma", "banán", "barack", "citrom", "dinnye", "dió", "eper", "körte", "mogyoró", "narancs", "szilva"}

halmazon, és ábrázoljuk a θ relációt:

azonos hosszú gyümölcsnevek ábrázolása irányított gráf formájában

Vegyük észre, hogy az azonos hosszúságú gyümölcsnevek diszjunkt elemhalmazokba, osztályokba csoportosíthatók.


Egy további példaként vegyük az I = {piros, zöld, kék} alaphalmaz részhalmazait és ábrázoljuk a köztük értelmezett binér relációt táblázatos formában! (Rövidítésként "piros" helyett "p"-t, "zöld" helyett "z"-t, és "kék" helyett "k"-t fogunk használni. Vegyük észre, hogy például p↔a, z↔b, és k↔c helyettesítéseket végrehajtva a táblázat megadja az I={a,b,c} halmaz összes részhalmazát és ezek tartalmazási viszonyait.)

A⊆B ←B→
↓A↓ {p} {z} {k} {p,z} {p,k} {k,z} {p,z,k}
{p}
{z}
{k}
{p,z}
{p,k}
{k,z}
{p,z,k}
↑A↑ {p} {z} {k} {p,z} {p,k} {k,z} {p,z,k}

2.3. Inverz reláció

Legyen 'A' és 'B' két tetszőleges halmaz, és ρ⊆AΧB az 'A' és 'B' halmazok közötti reláció. Ekkor a
ρ−1 ⊆ BΧA = {(b,a) | a∈A, b∈B, ρ(a,b)}
relációt a ρ reláció inverz relációjának nevezzük.

Az inverz reláció definíciójából következik, hogy ρ−1(b,a) akkor és csak akkor teljesül, ha ρ(a,b) teljesül. Példák:


Vizsgáljuk meg ismét a színek és autómárkák kapcsolatát leíró példát:

   A = {"fehér", "piros", "kék", "zöld", "fekete"} és
   B = {"Audi", "Mercedes", "Ford"}.

A színek halmazának (A) és a autómárkák halmazának (B) direkt szorzatán korábban értelmeztük az alábbi relációt:
   ξ⊆AΧB
   ξ = {("fehér","Audi"), ("kék","Audi"), ("fehér","Mercedes"), ("piros","Ford")}.

A ξ reláció inverze:
   ξ−1⊆BΧA
   ξ−1 = {("Audi","fehér"), ("Audi","kék"), ("Mercedes","fehér"), ("Ford","piros")}

Értelmezzük a ξ−1 inverz relációt a következőképpen:
ξ−1(y,x) ⇋ "az 'y' márkájú autóból jelenleg 'x' színű van raktáron"

A ξ−1 reláció ismeretében például feltehetjük az alábbi kérdést: ha Ford márkájú autót szeretnénk, milyen színűek vannak jelenleg raktáron? A választ az alábbi halmaz elemei adják meg:
{x∈A | ξ−1("Ford",x)}

A ξ−1 inverz relációt is ábrázolhatjuk nyíldiagrammal:

színek és autómárkák kapcsolata (nyíldiagram)


2.4. A kétváltozós (binér) relációk fontosabb tulajdonságai

Legyen 'A' tetszőleges halmaz, amelyen értelmezett az '=' reláció. Legyen továbbá ρ⊆AΧA kétváltozós (binér) reláció. Értelmezzük az alábbi tulajdonságokat:

A trichotómia lényege szemléletesen fogalmazva az, hogy egy trichotóm reláció segítségével egy halmaz bármelyik két (különböző) eleme összehasonlítható egymással. (Aszimmetrikus vagy antiszimmetrikus reláció esetén ennek a halmazok rendezésekor nagy jelentősége lesz.)


A trichotómia fogalma nem egyértelműen jelenik meg a szakirodalomban. Például bevezethetjük az alábbi fogalmakat is (vö. MaYoR 2020):

A trichotómiára adott korábbi meghatározásunkban az a=b esetben nem mondtunk semmit sem az elemek közti relációról (azaz mind (a,a)∈ρ, mind (a,a)∉ρ teljesülését megengedjük), azonban az a≠b esetben vagy az összefüggőséget, vagy (szigorúbb feltételként) a dichotómiát megköveteltük.


Az egyes relációtulajdonságok szemléltetése gráfokkal

Gyakorló feladatok (vö. Veress 1996: 26-29):

Bizonyítsa be, hogy bármely A, B és C halmazokra teljesülnek az alábbi azonosságok:

(a) AΧ(B∪C) = (AΧB)∪(AΧC)

(b) AΧ(B∩C) = (AΧB)∩(AΧC)

Adja meg felsorolással és ábrázolja az alábbi halmazok direkt szorzatát!

(a) A={1, 2} és B={a, b, c}

(b) A={1, 2} és B={0, 3}

(c) A={3, 4, 5} és B={6, 8, 10, 12}

(d) A=B={a, b, c}

Legyen A={3, 4, 5} és B={6, 8, 10, 12}. Adja meg az alábbi megfeleltetéseket és inverzeiket az elemek felsorolásával! Ábrázolja őket nyíldiagrammal, ráccsal és mátrixos (táblázatos) formában!

(a) ω = {(a,b) | a∈A, b∈B, a<b}

(b) σ = {(a,b) | a∈A, b∈B, a|b}

(c) κ = {(a,b) | a∈A, b∈B, a≡b (mod 3)} (a≡b (mod 3) ⇋ "az 'a' és 'b' természetes számok 3-mal való osztási maradéka azonos")

(d) ν = {(a,b) | a∈A, b∈B, |a−b| páros}

Adja meg az alábbi binér relációkat felsorolással és ábrázolja őket! Ezután vizsgálja meg a tulajdonságaikat!

(a) A={"alma", "ceruza", "fa", "kréta"} és
     α = {(x,y) | x∈A, y∈A, "az 'x' szó több betűből áll, mint az 'y' szó"}

(b) A={"alma", "fa", "kréta", "só"} és
     β = {(x,y) | x∈A, y∈A, "az 'x' szó kevesebb betűből áll, mint az 'y' szó"}

(c) A={1, 2, 3, 4, 5, 6} és
     γ = {(1,2), (1,4), (2,4), (2,5), (3,6), (4,5), (5,4), (5,5)}

(e) A={1, 2, 3, 4, 5, 6} és
     δ = {(x,y) | x∈A, y∈A, x+y=7}

(e) A={2, 3, 5} és
     ε = {(x,y) | x∈A, y∈A, x≥y}

(f) A={"áfonya", "kiwi", "málna", "meggy", "szeder"} és
     θ = {(a,b) | a∈A, b∈A, "az 'a' és 'b' gyümölcsnevek hossza megegyezik"}

(g) I={1, 2} és
     φ = {(A,B) | A∈2I, A∈2I, A⊆B}

(h) I={a, b, c} és
     μ = {(A,B) | A∈2I, A∈2I, A⊂B}


3.1. Nevezetes kétváltozós relációk: az ekvivalenciareláció

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt ekvivalenciarelációnak nevezzük, ha reflexív, szimmetrikus és tranzitív.

Például a természetes számokon értelmezett egyenlőség ( = ) ekvivalenciareláció.

Legyen 'A' tetszőleges véges halmaz,
Η = { A1, A2, ..., An } pedig az A halmaz nem üres részhalmazainak halmaza, amelyekre teljesül, hogy
   (a) Ai⊆A és Ai≠∅ (i=1, 2, ..., n),
   (b) a részhalmazok páronként diszjunktak, azaz minden 1 ≤ i≠j ≤ n esetén Ai ∩ Aj = ∅, és
   (c) a részhalmazok uniója magát az A halmazt adja, azaz
A1 ∪ A2 ∪ ... ∪ An = A teljesül.

A Η⊆2A halmazt A egy osztályozásának nevezzük, az AiΗ részhalmazokat (1 ≤ i ≤ n) pedig osztályoknak.

Legyen 'A' egy tetszőleges halmaz. Az 'A' halmaz részhalmazainak egy Η⊆2A rendszere osztályozás, ha
Η nem tartalmazza az üres halmazt,
Η elemei (az ún. osztályok) páronként diszjunktak, és
Η elemeinek uniója az 'A' halmazt adja.

Egy halmaz elemeinek osztályozását Venn-diagram segítségével például a következőképpen szemléltethetjük:

Egy halmaz felbontása diszjunkt osztályokra Venn-diagramon

Például tekintsük a korábban bevezetett, 10 tanulóból álló 'I' osztályt és értelmezzük a tanulók között a ψ⊆IΧI relációt a következőképpen:

ψ(x,y) ⇆ "az 'x' és 'y' tanulók érdemjegye megegyezik matematikából"

Ha bevezetjük a tárgyak
T = {"magyar", "matek", "tesi", "angol", ...}
halmazát és a
jegy : IΧT→{1, 2, 3, 4, 5}
"osztályozó" függvényt, a fenti reláció formálisan
ψ = {(x,y) | x∈I, y∈I, jegy(x,"matek")=jegy(y,"matek")}
módon adható meg.

A ψ reláció ekvivalenciareláció, mert

Hozzuk létre az 'I' osztályban az alábbi halmazokat a tanulók matematikából kapott jegyei alapján:

Ii = {x∈I | jegy(x,"matek")=i} (i=1,2,...,5)

Vegyük észre, hogy az egyes Ii halmazokba sorolt tanulók matematikai jegye megegyezik:

Mindegyik Ii halmazra igaz, hogy a halmazba tartozó bármelyik x∈Ii és y∈Ii tanuló esetén ψ(x,y) teljesül (azaz az 'x' és 'y' tanulók jegye azonos matematikából).

Tanulói csoportok kialakítása jegyek alapján Venn-diagramon

Tekintsük azokat az Ii halmazokat, amelyek nem üresek, és hozzuk létre ezekből a Η halmazrendszert:

Η = {Ii | Ii≠∅, i=1,2,...,5}

(a) Az így definiált Η halmazrendszer az 'I' osztály egy ψ reláció szerinti osztályozása, mivel Η nem tartalmazza az üres halmazt, továbbá
– az Ii halmazok diszjunktak (minden tanuló pontosan egy Ii halmazba tartozik), és
– az Ii halmazok uniója a teljes 'I' osztályt adja (azaz minden tanuló beletartozik valamelyik Ii halmazba).

(b) Az előző gondolatsor megfordítása is igaz: ha adottak az egyes Ii halmazok, a segítségükkel értelmezett
ψ' = {(x,y) | x∈I, y∈I, és van olyan Ii halmaz, amelyre x∈Ii és y∈Ii teljesül}
reláció megegyezik a korábban definiált ψ relációval.

Az ekvivalenciarelációk és az osztályozások között szoros kapcsolat van:
   (a) minden ρ ⊆ AΧA ekvivalenciarelációnak megfelel az 'A' halmaz egy "természetes" Η osztályozása (az egyes osztályokat a ρ szerint ekvivalens elemek alkotják);
   (b) az 'A' halmaz minden Η osztályozása "természetes" módon meghatároz egy ρ ⊆ AΧA ekvivalenciarelációt (azokat az elemeket tekintjük ρ szerint ekvivalensnek, amelyek azonos osztályba tartoznak).

(a) Ha adott egy ρ⊆AΧA ekvivalenciareláció, akkor az 'A' halmaznak pontosan azokat az x, y∈A elemeit soroljuk egy osztályba, amelyekre ρ(x,y) teljesül, azaz az elemek ρ szerint ekvivalensek.

Tekintsük például a Dienes Zoltán által kifejlesztett logikai készletet:
a teljes logikai készlet
A készlet elemei között számos olyan közös tulajdonság található (színek, formák stb.), amelyek a segítségével a készlet összes eleme diszjunkt csoportokba sorolható, vagyis osztályozható. Az osztályozás alapját képező ekvivalenciareláció nemcsak egy, hanem több közös tulajdonságot is magába foglalhat (pl. ρ(x,y) ⇋ "'x' és 'y' azonos színű és egyforma méretű" stb.)

(b) Ha adott az 'A' halmaz egy Η osztályozása, akkor az 'A' halmaznak pontosan azokat az x, y∈A elemeit tekintjük egymással relációban állóknak (ρ szerint ekvivalenseknek), amelyek azonos osztályba tartoznak.

Az előző feladat megfordítása: alakítsunk ki (diszjunkt) csoportokat a logikai készlet elemeiből és határozzuk meg a csoportosítás alapjául szolgáló közös tulajdonságot vagy tulajdonságokat!

Példák:


Az 'A' halmaz elemei között értelmezett egyenlőség (=) reláció ekvivalenciareláció, amelyhez az 'A' halmaz triviális

ΗA = {{x} | x∈A}

osztályozása tartozik.


Egy négy elemből álló A = {1, 2, 3, 4} halmaz összes lehetséges Η osztályozását (vagy felbontását, partícionálását) a következőképpen kaphatjuk meg:

Figyeljük meg, hogy mindegyik osztályozást egy másik osztályozásból kaptunk úgy, hogy egy kiválasztott osztályt felbontottunk két további (diszjunkt) osztályra. Ezért a kiinduló osztály minden esetben tartalmazza a felbontással ("finomítással") kapott osztályokat. A lehetséges osztályozások szemléletesen ábrázolhatóak egy ún. Hasse-diagramon, ahol az osztályok közötti relációkat nyíllal jelöltük (a diagramon a kiinduló osztályozás mindig feljebb, a felbontás eredményeként kapott osztályozás pedig mindig lejjebb szerepel, ezért a felbontási reláció irányát nem szükséges feltüntetni).

Egy négyelemű halmaz összes lehetséges felbontása diszjunkt osztályokra (partíciókra)

Az osztályozások közötti reláció egy lehetséges definíciója két tetszőleges Ηx és Ηy osztályra:
ΗxΗy ⇋ ∀AiΗx ∃AjΗy (Ai⊆Aj)
Az így definiált ≼ reláció könnyen beláthatóan reflexív, antiszimmetrikus és tranzitív.


Az osztályozások egyik leggyakoribb formája egy adott halmaz elemeinek megkülönböztetése több különböző tulajdonság alapján, és ennek megfelelően az elemek elrendezése egy hierarchikus, ún. fastruktúrában (vagy fadiagramon).

Tekintsük például a következő feladatot (vö. Miklovicz 2018: 16-17):

Juli azon gondolkodik, milyen ruhát vegyen fel. A szekrényében a következő ruhák vannak:
  • két sapka (piros, zöld),
  • három blúz (kék, piros, sárga) és
  • két szoknya (kék, zöld).

Legyen az 'R' halmaz Juli összes lehetséges öltözete:

R = {(piros sapka, kék blúz, kék szoknya), (piros sapka, kék blúz, zöld szoknya), (piros sapka, piros blúz, kék szoknya), ..., (zöld sapka, sárga blúz, zöld szoknya)}

Az 'R' halmaz elemszáma: |R|=2*3*2=12

Az 'R' halmazt három tulajdonság segítségével osztályozzuk:
sapka_szine : R→{piros, zöld}
bluz_szine : R→{kék, piros, sárga}
szoknya_szine : R→{kék, zöld}

Alakítsuk ki a következő négy osztályozást:

Ábrázoljuk a különböző osztályozásokat egy négy szintű fadiagramon:

különböző színű sapkák, blúzok és szoknyák választása döntési fával

Jegyezzük meg, hogy az ábrázolt fadiagram felhasználható arra is, hogy segítse Julit a megfelelő ruhaválasztásban. Juli először sapkát választ (például pirosat), utána ruhát (pélául sárgát), majd végül szoknyát (például kéket). A választás minden lépésben egy adott tulajdonság kiválasztását jelenti, amely meghatározza, hogy a fa melyik ágán kell tovább haladnunk, míg végül eljutunk a legalsó szintig. Ebben az értelemben a fadiagramot döntési fának is nevezhetjük.


3.2. Nevezetes kétváltozós relációk: rendezési relációk

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt reflexív (vagy "gyenge") rendezési relációnak nevezzük, ha reflexív, antiszimmetrikus és tranzitív.

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt irreflexív (vagy "szigorú") rendezési relációnak nevezzük, ha irreflexív, aszimmetrikus és tranzitív.

Ha az 'A' halmazon értelmezve van egy ρ rendezési reláció, azt (A; ρ) módon jelöljük.

Például az 'I' halmaz hatványhalmazán (azaz az 'I' halmaz részhalmazai között) értelmezett

Például a természetes számokon értelmezett

Legyen az (A; ρ) halmaz részben rendezett. Vezessük be az egymással rendezési relációban levő a, b∈A elemekre az a≼b ⇋ ρ(a,b) jelölést (⇋ "a előtte van b-nek" vagy "a megelőzi b-t").

Ha az (A; ρ) részben rendezett halmaz véges, akkor ábrázolhatjuk egy irányított gráf, az ún. Hasse-diagram segítségével. A Hasse-diagramot a következőképpen állíthatjuk elő:

Például ábrázoljuk az A={a, b, c} halmaz esetén a (2A; ⊆) részben rendezett halmaz elemeit Hasse-diagrammal: Az A={a, b, c} halmaz hatványhalmazának részhalmaz reláció szerinti Hasse-diagramja

Szemléletesen azt is mondhatjuk, hogy a fenti diagramon az üreshalmaz a "legkisebb" (legalsó) elem, az A={a, b, c} halmaz pedig a "legnagyobb" (legfelső) elem.

Figyeljük meg, hogy egyes csomópontokból több él indulhat ki, bizonyos csomópontokba több él futhat be, és a "legkisebb" elemből több különböző úton keresztül is eljuthatunk a "legnagyobb" elemhez. Visszafelé azonban egyetlen csomópontból sem vezet út, a fenti diagramon csak "felfelé" haladhatunk.

Ha egy véges 'A' halmazon értelmezünk egy ρ⊆AΧA teljes rendezési relációt, akkor egy megfelelő algoritmus segítségével az 'A' halmaz elemei "lineárisan" sorba rendezhetők.

A parciális és teljes rendezés közötti különbséget jól tudjuk szemléltetni, ha a (részben vagy teljesen) rendezett halmaz egyes elemeire értelmezzük a"legkisebb" ("legnagyobb") elem, ill. "minimális" ("maximális") elem fogalmakat.

Legyen ρ⊆AΧA az 'A' halmazon értelmezett rendezési reláció, és vezessük be az egymással relációban levő a, b∈A elemekre az a≼b ⇋ ρ(a,b) jelölést. Ekkor az (A; ≼) rendezett halmaz

Ha létezik egy részben rendezett halmaznak legnagyobb eleme, akkor az egyúttal maximális elem is. Ha létezik egy részben rendezett halmaznak legkisebb eleme, akkor az egyúttal minimális elem is (vö. Bogya 2018: 19).

Egy részben rendezett halmazban legnagyobb, ill. legkisebb elemből legfeljebb egy darab létezhet, ugyanakkor maximális, ill. minimális elemből több is lehet (vö. Bogya 2018: 19).

Teljesen rendezett halmazok esetében a legkisebb elem és a minimális elem, valamint a legnagyobb elem és a maximális elem egybeesik (vö. Nagy 2017: 5. ea.).

Egy teljesen rendezett halmaznak legfeljebb egy minimális eleme és legfeljebb egy maximális eleme lehet (Dringó-Kátai 1986: 29).


Legyen például A={1,2,...,8}, és tekintsük az 'A' halmazon az oszthatósági relációt (amely gyenge parciális rendezési reláció). Ekkor

Az (A; |) oszthatóság szerint részben rendezett halmaz Hasse-diagramja:
Az A={1,2,...,8} halmaz oszthatóság szerinti Hasse-diagramja

Gyakorló feladatok (vö. Veress 1996: 30-31):

Vizsgálja meg a következő relációk tulajdonságait! Állapítsa meg, melyek nevezetes relációk!

(a1) {(x,y) | x∈ℕ, y∈ℕ, x|y}

(a2) {(x,y) | x∈ℕ+, y∈ℕ+, x|y}

(a2) {(x,y) | x∈ℕ+, y∈ℕ+, 1<x, 1<y, x|y}

(b) {(x,y) | x∈ℤ, y∈ℤ, x|y} (ℤ ⇆ "az egész számok halmaza")

(c) {(x,y) | x∈ℕ, y∈ℕ, 1<x, x≠y, x|y} (1<x<y, x|y ⇆ "az 'x' (természetes) szám valódi osztója az 'y' (természetes) számnak")

(d) {(x,y) | x∈ℕ, y∈ℕ, y=3*x}

(e) {(x,y) | x∈ℤ, y∈ℤ, x≡y (mod 4)} (x≡y (mod 4) ⇋ "az 'x' és 'y' (egész) számok 4-vel való osztási maradéka azonos")

Adott a következő osztályozás:
Η = { A1, A2, A3 }, amelyre
    A1={(2,3), (2,5), (2,9)}
    A2={(4,7), (4,11)}
    A3={(6,7)}
Adja meg azt az 'A' halmazt, amelyen az osztályozást értelmezzük, valamint azt a ψ ekvivalenciarelációt, amely ehhez az osztályozáshoz vezet!

Vizsgálja meg, hogy az adott 'A' halmaznak osztályozását jelentik-e a megadott {A1, A2, A3} halmazrendszerek? Ha nem, változtassa meg a halmazrendszer elemeit! Adja meg az egyes osztályozásokhoz tartozó ψ ekvivalenciarelációt is!

(a) A = {ló, hal, egér, fecske, sas, sikló} és
A1={hal, sikló}
A2={fecske, sas}
A3={ló, egér}

(b) A = {autó, repülőgép, busz, helikopter, hajó, kamion} és
A1={autó, busz}
A2={repülőgép, helikopter}
A3={hajó}

(c) A = {1, 2, 3, 21, 32, 41, 342, 572} és
A1={1, 2, 3}
A2={2, 21, 32, 41}
A3={342, 572, 842}

Adjon meg egy ekvivalenciarelációt, amely létrehozza az 'A' halmazrendszer osztályozását! Végezze el és ábrázolja az 'A' halmaz osztályozását!
A = {{0, 2, 4, 6}, {0, 6}, {1, 2, 4, 8}, {1, 4}, {2, 4}}

Döntse el, hogy az alábbi Η halmazrendszerek osztályozásai-e a megadott 'A' halmaznak?

(a) A=P∪Q (ahol P és Q tetszőleges halmazok)
Η = {PQ, P∩Q, QP}

(b) A=ℤ
Η = {{páros egész számok}, {páratlan egész számok}}

(c) A=ℤ
Η = {{x∈ℤ | x≡k (mod 3)} | k=0, 1, 2}

(d) A=ℤ
Η = {{pozitív egész számok}, {negatív egész számok}}

(e) A=ℤ
Η = {{pozitív egész számok}, {nemnegatív egész számok}}

Vizsgálja meg az alábbi relációk tulajdonságait és válassza ki a rendezési relációkat!

(a) I = {egy osztály tanulóinak halmaza}
α = {(a,b) | a∈I, b∈I, 'a' több ötöst kapott a héten, mint 'b'}

(b) K = {egymásra rakott könyvek halmaza}
β = {(a,b) | a∈K, b∈K, az 'a' könyv a 'b' könyv felett van}

(c) L = {egymásra rakott könyvek halmaza}
β = {(a,b) | a∈K, b∈K, az 'a' könyv közvetlenül a 'b' könyv alatt van}

(d) M = {egy polcon levő könyvek halmaza}
β = {(a,b) | a∈K, b∈K, az 'a' könyv a 'b' könyv mellett van}

Adjon meg egy (vagy több) ekvivalenciarelációt és rendezési relációt az alábbi halmazokon! Adja meg és ábrázolja a relációkat!

(a) A = {veréb, ló, elefánt, sas, medve}

(b) A = {(5, 2), (8, 3), (4, 9), (7, 2), (11, 2), (13, 9)}

(c) A = {0.15, 1.03, 10.5, 30.1, 310, 501}


4.1. Függvények

Legyenek 'A' és 'B' tetszőleges halmazok, ρ⊆AΧB az 'A' és 'B' halmazok közötti reláció. Ekkor a

A ρ relációt hozzárendelésnek nevezzük, ha értelmezési tartománya a teljes A halmaz, azaz Dom(ρ)=A teljesül.

A ρ relációt függvénynek vagy leképezésnek nevezzük, ha
(1) értelmezési tartománya a teljes A halmaz, vagyis ρ hozzárendelés, és
(2) az értelmezési tartomány minden eleméhez az értékkészlet pontosan egy eleme tartozik, vagyis az értelmezési tartomány minden a∈A elemére |{b∈B | ρ(a,b)}|=1 teljesül.

Ha a ρ reláció függvény, akkor a továbbiakban az
f : A→B
jelölést (vagy ha nem okoz félreértést, egyszerűen az f(x) jelölést) fogjuk használni, tetszőleges a∈A elem, és az ehhez tartozó b∈B elem mellett
f(a)=b ⇋ ρ(a,b)
értelemben. Az f(a)=b∈B értéket az f(x) függvény a∈A helyen vett függvényértékének (helyettesítési értékének) vagy az a∈A elem képének nevezzük.


4.2. Függvények tulajdonságai

Legyen f : A→B egy tetszőleges függvény. Értelmezzük az alábbi tulajdonságokat:

Például legyen az I osztály tanulóinak halmaza:
I = {"Tercsi", "Fercsi", "Kata", "Klára", "Anett", "Peti", "Mari", "Pisti", "Zoli", "Zsuzsa"}, és
B = {"A", "B", ..., "Z"}
a nagybetűk halmaza. Értelmezzük az f : I→B függvényt bármely x∈I tanuló esetén a következőképpen:

f(x) ⇋ "az 'x' tanuló nevének kezdőbetűje"

Az f(x) függvény tulajdonságai:

Válasszunk ki tanulókat az I osztályból, és legyen a kiválasztott tanulók halmaza
I' = {"Tercsi", "Fercsi", "Kata", "Anett", "Zsuzsa"}. Ekkor az előbb definiált f(x) függvény leszűkítése I'-re, azaz az
f | I' : I'→B
függvény már injektív, mert minden x∈I' kiválasztott tanuló nevének kezdőbetűje különböző.


4.3. Inverz függvény, összetett függvény

Az f : A→B injektív függvény inverz függvénye alatt azt az
f−1 : Rng(f)⊆B→A
függvényt értjük, amelyre teljesül, hogy az értelmezési tartományának minden y∈Rng(f) elemére f−1(y)=x akkor és csak akkor teljesül, ha f(x)=y teljesül. (Ha az f : A→B függvény bijektív, akkor Rng(f)=B miatt inverz függvénye f−1 : B→A.)

Az inverz függvényt injektív függvények esetén értelmezzük, ezért az injektív függvényeket invertálható függvényeknek is nevezzük.

Legyen az f(x) függvény invertálható, és inverze az f−1(x) függvény. Ekkor az f−1(x) függvény is invertálható, és inverz függvénye az f(x) függvény.

Legyenek f : A→B és g : B→C tetszőleges függvények (valójában elegendő annyit megkövetelni, hogy g : Rng(f)⊆B→C teljesüljön). Ekkor azt a h : A→C függvényt, amelyre teljesül, hogy az értelmezési tartományának minden x∈A elemére
    h(x)=z akkor és csak akkor teljesül, ha
    az f(x)=y elemre g(y)=z teljesül,
a g(x) és f(x) függvények összetett függvényének (vagy közvetett függvényének) nevezzük, és h(x)=(g∘f)(x), vagy egyszerűbben h(x)=g(f(x)) módon jelöljük.

Az összetett függvény definíciója alapján az f(x) : A→B injektív függvényre és ennek f−1(x) inverz függvényére h(x)=(f−1∘f)(x)=x teljesül (h(x) : A→A).
Mivel az f−1(x) függvény invertálható, és inverz függvénye f(x), ezért h(x)=(f∘f−1)(x)=x szintén teljesül (h(x) : Rng(f)→Rng(f), Rng(f)⊆B).

Például tekintsük az alábbi valós függvényeket és inverz függvényeiket:

f(x) Dom(f) Rng(f) f−1(x) Dom(f−1) Rng(f−1)
x x
2*x x/2
1/x {0} 1/x {0}
x2 [0,+∞) x [0,+∞) [0,+∞)
ex [0,+∞) ln(x) [0,+∞)

Jegyezzük meg, hogy ha Descartes-féle koordináta-rendszerben ábrázoljuk a fenti valós függvényeket, az egyes függvények görbéjét az y=x egyenesre mint tengelyre tükrözve a megfelelő inverz függvény görbéjét kapjuk.

4.4. Valós függvények tulajdonságai

Legyen f : A⊆ℝ→B⊆ℝ valós függvény. Értelmezzük az alábbi tulajdonságokat:

Figyeljük meg, hogy a valós függvények számos tulajdonságát értelmezhetjük
lokálisan, az értelmezési tartomány egy meghatározott A'⊆A részhalmazán, és
globálisan, a függvény teljes 'A' értelmezési tartományán.

4.5. Sorozatok

Az s : ℕ+→B függvényt (végtelen) sorozatnak nevezzük. A sorozat szokásos jelölése:
   s1, s2, ..., sn, ... (n∈ℕ+)

A sorozatokat megadhatjuk a sorozat első néhány elemének felsorolásával vagy egy táblázattal, ahol a "hozzárendelési utasítás(oka)t a gyerek fedezi fel, illetve adja meg" (Vajda 1996: 51). Sorozatokat pl. színes alakzatokból felépített ábrák (ún. "sorozatminták") segítségével is megadhatunk, amely rendkívül szemléletessé teheti a sorozatok képzési szabályát.

Az s : ℕ+→B⊆ℝ függvényt számsorozatnak nevezzük.

A számsorozatok szokásos megadása általában képlettel, például az első elem (s1), esetleg további elemek (s2,...), és az általános elem (sn) megadásával történik. Az általános elemet sokszor a megelőző elem vagy elemek segítségével állítjuk elő. Ilyenkor rekurzív definícióról (vagy megadásról) beszélünk. Jegyezzük meg, hogy a sorozatok képlettel történő megadása egy algoritmust ad meg, amellyel a sorozat elemei előállíthatók.

Mivel a sorozatok speciális függvények, értelmezhetjük az alábbi tulajdonságokat:


5.1. A számosság fogalma

Legyenek H1 és H2 tetszőleges halmazok. A két halmazt egyenlő számosságúnak ("számosságilag ekvivalensnek") nevezzük, ha létezik φ : H1→H2 bijektív leképezés a két halmaz között. (Véges halmazok esetében a számosság megegyezik a halmaz elemeinek a számával.)

Például legyen egy osztályban a tanulók I halmaza

I = {"Tercsi", "Fercsi", "Kata", "Klára", "Anett", "Peti", "Mari", "Pisti", "Zoli", "Zsuzsa"}.

Az I halmaz 10 elemből áll (|I|=10), és bijektív módon leképezhető a természetes számok {1,2,...,10} halmazára például úgy, hogy névsorba szedjük a tanulók neveit, és minden tanulóhoz hozzárendeljük a tanuló sorszámát. (Ha két azonos név szerepel, ezeket pl. római számokkal megkülönböztetjük.)

Ha egy tetszőleges H halmaz elemeihez sorszámot rendelünk, akkor leképezzük a H halmazt a természetes számok ℕ halmazára. Ez lehetőséget ad a természetes szám fogalmának értelmezésére.

Egy H halmaz számosságát |H| módon jelöljük. Ha a H1 és H2 halmazok egyenlő számosságúak, akkor ezt H1 ~ H2 vagy |H1| = |H2| módon jelöljük. (Előfordul a H1≅H2 jelölés is, pl. Bonifert-Kovácsné Győri 1987: 56 et passim.)

Legyen ℋ tetszőlegesen választott halmazokból álló halmaz (ún. halmazrendszer). (ℋ elemei egyaránt lehetnek véges és végtelen halmazok.)

A természetes számok értelmezésekor ℋ helyett egy olyan Σ halmazrendszert használunk, amelynek az elemei véges halmazok (de a Σ halmazrendszer végtelen sok véges halmazt tartalmazhat).

A természetes számok értelmezésekor használt Σ halmazrendszernek az alábbi tulajdonságokkal kell rendelkeznie (vö. Borsodi-Göndöcs 1970: 81-82; Brindza 1996: 61-62):

  • a Σ halmazrendszer véges halmazokat tartalmaz;
  • az üres halmaz a Σ halmazrendszer eleme, azaz ∅∈Σ;
  • a különböző tulajdonságú objektumokat (pl. almák, kockák, virágcserepek stb.) tartalmazó minden H∈Σ alaphalmaz esetén teljesül, hogy H-val együtt H minden részhalmaza is eleme Σ-nak (azaz 2HΣ teljesül). Vagyis
    • bármely x∈H elemre {x}∈Σ (feltéve, hogy H legalább egy elemű);
    • bármely két különböző x, y∈H elemre {x,y}∈Σ (feltéve, hogy H legalább két elemű);
    • bármely három különböző x, y, z∈H elemre {x,y,z}∈Σ (feltéve, hogy H legalább három elemű);
    • ...

Ha megengedjük egy tetszőleges K∈Σ halmazon belül különböző típusú (különböző alaphalmazokba tartozó) elemek előfordulását ("keveredését"), akkor azt kell feltennünk, hogy

  • bármilyen K∈Σ halmaz,
  • bármilyen H∈Σ alaphalmaz,
  • és ennek bármilyen x∈H, x∉K eleme esetén
a K'=K∪{x} halmaz szintén eleme a Σ halmazrendszernek, azaz K'∈Σ teljesül (ez megfelel annak, hogy a Σ halmazrendszerbeli alaphalmazok uniójának hatványhalmaza szintén része a Σ halmazrendszernek, azaz 2H1∪H2∪...Σ teljesül).

A ℋ halmazrendszeren értelmezett  ~  reláció ekvivalenciareláció. Tetszőleges H1, H2, H3Σ halmazokra teljesülnek ugyanis az alábbi tulajdonságok:

A ℋ halmazrendszeren értelmezett  ~  ekvivalenciareláció létrehozza a ℋ halmazrendszer egy osztályozását, ahol az egyes ekvivalenciaosztályokba egyenlő számosságú halmazok tartoznak. Az egyes ekvivalenciaosztályokba tartozó halmazok számosságát kardinális számnak nevezzük (vö. Borsodi-Göndöcs 1970: 73).

Összefoglalva: egy tetszőleges ℋ halmazrendszer esetén az egyenlő számosság alapján képzett ekvivalenciaosztályokba azok a számosságilag ekvivalens halmazok tartoznak, amelyek között bijektív leképezés valósítható meg (vagyis "ugyanannyi elemük van"). A számosságilag ekvivalens halmazok kardinális száma megegyezik.

Ha egy ekvivalenciaosztályból kiválasztunk egy tetszőleges halmazt, azt az ekvivalenciaosztály osztályreprezentánsának nevezzük. A különböző ekvivalenciaosztályokból választott osztályreprezentánsok kardinális száma különböző.

A Σ halmazrendszer elemei véges halmazok. Az ezekhez rendelt kardinális számok leképezik a Σ halmazrendszert a természetes számok ℕ halmazába. Ez lehetőséget ad a természetes szám fogalmának értelmezésére.

Az 'A' halmaz kisebb számosságú, mint a 'B' halmaz (azaz |A|<|B|), ha

Egy tetszőleges A halmaz mindig kisebb számosságú, mint a hatványhalmaza (azaz |A|<|2A| teljesül). (Emiatt elvileg minden számosságnál van nagyobb számosság.)

Az 'A' halmaz nagyobb számosságú, mint a 'B' halmaz (azaz |A|>|B|), ha a 'B' halmaz kisebb számosságú, mint az 'A' halmaz (azaz |B|<|A|).

Jelöljön ℋ ismét egy tetszőlegesen választott halmazokból álló halmazrendszert. A ℋ halmazrendszeren értelmezett "kisebb számosságú" (<) reláció irreflexív rendezési reláció. Tetszőleges A, B, C∈ℋ halmazokra teljesülnek ugyanis az alábbi tulajdonságok:

A ℋ halmazrendszer ekvivalenciaosztályai között értelmezett "kisebb számosságú" (<) reláció teljes irreflexív rendezési reláció, ugyanis tetszőleges A, B∈ℋ halmazokra mint osztályreprezentánsokra az |A|<|B|, |B|<|A| és |A|=|B| relációk közül (pontosan) az egyik mindig teljesül (azaz a reláció trichotóm).

A ℋ halmazrendszeren értelmezett "kisebb számosságú" (<) reláció alapján a nem egyenlő számosságú ℋ-beli halmazok számosság szerint sorba rendezhetőek.

A Σ halmazrendszer elemei az "azonos számosságú" reláció alapján számosságilag ekvivalens halmazokból álló ekvivalencia­osztályokba sorolhatóak.

Válasszunk ki minden ekvivalenciaosztályból pontosan egy osztályreprezentánst. Mivel az osztályreprezentánsok különböző ekvivalencia­osztályokba tartoznak, számosságuk különböző lesz.

Rendezzük el az osztályreprezentánsokat a "kisebb számosságú" (<) reláció alapján. Így a következő sorozathoz juthatunk, amelyben a sorozat egyes elemeinek számosságát elnevezhetjük:

osztályreprezentánsok sorozata a számosság (kardinális szám) elnevezése
üres halmaz (∅) "nulla" (0)
{x}⊂Σ (egy elemű halmaz) "egy" (1)
{x,y}⊂Σ (két elemű halmaz) "kettő" (2)
{x,y,z}⊂Σ (három elemű halmaz) "három" (3)
... ...

Az osztályreprezentánsok rendezett sorozatában található halmazok számosságait természetes számoknak nevezzük (Brindza 1996: 62).

Legyen A egy és B két tetszőleges halmaz, amelyeken értelmezettek a
   ρ ⊆ AΧA és a
   σ ⊆ BΧB
teljes rendezési relációk. Ekkor azt a φ(x) : A→B leképezést, amelyre teljesül, hogy

minden olyan x, y∈A elemre, amelyekre ρ(x,y) teljesül,
   σ(φ(x),φ(y))
is teljesül,

hasonlósági leképezésnek nevezzük. (Szemléletesen azt mondhatjuk, hogy a φ(x) leképezés megőrzi a rendezési relációt vagy megtartja a rendezettséget, vö. Borsodi-Göndöcs 1970: 83-84.)

Ha az A és B halmazok között létezik hasonlósági leképezés, a halmazokat hasonló halmazoknak nevezzük, és A≈B módon jelöljük.

Bármely két véges, számosságilag ekvivalens és rendezett halmaz hasonló egymáshoz (Borsodi-Göndöcs 1970: 84).

Legyen 'A' véges és rendezett halmaz, amelyre |A|=n teljesül, ahol n∈ℕ természetes szám. Ekkor az előző tétel értelmében
A≈{1,2,...,n}
teljesül, vagyis létezik olyan φ(x) : A→{1,2,...,n} hasonlósági leképezés, amely megőrzi az 'A' halmaz rendezettségét. A
φ(x)∈{1,2,...,n}
természetes számokat az x∈A halmazelemek sorszámának nevezzük. Vegyük észre, hogy az 'A' véges (és rendezett) halmaz elemeihez rendelt sorszámok közül a legnagyobb sorszám a halmaz számosságával egyezik meg.


5.2. Végtelen halmazok számossága

Egy halmazt végtelen számosságúnak (vagy egyszerűen végtelennek) nevezünk, ha van olyan valódi részhalmaza, amellyel számosságilag ekvivalens. Ennek megfelelően egy halmazt végesnek nevezünk, ha nem végtelen. (Egy véges halmaz elemszáma nagyobb, mint bármelyik valós részhalmazának az elemszáma. Ha pedig két véges halmaz elemszáma különböző, akkor nem lehet köztük bijektív leképezést megvalósítani, vagyis nem lehetnek számosságilag ekvivalensek.)

Például a természetes számok ℕ halmaza végtelen, mert

Egy halmazt megszámlálhatóan végtelennek nevezünk, ha a természetes számok ℕ halmazával számosságilag ekvivalens. Egy halmazt megszámlálhatónak nevezünk, ha vagy véges, vagy megszámlálhatóan végtelen.

Példák megszámlálhatóan végtelen halmazokra:

Példák nem megszámlálhatóan végtelen halmazokra:

Megszámlálhatóan végtelen számú megszámlálhatóan végtelen halmaz uniója szintén megszámlálhatóan végtelen halmaz. Legyenek a halmazok a következők:

Rendezzük el a fenti halmazok
   A={aij∈Aij | i,j∈ℕ+}
uniójának elemeit a következőképpen:

a11 a12 a13 a14 ...
a21 a22 a23 a24 ...
a31 a32 a33 a34 ...
...

Tekintsük a fenti módon elrendezett számokat egy sn : ℕ+→ℝ számsorozat elemeinek, azaz legyen

Mivel az sn számsorozat egy részsorozata például az A1 halmaz elemeiből áll, amely megszámlálhatóan végtelen, az sn számsorozat értékkészlete is megszámlálhatóan végtelen halmaz. Mivel az A halmaz megegyezik az sn számsorozat értékkészletével, ezért az A halmaz is megszámlálhatóan végtelen.


5.3. A természetes számfogalom kialakítása

Ahhoz, hogy a számfogalom minél szélesebb körű absztrakció eredménye legyen, át kell gondolnunk, hogy melyek azok a mindennapi szituációk, amelyekben számokkal találkozunk. Ennek megfelelően a természetes számot darabként, sorszámként és mérőszámként egyaránt értelmezzük. (Herendiné Kónya 2013: 12)

A természetes számokat értelmezhetjük véges halmazok számosságaként. Két halmaz számosságát (elemszámát, "darabszámát") kölcsönösen egyértelmű leképezésekkel hasonlíthatjuk össze.

Egy halmaz számosságát közvetlenül, számlálással is meghatározhatjuk:

Ebben az értelemben a számlálás olyan eljárás, amellyel véges halmazok számosságát, vagyis az egyes halmazokhoz rendelhető kardinális számot határozhatjuk meg.

Tekintsünk át néhány feladattípust, amelyek elvezethetnek a természetes számok fogalmának kialakításához:

A természetes számok megismerését nagyon részletesen, körültekintően kell a tanítás során megvalósítanunk. Nullától tízig a számok tanítását egyesével, hasonló algoritmus szerint végezzük. (Herendiné Kónya 2013: 14)

6.1. Kijelentések, állítások

Kijelentésen vagy állításon olyan kijelentő mondatot értünk, amely valamely személyről, tárgyról, dologról stb. megállapít valamit. Egy kijelentés logikai értéke (vagy igazságértéke) igaz (1) vagy hamis (0) lehet. (vö. Kopasz 1996: 11)

Egy kijelentésről mindig egyértelműen eldönthető, hogy az igazságértéke igaz vagy hamis.

Egy kijelentés egy predikátumból és egy vagy több individuumnévből áll.

Ha egy kijelentést egy betűvel helyettesítünk, kijelentésváltozót kapunk. A fentiek értelmében a kijelentésváltozók logikai értéke 1 vagy 0 lehet. Például bevezethetjük a 'p' kijelentésváltozót a következőképpen: p ⇋ "Paks a Duna mellett fekszik." Mivel Paks tényleg a Duna mellett fekszik, |p|=1 teljesül.

Példák:


6.2. Nyitott mondatok

Ha egy kijelentésben egy vagy több individuumnevet individuumváltozókkal helyettesítünk, nyitott mondathoz jutunk. (A továbbiakban, ha nem okoz félreértést, individuumváltozók helyett egyszerűen változókról fogunk beszélni.)

Egy nyitott mondat esetében minden individuumváltozó egy meghatározott alaphalmazból vehet fel értéket. Az alaphalmaz meghatározza az illető változó típusát.

Általános esetben különböző típusú változók is lehetségesek, amelyek különböző alaphalmazokból vehetnek fel értékeket (például tanulók, tanárok, tárgyak, osztályzatok stb.). Azt a kört, amelyben a logikai vizsgálatok során a különböző kijelentéseket (nyitott mondatokat, predikátumokat, individuumváltozókat stb.) értelmezzük, és amelyben vizsgálható, hogy az egyes individuumok milyen tulajdonságokkal rendelkeznek, tárgyalási univerzumnak nevezzük. (vö. Margitay 2014: 183-184)

Egy nyitott mondat logikai értéke a benne szereplő változók értékétől függ.

A változók helyére különböző értékeket helyettesítve a nyitott mondat értéke különböző lehet (egyszer igaz, másszor hamis). (Vannak azonban olyan nyitott mondatok, amelyek a változók minden lehetséges értékére igaz logikai értéket adnak; például az I osztály minden 'u' és 'v' tanulójára igaz, hogy "Ha az 'u' tanuló szomszédja a 'v' tanulónak, akkor a 'v' tanuló is szomszédja az 'u' tanulónak.")

Példák:


6.3. Formulák és értékelések

Mind a zárt formulák, mind az értékelt formulák egyértelmű logikai értékkel rendelkező állítások.

6.4. Logikai alapelvek

Arisztotelésztől származik két fontos logikai alapelv:

A fenti alapelvekből következik, hogy az állítások egyértelmű logikai értékkel rendelkeznek:
(1) legyen a 'p' állítás igaz; ekkor 'p' tagadása nem lehet igaz, mert ez sértené az ellentmondásmentesség alapelvét;
(2) legyen a 'p' állítás hamis; ekkor 'p' tagadása nem lehet hamis, mert ez sértené a harmadik kizárásának alapelvét.

Példák:


6.5. Logikai műveletek

Az állítások között meghatározott logikai műveleteket értelmezünk, amelyek segítségével összetett állításokat fogalmazhatunk meg.

értékelési alapelv: az összetett állítások logikai értékét a logikai műveletekkel összekapcsolt állítások (komponensek) logikai értékei egyértelműen meghatározzák (ebben az értelemben pl. a "szerintem ekvivalensek" nem logikai művelet)

egy- és kétváltozós logikai műveletekkel foglalkozunk:

a legfontosabb logikai műveletek (vö. Kopasz 1996: 12-15):

Mivel a fenti logikai műveletek egy-, ill. kétváltozós logikai függvények, ezért megadásukra értéktáblázatokat használunk.

negáció, tagadás ("nem A", "NOT A"): ( ⌝A )

negáció
A ( ⌝A )
0 1
1 0

konjunkció ("A és B", "A AND B"): ( A ∧ B )

konjunkció
A B ( A ∧ B )
0 0 0
0 1 0
1 0 0
1 1 1

diszjunkció ("A vagy B", "A OR B"): ( A ∨ B ) (a diszjunkció az ún. megengedő vagy-nak felel meg)

diszjunkció
A B ( A ∨ B )
0 0 0
0 1 1
1 0 1
1 1 1

kizáró vagy ("A XOR B"): ( A ⨁ B )

kizáró vagy
A B ( A ⨁ B )
0 0 0
0 1 1
1 0 1
1 1 0

implikáció ("A-ból következik B"): ( A ⊃ B )

implikáció
A B ( A ⊃ B )
0 0 1
0 1 1
1 0 0
1 1 1

implikáció tagadása ("A de/és nem B", "A AND NOT B"): ( (⌝(A ⊃ B) ~ (A ∧ ⌝B))

implikáció
A B ⌝(A ⊃ B)
0 0 0
0 1 0
1 0 1
1 1 0

ekvivalencia ("A ekvivalens B-vel"): ( A ≡ B )

ekvivalencia
A B ( A ≡ B )
0 0 1
0 1 0
1 0 0
1 1 1

7.1. Kijelentéslogika; logikai azonosságok

A kijelentéslogika esetében nem foglalkozunk a kijelentések "belső szerkezetével" (Szendrei-Tóth 1978: 14). A továbbiakban

Ha két logikai kifejezés logikai értéke a kifejezésekben szereplő kijelentésváltozók minden lehetséges értékére azonos, akkor a logikai kifejezések ekvivalensek. A logikai azonosságok segítségével ekvivalens logikai kifejezéseket adunk meg.

A logikai azonosságok a logikai műveletek legfontosabb tulajdonságait adják meg.

Legyenek A, B, C, ... tetszőleges kijelentésváltozók. A fontosabb logikai azonosságok a következők (vö. Kopasz 1996: 12-17):

  • kettős tagadás: ⌝(⌝A) = A
  • a konjunkció idempotenciája: A∧A = A
  • a konjunkció kommutativitása: A∧B = B∧A
  • a konjunkció asszociativitása: (A∧B)∧C = A∧(B∧C)
  • konjunkció szabványkijelentésekkel:
    • A∧⊤ = A
    • A∧⊥ = 
  • a diszjunkció idempotenciája: A∨A = A
  • a diszjunkció kommutativitása: A∨B = B∨A
  • a diszjunkció asszociativitása: (A∨B)∨C = A∨(B∨C)
  • diszjunkció szabványkijelentésekkel:
    • A∨⊤ = 
    • A∨⊥ = A
  • disztributivitás:
    • A∧(B∨C) = (A∧B)∨(A∧C)
    • A∨(B∧C) = (A∨B)∧(A∨C)
  • abszorpció (elnyelés; elimináció):
    • A∧(A∨B) = A
    • A∨(A∧B) = A
  • de Morgan-féle azonosságok:
    • ⌝(A∧B) = ⌝A∨⌝B
    • ⌝(A∨B) = ⌝A∧⌝B
  • a kizáró vagy kifejezése:
    • A⨁B = (A∨B)∧⌝(A∧B)
    • A⨁B = (A∧⌝B)∨(B∧⌝A)
  • az implikáció kifejezése:
    • A⊃B = ⌝A∨B
    • A⊃B = (A∧B)∨(⌝A∧B)∨(⌝A∧⌝B)
  • az ekvivalencia kifejezése:
    • A≡B = (A⊃B)∧(B⊃A)
    • A≡B = (A∧B)∨(⌝A∧⌝B)

Jegyezzük meg, hogy a fenti logikai azonosságokban használt egyenlőségjel ( = ) valójában az általa összekapcsolt logikai kifejezések ekvivalenciáját fejezi ki. (A logikai azonosságokban ("logikai egyenletekben", Kopasz 1996: 15) szereplő kijelentésváltozók minden lehetséges értéke mellett az egyenlőségjel bal- és jobboldalán szereplő logikai kifejezések azonos logikai értéket adnak. A logikai kifejezések (formulák) ekvivalenciájának jelölésére szokásosabb az A ~ B jelölés.)

A logikai azonosságokat átalakíthatjuk úgy, hogy eredményül érvényes logikai azonosságokat kapunk:


7.2. Logikai következmény, logikai következtetések

Legyenek P1, P2, ..., Pn és Q (logikai) formulák.

A P1, P2, ..., Pn formuláknak a Q formula a következménye, ha minden olyan esetben, amikor a P1, P2, ..., Pn formulák igazak, akkor a Q formula is igaz (vö. Kopasz 1996: 18).

A köznyelvben szokásos elnevezés szerint, ha a P1, P2, ..., Pn formuláknak a Q formula a következménye, akkor a P1, P2, ..., Pn premisszák és a Q konklúzió ok-okozati kapcsolatban állnak.

Következtetésről beszélünk, ha adott premisszák teljesülése mellett megállapítjuk egy adott konklúzió teljesülését (azaz igazoljuk, hogy a konklúzió a premisszák következménye). (Ennek tipikus formája a "ha ... teljesül, akkor ... is teljesül" következtetési forma.)

Azt, hogy a P1, P2, ..., Pn premisszák következménye a Q konklúzió
P1, P2, ..., Pn ⊨ Q
módon jelöljük. Szokásos a

P1, P2, ..., Pn
Q

vagy

P1
P2
...
Pn
Q

jelölés is.

A következtetések helyességének igazolásakor a konklúzió logikai értékét kell megvizsgálnunk minden olyan esetben, amikor a premisszák igazak. Ezt például a következőképpen tehetjük meg:

A következtetések helyességét (vagy érvényességét) azonban nem mindig kell az összes lehetséges eset megvizsgálásával igazolnunk.

Ha a következtetések során meghatározott szabályokat alkalmazunk, akkor biztosan helyes következtetésekre jutunk.

Először határozzuk meg a helyes következtetések általános formáját (formuláját vagy sémáját):

A P1, P2, ..., Pn premisszáknak a Q konklúzió akkor és csak akkor következménye, ha a
P1∧P2∧...∧Pn ⊃ Q
általános formula minden esetben teljesül.

Az ún. következtetési sémák az általános formula konkrét megvalósításai:
    – a premisszák (P1,P2,...) és a konklúzió (Q) helyén csak meghatározott formulák szerepelnek;
    – ezeket a formulákat úgy választjuk meg, hogy a sémák mint összetett formulák minden esetben teljesüljenek.
Például az alapvető modus ponens séma esetében P1 ⇋ A, P2 ⇋ (A⊃B), és Q ⇋ B (ahol A és B tetszőleges kijelentésváltozók); a modus ponens séma a premisszák és a konklúzió ilyen megválasztása esetén az A és B kijelentésváltozók minden lehetséges értékére igaz logikai értéket ad (tehát a séma alkalmazásakor nem szükséges értéktáblázatot készítenünk).

Egyes következtetési sémák két premisszát tartalmaznak, tehát P1, P2 ⊨ Q alakúak (ezek az ún. szillogizmusok).

Egy következtetés akkor és csak akkor érvényes, ha sémája érvényes, azaz, ha érvényes következtetési séma behelyettesítésével keletkezett. (Margitay 2014: 134)

Ezek után próbáljuk meghatározni, hogy egy összetett érvelés (levezetés) milyen általános formát követ.

Ha az A1, A2, ..., Ak premisszáknak következménye a Pi konklúzió (i=1,2,...,n), azaz
A1, A2, ..., Ak ⊨ P1
A1, A2, ..., Ak ⊨ P2
...
A1, A2, ..., Ak ⊨ Pn
teljesül, és a P1, P2, ..., Pn premisszáknak következménye a Q konklúzió, azaz
P1, P2, ..., Pn ⊨ Q
teljesül, akkor
A1, A2, ..., Ak ⊨ Q
is teljesül, vagyis az A1, A2, ..., Ak premisszáknak következménye lesz a Q konklúzió is. (vö. Szendrei-Tóth 1978: 52)

Egy levezetés tehát egy adott tárgyalási univerzumban a következő elemekből áll:
  – kezdeti premisszákból (amelyek az adott tárgyalási univerzumban értelmezett formulák);
  – a következtetési sémák többszöri, a fenti sémának megfelelő alkalmazásából (a sémákban szereplő kijelentésváltozókat az adott tárgyalási univerzumban értelmezett formulákkal helyettesítve);
  – a végső konklúzióból (amely szintén az adott tárgyalási univerzumban értelmezett formula).

A következtetési sémák, ill. levezetések helyes használata az alábbi következményeket eredményezi:

Tekintsük az alábbi példát (vö. Borsodi 1972: 309). Döntsük el (osztás nélkül!), hogy 1971 osztható-e 3-mal?

Értelmezzük az alábbi formulákat a természetes számok halmaza (ℕ) mint tárgyalási univerzum felett:

  • P1(x) ⇋ "az x∈ℕ természetes szám számjegyeinek összege osztható 3-mal"
  • Q(x) ⇋ "az x∈ℕ természetes szám osztható 3-mal"
  • P2(x) ⇋ P1(x)⊃Q(x)

Megállapíthatjuk a következőket:

  • mivel a P1(x)⊃Q(x) implikáció minden x∈ℕ természetes számra igaz, igaz az x=1971 természetes számra is, vagyis P2(1971) = P1(1971)⊃Q(1971) teljesül.
    Jegyezzük meg, hogy
    • a fenti implikáció bármilyen természetes számra igaz, vagyis olyan x'∈ℕ természetes számra is, amelyre P1(x') nem teljesül (de ekkor általánosan semmilyen következtetést nem tudunk levonni Q(x')-re vonatkozóan);
    • esetünkben azonban nemcsak a P1(x)⊃Q(x) implikáció, hanem speciálisan a P1(x)≡Q(x) ekvivalencia is igaz minden természetes számra (vagyis egy olyan x'∈ℕ természetes számra, amelyre P1(x') nem teljesül, Q(x') sem teljesül);
  • P1(1971) szintén igaz (ugyanis 1+9+7+1=18=6*3 osztható 3-mal).

Mivel a premisszák igazak, a
P1(1971), P1(1971)⊃Q(1971) ⊨ Q(1971)
következtetés (ún. modus ponens szabály) alapján a konklúzió, Q(1971) is igaz. Tehát arra a következtetésre jutottunk, hogy 1971 osztható 3-mal.

Mivel definíció szerint P2(1971) = P1(1971)⊃Q(1971), ezért az alkalmazott következtetési szabály megfelel a következtetési szabályok
P1(1971), P2(1971) ⊨ Q(1971)
szillogizmusok esetére érvényes általános alakjának.

Jegyezzük meg végül, hogy a kapott következtetéshez egy lépésben is eljuthatunk, ha a kategorikus szillogizmus következtetési szabályát alkalmazzuk.


7.3. Következtetési sémák

Ismerjünk meg néhány alapvető, két premisszát tartalmazó következtetési sémát (Kopasz 1996: 19-20):

A következtetési sémákat átalakíthatjuk úgy, hogy eredményül érvényes következtetési sémát kapunk:

Speciálisan a logikai azonosságok önmaguk is kétirányú ("megfordítható") következtetési sémáknak tekinthetők (vö. Borsodi 1972: 313).


8.1. Predikátumlogika; a logikai műveletek és a halmazműveletek kapcsolata

A predikátumlogika esetében formulákkal foglalkozunk, és figyelembe vesszük a kijelentések "belső szerkezetét", amely "a predikátumok felhasználása révén tárul fel" (Szendrei-Tóth 1978: 63).

A logikai műveletek és a halmazműveletek között szoros kapcsolat van. Példaként legyenek P(x) és Q(x) a tanulók I alaphalmazán értelmezett atomi formulák, amelyekben egyváltozós predikátumok fordulnak elő:

P(x) ⇋ "az 'x' tanuló kiváló matematikából";
Q(x) ⇋ "az 'x' tanuló kiváló énekből".

Tekintsük továbbá az I alaphalmaznak azokat a (legbővebb) részhalmazait, amelyekben a P(x), ill. Q(x) formulák minden értékelése igaz logikai értéket ad:

IP = {x∈I | |P(x)|=1} (a matematikából kiváló tanulók halmaza)
IQ = {x∈I | |Q(x)|=1} (az énekből kiváló tanulók halmaza)

Az IP⊆I és IQ⊆I halmazokat a P(x), ill. Q(x) formulák igazsághalmazának nevezzük. Ekkor fennállnak az alábbi összefüggések:


8.2. Kvantifikáció

Legyen A(x) tetszőleges formula a H alaphalmazon. Vezessük be a következő két logikai szimbólumot, ún. kvantort:

Az univerzális kvantor szoros kapcsolatban áll a konjunkcióval. Ha a 'H' alaphalmaz véges, akkor úgy tekinthetjük, mint az alábbi konjunkciók sorozatát:
   ∀x A(x) ≃ A(x1)∧A(x2)∧...∧A(xn)
ahol az x1, x2, ..., xn elemek az x∈H változó összes lehetséges értékét jelentik.

Az egzisztenciális kvantor szoros kapcsolatban áll a diszjunkcióval. Ha a 'H' alaphalmaz véges, akkor úgy tekinthetjük, mint az alábbi diszjunkciók sorozatát:
   ∃x A(x) ≃ A(x1)∨A(x2)∨...∨A(xn)
ahol az x1, x2, ..., xn elemek az x∈H változó összes lehetséges értékét jelentik.

A kvantorok segítségével ún. kategorikus állítások fogalmazhatóak meg. A kategorikus állításokat tartalmazó következtetési szabályok az ún. kategorikus szillogizmusok. Például a modus ponens szabály megfelelője a következő:

A(x0) , ∀x (A(x)⊃B(x)) ⊨ B(x0)
"ha az A(x)⊃B(x) implikáció minden x∈H elem esetén teljesül és egy adott x0∈H elemre A(x0) igaz, akkor erre az x0∈H elemre B(x0) is igaz lesz"


Irodalom- és forrásjegyzék

Balassa Zsófia (szerk.) 1996. Matematika feladatgyűjtemény az általános képzéshez a tanítóképző főiskolák számára. Budapest: Nemzeti Tankönyvk.

Bogya Norbert 2018. Elméleti összefoglaló a Diszkrét matematika I. gyakorlathoz. Szeged: SZTE.
http://eta.bibl.u-szeged.hu/1531/1/diszkret_mat.pdf (2020-09-20)

Bonifert Domokos – Kovácsné Győri Ida 1987. Matematika a tanítók intenzív továbbképzéséhez. Budapest: [k.n.].

Borsodi István 1972. A matematikai logika elemei. In: Borsodi István – Göndöcs László (szerk.) 1972. 255-320.

Borsodi István – Göndöcs László (szerk.) 1970. Matematika a tanítóképző intézetek első évfolyama számára. Budapest: Tankönyvk.

Borsodi István – Göndöcs László (szerk.) 1972. Matematika a tanítóképző intézetek harmadik évfolyama számára. Budapest: Tankönyvk.

Brindza Attila 1996. A természetes számok halmaza. In: Pappné Ádám Györgyi (szerk.) 1996. 55-72.

Dragálin Albert, Buzási Szvetlana 1986. Bevezetés a matematikai logikába. Debrecen: KLTE TTK.

Dringo L. – Kátai I. 1986. Bevezetés a matematikába. Budapest: Tankönyvk.

Farkas Miklós (szerk.) 2001. Matematika. I. kötet. A matematika alapjai. Budapest: Műegyetemi K.

Herendiné Kónya Eszter 2013. A természetes számfogalom alakítása. In: Herendiné Kónya Eszter (szerk.) 2013. 12-27.

Herendiné Kónya Eszter (szerk.) 2013. A matematika tanítása az alsó tagozaton. Budapest: Nemzedékek Tudása Tankönyvk.

Kiss Andrea 1996. Logika, halmazok. In: Balassa Zsófia (szerk.) 1996. 11-25.

Kiss Emil 2007. Bevezetés az algebrába. Budapest: Typotex K.

Kopasz Éva 1996. Logika, halmazok. In: Pappné Ádám Györgyi (szerk.) 1996. 11-29.

Lavrov, I. A. – Maximova, L. L. 1987. Halmazelméleti, matematikai logikai és algoritmuselméleti feladatok. Budapest: Műszaki K.

Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. Matemaikai kisenciklopédia. Budapest: Gondolat K.

Margitay Tihamér 2014. Az érvelés mestersége. Budapest: Typotex K.
https://regi.tankonyvtar.hu/hu/tartalom/tamop425/2011-0001-526_margitay_az_erveles/adatok.html, 2020-08-26.

[MaYoR 2020] oktatas:matematika:halmazok:relacio [MaYoR elektronikus napló].
https://wiki.mayor.hu/doku.php?id=oktatas:matematika:halmazok:relacio, 2020-09-13.

Miklovicz András 2018. Alapozó feladatok. Halmazok és logika 3. osztályosoknak. Budapest: Babilon K.

Monostory Iván (szerk.) 2006. Matematika példatár I-II. A matematika alapjai. Egyváltozós valós függvények. Budapest: Műegyetemi K.

Nagy Gábor 2017. Diszkrét matematika 1. Középszint.
http://compalg.inf.elte.hu/~nagy/dm1_ea_17osz.html (2020-09-20)

Pappné Ádám Györgyi 1996. A számfogalom bővítése. In: Pappné Ádám Györgyi (szerk.) 1996. 73-102.

Pappné Ádám Györgyi (szerk.) 1996. Matematika az általános képzéshez a tanítóképző főiskolák számára. Budapest: Nemzeti Tankönyvk.

Pintér Klára 2013. Matematika módszertan.
http://www.jgypk.hu/mentorhalo/tananyag/Matematika_mdszertan/index.html, 2020-09-18.

Pintér Klára 2013. Matematika I. (tantárgypedagógia) óvóképzős hallgatók számára.
http://www.jgypk.hu/mentorhalo/tananyag/Matematika_I._tantrgypedaggia/index.html, 2020-09-18.

Ruzsa Imre 1968. Halmazelmélet. In: Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. 448-485.

Sashalminé Kelemen Éva 2003. A matematikai logika és a halmazelmélet elemei. Eger: EKF Líceum K.

Szászné Virányi Katalin – Brindza Attila 1996. A természetes számok halmaza. In: Balassa Zsófia (szerk.) 1996. 37-45.

Szendrei János 1975. Algebra és számelmélet. Budapest: Tankönyvk.

Szendrei János – Tóth Balázs 1978. Logika a matematika szakos hallgatók részére. Budapest: Tankönyvk. (Tanárképző főiskolai jegyzet.)

Vajda János 1996. Megfeleltetések, relációk, leképezések (függvények), sorozatok. In: Pappné Ádám Györgyi (szerk.) 1996. 30-54.

Vajda János 1996. A számfogalom bővítése. In: Balassa Zsófia (szerk.) 1996. 46-51.

Veress Róbertné 1996. Megfeleltetések, relációk, leképezések (függvények), sorozatok. In: Balassa Zsófia (szerk.) 1996. 26-36.

Internetes források:

A matematikai logika alapjai. (Informatika 6. évfolyam | Sulinet Tudásbázis)
https://tudasbazis.sulinet.hu/HU/informatika/informatika/informatika-6-evfolyam/logikai-muveletek-es-kapuk/a-matematikai-logika-alapjai (2018-12-08)

Mikulás mese gyűjteménye. Grimm legszebb meséi. Hófehérke.
http://www.mikulasbirodalom.hu/mese/grim/hofeherke.htm, 2020-07-30.

Fa (adatszerkezet). Wikipédia.
https://hu.wikipedia.org/wiki/Fa_(adatszerkezet), 2020-09-20.

Görög ábécé. Wikipédia.
https://hu.wikipedia.org/wiki/G%C3%B6r%C3%B6g_%C3%A1b%C3%A9c%C3%A9, 2020-09-16.

Halmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Halmaz, 2020-07-27.

Hasse-diagram. Wikipédia.
https://hu.wikipedia.org/wiki/Hasse-diagram, 2020-08-20.

Háló (matematika). Wikipédia.
https://hu.wikipedia.org/wiki/H%C3%A1l%C3%B3_(matematika), 2020-09-20.

Hatványhalmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Hatv%C3%A1nyhalmaz, 2020-07-30.

Osztályfelbontás. Wikipédia.
https://hu.wikipedia.org/wiki/Oszt%C3%A1lyfelbont%C3%A1s, 2020-09-26.

Rendezett halmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Rendezett_halmaz, 2020-07-30.

Set Operations and Venn Diagrams.
https://www.math24.net/set-operations-venn-diagrams/, 2020-07-30.

Symmetric difference. Wikipedia.
https://en.wikipedia.org/wiki/Symmetric_difference, 2020-07-30.

Számosság. Wikipédia.
https://hu.wikipedia.org/wiki/Sz%C3%A1moss%C3%A1g, 2020-07-30.

Kardinális szám. Wikipédia.
https://hu.wikipedia.org/wiki/Kardin%C3%A1lis_sz%C3%A1m, 2020-07-30.

Természetes számok. Wikipédia.
https://hu.wikipedia.org/wiki/Term%C3%A9szetes_sz%C3%A1mok, 2020-07-30.

Tree (set theory). Wikipedia.
https://en.wikipedia.org/wiki/Tree_(set_theory), 2020-09-26.

Venn diagram. Wikipedia.
https://en.wikipedia.org/wiki/Venn_diagram, 2020-07-26.

Venn-diagram. Wikipédia.
https://hu.wikipedia.org/wiki/Venn-diagram, 2020-08-13.


Boda István, 2020.