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. Függvények és sorozatok fogalma, megadási módjai, tulajdonságai. (Vajda 1996: 42-54; Borsodi-Göndöcs 1970: 61-71; 235-239)
  5. A számosság fogalma. Műveletek számosságokkal. (Brindza 1996: 55-60; Borsodi-Göndöcs 1970: 72-80)
  6.  további témakörök (6-13) ⇒ 

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 (ritkábban a  :  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) (q.e.d. = ezt akartuk bizonyítani)

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 1968a: 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 ö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"; ⇋ "...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!)

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 is (x∈A).
Ha egy C halmaz minden 'x' elemére teljesül, hogy eleme az 'A' halmaznak is, akkor a C halmaz része az A halmaznak (C⊆A).
Legyen C=A∩B. Láttuk, hogy a 'C' halmaz minden 'x' elemére (x∈C) teljesül, hogy 'x' eleme az 'A' halmaznak is (x∈A).
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 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∪Bx∈A ∨ x∈B
     x∈A ∧ A⊆B ⇒ x∈B
     x∈Bx∈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 nevezzük.)

(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∪Cx∈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
[tehát x∈A ∨ x∈Cx∈B ∨ x∈D teljesül!]
x∈B ∨ x∈D x∈B∪D
tehát A∪C⊆B∪D teljesül (q.e.d.)

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

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

(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) (q. e. d.)

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

(1) Bizonyítsuk be az (A∩B) = AB azonosságot.
A bizonyítás lépései formálisan leírva:
  • x∈(A∩B)
    • x∉(A∩B)
      • Ha az 'A' és 'B' halmazok elemei meghatározott tulajdonságok alapján választhatók ki, akkor A∩B azokat az elemeket jelenti, amelyek nem rendelkeznek egyszerre mind a két (ti. 'A' és 'B') tulajdonsággal. Ez ekvivalens azzal, hogy ezek az elemek vagy az egyik tulajdonsággal (A), vagy a másikkal (B) nem rendelkeznek.
    • x∉A ∨ x∉B
    • x∈A ∨ x∈B
    • x∈AB
  • x∈AB
    • x∈A ∨ x∈B
      • x∉A ⇒ x∉(A∩B)
      • x∉B ⇒ x∉(A∩B)
    • x∉(A∩B) ⇒
    • x∈(A∩B)
  • (A∩B)ABAB(A∩B)
    • (A∩B)=AB (q. e. d.)
(2) Bizonyítsuk be az (A∪B) = AB azonosságot.
A bizonyítás lépései formálisan leírva:
  • x∈(A∪B)
    • x∉(A∪B)
      • Ha az 'A' és 'B' halmazok elemei meghatározott tulajdonságok alapján választhatók ki, akkor A∪B kizárja azokat az elemeket, amelyek akár az 'A', akár a 'B' tulajdonsággal (vagy mindkettővel) rendelkeznek. Ez ekvivalens azzal, hogy ezek az elemek nem rendelkeznek sem az egyik (A), sem a másik (B) tulajdonsággal.
    • x∉A ∧ x∉B
    • x∈A ∧ x∈B
    • x∈AB
  • x∈AB
    • x∈A ∧ x∈B
    • x∉A ∧ x∉B ⇒
    • x∉(A∪B) ⇒
    • x∈(A∪B)
  • (A∪B)ABAB(A∪B)
    • (A∪B)=AB (q. e. d.)

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.

Az 'A' halmaz önmagával képzett Descartes-szorzatát az 'A' halmaz 2-ik hatványának ("négyzetének") nevezzük és A2 ⇋ AΧA módon jelöljük; az 'A' halmaz önmagával vett n-szeres Descartes-szorzatát (n≥2) pedig az 'A' halmaz n-ik hatványának nevezzük és An ⇋ AΧAΧ...ΧA módon jelöljük.


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} {z,k} {p,z,k}
{p}
{z}
{k}
{p,z}
{p,k}
{z,k}
{p,z,k}
↑A↑ {p} {z} {k} {p,z} {p,k} {z,k} {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) (a Descartes-szorzat az unióra nézve disztributív)

(b) AΧ(B∩C) = (AΧB)∩(AΧC) (a Descartes-szorzat a metszetre nézve disztributív)

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

(d) 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, B∈2I, A⊆B}

(h) I={a, b, c} és
     μ = {(A,B) | A∈2I, B∈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.

A halmazelemek közti egyenlőség reláció és pl. a racionális számok között értelmezett egyenlőség reláció nem esik egybe. Tekintsük például a
    P={1, 2/2, 0.5, 1/2, 2/4}⊆ℚ, |R|=5
halmazt. A P halmaznak a racionális számok között értelmezett egyenlőség (=) reláció szerinti osztályozása
    P1={1, 2/2} és P2={0.5, 1/2, 2/4}.


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 vonallal 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! (A szekrénynek a Η0 osztályozás, a sapkák hierarchia­szintjének a Η1 osztályozás, a blúzok hierarchia­szintjének a Η2 osztályozás, végül a szoknyák hierarchia­szintjének a Η3 osztályozás felel meg.)

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; innentől már csak 6 öltözet közül választhat), utána ruhát (pélául sárgát; innentől már csak 2 öltözet közül választhat), majd végül szoknyát (például kéket; ezzel megvan az az öltözet, amely mellett döntött). 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.

Természetesen Juli megválaszthatja az öltözetét úgy is, hogy először egy szoknyát választ, ezután a kiválasztott szoknyához egy blúzt, majd végül egy sapkát mint kiegészítőt. Ez az alábbi döntési fának felel meg:

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

