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)
    • Gyakorló feladatok
  2. Relációk fogalma, megadási módjai, tulajdonságai. (Vajda 1996: 30-42; Borsodi-Göndöcs 1970: 48-61)
    • Gyakorló feladatok
  3. Az ekvivalenciareláció és a rendezési relációk. (Vajda 1996: 40-41; Borsodi-Göndöcs 1970: 58-60)
    • Gyakorló feladatok
  4. Függvények fogalma, megadási módjai, tulajdonságai. (Vajda 1996: 42-50; Borsodi-Göndöcs 1970: 61-71)
    • Gyakorló feladatok
  5. Sorozatok. A számosság fogalma. A természetes számfogalom kialakítása. (Vajda 1996: 50-54; Brindza 1996: 55-60; Borsodi-Göndöcs 1970: 235-239; 72-80)
    • Gyakorló feladatok
  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 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). Egy adott halmaz esetében mindig feltételezzük, hogy a halmazelemek azonosságát ("egyenlőségét"), ill. különbözőségét tetszőlegesen kiválasztott két elem esetén bármikor el tudjuk dönteni.

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

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

Ha a Venn-diagramon például az 'I' alaphalmaz A⊆I, B⊆I, C⊆I és D⊆I részhalmazainak az elemeit akarjuk ábrázolni, akkor olyan alakzatokat kell használnunk, ahol négy lehetséges szín összes lehetséges kombinációja megjelenik az ábrázolt alakzatok közös, egymást kölcsönösen átfedő részeiként (beleértve azt is, amikor nincs szín, amely az E=I(A∪B∪C∪D) részhalmaz elemeinek felel meg). Tehát ha 'a', 'b', 'c' és 'd' színű alakzatokkal dolgozunk, akkor az
{a}, {b}, {c}, {d}, {a,b}, {a,c}, ..., {c,d}, {a,b,c}, ..., {b,c,d}, {a,b,c,d}
színeknek, ill. színkombinációknak kell megjelennie (egy "üres" téglalapban, amelynek "nincs színe"). Vegyük észre, hogy a fenti felsorolással a színek négy elemű halmazának a hatványhalmazát adtuk meg, amelynek elemszámára 24=16 teljesül.

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 a H 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? például legyen
A = {"azok a törpék, akik szeretik az epret"}
B = {"azok a törpék, akik szeretik a barackot"}
C = {"azok a törpék, akik szeretik a dinnyét"}
A kérdések megválaszolásához természetesen tudnunk kell azt is, hogy mit szeretnek az egyes törpék; pl. "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"

A két halmaz közötti részhalmaz viszony (vagy reláció) bizonyításának során az alábbi következtetések megértése és memorizálása nagyon fontos:

I.
Az 'A' halmaz részhalmaza a 'B' halmaznak.   A⊆B
Az 'A' halmaz minden eleme eleme a 'B' halmaznak is.   (tetszőleges 'x' elemre) x∈A ⇒ x∈B
II.
Az 'A' halmaz minden eleme eleme a 'B' halmaznak is.   (tetszőleges 'x' elemre) x∈A ⇒ x∈B
Az 'A' halmaz részhalmaza a 'B' halmaznak.   A⊆B

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 a hatványhalmaz elemei 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) (bi∈{0,1}, 1<=i<=n)
bináris jelsorozatot az 'A' halmaz egyes részhalmazainak a következőképpen:
egy tetszőleges R⊆A részhalmaznak az 'A' halmaz i-dik eleme pontosan akkor legyen az eleme, ha bi=1 teljesül (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:

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

Az A⊆B ⇔ A=A∩B összefüggés bizonyításának lépései formálisan leírva (∧ ⇋ "és", ∨ ⇋ "vagy"):
  • tegyük fel, hogy A⊆B
    • x∈A ⇒ x∈B
      • x∈A ∧ x∈B ⇒ x∈(A∩B)
      • tehát A⊆(A∩B)
    • x∈(A∩B) ⇒ x∈A ∧ x∈B
      • x∈A ∧ x∈B ⇒ x∈A
      • tehát (A∩B)⊆A
    • A⊆(A∩B) ∧ (A∩B)⊆A ⇒ A=A∩B (antiszimmetria!)
  • tegyük fel, hogy (A∩B)=A
    • x∈A ⇒ x∈(A∩B)
      • x∈(A∩B) ⇒ x∈A ∧ x∈B
      • x∈A ∧ x∈B ⇒ x∈B
      • tehát 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 ismét érvényes azonosságokat kapunk (vö. Ruzsa 1968a: 458-459):

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


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 A, B∈2I részhalmazait és ábrázoljuk a köztük értelmezett "'A' részhalmaza 'B'-nek" (A⊆B) 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 a táblázat tartalma minden három elemű halmaz esetében ugyanaz lesz. 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:

(1) reflexivitás – irreflexivitás – egyik sem

(2) szimmetria – antiszimmetria – aszimmetria – egyik sem

(3) tranzitivitás – nem teljesülő tranzitivitás

(4) trichotómia – nem teljesülő trichotómia

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 "megengedő" trichotómia esetében az összefüggőséget követlejük meg. A trichotómia "megengedő" meghatározása az a=b esetben nem mond semmit sem az elemek közti relációról (azaz mind (a,a)∈ρ, mind (a,a)∉ρ teljesülését megengedjük).

A "szigorú" trichotómia esetében a dichotómiát követeljük meg (amely magában foglalja az összefüggőséget). A "szigorú" trichotómia egyik elfogadott definíciója az, hogy bármely a, b∈I esetén a ρ(a,b), ρ(b,a) és a=b relációk közül pontosan egy teljesül; ebben az esetben, ha a=b, akkor sem ρ(a,b), sem ρ(b,a) nem teljesül, vagyis a reláció irreflexív. Ebben az értelemben például a < reláció trichotóm, de a ≤ reláció nem az.


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

Gyakorló feladatok


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 az 'A' halmaz 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.

Például jegy("Fercsi","matek")=5 és jegy("Kata","matek")=5 esetében ("Fercsi","Kata")∈ψ, azaz ψ("Fercsi","Kata") teljesül.

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 két 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

Vegyü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, amelyekbe az 'i' érdemjegyet kapott tanulók tartoznak bele (1≤i≤5), 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.


A fenti konkrét példából is jól látszik, hogy 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.

Mivel a ρ reláció reflexív, az osztályok nem üresek. Mivel a ρ reláció szimmetrikus, két elem csak egy osztályba tartozhat, és a reláció tranzitivitása miatt ez nemcsak kettő, hanem három (négy, öt, ...) elemre is igaz. Ha tehát két osztálynak lenne közös eleme, akkor a ρ reláció szimmetriája és tranzitivitása miatt az oszályok egybeesnének, ezért a különböző osztályok diszjunktak. Mivel pedig minden elem beletartozik valamelyik osztályba, ezért az osztályok uniója lefedi a teljes 'A' halmazt.

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.

Mivel minden elem önmagával azonos osztályban van, az "egy halmazba tartozás" reflexív reláció. Ha két elem ugyanabban az osztályban van, akkor sorrendtől függetlenül relációban vannak, tehát a reláció szimmetrikus. Ha pedig egy adott elem két másikkal azonos osztályban van, akkor biztos, hogy azok az elemek is ugyanabban az osztályban vannak, tehát a reláció tranzitív is.

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. (Például ha A={a,b,c}, akkor ΗA = {{a},{b},{c}}, azaz minden osztály egy egyelemű halmaz, és az osztályok száma megegyezik 'A' elemeinek számával, azaz |ΗA|=3 teljesül.)

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ás (az osztályok közötti "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ályok közötti "felbontási" 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 (vagyis rendezési reláció, amivel a következőkben fogunk foglalkozni).

Végül figyeljük meg, hogy az ábrán 24−1=15 csomópont található, ami a négy elemből álló (véges) 'A' halmaz összes lehetséges osztályozásainak számát adja meg. Mivel a 'k'-dik szinten lehetséges osztályozás lehetséges ('n' elemből 'k' osztályt választunk ki az elemek sorrendjétől függetlenül), az összefüggés a binomiális tétel alapján könnyen belátható.


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 a természetes számokon (ℕ) értelmezett

Például az 'I' halmaz 2I hatványhalmazán (azaz az 'I' halmaz összes részhalmazának halmazán) é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≼b ⇋ "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 tetszőleges 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ó elemeket a megfelelő cellában 1 értékkel jelöljük;
– a "közvetlenül" relációban álló (egymást fedő) elemeket a megfelelő cellában piros színnel kiemeljük, a "nem közvetlenül" relációban álló elemek esetében pedig fekete háttért alkalmazunk;
– 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:

Összefoglalva, ha egy 'A' halmaz összes részhalmazát a részhalmaz-reláció szerint parciálisan elrendezzük és a rendezést egy Hasse-diagramon ábrázoljuk, akkor

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

Jegyezzük meg, hogy a fenti megállapítások akkor is teljesülnek, ha az 'A' halmaz részhalmazainak egy olyan B⊆2A halmazát rendezzük el a fenti módon, amely zárt az unióképzés és metszetképzés műveleteire (azaz bármely két P, Q∈B halmazra P∪Q∈B és P∩Q∈B 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.


Ezek után ábrázoljuk az A={1, 2, 3, 4} számhalmaz esetén az (A; ≤) teljesen vagy lineárisan rendezett halmaz elemeit Hasse-diagrammal. Az előző ábrával összehasonlítva figyeljük meg a parciális és teljes rendezés közötti különbséget a Hasse-diagramon:

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

Vegyük észre, hogy a diagram a teljes rendezés miatt egy egyenesre egyszerűsödött.

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 azzal is jól tudjuk szemléltetni, ha a részben (parciálisan), ill. teljesen rendezett halmazok megfelelő 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

Ha az 'A' halmazt kibővítjük úgy, hogy 'A' tetszőleges két elemének legkisebb közös többszöröse is eleme legyen a halmaznak (azaz az 'A' halmaz elemein kívül a {2,3,5,7}, {22=4,3,5,7} és {23=8,3,5,7} számokból képezhető összes 2,3 és 4 tényezőből álló különböző részszorzat), akkor az így kapott

AK=A∪{10, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 56, 60, 70, 84, 120, 125, 140, 147, 210, 280, 420, 840}

kibővített halmaznak egy legkisebb eleme (1) lesz, amely egyben minimális elem is, és egy legnagyobb eleme lesz (23*3*5*7=840), amely egyben maximális elem is. Emellett az így képzett AK halmaz zárt lesz a halmaz elemei között értelmezett legkisebb közös többszörös (lkkt) műveletre.

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,4]=12 vagy [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.


3.3. Hálók (kiegészítő anyag)

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

Az (A; ≼) részben rendezett halmazon értelmezett műveleteket bizonyos feltételek fennállása esetén a ≼ rendezési reláció segítségével is definiálhatjuk.

Az (A; ≼) részben rendezett halmaz egy tetszőleges R⊆A (R≠∅) részhalmazának a legnagyobb alsó korlátja (infimuma) alatt azt az Xinf∈A elemet értjük, amelyre
(1) ∀X∈R (Xinf≼X) (azaz az Xinf elem megelőzi 'R' minden elemét), és
(2) ∀Y∈A (∀X∈R (Y≼X) ⊃. Y≼Xinf) (azaz azok az elemek, amelyek megelőzik 'R' minden elemét, megelőzik az Xinf elemet is)
teljesül. Az 'R' részhalmaz legnagyobb alsó korlátját inf R módon jelöljük.

Például a (2I,⊆) részben rendezett halmazon P∩Q=inf {P, Q} teljesül minden P, Q∈2I (azaz P, Q⊆I) részhalmazra (vö. Szendrei 1975: 416).

Az (A; ≼) részben rendezett halmaz tetszőleges egy R⊆A (R≠∅) részhalmazának a legkisebb felső korlátja (szuprémuma) alatt azt az Xsup∈A elemet értjük, amelyre
(1) ∀X∈R (X≼Xsup) (azaz 'R' minden eleme megelőzi az Xsup elemet), és
(2) ∀Y∈A (∀X∈R (X≼Y) ⊃. Xsup≼Y) (azaz az Xsup elem megelőzi az összes olyan elemet, amelyeket 'R' minden eleme megelőz)
teljesül. Az 'R' részhalmaz legkisebb felső korlátját sup R módon jelöljük.

Például a (2I,⊆) részben rendezett halmazon P∪Q=sup {P, Q} teljesül minden P, Q∈2I (azaz P, Q⊆I) részhalmazra (vö. Szendrei 1975: 416).

Ha egy (A; ≼) részben rendezett halmaz bármely két P, Q∈A eleme esetén léteznek a P⌢Q ⇋ inf {P, Q} és a P⌣Q ⇋ sup {P, Q} elemek (azaz P⌢Q∈A és P⌣Q∈A teljesül), akkor az (A; ≼) részben rendezett halmaz meghatároz egy (A; ⌢, ⌣) hálót.

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

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)

Például az alábbi hálók esetében a hálók legkisebb eleme (zéruseleme vagy nulleleme), ill. legnagyobb eleme (egységeleme) a következő:
– ha A=2I (ahol I egy meghatározott alaphalmaz), akkor (A; ⊆) háló; ekkor 'o' az üreshalmazt (∅), 'i' pedig magát az 'I' halmazt jelenti (amely megkapható, mint az 'A' halmaz összes elemének uniója);
– ha A⊆ℕ+ az 1-et tartalmazó és az lnko és lkkt műveletekre zárt, véges számhalmaz, akkor (A; |) háló; ekkor 'o' az 1 természetes számot, 'i' pedig 'A' összes elemének legkisebb közös többszörösét jelenti.

Ha egy (A; ⌢, ⌣) háló esetében további tulajdonságok is teljesülnek, egy gyakorlati szempontból nagyon fontos struktúrához jutunk el. Ehhez először definiáljuk a háló egy tetszőleges elemének a komplementumát.

Ha az (A; ⌢, ⌣) hálónak van o∈A zéruseleme és i∈A egységeleme, akkor a háló egy a∈A elemének a komplementuma az az a'∈A elem (ha ilyen elem létezik), amelyre a⌢a'=o és a⌣a'=i teljesül. Általános esetben lehetséges, hogy egy elemnek nincs komplementuma, ill. az is lehet, hogy több komplementuma is létezik. Ha viszont az (A; ⌢, ⌣) hálóban értelmezett ⌢ és ⌣ műveletekre tetszőleges a,b,c∈A elemek esetén teljesül az
a⌢(b⌣c)=(a⌢b)⌣(a⌢c)
azonosság (disztributivitás), akkor a háló minden elemének legfeljebb egy komplementuma létezhet. Azokat a hálókat, amelyekben teljesül a disztributivitás fenti azonossága, disztributív hálóknak nevezzük (vö. Szendrei 1975: 418-420).

Az olyan, zéruselemmel és egységelemmel rendelkező, disztributív hálót, amelyben minden elemnek létezik komplementuma, Boole-algebrának (vagy Boole-hálónak) nevezzük.

Például egy adott 'I' alaphalmaz részhalmazainak halmaza a korábban megismert tulajdonságok alapján Boole-algebra.

Gyakorló feladatok


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 megadására 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 a következő értelemben:


Például tekintsük a valós számok között (pontosabban a valós számokból képzett ℝΧℝ halmazon) a
    ρ={(x,y) | x∈ℝ, y∈ℝ, x=y}
relációt. Ez könnyen ellenőrizhetően függvény, amit a szokásos módon
    f(x)=y ⇋ ρ(x,y)
vagy egyszerűen
    y=x
formában adhatunk meg. Az f(x)=y valós függvényt lineáris függvénynek nevezzük.


Egy másik példaként emlékezzünk vissza a természetes számok között értelmezett
    σ = {(a,b) | a∈ℕ, b∈ℕ, a|b} ⊆ ℕΧ
oszthatósági relációra. Ennek segítségével értelmezhetjük az
    p:ℕΧℕ→{0,1}
logikai függvényt a következőképpen:

p(x,y) { 1 ha x∣y, vagyis (x,y)∈σ
0 ha x∤y, vagyis (x,y)∉σ

Könnyen belátható, hogy tetszőleges x,y∈ℕ valós számokra σ(x,y) pontosan akkor teljesül, ha p(x,y)=1 teljesül.


Harmadik példaként állítsuk elő a (1,2,4,8,16,...) végtelen számsorozatot a pozitív természetes számok ℕ+ halmazán értelmezett
    s:ℕ+→ℝ
függvény segítségével, amelyre
    s(n)=2n (n∈ℕ+)
teljesül. (Jegyezzük meg, hogy egy s(n) számsorozatot az sn ún. "általános elem" segítségével szokás megadni. A példában szereplő sorozatot ennek megfelelően
    sn=2n (n=1,2,...)
módon adhatjuk meg.)


4.2. Függvények tulajdonságai

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

Tömören a függvények fenti tulajdonságait így írhatjuk le:
– injektivitás: ∀a∈A ∀a'∈A (a≠a' ⊃ f(a)≠f(a'))
– szürjektivitás: ∀b∈B ∃a∈A (f(a)=b)
– bijektivitás: ∀b∈B ∃!a∈A (f(a)=b)
A tulajdonságok teljesülése esetén a megadott logikai kifejezések igazak.

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 például 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 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. (A megoldással kapott x=f−1(y) függvényen még az x↔y és y↔x helyettesítést kell végrehajtanunk, hogy az f−1(x) függvényt megkapjuk.)

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:

A g(x) függvény képletében az x↔3*x+4 helyettesítést végrehajtva a h(x)=g(f(x)) összetett függvényre
    h(x)=g(f(x))=(3*x+4)2=9*x2+24*x+16
adódik.
Az f(x) : A→B injektív függvényre és ennek f−1(x) : B→A 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 is invertálható, és inverz függvénye f(x), ezért h(x)=(f∘f−1)(x)=x szintén teljesül.

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,+∞)

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. (Speciálisan, ha a függvény görbéje szimmetrikus az y=x egyenesre, akkor inverz függvénye önmaga.)

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 y↔x helyettesítést 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.


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) = x, f(x) = 2*x−40 és g(x) = −3*x+60:


Az f(x)=x2 : ℝ → ℝ, ill. f(x)=−x2 : ℝ → ℝ hatványfüggvény (másodfokú fü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.

Gyakorló feladatok


5.1. Sorozatok

Legyen n∈ℕ+ egy természetes szám. Az s:{1,2,...,n}⊆ℕ+→B függvényt véges sorozatnak, az s:ℕ+→B függvényt pedig végtelen sorozatnak (vagy egyszerűen sorozatnak) nevezzük. Egy (végtelen) sorozatot
    s1, s2, ..., sn, ... vagy
    (s1, s2, ..., sn, ...)
módon szokás jelölni, ahol sn a sorozat ún. általános eleme (n∈ℕ+).

A véges sorozatok úgy is felfoghatók, mint a 'B' halmaz önmagával képzett direkt szorzatának az elemei (ahol a direkt szorzat annyi tényezőből áll, ahány elemből áll a sorozat). Például egy 'n' elemből álló véges sorozat egy rendezett szám n-esnek felel meg, amely a Bn direkt szorzat egy meghatározott eleme. Ha a 'B' halmaz véges, és |B|=m, akkor mn darab különböző 'n' elemű sorozatot alkothatunk a 'B' halmaz elemeiből.

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

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.

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

A sorozatok képlettel vagy rekurzív definícióval történő megadása egy algoritmust ad meg, amellyel a sorozat elemei előállíthatók.

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 a következőket:
(1) 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 a δ különbség értéke ε értékénél kisebb lesz.
(2) A sorozat elemeinek eltérése az 1 számtól (másképpen megfogalmazva a tn=1 konstans elemekből álló sorozat azonos indexű elemeitől)
    δ=tn−sn=1−sn=1−(1−1/n)=1/n>0
'n' növelésével most is 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 δ különbség értéke ε értékénél kisebb lesz.

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

Például ha div jelöli az egész osztás és mod a maradékképzés műveletét, akkor a q=7/13≈0.538461538461538... szám tizedesjegyeit az alábbi két sorozat állítja elő:
    s1=7
    dn=(10*sn) div 13 (n∈ℕ+)
    sn+1=(10*sn) mod 13 (n∈ℕ+)
Vegyük észre, hogy a dn és sn sorozatok előállítása megfelel a jól ismert osztási algoritmusnak, ahol
– a dn sorozat elemei a hányados tizedesjegyeinek (0≤dn<10),
– az sn sorozat elemei az osztási maradékoknak (0≤sn<13)
felelnek meg.
A rekurzív módon megadott sn és dn sorozatok periodikusak:

Például számoljuk ki az alábbi sorozatelemeket:
d1=(10*s1) div 13=10*7 div 13=70 div 13=5 (mivel 70/13≈5.384615...)
s2=(10*s1) mod 13=10*7 mod 13=70 mod 13=5 (mivel 5*13=65, a maradék pedig 70-65=5)
d2=(10*s2) div 13=10*5 div 13=50 div 13=3 (mivel 50/13≈3.846153...)
s3=(10*s2) mod 13=10*5 mod 13=50 mod 13=11 (mivel 3*13=39, a maradék pedig 50-39=11)
és így tovább...

Általános esetben (pl. q=5/4 esetén stb.) előfordulhat, hogy egy adott m∈ℕ+ esetén sm=0 teljesül. Ettől az 'm' számtól kezdődően a maradék minden m'>m természetes szám esetén zérus lesz.


5.2. 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 (azaz az 'I' véges halmaz számosságá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 {1,2,...,n}⊂ℕ részhalmazára (ahol n=|H| a 'H' halmaz elemeinek a száma). Ez lehetőséget ad a természetes szám fogalmának az értelmezésére.

Amikor egy 'n' elemű 'H' halmaz elemeihez sorszámot rendelünk, akkor egy bijektív
    ψ:H→S⊆ℕ+
leképezést hozunk létre (ahol S={1,2,...,n} a sorszámok halmaza). A ψ leképezés bijektivitása miatt létezik a φ=ψ−1 inverz függvény. Mivel
    φ:S⊆ℕ+→H
ezért a φ leképezés létrehozásával a 'H' halmaz elemeit lényegében "sorozatba rendezzük", vagyis egy (véges) sorozatot definiálunk.


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 (ti. ebben az esetben minden ekvivalens halmaz elemszáma ugyanaz).

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. (Mivel az alaphalmazok hatványhalmaza része a Σ halmazrendszernek, ezért tetszőlegesen választott alaphalmazok metszetének hatványhalmaza is része a Σ halmazrendszernek.)

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 lényegében egyfajta "világhalmaz", amely az összes, a tanítás során felhasználható véges halmazt magában foglalja.

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.

Mind a sorszám fogalma (a halmazelemek "megszámlálása"), mind pedig a véges halmazok elemszáma alkalmas a természetes számok fogalmának bevezetésére. Azonban a tizes számrendszert alapul véve az első 10-11 szám (a decimális számjegyek, és esetleg a 10-es szám) bevezetése után mindkét esetben szükség van a "nagyobb" természetes számok formális, valamilyen algoritmus segítségével történő azonosítására. Erre szolgál a helyiérték fogalma, és a számok adott (célszerűen tízes) számrendszerben történő előállítása (amelynek segítségével már tetszőleges természetes számot "elnevezhetünk").


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, a fenti definícióban 'valódi részhalmaz' viszony helyett elegendő lenne egyszerűen a 'részhalmaz' viszonyt megkövetelni.

A definíció alapján 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.) (Tegyük fel indirekt módon, hogy B⊆A és |A|<|B| teljesül. Ekkor azonban a definíció alapján A⊂B (valamint |A|≠|B|) teljesül, ami ellentmondás (mivel egy halmaz sem valódi része önmagának). Ha a definícióban nem valódi részhalmaz viszony szerepelne, akkor pedig B⊆A és A⊆B együttes teljesüléséből A=B következne, de ez |A|≠|B| miatt szintén ellentmondáshoz vezetne.)

Egy 'A' halmaz As⊆A részhalmaza vagy kisebb, vagy egyenlő számosságú, mint az 'A' halmaz (azaz vagy |As|<|A| vagy |As|=|A| teljesül).

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 ℋ halmazrendszer ekvivalenciaosztályai között é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).

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| 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 korábban bevezetett Σ halmazrendszer elemei (amelyek véges halmazok) az "egyenlő számosságú" reláció alapján számosságilag ekvivalens halmazokból álló ekvivalenciaosztá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
∅∈Σ vagy {}∈Σ (üres halmaz, "nulla elemű" 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).

Megjegyzés: 10-nél nagyobb természetes számok esetén az "elnevezéshez" már szükségünk van a helyiérték fogalmára is.


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 az 'A' és 'B' halmazok között (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.3. 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ódi 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
– egyrészt a páros számok halmaza
    P = {n∈ℕ | 2|n}
a természetes számok valódi részhalmaza (P⊂ℕ);
– másrészt
    φ(n) : ℕ→P, φ(n)=2*n (n∈ℕ)
bijektív leképezés a természetes számok és a páros számok között;
tehát P~ℕ és emiatt |P|=|ℕ| teljesül.

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

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:


Érvényes továbbá a következő tétel:

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.

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

Következmények:

(1) A természetes számokból képzett rendezett számpárok halmaza megszámlálhatóan végtelen. (A fenti jelölésekkel legyen aij=(i,j). Ekkor az sn sorozat nyilvánvalóan a természetes számokból képezhető összes számpárt tartalmazza.)

(2) A pozitív racionális számok halmaza megszámlálhatóan végtelen. (Rendeljük hozzá a pozitív természetes számokból képezhető (i,j) számpárokhoz az i/j törtet. Így az összes pozitív racionális számot megkapjuk.)

(3) A racionális számok halmaza megszámlálhatóan végtelen. (A racionális számok halmaza előállítható a negatív és pozitív racionális számok halmazának, valamint a {0} halmaznak az uniójaként.)

Azonban ha a korábbi tételben unióképzés helyett direkt szorzatok szerepelnek, már nem megszámlálható halmazhoz jutunk:

Megszámlálhatóan végtelen számú véges vagy megszámlálhatóan végtelen halmaz direkt szorzata nem megszámlálhatóan végtelen halmaz.

Például a [0,1) közötti valós számokat előállítva
    0.d1d2d3... (0≤di≤9, i∈ℕ)
tizedestört alakban kontinuum számosságú halmazt kapunk.


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

A továbbiakban csak véges halmazokkal foglalkozunk.

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.

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

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)

Gyakorló feladatok

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

Kozma László 2004. Matematikai alapok. [Egyetemi jegyzet.] Debrecen: Debreceni Egyetem.

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

Tizedestört. Wikipédia.
https://hu.wikipedia.org/wiki/Tizedest%C3%B6rt, 2020-11-22.

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.