A fastruktúra legfelső csomópontját gyökérelemnek szokás nevezni, a fastruktúra legalsó szintjén levő csomópontokat pedig levélelemeknek.

Figyeljük meg, hogy a levélelemeket leszámítva minden csomópontból egy vagy több él indul ki; és a gyökérelemet leszámítva minden csomópontba pontosan egy él fut be. Ezt úgy is kifejezhetjük, hogy
– a gyökérelemnek nincs szülőeleme, de több leszármazottja lehet,
– a levélelemeknek pontosan egy szülőeleme van, de nincsenek leszármazott elemei,
– minden további csomópontnak pontosan egy szülőeleme és több leszármazottja lehet.

Egy fastruktúrában a gyökérelemből kiindulva és végig lefelé haladva a struktúrában minden levélelemhez pontosan egy út vezet.


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

A Hasse-diagram két fontos tulajdonsága:
  • a diagramban, ha kiindulunk egy csomópontból, az élek irányában haladva sosem jutunk vissza a kiinduló csomópontba (a diagram nem tartalmaz önmagába záruló irányított utat, "kört")
  • ha a diagramot "fejjel lefelé" fordítjuk, egy "duális" Hasse-diagramhoz jutunk, ahol
    • az első diagram az (A; ≼) rendezésnek felel meg
    • a második diagram pedig az (A; ≽) rendezésnek felel meg (ahol a≽b ⇔ b≼a teljesül)

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, amely minden elemnek részhalmaza; az A={a, b, c} halmaz pedig a "legnagyobb" (legfelső) elem, amelynek minden, az ábrán szereplő elem a részhalmaza.

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ő irányított úton keresztül is eljuthatunk a "legnagyobb" elemhez. Visszafelé azonban egyetlen csomópontból sem vezet út, a fenti diagramon csak "felfelé" haladhatunk.

Korábban már ábrázoltuk táblázatos formában egy három elemű alaphalmaz részhalmazai között értelmezett részhalmaz relációt. Ábrázoljuk most az A={a b c} alaphalmaz esetén a (2A; ⊆) részben rendezett halmaz P, Q∈2A elemei közötti részhalmaz relációt (P⊆Q) egy táblázatban a következőképpen:
– a relációban álló különböző vagy azonos (azaz önmagával relációban álló, reflexív) elemeket a megfelelő cellában 1 értékkel jelöljük (fekete háttéren);
– a "közvetlenül" relációban álló (egymást fedő) elemeket a megfelelő cellában szintén 1 értékkel jelöljük, és piros színnel kiemeljük;
– a relációban nem álló elemeket pedig a megfelelő cellában 0 értékkel jelöljük.

P⊆Q ←Q→
↓P↓ {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}
1 1 1 1 1 1 1 1
{a} 0 1 0 0 1 1 0 1
{b} 0 0 1 0 1 0 1 1
{c} 0 0 0 1 0 1 1 1
{a,b} 0 0 0 0 1 0 0 1
{a,c} 0 0 0 0 0 1 0 1
{b,c} 0 0 0 0 0 0 1 1
{a,b,c} 0 0 0 0 0 0 0 1
↑P↑ {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}

Figyeljük meg, hogy a Hasse-diagramon pontosan annyi élt ábrázoltunk, ahány cellában pirossal kiemelt 1 érték szerepel a táblázatban (összesen 12).

Az A={a, b, c} halmaz esetén a (2A; ⊆) részben rendezett halmaz elemeit ábrázoló Hasse-diagram számos információt szolgáltat:

Emeljük ki a következő két megállapítást:

  • ha 'P' és 'Q' az ábrán szereplő két tetszőleges csomópont, akkor az uniójukat jelentő csomópont (C) az a "legkisebb" olyan halmaz, amelyre mind P⊆C, mind Q⊆C teljesül;
  • ha 'P' és 'Q' az ábrán szereplő két tetszőleges csomópont, akkor a metszetüket jelentő csomópont (C) az a "legnagyobb" olyan halmaz, amelyre mind C⊆P, mind C⊆Q teljesül

Például ha a P⊆A és Q⊆A elemek unióját keressük, akkor
    (1) induljunk ki a C0=A={a, b, c} halmazból és vizsgáljuk meg az összes C0-t közvetlenül megelőző csomópontot;
    (2) ha találunk egy olyan C1→C0 elemet, amelyre mind P⊆C1, mind Q⊆C1 teljesül (amely egybeeshet P-vel vagy Q-val), akkor a következő lépésben a C1-t közvetlenül megelőző csomópontokat vizsgáljuk meg (majd ismételjük meg ugyanezt C2→C1-re, C3→C2-re stb.);
    (3) a legutolsó Ci csomópont, amelyre mind Q⊆Ci, mind P⊆Ci teljesül, éppen a keresett unió lesz, azaz Ci=Q∪P teljesül.


Második példaként ábrázoljuk az A={1, 2, 3, 4} számhalmaz esetén az (A; ≤) (teljesen vagy lineárisan) rendezett halmaz elemeit Hasse-diagrammal:

Az A={1,2,3,4} halmaz <= reláció szerinti Hasse-diagramja

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 (parciális vagy teljes) rendezési reláció, és vezessük be most is az egymással relációban levő a, b∈A elemekre az a≼b ⇋ ρ(a,b) jelölést. Ekkor az (A; ≼) (részben vagy teljesen) rendezett halmaz

A legkisebb / legnagyobb és minimális / maximális elemekre teljesülnek az alábbi tételek:

(részben rendezett halmazokra)

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

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

Jegyezzük meg, hogy bizonyos feltételek fennállása mellett a természetes számok között értelmezett oszthatósági relációt ábrázoló Hasse-diagram a korábbi, az A={a, b, c} halmaz részhalmazait ábrázoló Hasse-diagramhoz hasonló információkat szolgáltat.
(1) A részhalmazok közötti unió műveletének a diagramon ábrázolt természetes számok között értelmezett legkisebb közös többszörös (lkkt) művelet felel meg (például [2,3]=6 stb.).
(2) A részhalmazok közötti metszet műveletének pedig a diagramon ábrázolt természetes számok között értelmezett legnagyobb közös osztó (lnko) művelet felel meg (például (4,6)=2 stb.).
Mindennek az a feltétele, hogy az (A; |) részben rendezett halmaz mind az lkkt, mind az lnko műveletekre zárt legyen (a fenti diagramon ábrázolt 'A' halmazra ez nyilván nem teljesül, pl. [3,5]=15 nem eleme A-nak).


Legyen A={1, 2, 3, 5, 6, 10, 15, 30} és ábrázoljuk az (A; |) részben rendezett halmazt Hasse-diagram segítségével:

Az A={1, 2, 3, 5, 6, 10, 15, 30} halmaz oszthatóság szerinti Hasse-diagramja

Figyeljük meg, hogy az (A; |) halmaz zárt az lkkt és az lnko műveletekre, azaz bármely két a, b∈A⊆ℕ természetes szám esetén (a,b)∈A és [a,b]∈A teljesül.

Azokat a korábban bevezetett (A; ≼) részben rendezett halmazokat, amelyek zártak az elemek között értelmezett (és meghatározott tulajdonságokkal rendelkező) metszet (vagy lnko stb.), és unió (vagy lkkt stb.) műveletekre, hálóknak nevezzük, és (A; ⌢, ⌣) módon jelöljük (vö. Birkhoff-Bartee 1974: 218; Szendrei 1975: 416).

Egy adott alaphalmaz esetében a metszet és unió művelet legfontosabb tulajdonságait korábban már megismertük. Ezek közül egy tetszőleges (A; ⌢, ⌣) háló esetében az alábbi tulajdonságok megléte szükséges (ahol X, Y és Z a háló tetszőleges elemei, azaz X, Y, Z∈A):

Jegyezzük meg, hogy halmazok esetén A=2I az I alaphalmaz hatványhalmazát, ill. ennek egy részhalmazát jelenti, amely zárt a metszet és unió műveletekre.

Abban az esetben, ha az 'A' halmaz véges (|A|=n, n∈ℕ+), akkor az (A; ⌢, ⌣) hálónak mindig van legkisebb eleme (záruseleme vagy nulleleme, o∈A), ill. legnagyobb eleme (egységeleme, i∈A), amelyekre teljesülnek az alábbi azonosságok (vö. Jaglom 1982: 65):
o=a1⌢a2⌢...⌢an (ai∈A, 1<=i<=n)
i=a1⌣a2⌣...⌣an (ai∈A, 1<=i<=n)
Az általunk eddig bevezetett hálók esetében
– (A; ⊆) mellett 'o' az üreshalmazt (∅), 'i' pedig magát az 'A' halmazt jelenti (pl. A=2I, ahol egy I alaphalmaz);
– (A; |) mellett pedig 'o' az 1 természetes számot, 'i' pedig 'A' összes elemének legkisebb közös többszörösét jelenti (ami ebben az esetben az 'A' természetes számokból álló és az lnko és lkkt műveletekre zárt számhalmaz abszolút értékben legnagyobb eleme).

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}

az oszthatóságot korábban úgy határoztuk meg, hogy a természetes számok körében
    x|y ⇋ "van olyan q∈ℕ természetes szám, amelyre y=q*x teljesül"
Ennek megfelelően a feladatban megadott reláció tulajdonságai:
(1) reflexivitás: ha x∈ℕ tetszőleges természetes szám, akkor
x=1*x ⇒ x|x tehát (x,x) teljesül, vagyis a reláció reflexív;
(2.1) szimmetria: mivel pl. 3∣6 és 6∤3, vagyis a reláció nem szimmetrikus (egy ellenpélda elég!);
(2.2) aszimmetria: mivel a reláció reflexív, ezért nem lehet aszimmetrikus;
(2.3) antiszimmetria: legyenek x, y∈ℕ természetes számok és x≠y; feltéve, hogy
x|y ⇋ ∃q∈ℕ (y=q*x), három eset lehetséges ("esetszétválasztás"):
    (a) ha x=0 ∧ y=q*x ⇒ y=0 ⇒ x=y, ami x≠y miatt ellentmondás, vagyis ez az eset nem állhat fenn;
    (b) ha x>0 ∧ y=0 ⇒ y∤x (mivel a 0 egyedül önmagának az osztója);
    (c) ha x>0 ∧ y>0 ∧ y=q*x ⇒ q≥1, vagyis pozitív természetes számok esetén x|y ⇒ x≤y teljesül; ha feltesszük, hogy y|x, akkor x|y ∧ y|x ⇒ x≤y ∧ y≤x ⇒ x=y következik, amiből x≠y miatt ellentmondásra jutunk; ezért a feltétel nem lehet igaz, vagyis y∤x;
mivel az összes lehetséges esetben y∤x adódott, ezért x|y ∧ x≠y ⇒ y∤x teljesül, vagyis a reláció antiszimmetrikus;
(3) tranzitivitás: ha x, y, z∈ℕ olyan természetes számok, amelyekre x|y és y|z teljesül, akkor léteznek olyan p, q∈ℕ természetes számok, amelyekre y=p*x és z=q*y teljesül. Emiatt z=q*y=q*(p*x)=(q*p)*x teljesül, vagyis létezik olyan r=q*p természetes szám, amelyre z=r*x teljesül. Ez viszont azt jelenti, hogy x|z teljesül, vagyis a reláció tranzitív;
(4) trichotómia: mivel pl. 3∤7 és 7∤3, valamint nyilvánvalóan 3≠7, ezért a reláció nem trichotóm (egy ellenpélda itt is elég!).

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

(a3) {(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?

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

Vizsgáljuk meg, hogy Η elemei osztályoknak tekinthetőek-e.
(1) Η elemeinek uniója az A=P∪Q halmaz:
PQ ∪ P∩Q ∪ QP = (P∩Q) ∪ (P∩Q) ∪ (Q∩P) = [(P∩Q) ∪ (P∩Q)] ∪ (Q∩P) = [P ∩ (Q ∪ Q)] ∪ (Q∩P) = [P ∩ I] ∪ (Q∩P) = P ∪ (Q∩P) = (P ∪ Q) ∩ (P ∪ P) = (P ∪ Q) ∩ I = (P ∪ Q) (megjegyzés: a pirossal aláhúzott átalakítás P kiemelése, ami a disztributív azonosság "megfordítása");
(2) Η elemei páronként diszjunktak:
(2.1) (PQ) ∩ (P∩Q) = (P∩Q) ∩ (P∩Q) = (P∩P) ∩ (Q∩Q) = P ∩ ∅ = ∅;
(2.2) (QP) ∩ (P∩Q) = (Q∩P) ∩ (P∩Q) = (Q∩Q) ∩ (P∩P) = Q ∩ ∅ = ∅;
(2.3) (QP) ∩ (PQ) = (Q∩P) ∩ (P∩Q) = (Q∩Q) ∩ (P∩P) = ∅ ∩ ∅ = ∅;
(3) Η elemei nem üreshalmazok:
(3.1) PQ = P∩Q ≠ ∅ ⇒ ∃x (x∈P ∧ x∉Q);
(3.2) Q∩P ≠ ∅ ⇒ ∃x (x∈P ∧ x∈Q);
(3.3) QP = Q∩P ≠ ∅ ⇒ ∃x (x∉P ∧ x∈Q);
Mivel a (3.1), (3.2) és (3.3) feltételek mindegyikének teljesülnie kell ahhoz, hogy a Η halmazrendszer osztályozás legyen, ezért a 'P' és 'Q' halmazoknak legalább két-két elemük kell, hogy legyen, amelyek közül
– egy elem közös elem (vagyis mindkét halmaznak eleme),
– egy-egy elem pedig csak a 'P', ill. a 'Q' halmaznak eleme (a másik halmaznak nem).

(a2) A={a logikai készlet elemei}, P⊂A és Q⊂A tetszőleges (nem üres) halmazok
Η = {PQ, P∩Q, QP, PQ}

Általánosan igaz, hogy egy adott 'I' alaphalmaz és ennek két tetszőleges részhalmaza (A⊆I, B⊆I) esetén
I = A∖B ∪ B∖A ∪ A∩B ∪ AB = A∩B ∪ A∩B ∪ B∩AAB
teljesül, ahol az unióképzésben szereplő tagok páronként diszjunktak. (A formula könnyebb megjegyezhetősége érdekében az unióképzés egyes tagjait nem tettük zárójelbe, vagyis feltételezzük, a formula kiértékelésekor először minden esetben a metszetképzést hajtjuk végre.) Az 'I' alaphalmaz felbontását Venn-diagramon szemléltethetjük: az 'I' alaphalmaz felbontása Venn-diagramon

(b) A=ℤ
Η = {{páros egész számok}, {páratlan egész számok}} (megjegyzés: a nullát páros számnak tekintjük, mert osztható 2-vel)

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

Ábrázolja Hasse-diagramon az alábbi részben rendezett halmazokat és határozza meg a legkisebb / legnagyobb, ill. minimális / maximális elemeket, ha léteznek!

(a) ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; |) (vö. Dringó-Kátai 1986: 29; vö. az (1) (a1) feladattal)

(b) ({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; |) (vö. Dringó-Kátai 1986: 29; vö. az (1) (a2) feladattal)

(c) ({2, 3, 4, 5, 6, 7, 8, 9, 10}; |) (vö. Dringó-Kátai 1986: 29; vö. az (1) (a3) feladattal)

(d) ({1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72}; |)


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

Jegyezzük meg, hogy az f(x) függvény létrehozza az értelmezési tartományának (azaz a Dom(f)=I halmaznak) egy osztályozását. Legyen Ik={x∈I | f(x)=k} (k∈B) azoknak a tanulóknak a halmaza, akiknek a neve 'k' betűvel kezdődik (például IA={"Anett"}, IB=∅, IK={"Kata", "Klára"} stb.).
Ekkor Ik∩Ij=∅ (j, k∈B, j≠k) és IA∪IB∪...∪IZ=I teljesülése miatt
    {Ik | k∈B, Ik≠∅}
az 'I' halmaz egy osztályozása.


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

Adott y=f(x) valós függvény esetében rendszerint a következő kérdésre keressük a választ: mi az az y∈ℝ szám, amelyet az f(x) függvény az x∈ℝ érték mellett felvesz?
Az y=f(x) valós függvény x=f−1(y) inverz függvénye esetében pedig az alábbi kérdésre keressük a választ: melyik az az x∈ℝ szám, amelyre az f(x) függvény éppen az y∈ℝ értéket veszi fel? (Vegyük észre, hogy az inverz függvény meghatározása formálisan az f(x)=y egyenlet megoldását jelenti x-re.)

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, összetételének, kompozíciójának) nevezzük, és h(x)=(g∘f)(x), vagy egyszerűbben h(x)=g(f(x)) módon jelöljük.

Például tekintsük az alábbi függvényeket:

Ekkor a h(x)=g(f(x)) összetett függvényre
    h(x)=g(f(x))=(3*x+4)2
teljesül.
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} {0} 1/x {0} {0}
x2 [0,+∞) [0,+∞) x [0,+∞) [0,+∞)
(−∞,0] [0,+∞) −√x [0,+∞) (−∞,0]
ex (0,+∞) ln(x) (0,+∞)

Például f(x)=2*x esetében az y=2*x alakból x=y/2 adódik. Az y=f(x) függvény inverz függvénye tehát
    x=f−1(y)=y/2.
Ebből az x↔f−1(x) és y↔x helyettesítéseket elvégezve
    f−1(x)=x/2
adódik. Könnyen ellenőrizhető, hogy
   (f−1∘f)(x) = f−1(f(x)) = f−1(2*x) = (2*x)/2 = x
és
   (f∘f−1)(x) = f(f−1(x)) = f(x/2) = 2*(x/2) = x
teljesül.

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.


Néhány fontosabb valós függvény

Az f(x)=∣x∣ : ℝ → ℝ abszolút érték függvény görbéje:


Az f(x)=m*x+c (m,c ∈ ℝ) : ℝ → ℝ lineáris függvény görbéi, ha
f(x) = 2*x−40 és g(x) = −3*x+60:


Az f(x)=x2 : ℝ → ℝ hatványfüggvény görbéje:


Az f(x)=√x : [0,+∞) → ℝ és
g(x)=−√x : [0,+∞) → ℝ négyzetgyökfüggvények görbéi:


Az f(x)=x3 : ℝ → ℝ hatványfüggvény görbéje:


Az f(x)=4*x3−16*x2+2*x+20: ℝ → ℝ harmadfokú polinom görbéje:


Az f(x)=1/x : ℝ∖{0} → ℝ∖{0} függvény görbéje:


Az f(x)=ex : ℝ → ℝ és
g(x)=e−x : ℝ → ℝ exponenciális függvények görbéi (ahol e≈2,718281828 az ún. Euler-féle szám):


Az f(x)=ln(x)=loge(x) : (0,+∞) → ℝ természetes alapú logaritmusfüggvény görbéje (ahol e≈2,718281828 az ún. Euler-féle szám):


Az f(x)=sin(x) : ℝ → [−1,1] szinuszfüggvény görbéje:


Az f(x)=|sin(x)| : ℝ → [0,1] abszolút szinuszfüggvény görbéje:


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 történik, amely a sorozat általános elemének (sn) kiszámítási módját adja meg.

Például az sn=1/n sorozat első négy eleme s1=1, s2=1/2, s3=1/3, s4=1/4. A sorozat első 30 elemének ábrázolása grafikonon:

Az 1/n sorozat első 30 eleme

Egy másik példa: legyen

sn = {  1/n  ha 'n' páratlan
n  ha 'n' páros

Ekkor az sn sorozat első négy eleme s1=1, s2=2, s3=1/3, s4=4.

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. Rekurzív definíció esetén mindig meg kell adnunk a sorozat első elemét (s1), ill. egyes esetekben a sorozat néhány további elemét (s2, ...) is. 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.

Például az
s1 = 1
s2 = 1
sn = sn−1 + sn−2
rekurzív képlettel megadott ún. Fibonacci-sorozat első néhány eleme s1=1, s2=1, s3=2, s4=3, s5=5, s6=8, ... (jegyezzük meg, hogy a Fibonacci-sorozat esetében szokás a sorozat nulladik eleméről is beszélni, amely s0=0).

Mivel a számsorozatok speciális függvények, esetükben is értelmezhetjük az alábbi tulajdonságokat:

Például az sn=1−1/n sorozat korlátos (Ka=0, Kf=1, K=1) és szigorúan monoton növekvő, mivel
sn=1−1/n=n/n−1/n=(n−1)/n=[(n−1)*(n+1)]/[n*(n+1)]=[n*n−1]/[n*(n+1)] és
sn+1=1−1/(n+1)=(n+1)/(n+1)−1/(n+1)=n/(n+1)=[n*n]/[n*(n+1)] miatt
sn<sn+1
teljesül minden n∈ℕ+ pozitív természetes számra. A sorozat első 30 elemének ábrázolása grafikonon:

Az 1-1/n sorozat első 30 eleme

Érdemes megfigyelnünk, hogy a sorozat szomszédos elemeinek különbsége
    δ=sn+1−sn=1/[n*(n+1)]>0
'n' növelésével egyre kisebb lesz, sőt "minden határon túl csökken". Bármilyen kis 0<ε≪1 valós számot választunk, ha 'n' értékét elegendően nagyra választjuk, akkor δ értéke ε értékénél kisebb lesz.

Értelmezzük végül a sorozatokra a periodicitás fogalmát.

Gyakorló feladatok (vö. Veressné 1996: 31-35):

Döntse el, hogy az alábbi relációk (megfeleltetések) közül melyek hozzárendelések és/vagy melyek függvények (leképezések)! Határozza meg a függvények fontosabb tulajdonságait!

(a) A={3, 9, 49, 55} és
     α = {(x,y) | x∈A, y∈ℕ, "az 'y' az 'x' valódi osztója"}

(b) A={3, 5, 7}, B={12, 15, 49, 50, 71} és
     β = {(x,y) | x∈A, y∈ℕ, "az 'y' az 'x' többszöröse"}

(c) A={-1, 0, 1, 2}, B={-1, 0, 3} és
     γ = {(x,y) | x∈A, y∈ℕ, y=x2−1}

(d) A={8, 12, 14, 15} és
     δ = {(x,y) | x∈A, y∈ℕ, "az 'y' az 'x' osztóinak a száma"}

(e) A={325, 472, 538, 941}, B={2, 3, 4, 7} és
     ε = {(x,y) | x∈A, "az 'y' az 'x' tízesek helyén álló számjegye"}

(f) A={a logikai készlet elemei}, B={piros, sárga, zöld, kék} és
     η = {(x,y) | x∈A, "az 'y' az 'x' színe"}

Vizsgálja meg az alábbi valós függvényeket! Ábrázolja őket és határozza meg a főbb tulajdonságaikat!

(a) f : ℝ→ℝ, f(x)=x+1

(b) f : [−1; 3]→ℝ, f(x)=x2−2*x

(c) f : [0; 10]→ℝ, f(x)=√x

(d) f : [0; 1]→ℝ, f(x)=√1−x2

(e) f : [0; 2]→ℝ,

f(x) = {  x+1  ha 0≤x≤1
 4−2*x  ha 1≤x≤2

(f) f : ℝ∖{0}→ℝ, f(x)=1/x

(g) f : ℝ∖{0}→ℝ, f(x)=1/x2

(h) f : ℝ∖{0}→ℝ, f(x)=2+3/x

(i) f : ℝ→ℝ, f(x)=|3*x−1|

(j) f : ℝ∖{0}→ℝ, f(x)=1/|x|

(k) f : ℝ→ℝ, f(x)=2x

(l) f : (0; ∞)→ℝ, f(x)=|lg10(x)|

(m) f : ℝ→ℝ, f(x)=sin(x)

(n) f : ℝ→ℝ, f(x)=sin|x|

Adja meg az alábbi sorozatok elemeinek (egy lehetséges) kiszámítási módját, és írja fel a sorozatok első 10 tagját!

(a1) 2, 5, 8, 11, ... (állandó különbségű vagy számtani sorozat)

(a2) 3, 6, 9, 12, ...

(b1) 1, 2, 4, 7, 11, ... (egyenletesen változó különbségű vagy többletes sorozat)

(b2) 1, 4, 9, 16, 25, ...

(b3) 3, 6, 12, 24, ... (arányosan változó különbségű sorozat)

(c) 1, 2, 4, 5, 7, 8, ... (periodikusan változó különbségű sorozat)

(d1) 1, 2, 4, 8, 16, ... (állandó hányadosú vagy mértani sorozat)

(d2) 1, 1/3, 1/9, 1/27, ...

(d3) 1, −3, 9, −27, ... (váltakozó előjelű vagy alternáló sorozat)

(e) 1, 2, 6, 24, 120, ... (egyenletesen változó hányadosú sorozat)

(f1) 1, 2, 4, 1, 2, 4, ... (periodikus sorozat)

(f2) 1, 2, 4, 4, 2, 1, 1, 2, 4, ... (periodikus sorozat)

(g) 1, 1, 2, 3, 5, 8, ... (Fibonacci-sorozat)

(h1) 0, 1/2, 2/3, 3/4, ... (összetett sorozat)

(h2) 1, 10, 2, -8, 3, -6, ...

Számítsa ki és írja fel egy táblázatban az alábbi sorozatok első 10 tagját! Vizsgálja meg a megadott sorozatok tulajdonságait!

(a1) sn=n/(n+3)

(a2) sn=−(n+1)/n

(b) sn=2−1/n

(c) sn=sin(n*π/2)

(d) s1=0, s2=1, sn+1=(sn−1+sn)/2 (n>1)

(e) s1=5, s2=−1, sn+1=(sn−1+sn)/2 (n>1)


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.

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

Ha két véges halmaz között létezik bijektív leképezés, akkor a halmazok elemszáma megegyezik. Másrészt ha két véges halmaz elemszáma megegyezik, akkor mindig létesíthetünk köztük bijektív leképezést (például úgy, hogy a halmazok elemeit sorszámmal látjuk el, és az azonos sorszámú elemeket rendeljük egymáshoz). Emiatt véges halmazok esetében a számosságot a halmaz elemeinek a számával adjuk meg.

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. (Megjegyzés: ha két azonos név szerepel, ezeket pl. római számokkal megkülönböztetjük.)

Vegyük észre, hogy az I halmaz elemszámát az utolsó elem sorszáma adja.

Ha egy tetszőleges véges H halmaz elemeihez sorszámot rendelünk, akkor bijektív módon leképezzük a H halmazt a természetes számok egy {1,2,...,n}⊂ℕ részhalmazára. Ez lehetőséget ad a természetes szám fogalmának az értelmezésére.

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

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). Véges halmazok esetén egy halmaz kardinális száma megegyezik a halmaz elemeinek a számával.

Ö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 kardinális szám ezeknek a halmazoknak a (közös) számossága, így 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.

Mivel véges halmazok esetén egy halmaz számossága megegyezik a halmaz elemszámával, egy véges halmazokból álló ekvivalenciaosztály bármelyik osztályreprezentánsának az elemszáma megegyezik az ekvivalenciaosztályba tartozó halmazok (közös) elemszámával.

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

A Σ 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 véges 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; másképpen megfogalmazva tetszőlegesen választott H1, H2, ... alaphalmazok unióját is alaphalmaznak tekintjük).

A konstrukció lényege az, hogy a Σ halmazrendszer elég nagy ahhoz, hogy benne minden lehetséges számosságú véges halmaz előforduljon, valamint zárt legyen a halmazok között korábban értelmezett műveletekre.

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 halmazelméleti értelmezésére.

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

Mivel egy halmaz nyilvánvalóan számosságilag ekvivalens önmagával, egy tetszőleges 'A' halmaz számossága sosem lehet kisebb, mint egy részhalmazának a számossága. (Egyenlő viszont lehet, például végtelen halmazok esetében.)

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

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 elemei között értelmezett "kisebb számosságú" (<) reláció parciális irreflexív rendezési reláció, mivel bármely két egymástól különböző, egyenlő számosságú halmaz nem áll relációban egymással (azaz a reláció nem trichotóm).

A ℋ halmazrendszer ekvivalenciaosztályai között értelmezett "kisebb számosságú" (<) reláció azonban 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).

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|). Hasonlóan értelmezhetjük az |A|≥|B| és |A|≤|B| (gyenge) rendezési relációkat is.

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ők.

A Σ halmazrendszer elemei az "egyenlő 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.

A végesség definíciója összhangban áll azzal, hogy egy véges halmaz elemszáma mindig 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. (A sorozatok fogalmával kifejezve azok a halmazok megszámlálhatók, amelyek sorozatba rendezhetők, vö. Borsodi-Göndöcs 1970: 77).

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

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

A véges és megszámlálhatóan végtelen halmazok közötti műveletek egyes esetekben megszámlálhatóan végtelen halmazt eredményeznek:

Az utolsó tétel bizonyításához tekintsük a következő, negszámlálhatóan végtelen számú és megszámlálhatóan végtelen számosságú halmazokat:

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

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


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[I.], sorszámként[II.] és mérőszámként egyaránt értelmezzük. (Herendiné Kónya 2013: 12)

I. A természetes számokat értelmezhetjük véges halmazok számosságaiként.

Ha két halmazra nem teljesül az "ugyanannyi eleme van" reláció, a következő lépés értelemszerűen a "több (kevesebb) eleme van" reláció megállapítása. (Ehhez a nagyobb elemszámú halmaznak egy olyan valódi részhalmazát kell kiválasztanunk, amelynek ugyanannyi eleme van, mint a kisebb elemszámú halmaznak.)

II. 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 az alsó tagozaton elvezethetnek a természetes számok fogalmának kialakításához:

  • halmazok képzése hasonló elemek kiválasztásával
    • közös tulajdonságok alapján (pl. az elemek színe, nagysága, alakja vagy formája, hasonló részletek (szögek, lábak stb.) megléte vagy száma szerint) (pl. Bonifert-Kovácsné Győri 1987: 60)
    • közös típusba vagy fajtába tartozás alapján (pl. almák, kockák, virágcserepek, sálak, sapkák stb.) (pl. Bonifert-Kovácsné Győri 1987: 61, Herendiné Kónya 2013: 13)
  • két halmaz összehasonlítása az elemek száma szerint, az egyes elemek párosításával
    • inhomogén halmazok esetén a kapcsolatban álló elemek összekötésével (pl. pohár - szívószál, váza - virág, papír - ceruza stb.) (pl. Bonifert-Kovácsné Győri 1987: 59)
    • homogén vagy inhomogén, rendezetlen halmazok esetén tetszőlegesen párosítva az elemeket (pl. Bonifert-Kovácsné Győri 1987: 60)
  • több halmaz összehasonlítása az elemek száma szerint
    • azonos elemszámú vagy számosságú halmazok csoportosítása (pl. egy ábrán bekeretezéssel) (pl. Bonifert-Kovácsné Győri 1987: 61)
    • számosságilag ekvivalens halmazokat tartalmazó halmazcsoportokhoz kardinális szám rendelése a halmazokkal megegyező számosságú számképek hozzákapcsolásával (a számképek adott számú pöttyöt, kört, vonalt, háromszöget, négyzetet stb. tartalmazó halmazok; vö. pl. Bonifert-Kovácsné Győri 1987: 60-61)
      • a számképek absztrakt alakzatokat tartalmazó, egy adott halmazzal megegyező számosságú halmazok (egy adott számkép a vele azonos számosságú halmazokból alkotott ekvivalenciaosztály osztályreprezentánsának tekinthető)
    • egy megadott számképhez egy olyan halmaz előállítása, amelynek ugyanannyi eleme van, mint ami a számképben szerepel (pl. Bonifert-Kovácsné Győri 1987: 61)
  • két halmaz összehasonlítása az elemek száma szerint a megfelelő relációjel (<, =, >) beírásával a halmazok között (pl. Bonifert-Kovácsné Győri 1987: 60, Herendiné Kónya 2013: 14)
  • több halmaz összehasonlítása az elemek száma szerint, pl. vonalakkal és nyilakkal összekötve a halmazokat (pl. Herendiné Kónya 2013: 14)
    • az egyenlő (vagy azonos) számosságú halmazokat vonallal kössük össze
    • a → nyíl mutasson a nagyobb számosságú halmaz felé (pl. különböző (egyszeres, kétszeres stb.) vastagságú nyilak használhatóak egy halmaz tőle (eggyel, kettővel stb.) különböző elemszámú halmazokkal való összekötésére)
  • egy adott elemszámú halmazhoz vele azonos elemszámú halmazok konstruálása (pl. tanulókhoz ceruzák, füzetek, szendvicsek stb. rendelése; vö. pl. Herendiné Kónya 2013: 15)
    • a hiányzó elemek berajzolásával (pl. több ceruza kell)
    • a felesleges elemek áthúzásával (pl. kevesebb füzet kell)
  • homogén rendezett halmazok esetén az elemek nagyság szerinti elrendezése, és az elemek párosítása ebben a sorrendben (pl. a hét törpe és a hozzájuk tartozó tárgyak stb.)
  • két halmaz összehasonlítása az elemek tényleges száma szerint
    • a halmazok elemeinek párosítása (pl. vonallal összekötve az elempárokat), majd az egyes halmazok elemszámának megállapítása és a megfelelő számjegy hozzákapcsolása a halmazokhoz (pl. Bonifert-Kovácsné Győri 1987: 63)
    • homogén rendezett halmazok esetén nagyság szerint rendezve az egyes halmazok elemeit, és ebben a sorrendben párosítva az elemeket (pl. futóverseny stb.) (pl. Herendiné Kónya 2013: 19)
  • egy halmaz elemeinek összekötése a természetes számokat tartalmazó {1,2,3,...} halmazzal és az utolsó (legnagyobb) szám bekarikázása (számlálás)
    • homogén rendezett halmaz esetén a halmaz elemeinek nagyság szerinti elrendezése, és az elemek sorszámának beírása (pl. futóverseny, sorbaállítás magasság, terület stb. szerint) (pl. Herendiné Kónya 2013: 19)
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)

(→ következő témakörök)


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.

Birkhoff, Garrett – Bartee, Thomas C. 1974. A modern algebra a számítógép-tudományban. Budapest: Műszaki K.

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.

Csizmadia László 2009. Bevezetés az analízisbe. [előadás vázlat]
http://www.math.u-szeged.hu/~csizmadia/Bevanalea1.pdf, 2020-10-26.

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.

Farkas Miklós – Fritz Józsefné – Kiss Ernőné 2000. Matematika. II. kötet. Egyváltozós valós függvények. (szerk. Farkas Miklós.) Budapest: Műegyetemi K.

Bognár László – Forrai Gábor (szerk.) 2004. Esszéírás és Informális logika. Budapest: Budapest – Miskolc: Bölcsész Konzorcium.
https://www.uni-miskolc.hu/~bolantro/informalis/index.html, 2020-11-07.
http://gepeskonyv.btk.elte.hu/adatok/Altalanos%20bolcseszet/6Forrai/essz%E9%EDr%E1s%20%E9s%20inform%E1lis%20logika/index.html, 2020-11-07.

Fried Ervin 1968. Algebra. In: Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. 5-132.

Fried Katalin – Korándi József – Török Judit 2013. A modern algebra alapjai. Budapest: ELTE Természettudományi Kar.
https://regi.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0073_bevezetes_modern_algebraba/index.html, 2020-10-26.

Gémes Margit – Szentmiklóssy Zoltán 2015. Bevezetés a matematikába. Jegyzet és példatár kémia BsC-s hallgatók számára. Budapest: ELTE TTK Matematikai Intézet.
http://web.cs.elte.hu/~szzoltan/bmk/bmk.html#content, 2020-10-25.

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 1968a. Halmazelmélet. In: Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. 448-485.

Ruzsa Imre 1968b. Matematikai logika. In: Lukács Ernőné, Tarján Rezsőné (szerk.) 1968. Matemaikai kisenciklopédia. Budapest: Gondolat K. 530-564.

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

Tallér József 1996. A logika alapjai. Szeged: Mozaik Oktatási Stúdió.

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.

Wikipédia / Wikipedia szócikkek:

Egész számok. Wikipédia.
https://hu.wikipedia.org/wiki/Eg%C3%A9sz_sz%C3%A1mok, 2020-10-14.

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

Fibonacci-számok. Wikipédia.
https://hu.wikipedia.org/wiki/Fibonacci-sz%C3%A1mok, 2020-10-13.

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.

Cantor-tétel. Wikipédia.
https://hu.wikipedia.org/wiki/Cantor-t%C3%A9tel, 2020-10-20.

Hatvány. Wikipédia.
https://hu.wikipedia.org/wiki/Hatv%C3%A1ny, 2020-10-03.

Logikai függvények. Wikipédia.
https://hu.wikipedia.org/wiki/Logikai_f%C3%BCggv%C3%A9nyek, 2020-11-08.

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

Páros és páratlan számok. Wikipédia.
https://hu.wikipedia.org/wiki/P%C3%A1ros_%C3%A9s_p%C3%A1ratlan_sz%C3%A1mok, 2020-10-22.

A nulla paritása. Wikipédia.
https://hu.wikipedia.org/wiki/A_nulla_parit%C3%A1sa, 2020-10-22.

Giuseppe Peano. Wikipédia.
https://hu.wikipedia.org/wiki/Giuseppe_Peano, 2020-10-02.

Permanenciaelv. Wikipédia.
https://hu.wikipedia.org/wiki/Permanenciaelv, 2020-10-03.

Pitagorasz-tétel. Wikipédia.
https://hu.wikipedia.org/wiki/Pitagorasz-t%C3%A9tel, 2020-10-24.

Polinom. Wikipédia.
https://hu.wikipedia.org/wiki/Polinom, 2020-10-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.

Siklófélék. Wikipédia.
https://hu.wikipedia.org/wiki/Sikl%C3%B3f%C3%A9l%C3%A9k, 2020-10-12.

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.

Teljes indukció. Wikipédia.
https://hu.wikipedia.org/wiki/Teljes_indukci%C3%B3, 2020-10-02.

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.

Valós számok. Wikipédia.
https://hu.wikipedia.org/wiki/Val%C3%B3s_sz%C3%A1mok, 2020-10-25.

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.