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:
az elemek felsorolásával: a halmaz elemeit kapcsos zárójelek között adjuk meg, vesszővel elválasztva (jegyezzük meg, hogy a felsorolt elemek sorrendje nem számít);
az elemek jellemzésével: ilyenkor a halmaz elemeit egy alaphalmazból választjuk ki az elemek egy vagy több közös tulajdonságának a megadásával (az így megadott halmaz az alaphalmaz részhalmaza⇒ lesz).
Példák halmazok megadására az elemek felsorolásával:
egy osztály tanulóinak halmaza:
I = {"Tercsi", "Fercsi", "Kata", "Klára", "Anett", "Peti", "Mari", "Pisti", "Zoli", "Zsuzsa"}
az I véges halmaz elemeinek száma: |I|=10
a decimális számjegyek halmaza:
D = {0,1,2,3,4,5,6,7,8,9}
a D véges halmaz elemeinek száma: |D|=10
a bináris számjegyek halmaza:
B = {0,1}
a B véges halmaz elemeinek száma: |B|=2
a hexadecimális számjegyek halmaza:
X = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
az X véges halmaz elemeinek száma: |X|=16
a természetes számok halmaza:
ℕ = {0,1,2,3,4,...,∞}
a pozitív természetes számok halmaza:
ℕ+ = {1,2,3,4,...,∞}
a primszámok halmaza:
ℙ = {2,3,5,7,11,13,...,∞}
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. Ebben az értelemben a vessző a logikai 'és' műveletnek felel meg. (Az elemek jellemzése során számos további logikai műveletet is használhatunk.)
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:
egy 'I' osztályban tanuló fiúk és lányok halmaza:
Q = {q∈I | "q fiú"}
R = {r∈I | "r lány"}
(például a Q halmaz fenti megadását "azok a 'q' tanulók az 'I' osztályból, akik fiúk" módon olvashatjuk)
egy 'b' természetes szám (b∈ℕ) osztóinak halmaza:
Db = {a∈ℕ | van olyan q∈ℕ természetes szám, amelyre b=q*a teljesül}
tömören ezt így írhatjuk le:
Legyen az alaphalmaz a természetes számok halmaza (ℕ) és ennek megfelelően jelöljenek az 'a', 'b', 'c', ..., 'q' szimbólumok ("változók") természetes számokat (a, ..., q∈ℕ). Ekkor a 'b' természetes szám osztóinak halmaza
Db = {a∈ℕ | ∃q (b=q*a)}
az ∃ ún. egzisztenciális kvantor jelentése: "van olyan", ill. "létezik olyan"
az oszthatóság⇒ fogalmát felhasználva a 'b' természetes szám osztóinak halmaza
Db = {a∈ℕ | a|b}
módon is leírható.
a kétjegyű páros számok halmaza:
P = {n∈ℕ | 10≤n<100, 2|n}
ahol
▸ 2|n ⇋ "2 osztója n-nek";
▸ a P halmaz fenti megadását "azok az 'n' természetes számok, amelyek a [10,100) balról zárt, jobbról nyílt intervallumba esnek és párosak" módon olvashatjuk;
▸ az [10,100) intervallum a ℕ halmaz részhalmaza, azaz
[10,100)⊆ℕ teljesül;
▸ a [10,100) balról zárt, jobbról nyílt intervallumot [10,100[ formában is jelölhetjük.
a primszámok halmaza:
ℙ = {n∈ℕ | n>1, és nem létezik olyan k∈ℕ természetes szám, amelyre 1<k<n és k|n teljesül}
formálisan ezt így írhatjuk le:
legyen az alaphalmaz a természetes számok halmaza (ℕ) és ennek megfelelően jelöljenek az 'a', ..., 'k', ..., 'n' változók természetes számokat (a, ..., n∈ℕ).
Ekkor a primszámok halmaza
ℙ = {n∈ℕ | n>1 ∧ ⌝∃k (1<k<n ∧ k|n)}
a fenti formális leírás logikailag ekvivalens (≡) a következővel:
ℙ = {n∈ℕ | n>1 ∧ ∀k (1<k<n ⊃ k∤n)}
a fenti leírás második feltétele például a következőképpen olvasható:
"bármely 'k' természetes számra teljesül, hogy ha a (1<k<n) feltétel igaz, abból következik az, hogy 'k' nem osztója 'n'-nek"
az ∧ szimbólum a logikai "és" műveletet jelöli
a ⌝ szimbólum a logikai "nem" műveletet jelöli
az ∀ ún. univerzális kvantor jelentése: "bármely olyan", ill. "minden olyan"
az ⊃ szimbólum az implikáció logikai műveletét jelöli. Jelentése: "ha ... akkor ...", ill. "...-ből következik, hogy ..."
érdemes megjegyezni, hogy a második feltételben használt kifejezések a logikai műveletek felhasználásával a következőképpen írhatóak le:
(1<k<n) ⇋ (1<k ∧ k<n)
k∤n ⇋ ⌝(k|n)
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
megadunk egy alaphalmazt (rendszerint téglalappal);
megadjuk az alaphalmaz egy vagy több részhalmazát⇒ az alaphalmazt ábrázoló alakzaton belül (például körökkel, ellipszisekkel vagy tetszőleges zárt görbével);
megadjuk az alaphalmaz elemeit a Venn-diagramon ábrázolt zárt alakzatok belső pontjaiként (ha egy pont egy adott alakzat belső pontja, akkor a pontnak megfeleltetett elem az alakzatnak megfeleltetett részhalmaznak az eleme).
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,3,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:
Kérdés: hová kerül a H halmaz '3' eleme a 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. "Tudor, 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
A fenti következtetések esetében az "aláhúzás" az ok-okozati viszonyt fejezi ki a vonal felett álló logikai feltétel (premissza) és a vonal alatt álló következtetés között. Például az I. következtetési szabály így olvasandó:
– "Ha az 'A' halmaz részhalmaza a 'B' halmaznak, akkor az 'A' halmaz minden eleme eleme a 'B' halmaznak is."
– "Ha A⊆B teljesül, akkor tetszőleges (bármely, minden stb.) 'x' elemre x∈A teljesüléséből x∈B következik."
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, a másiknak nem
(azaz vagy x∈A és x∉B, vagy x∈B és x∉A teljesül).
Az 'A' halmaz részhalmazai:
∅⊆A (az üres halmaz minden halmaznak részhalmaza)
A⊆A (minden halmaz részhalmaza önmagának)
valódi részhalmaz (R⊂A): az 'A' halmaznak az az 'R' nem üres részhalmaza, amely nem tartalmazza A összes elemét (azaz van az A halmaznak olyan eleme, amely nem eleme az R részhalmaznak). Formálisan
R⊂A ⇋ R⊆A, R≠∅ és R≠A
Emeljük ki, hogy R≠∅, azaz az üres halmaz egyetlen halmaznak sem valódi részhalmaza.
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:
unió (egyesítés):
A∪B = {x∈I | x∈A vagy⇒ x∈B}
(Az A és B halmazok uniója pontosan azokat az elemeket tartalmazza, amelyek az A és B halmazok közül legalább az egyik halmaznak az elemei.)
metszet (közös rész):
A∩B = {x∈I | x∈A és⇒ x∈B}
(Az A és B halmazok metszete pontosan azokat az elemeket tartalmazza, amelyek az A és B halmazok közül mindkét halmaznak az elemei.)
az A és B halmazokat diszjunktaknak nevezzük, ha nincs közös elemük (azaz A∩B=∅ teljesül)
komplementer (kiegészítő) halmaz (ún. abszolút komplementer halmaz): A = {x∈I | x∉A}
(Az A halmaz (I-re vonatkozó) komplementere az I alaphalmaz összes olyan eleme, amely az A halmaznak nem eleme. Ez a logikai nem (negáció)⇒ műveletével
A={x∈I | ⌝(x∈A)}
módon fejezhető ki.)
különbség vagy differencia: A∖B
= {x∈I | x∈A és x∉B} =
A∩B
(Az A és B halmazok különbsége A-nak az összes olyan elemét tartalmazza, amely a B halmaznak nem az eleme. Ez a logikai és és nem⇒ műveleteivel
{x∈I | (x∈A) ∧ ⌝(x∈B)}
módon fejezhető ki.)
az I∖B különbséget a 'B' halmaznak az 'I' halmazra vonatkozó abszolút komplementer halmazának,
az A∖B különbséget pedig a 'B' halmaznak az 'A' halmazra (pontosabban az A∪B halmazra) vonatkozó relatív komplementer halmazának is nevezzük
a 'B' halmaznak az 'I' alaphalmazra vonatkozó (abszolút) komplementer halmazának a kifejezése:
B
=
BI
=
I∖B
= I∩B
a 'B' halmaznak az 'A' halmazra, ill. az (A∪B) halmazra vonatkozó relatív komplementer halmazának a kifejezése:
BA∪B
=
(A∪B)∖B
≡
A∖B
=
A∩B
szimmetrikus differencia:
AΔB = {x∈I | x∈A∖B vagy⇒ x∈B∖A}
(Az A és B halmazok szimmetrikus különbsége az A halmaznak a B elemeitől különböző elemeiből vagy a B halmaznak az A elemeitől különböző elemeiből áll.
Másképpen megfogalmazva: az A és B halmazok szimmetrikus különbsége pontosan azokat az elemeket tartalmazza, melyek vagy csak az A halmaznak, vagy csak a B halmaznak az elemei. Ez a logikai kizáró vagy⇒ műveletével
{x∈I | (x∈A) ⨁ (x∈B)}
módon fejezhető ki.)
a szimmetrikus differencia két lehetséges kifejezése:
AΔB =
(A∖B)∪(B∖A)
=
(A∩B)∪(B∩A)
AΔB =
(A∪B)∖(A∩B)
=
(A∪B)∩(A∩B)
Mindegyik fenti halmazművelet eredménye egy I-beli halmaz, vagyis
A∪B⊆I,
A∩B⊆I,
A⊆I,
A∖B⊆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.
(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 különbség (differencia) segítségével az A⊆B összefüggés
A∖B = A∩B = ∅
módon is kifejezhető. Ezt komplementálva az ekvivalens
A∪B = I
összefüggéshez jutunk.
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)
=
A∪B
(A∪B)
=
A∩B
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 azonosságban szereplő bármelyik (A, B, ...) változó minden előfordulását helyettesíthetjük egy másik kifejezéssel (ez az ún. helyettesítés elve)
például, ha a kommutativitást kifejező
A∪B=B∪A
azonosságban egyidejűleg végrehajtjuk az
A↔(A∩B) és
B↔A
helyettesítéseket, akkor a szintén bármilyen A és B esetén érvényes
(A∩B)∪A=A∪(A∩B)
azonossághoz jutunk, tehát az abszorpció azonossága
(A∩B)∪A=A
módon is kifejezhető;
egy azonosságban szereplő bármelyik kifejezést helyettesíthetjük (kicserélhetjük, "pótolhatjuk") egy vele azonosan egyenlő kifejezéssel (ez az ún. pótlás elve)
például, ha az A∪B=B∪A azonosság bal oldalán szereplő A változót kicseréljük ("pótoljuk") az abszorpciót kifejező
A∪(A∩B)=A
azonosságnak megfelelően az
A↔(A∪(A∩B))
(ekvivalens) kifejezéssel, akkor a szintén bármilyen A és B esetén érvényes
(A∪(A∩B))∪B=B∪A
azonossághoz jutunk; az unióképzés kommutativitása és asszociativitása miatt ez
A∪B=A∪(A∩B)∪B
módon is felírható.
A fenti átalakításokat használjuk olyankor, amikor két kifejezés azonosságát akarjuk levezetni. A levezetés során kiindulunk az egyik (rendszerint összetettebb) kifejezésből, és olyan átalakításokat keresünk, amelyek révén végül a másik kifejezést kapjuk.
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:
∪ helyett ∩
∩ helyett ∪
∅ helyett I
I helyett ∅
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.
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Χ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 'ρ' az A-n értelmezett kétváltozós (binér) reláció, akkor
ρ⊆AΧA
teljesül.
Az
An=AΧAΧ...ΧA
n-szeres Descartes-szorzatnak (azaz az 'A' halmaz n-edik hatványának⇒) bármely részhalmazát n-változós homogén relációnak nevezzük.
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:
az I osztály tanulói között értelmezett
τ = {(x,y) | x∈I, y∈I, szomszédok(x,y)} ⊆ IΧI szomszédsági reláció jelentése:
τ(x,y) ⇋ "az 'x' tanuló szomszédja az 'y' tanulónak"
a természetes számok között értelmezett
σ = {(a,b) | a∈ℕ, b∈ℕ, ∃q∈ℕ (b=q*a)} ⊆ ℕΧℕ oszthatósági reláció jelentése:
σ(a,b) ⇋ "az 'a' természetes szám osztója a 'b' természetes számnak"
az oszthatósági reláció szokásos jelölése:
σ(a,b) ⇋ a|b
egy I alaphalmaz 2I hatványhalmazán értelmezett
Φ = {(A,B) | A∈2I, B∈2I,
A⊆B} ⊆ 2IΧ2I részhalmaz reláció jelentése:
A⊆B ⇋ "minden a∈A esetén a∈B teljesül"⇒
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:
É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:
A ξ relációt ábrázolhatjuk egy "rács" segítségével is:
A fenti ábra 90 fokkal elforgatva:
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ő:
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
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∈2Iré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 által megjelenített tartalom 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}
A fenti táblázat a korábban bevezetett
Φ⊆2IΧ2I
részhalmaz reláció⇒ kétdimenziós megjelenítése három elemű I alaphalmaz esetén.
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:
az I osztály tanulói között korábban értelmezett τ⊆IΧI szomszédsági reláció inverze
τ−1 ⊆ IΧI
= {(y,x) | x∈I, y∈I, τ(x,y)};
az inverz reláció jelentése:
τ−1(y,x) ⇋ "az 'y' tanulónak szomszédja az 'x' tanuló"
(vegyük észre, hogy tetszőleges 'a' és 'b' tanulókra τ(a,b) teljesüléséből következik τ(b,a), azaz τ−1(a,b) teljesülése; az ilyen tulajdonságú relációkat szimmetrikus relációknak⇒ nevezzük)
a természetes számok között korábban értelmezett σ⊆ℕΧℕ oszthatósági reláció inverze
σ−1 ⊆ ℕΧℕ = {(b,a) | a∈ℕ, b∈ℕ, a|b};
az inverz reláció jelentése:
σ−1(b,a) ⇋ "a 'b' természetes szám osztható az 'a' természetes számmal", vagy
σ−1(b,a) ⇋ "a 'b' természetes szám többszöröse az 'a' természetes számnak"
(Az a, b∈ℕ természetes számokra σ(a,b) és σ(b,a), azaz σ−1(a,b) akkor és csak akkor teljesül egyszerre, ha a=b teljesül; az ilyen tulajdonságú relációkat antiszimmetrikus relációknak⇒ nevezzük. Az egész számok körében azonban az oszthatósági reláció már nem antiszimmetrikus!)
a természetes számok között értelmezett "kisebb, mint" (<), ill. "kisebb-egyenlő, mint" (≤) reláció inverze a "nagyobb, mint" (>), ill. "nagyobb-egyenlő, mint" (≥) reláció: az x, y∈ℕ természetes számokra y>x (ill. y≥x) pontosan akkor teljesül, ha x<y (ill. x≤y) teljesül
az I alaphalmaz 2I haványhalmazán értelmezett részhalmaz reláció (⊆) inverze a tartalmazási reláció (⊇): az A, B∈2I halmazokra B⊇A pontosan akkor teljesül, ha A⊆B teljesül (azaz az 'A' halmaz a 'B' halmaz részhalmaza).
A tartalmazási reláció jelentése:
B⊇A ⇋ "a 'B' halmaz tartalmazza az 'A' halmazt"
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")}.
É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:
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
reflexivitás: minden a∈A elemre (a,a)∈ρ teljesül
(azaz minden elem relációban van önmagával)
Például a természetes számokon értelmezett
oszthatóság ( | ) reflexív reláció, mivel minden természetes szám osztója önmagának
egyenlőség ( = ) reflexív reláció, mivel minden természetes szám egyenlő önmagával
irreflexivitás: minden a∈A elemre (a,a)∉ρ teljesül (másképpen megfogalmazva: nincs olyan a∈A elem, amelyre (a,a)∈ρ teljesül)
(azaz egyetlen elem sincs relációban önmagával)
Például a természetes számokon értelmezett
"kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk irreflexívek, mivel egyetlen természetes szám sem kisebb (vagy nagyobb) önmagánál
(2) szimmetria – antiszimmetria – aszimmetria – egyik sem
szimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∈ρ teljesülése következik
(azaz a relációban álló elemek kölcsönösen relációban vannak egymással)
Például a természetes számokon értelmezett
egyenlőség ( = ) szimmetrikus reláció
antiszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ és (b,a)∈ρ egyszerre teljesül, akkor ebből a=b teljesülése következik (másképpen megfogalmazva: tetszőleges a, b∈A, a≠b elemekre (a,b)∈ρ teljesüléséből (b,a)∉ρ következik; antiszimmetrikus reláció esetében azonban létezhet olyan a∈A elem, amelyre (a,a)∈ρ teljesül, mivel a=a nyilvánvalóan teljesül)
(azaz egyetlen elem sincs kölcsönösen relációban egy másikkal, azonban önmagával relációban állhat)
Például a természetes számokon értelmezett
"kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk antiszimmetrikusak (vagyis egyrészt ha két n,m∈ℕ természetes számra n≤m és m≤n (vagy n≥m és m≥n) egyszerre teljesül, akkor n=m, azaz a két szám azonos, nem lehetnek különbözőek; másrészt bármely n∈ℕ természetes szám relációban áll önmagával, mivel n≤n és n≥n teljesül)
aszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∉ρ teljesülése következik
(azaz egyetlen elem sincs kölcsönösen relációban egy másik elemmel, és nem állhat relációban önmagával sem)
Jegyezzük meg, hogy aszimmetrikus reláció esetében (a,a)∈ρ teljesüléséből (a,a)∉ρ következik, ami ellentmondás, vagyis nem létezik olyan a∈A elem, amelyre (a,a)∈ρ teljesül; tehát az aszimmetrikus reláció mindig irreflexív.
Mivel különböző elemekre mind aszimmetrikus, mind antiszimmetrikus reláció esetében teljesül, hogy (a,b)∈ρ teljesüléséből (b,a)∉ρ teljesülése következik, az aszimmetrikus relációk mindig antiszimmetrikusak.
A fenti két megállapítást úgy foglalhatjuk össze, hogy egy reláció akkor és csak akkor aszimmetrikus, ha antiszimmetrikus és irreflexív.
Például a természetes számokon értelmezett
"kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk aszimmetrikusak (és korábban láttuk, hogy irreflexívek is)
(3) tranzitivitás – nem teljesülő tranzitivitás
tranzitivitás: ha az a∈A, b∈A és c∈A elemekre
(a,b)∈ρ
és
(b,c)∈ρ
teljesül, akkor ebből
(a,c)∈ρ
teljesülése következik
(azaz ha egy elem relációban áll egy másikkal, ez pedig relációban áll egy harmadikkal, akkor az első elem közvetlen relációban van a harmadik elemmel is)
Például a természetes számokon értelmezett
linearitás vagy trichotómia: tetszőleges a∈A és b∈A elemekre
vagy (a,b)∈ρ,
vagy (b,a)∈ρ,
vagy a=b
teljesül; tehát ha a≠b különböző elemek, akkor az (a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyiknek teljesülnie kell
(azaz minden elem relációban áll mindegyik másikkal, és az elemek közti reláció lehet kölcsönös is)
A fenti relációk közül legalább egynek mindig teljesülnie kell, de egyszerre akár több is teljesülhet (vö. Vajda 1996: 36). Szigorúbb feltétel, hogy a≠b esetén az (a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül (pl. Dringó-Kátai 1986: 28, Bonifert-Kovácsné Győri 1987: 32).*
Például a természetes számokon értelmezett
"kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk trichotómak (és reflexívek)
"kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk trichotómak (és irreflexívek)
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):
összefüggőség: tetszőleges a∈A és b∈A, a≠b elemekre az
(a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyik teljesül;
dichotómia: tetszőleges a∈A és b∈A, a≠b elemekre az
(a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül.
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
reflexivitás: a gráf minden csomópontjához egy hurokél tartozik
irreflexivitás: a gráf egyetlen csomópontjához sem tartozik hurokél
szimmetria: a gráf minden összekötött (azaz relációban levő) csomópontját két, ellentétes irányú él köti össze (hurokélek is lehetségesek!)
antiszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek azonban lehetségesek
aszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek nem lehetségesek
tranzitivitás: ha egy csomópontból egy másik csomóponton keresztül eljuthatunk egy harmadik csomópontba (a csomópontokat összekötő élek irányát követve), akkor az első csomópontból közvetlenül, egy lépésben (azaz egy összekötő élen keresztül) is eljuthatunk a harmadik csomópontba
trichotómia: bármely két csomópont össze van kötve, és az összekötött csomópontok közül az egyikből mindig közvetlenül eljuthatunk a másik csomópontba; hurokélek lehetségesek (azonban a közvetlen visszajutást, azaz a két csomópontot ellentétes irányban összekötő párhuzamos éleket a trichotómia szigorúbb feltétele esetében nem engedjük meg)
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:
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
bármely x∈I tanulóra ψ(x,x) nyilvánvalóan teljesül (reflexivitás);
ha az x∈I és y∈I tanulókra ψ(x,y) teljesül, akkor ψ(y,x) is teljesül (szimmetria);
ha az x∈I és y∈I tanulókra ψ(x,y) teljesül, valamint az y∈I és z∈I tanulókra ψ(y,z) szintén teljesül, akkor ψ(x,z) is teljesül (tranzitivitás).
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:
az I5 halmazban mindenki jelest kapott matematikából
("jeles" tanulók);
az I4 halmazban mindenki jót kapott matematikából
("jó" tanulók);
az I3 halmazban mindenki közepest kapott matematikából
("közepes" tanulók);
az I2 halmazban mindenki elégségest kapott matematikából
("gyenge" tanulók);
az I1 halmazban mindenki elégtelent
kapott matematikából
("problémás" tanulók).
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).
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 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:⇒
kiindulunk magából az 'A' halmazból, amely egy osztályból álló osztályozásnak tekinthető (azaz minden elemét ekvivalensnek tekintjük) (Η={A1}, ahol A1=A={1, 2, 3, 4} );
képezzük a két osztályból álló osztályozásokat: az 'A' halmaz elemeit két diszjunkt osztályra bontjuk az összes lehetséges módon (pl. az ábra második sorában szereplő első osztályozás, '14/23' jelentése: Η={A1, A2}, ahol A1={1, 4} és A2={2, 3} );
képezzük a három osztályból álló osztályozásokat: a két osztályból álló osztályozásokat tovább bontjuk úgy, hogy egy kiválasztott osztályt két további osztályra bontunk az összes lehetséges módon (pl. az ábra harmadik sorában szereplő első osztályozás, '1/23/4' jelentése: Η={A1, A2, A3}, ahol A1={1}, A2={2, 3} és A3={4} );
végül megkapjuk a négy osztályból álló osztályozást: egy ilyen osztályozás van, amelyben az egyes osztályok az 'A' halmaz egy elemű részhalmazai
(Η={A1, A2, A3, A4}, ahol
A1={1}, A2={2}, A3={3}, A4={4}
(vegyük észre, hogy ez az osztályozás megegyezik a korábban említett ΗA triviális osztályozással).
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.
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:
kiindulunk magából az 'R' halmazból, amely egy osztályból álló osztályozásnak tekinthető
Η0={R},
|Η0|=1
képezzük a sapka színe szerinti osztályozást: az 'R' halmaz elemeit annyi osztályra bontjuk, ahány különböző színű sapkája van Julinak
Η1={Spiros, Szöld}, |Η1|=2, ahol
Spiros={x∈R | sapka_szine(x)=piros} és
Szöld={x∈R | sapka_szine(x)=zöld};
mivel Spiros∩Szöld=∅ és Spiros∪Szöld=R teljesül, ezért Η1 az 'R' halmaz osztályozása
képezzük a blúz színe szerinti osztályozást: a sapka színe szerint képzett osztályokat (pl. Spiros) annyi további osztályra bontjuk, ahány különböző színű blúza van Julinak
Η2={Bpiros−kék, Bpiros−piros, ..., Bzöld−sárga}, |Η2|=2*3=6, ahol pl.
végül képezzük a szoknya színe szerinti osztályozást: a sapka és a blúz színe szerint képzett osztályokat (pl. Bpiros−kék) annyi további osztályra bontjuk, ahány különböző színű szoknyája van Julinak
Η3={Zpiros−kék−kék, Zpiros−kék−zöld, ..., Zzöld−sárga−zöld}, |Η3|=2*3*2=12, ahol az egyes osztályok az 'R' halmaz elemeiből képzett egyelemű halmazok (mivel feltettük, hogy Julinak minden színű sapkából, blúzból és szoknyából egy darab van), pl.
Zpiros−kék−kék={x∈R | sapka_szine(x)=piros, bluz_szine(x)=kék, szoknya_szine(x)=kék}={(piros sapka, kék blúz, kék szoknya)}
Zpiros−kék−zöld={x∈R | sapka_szine(x)=piros, bluz_szine(x)=kék, szoknya_szine(x)=zöld}={(piros sapka, kék blúz, zöld szoknya)}
...
Bpiros−kék=Zpiros−kék−kék∪Zpiros−kék−zöld
Bpiros−piros=Zpiros−piros−kék∪Zpiros−piros−zöld
...
Á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 hierarchiaszintjének a Η1 osztályozás,
a blúzok hierarchiaszintjének a Η2 osztályozás, végül
a szoknyák hierarchiaszintjének a Η3 osztályozás felel meg.)
A fadiagram minden szintje az adott 'R' halmaz egy osztályozásának felel meg.
A fadiagram élei az egyes osztályok kapcsolatát mutatják: a magasabb hierarchiaszinten levő ("szülő") osztályokhoz kapcsolt ("leszármazott") osztályok a szülő osztály elemeit bontják fel diszjunkt alosztályokra.
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:
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.
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.
Ha a ρ rendezési reláció trichotóm, akkor teljes rendezési relációnak nevezzük, az (A; ρ) halmazt pedig teljesen rendezett halmaznak (a ρ reláció szerint)
(szokásos a lineárisan rendezett halmaz elnevezés is, Szendrei 1975: 41);
ha a ρ rendezési reláció nem trichotóm, akkor parciális rendezési relációnak nevezzük, az (A; ρ) halmazt pedig részben (vagy parciálisan) rendezett halmaznak (a ρ reláció szerint).
Például a természetes számokon (ℕ) értelmezett
"kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk gyenge és teljes rendezési relációk, mert reflexívek, antiszimmetrikusak és tranzitívek, valamint trichotómak;
"kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk szigorú és teljes rendezési relációk, mert irreflexívek, aszimmetrikusak és tranzitívek, valamint trichotómak.
oszthatóság ( | ) gyenge és parciális rendezési reláció, mert reflexív, antiszimmetrikus és tranzitív, azonban nem trichotóm (mivel pl. a 3 és 7 természetes számok nem osztói egymásnak, és nem egyenlőek);
Például az 'I' halmaz 2I hatványhalmazán (azaz az 'I' halmaz összes részhalmazának halmazán) értelmezett
részhalmaz (⊆) reláció gyenge és parciális rendezési reláció a 2I hatványhalmazon, mert reflexív, antiszimmetrikus és tranzitív, de nem trichotóm; tehát (2I; ⊆) parciálisan rendezett halmaz
(mivel pl. az {a,b} és {a,c} halmazok között sem a részhalmaz reláció, sem az egyenlőség nem áll fenn, a ⊆ reláció nem trichotóm);
valódi részhalmaz (⊂ ) reláció szigorú és parciális rendezési reláció a 2I hatványhalmazon, mert irreflexív, aszimmetrikus és tranzitív, de nem trichotóm; tehát (2I; ⊂) szintén parciálisan rendezett halmaz
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").
Láttuk korábban, hogy minden binér reláció ábrázolható egy irányított gráf segítségével. Rendezési relációk esetén a gráf ábrázolása jelentősen leegyszerűsíthető.
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ő:
az 'A' halmaz elemeit a gráf csomópontjaiként ábrázoljuk;
csak azok között az x, y∈A (x≠y) elemek között rajzolunk élt, amelyekre
egyrészt x≼y teljesül,
másrészt nem létezik olyan "köztes" z∈A (z≠x, z≠y) elem, amelyre x≼z≼y teljesül (ilyenkor azt mondjuk, hogy az 'x' elem közvetlenül megelőzi az 'y' elemet, vagy másképpen az 'y' elem fedi az 'x' elemet, vö. Kiss 2007: 336)
;
a gyenge rendezési reláció reflexivitásából⇒ adódó hurokéleket a diagramon nem ábrázoljuk;⇒
ha az x, y∈A (x≠y) elemekre x≼y teljesül, akkor x-et lejjebb, y-t feljebb ábrázoljuk. Ilyen ábrázolás esetén a csomópontok elhelyezkedése meghatározza a relációt jelző él irányát (mivel az élek mindig felfelé mutatnak, a gráfban a rendezési reláció irányát követve "felfelé haladunk"), ezért a relációban álló csomópontokat irányítás nélkül is összeköthetjük.
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 rendezési reláció antiszimmetriája és tranzitivitása miatt 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:
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:
az élekkel összekötött csomópontok részhalmaz relációban (⊆) állnak (egy vagy több köztes csomópont esetén az összekötött csomópontok közötti részhalmaz relációt az ábra a reláció tranzitivitása miatt közvetve ábrázolja)
általánosan megfogalmazva a rendezési reláció (≼) iránya alulról felfelé mutat (azaz a "kisebb" elemből a "nagyobb" elem felé) (pl. {a}→{a,b} tehát {a}⊆{a,b})
az ábrán a "legnagyobb" elem maga az 'A' halmaz, amelynek minden, az ábrán szereplő elem a részhalmaza
az ábrán a "legkisebb" elem az üreshalmaz (∅), amely minden elemnek részhalmaza
két részhalmaz unióját úgy kapjuk meg, hogy az ábrán felfelé haladva megkeressük az első (relatíve "legkisebb") olyan közös csomópontot, amelyhez mindkét részhalmazból él vezet;
például
{a}→{a,b} és {b}→{a,b} tehát {a}∪{b}={a,b}
{a}→{a,b}→{a,b,c} és {b,c}→{a,b,c} tehát {a}∪{b,c}={a,b,c}
{a}→{a,b} tehát {a}∪{a,b}={a,b} (ebben a példában a közös csomópont egybeesik az egyik részhalmazzal)
két részhalmaz metszetét úgy kapjuk meg, hogy az ábrán lefelé haladva megkeressük az első (relatíve "legnagyobb") olyan közös csomópontot, amelyből mindkét részhalmazhoz él vezet;
például
{a}→{a,b} és {a}→{a,c} tehát {a,b}∩{a,c}={a}
∅→{a} és ∅→{b}→{b,c} tehát {a}∩{b,c}=∅
{a}→{a,b} tehát {a}∩{a,b}={a} (ebben a példában a közös csomópont most is egybeesik az egyik részhalmazzal)
Ö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:
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
legkisebb eleme az az
xlk∈A
elem, amelyre igaz, hogy minden y∈A elemre
xlk≼y
teljesül;
legnagyobb eleme az az
xln∈A
elem, amelyre igaz, hogy minden
y∈A elemre y≼xln
teljesül;
minimális eleme az az xmin∈A elem, amelyre igaz, hogy nem létezik olyan y∈A, y≠xmin elem, amelyre y≼xmin teljesül (vagyis nincs az 'A' halmaznak másik olyan eleme, amely a minimális elemnél "kisebb");
maximális eleme az az xmax∈A elem, amelyre igaz, hogy nem létezik olyan y∈A, y≠xmax elem, amelyre xmax≼y teljesül (vagyis nincs az 'A' halmaznak másik olyan eleme, amely a maximális elemnél "nagyobb").
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' halmaz legkisebb eleme 1 (mivel 1 minden természetes számnak osztója, tehát 'A' minden elemének is osztója);
az 'A' halmaznak legnagyobb eleme nem létezik (ugyanis 'A'-ban nincs olyan elem, amelynek 'A' minden eleme osztója lenne);
az 'A' halmaz minimális eleme 1 (mert nincs olyan természetes szám, amely rajta kívül osztója lenne, tehát 'A' elemei között sincs ilyen szám);
az 'A' halmaz maximális elemei az 5, 6, 7 és 8 számok (ugyanis 'A'-ban nincs olyan elem, amelynek ezek a számok osztói lennének).
Az (A; |) oszthatóság szerint részben rendezett halmaz 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
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:
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):
X⌢X=X (idempotencia)
X⌢Y=Y⌢X (kommutativitás)
(X⌢Y)⌢Z=X⌢(Y⌢Z) (asszociativitás)
X⌢(X⌣Y) = X (abszorpció, elnyelés)
X⌣X=X (idempotencia)
X⌣Y=Y⌣X (kommutativitás)
(X⌣Y)⌣Z=X⌣(Y⌣Z) (asszociativitás)
X⌣(X⌢Y) = X (abszorpció, elnyelés)
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 (azaz a 2I hatványhalmaz) a korábban megismert tulajdonságok⇒ alapján Boole-algebra.
Legyenek 'A' és 'B' tetszőleges halmazok,
ρ⊆AΧB
az 'A' és 'B' halmazok közötti reláció. Ekkor a
Dom(ρ) ⇋ {a∈A | van olyan b∈B, amelyre ρ(a,b) teljesül}
halmazt a ρ reláció értelmezési tartományának ("indulási halmazának"), a
Rng(ρ) ⇋ {b∈B | van olyan a∈A, amelyre ρ(a,b) teljesül}
halmazt a ρ reláció értékkészletének ("érkezési halmazának") nevezzük.
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.
Tömören az első és második feltételt így írhatjuk le:
∀a∈A ∃!b∈B (ρ(a,b))
minden esetben teljesül.
A második feltételt leírhatjuk úgy is, hogy
∀a∈A(ρ(a,b)∧ρ(a,b')⊃.b=b')
minden esetben 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:
tetszőleges
(a,b)∈ρ⊆AΧB
elempár esetén
f(a)=b ⇋ ρ(a,b)
teljesül;
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.
Ha adott az értékkészlet egy b∈B képeleme, akkor az értelmezési tartománynak azokat az a∈A elemeit, amelyekre f(a)=b teljesül, az
Ab = {a∈A | f(a)=b}
halmazzal adhatjuk meg. Ha a 'b' értéket az 'a' elem egy tulajdonságának tekintjük, akkor azt mondhatjuk, hogy az Ab⊆A halmaz elemei egy adott b∈B tulajdonsággal rendelkeznek. Az információkeresés terminológiáját átvéve az Ab halmazt a 'b' elem forráshalmazának, a halmaz elemeit pedig a 'b' elem forrásainak nevezhetjük.
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.⇒
Könnyen ellenőrizhető, hogy σ nem függvény (pl. egyrészt 2|4 és 2|6, másrészt 3|12 és 4|12 teljesül). Azonban σ segítségével értelmezhetjük a
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)∉σ
A definíció alapján tetszőleges x,y∈ℕ valós számokra σ(x,y) pontosan akkor teljesül, ha p(x,y)=1 teljesül.
Jegyezzük meg, hogy azon (x,y) számpárok halmaza, amelyekre p(x,y)=1, éppen a σ halmazt adja meg, azaz
Ip(x,y)={(x,y)∈ℕΧℕ | p(x,y)=1} = σ
teljesül.
Általánosan is igaz, hogy minden relációhoz hozzárendelhetünk egy logikai függvényt, amely pontosan akkor igaz, ha az elempárokat (vagy elem n-eseket) alkotó elemek relációban vannak egymással.
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−1 (n∈ℕ+)
teljesül.
Jegyezzük meg, hogy egy s(n) számsorozatot többnyire az sn ún. "általános elem" segítségével szokás megadni. A példában szereplő sorozatot ennek megfelelően
sn=2n−1 (n=1,2,...)
módon adhatjuk meg.
Az s(n) számsorozat általános tagját megadhatjuk a megelőző elem segítségével (ún. rekurzív módon). Ekkor a sorozat első elemét is meg kell adnunk:
s1=1
sn=2*sn−1 (n=2,3,...)
Az első pár elem kiszámításával ellenőrizhetjük, hogy a sorozat kétféle megadása ugyanazokat a sorozatelemeket szolgáltatja. (Ha ezt általánosan szeretnénk bizonyítani, azt például teljes indukciós bizonyítással tehetjük 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:
injektivitás: az 'f' függvény injektív vagy kölcsönösen egyértelmű, ha különböző értelmezési tartománybeli elemekhez különböző képelemek tartoznak, vagyis bármely a∈A és a'∈A, a≠a' elemek esetén f(a)≠f(a') teljesül;
Például az f(x)=x lineáris függvény⇒ injektív függvény.
Ezzel szemben például az f(x)=x2 másodfokú függvény⇒nem injektív függvény.
ha az 'A' értelmezési tartomány véges halmaz, akkor injektív függvény esetében |A|=|Rng(f)| teljesül;
szürjektivitás: az 'f' függvény szürjektív, ha az értékkészlet minden eleme legalább egy értelmezési tartománybeli elem képe, azaz bármely b∈B elem esetén létezik olyan a∈A elem, amelyre f(a)=b teljesül;
Például az f(x)=x lineáris függvény⇒ szürjektív függvény.
Ezzel szemben például az f(x)=x2 másodfokú függvény⇒nem szürktív függvény (csak nemnegatív értékeket vehet fel).
szürjektív függvény esetében
B=Rng(f)
teljesül;
bijektivitás: az 'f' függvény bijektív, ha injektív és szürjektív; ennek megfelelően
ha az 'A' értelmezési tartomány véges halmaz, akkor az injektivitás miatt |A|=|B| teljesül;
a szürjektivitás miatt B=Rng(f) teljesül.
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"},
továbbá legyen
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:
az f(x) függvény nem injektív, mivel pl.
f("Kata") = f("Klára") = "K";
az f(x) függvény nem szürjektív, mivel pl. "C" betűvel nem kezdődik egyik tanuló neve sem;
az f(x) függvény tehát nem bijektív.
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='A' (k='B', ..., k='Z') betűvel kezdődik:
IA={"Anett"}
IB=∅
...
IK={"Kata", "Klára"}
...
IZ={"Zoli", "Zsuzsa"}
Ekkor
Ik∩Ij=∅ (k, j∈B, k≠j) és IA∪IB∪...∪IZ=I
teljesülése miatt Η={Ik | k∈B, Ik≠∅}⊆2I
az 'I' halmaz egy osztályozása. Jegyezzük meg, hogy ha k∈B helyett csak azokat a betűket vesszük figyelembe, amelyek az f(x) függvény értékkészletének elemei (azaz ha a Η halmazrendszer fenti megadásában k∈B helyett k∈Rng(f) szerepel), akkor Η={Ik | k∈Rng(f)}
pontosan az 'I' halmaz fenti osztályozását adja meg. (Jegyezzük meg, hogy az IA, IB, ..., IZ osztályok a nagybetűkből álló B halmaz egyes elemeinek a forráshalmazai.⇒)
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 is végre kell hajtanunk, 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:
f(x)=3*x+4
g(x)=x2
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.
Legyen f(x) invertálható függvény. Ekkor
(1) az
f(x):A→B
invertálható függvényre és ennek
f−1(x):B→A
inverz függvényére
(f−1∘f)(x)=x
teljesül;
(2) mivel ebben az esetben az f−1(x) függvény is invertálható, és inverz függvénye f(x), ezért
(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:
értelmezési tartomány: Dom(f)=A
értékkészlet: Rng(f)⊆B; az értékkészlet definíciója⇒ alapján Rng(f) = {f(x) | x∈A}
invertálhatóság: az f(x) valós függvénynek létezik az f−1(x) inverz függvénye⇒
(ha Descartes-féle koordináta-rendszerben ábrázoljuk az f(x) függvényt, az inverz függvény létezésének feltétele, hogy az 'x' tengellyel párhuzamos bármelyik egyenesnek az f(x) függvény grafikonjával legfeljebb egy közös pontja legyen).
zérushely: Azt az x0∈A értéket, amelyre
f(x0)=0
teljesül, az f(x) függvény zérushelyének nevezzük. A zérushely(ek)ben a függvény grafikonja metszi a koordináta-rendszer 'x' tengelyét.
korlátosság:
az f valós függvény alulról korlátos, ha van olyan
Ka∈ℝ
valós szám, amelyre Ka≤f(x) teljesül az értelmezési tartomány minden x∈A elemére
(a Ka számot alsó korlátnak nevezzük; azt az alsó korlátot, amely minden lehetséges alsó korlátnál nagyobb, legnagyobb
alsó
korlátnak (infimumnak) nevezzük, és Inf Rng(f) módon jelöljük);
az f valós függvény felülről korlátos, ha van olyan
Kf∈ℝ
valós szám, amelyre f(x)≤Kf teljesül az értelmezési tartomány minden x∈A elemére
(a Kf számot felső korlátnak nevezzük; azt a felső korlátot, amely minden lehetséges felső korlátnál kisebb, legkisebb
felső
korlátnak (szuprémumnak) nevezzük, és Sup Rng(f) módon jelöljük);
az f valós függvény korlátos, ha van olyan
K∈ℝ
valós szám, amelyre |f(x)|≤K teljesül az értelmezési tartomány minden
x∈A elemére.
(Ha az f(x) valós függvény korlátos, és korlátja K, akkor alulról és felülről is korlátos. Az f(x) valós függvény egy lehetséges alsó korlátja Ka=−K, egy lehetséges felső korlátja pedig Kf=K.)
monotonitás:
az f valós függvény az értelmezési tartomány egy Am⊆A részhalmazán monoton növekedő, ha minden
x1∈Am, x2∈Am,
x1<x2
szám esetén
f(x1)≤f(x2)
teljesül;
az f valós függvény az értelmezési tartomány egy Am⊆A részhalmazán szigorúan monoton növekedő, ha minden
x1∈Am, x2∈Am, x1<x2
szám esetén
f(x1)<f(x2)
teljesül;
az f valós függvény az értelmezési tartomány egy Am⊆A részhalmazán monoton csökkenő, ha minden
x1∈Am, x2∈Am,
x1<x2
szám esetén
f(x1)≥f(x2)
teljesül;
az f valós függvény az értelmezési tartomány egy Am⊆A részhalmazán szigorúan monoton csökkenő, ha minden
x1∈Am, x2∈Am, x1<x2
szám esetén
f(x1)>f(x2)
teljesül.
konvexitás, görbület:
az f valós függvényt egy intervallumon konvexnek ("felfelé görbülőnek") nevezzük, ha az intervallum bármely x1 és x2 helyén teljesül a
f((x1+x2)/2)≤(f(x1)+f(x2))/2
egyenlőtlenség. (Reiman 1992: 492)
Például az f(x)=x2 másodfokú függvény⇒ esetében könnyen ellenőrizhető, hogy a fenti egyenlőtlenség az értelmezési tartomány bármely x1 és x2 pontjában teljesül. Szemléletesen ez azt jelenti, hogy a másodfokú függvény bármely pontjában a görbe érintője a görbe alatt helyezkedik el, a függvény "felfelé görbül".
az f valós függvényt egy intervallumon konkávnak ("lefelé görbülőnek") nevezzük, ha az intervallum bármely x1 és x2 helyén teljesül a
f((x1+x2)/2)≥(f(x1)+f(x2))/2
egyenlőtlenség. (Reiman 1992: 492)
Például az f(x)=−x2 másodfokú függvény⇒ esetében könnyen ellenőrizhető, hogy a fenti egyenlőtlenség az értelmezési tartomány bármely x1 és x2 pontjában teljesül. Szemléletesen ez azt jelenti, hogy a másodfokú függvény bármely pontjában a görbe érintője a görbe felett helyezkedik el, a függvény "lefelé görbül".
szélsőérték (minimum- és maximumhelyek):
az f valós függvénynek az értelmezési tartomány egy As⊆A részhalmazán lokális minimuma van, ha létezik olyan xmin∈As érték, amelyre teljesül, hogy
minden x∈As szám esetén f(xmin)≤f(x) teljesül
(az xmin számot ilyen esetben lokális minimumhelynek, az f(xmin) függvényértéket pedig lokális minimumértéknek nevezzük);
ha As azonos a függvény teljes értelmezési tartományával (As=A), akkor abszolút minimumról beszélünk (továbbá abszolút minimumhelyről és abszolút minimumértékről);
az f valós függvénynek az értelmezési tartomány egy As⊆A részhalmazán lokális maximuma van, ha létezik olyan xmax∈As érték, amelyre teljesül, hogy
minden x∈As szám esetén f(x)≤f(xmax) teljesül
(az xmax számot ilyen esetben lokális maximumhelynek, az f(xmax) függvényértéket pedig lokális maximumértéknek nevezzük);
ha As azonos a függvény teljes értelmezési tartományával (As=A), akkor abszolút maximumról beszélünk (továbbá abszolút maxumumhelyről és abszolút maximumértékről).
paritás:
az f valós függvény páros, ha minden olyan x∈A számra, amelyre −x∈A, f(−x)=f(x) teljesül
(a páros függvények grafikonja tengelyesen szimmetrikus a koordináta-rendszer 'y' tengelyére);
az f valós függvény páratlan, minden olyan x∈A számra, amelyre −x∈A, f(−x)=−f(x) teljesül
(a páratlan függvények grafikonja középpontosan vagy centrálisan szimmetrikus a koordináta-rendszer origójára).
periodicitás: létezik olyan p∈ℝ, p≠0 szám, hogy
minden x∈A számra (x−p)∈A és (x+p)∈A, valamint
f(x)=f(x+p)
teljesül. A fenti tulajdonságú függvényt periodikusnak, a 'p' számot pedig az f(x) függvény (egyik) periódusának nevezzük (vö. Farkas-Fritzné-Kissné 2000: 13).
(Szemléletesen ez azt jelenti, hogy ha a függvény görbéjét az 'x' tengely mentén 'p' értékkel (bármilyen irányban) eltoljuk, a görbe önmagába megy át.)
Ha létezik a fenti tulajdonságú p>0 periódusok között legkisebb, akkor ezt a pτ>0 számot a függvény (legkisebb) periódusának nevezzük.
Ha a 'p' szám egy periódus, akkor annak minden egész számú többszöröse is egy periódus.
Ha a 'p' és 'q' szám egy-egy periódus, akkor a p+q szám, valamint a p−q szám is egy-egy periódus.
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.
Vizsgáljuk meg a fenti tulajdonságok teljesülését a korábban ábrázolt valós függvények⇒ esetében!
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 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.
(Egydimenziós mintára példa lehet egy gyöngysor, kétdimenziós mintára pedig egy hímzés.)
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.
(Egyes esetekben az első sorozatelem indexe zérus, azaz egy számsorozatot
s:ℕ→B⊆ℝ
leképezéssel is megadhatunk.)
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:
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.
Egy sorozat általános elemét sokszor a megelőző elem vagy elemek segítségével állítjuk elő.
Ilyenkor rekurzív definícióról (vagy rekurzív 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.
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:
korlátosság:
a számsorozat alulról korlátos, ha van olyan Ka valós szám, amelyre Ka≤si teljesül (i∈ℕ+);
a számsorozat felülről korlátos, ha van olyan Kf valós szám, amelyre si≤Kf teljesül (i∈ℕ+);
a számsorozat korlátos, ha van olyan K valós szám, amelyre |si|≤K teljesül (i∈ℕ+)
(a számsorozat akkor és csak akkor korlátos, ha alulról és felülről is korlátos).
monotonitás:
ha a számsorozat elemeire si≤si+1 (i∈ℕ+) teljesül, a számsorozatot monoton növekvőnek nevezzük;
ha a számsorozat elemeire si<si+1 (i∈ℕ+) teljesül, a számsorozatot szigorúan monoton növekvőnek nevezzük;
ha a számsorozat elemeire si≥si+1 (i∈ℕ+) teljesül, a számsorozatot monoton csökkenőnek nevezzük;
ha a számsorozat elemeire si>si+1 (i∈ℕ+) teljesül, a számsorozatot szigorúan monoton csökkenőnek nevezzük.
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:
É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".
(2) Bármilyen kis 0<ε≪1 valós számot választunk, ha veszünk két sk, sm tetszőleges sorozatelemet (k≥m), amelyek mindegyike az
Nε=1/ε
küszöbszámnál nagyobb indexű, akkor vannak olyan r≥t≥0 természetes számok, amelyekre
k=Nε+r és m=Nε+t
teljesül. Ekkor
Δ=sk−sm=
1/m−1/k=
(r−t)/[(Nε+r)*(Nε+t)]<
1/Nε=ε
teljesül. (Vezessük be az x=Nε változót, ekkor a fenti egyenlőtlenségből x>0 miatt egyszerű átszorzással
x*(r−t)<(x+r)*(x+t)
adódik. A zárójeleket felbontva és egyszerűsítve a
0<x2+2*t*x+r*t
egyenlőtlenséget kapjuk, amely x>0, r≥t≥0 miatt nyilvánvalóan fennáll.)
Tehát bármilyen kis 0<ε≪1 valós számot választunk, ha 'n' értékét elegendően nagyra választjuk, akkor két tetszőleges sorozatelem különbsége ε értékénél kisebb lesz.
(3) A sorozat elemeinek eltérése az 1 számtól (másképpen megfogalmazva az un=1 konstans elemekből álló sorozat azonos indexű elemeitől)
Δ=un−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 a Δ különbség értéke ε értékénél kisebb lesz.
(4) A fenti tulajdonságok fennállása esetén beszélünk a sorozatok határértékéről. Esetünkben az sn sorozat határértéke 1, amit
sn→1 (n→∞)
módon jelölünk.
Értelmezzük végül a sorozatokra a periodicitás fogalmát.
periodicitás: az sn számsorozat esetében létezik olyan k∈ℕ+ szám, hogy
minden n∈ℕ számra
sn+k=sn
teljesül. A fenti tulajdonságú számsorozatot periodikusnak, a legkisebb ilyen tulajdonságú 'k' számot pedig az sn számsorozat periódusának nevezzük. (Ilyenkor szokásos a k-periodikus sorozat elnevezés is.)
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∈ℕ+)
Például
7=0*13+7 (d0=0, s1=7)
70=5*13+5 (d1=5, s2=5)
50=3*13+11 (d2=3, s3=11)
...
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.
Az előző feladat megfordítása az, hogy egy végtelen szakasos tizedes tört esetén keressük meg azt a racionális törtszámot, amely az adott tizedestörtet állítja elő. Például vizsgáljuk meg az algoritmust az előzőekben használt
q=0.538461538461538...
végtelen szakaszos tizedes törtre.⇒
Ha a kapott racionális törtszám számlálójában és nevezőjében nagy egész számok fordulnak elő, érdemes megvizsgálnunk azt, hogy a tört egyszerűsíthető-e, azaz a számláló és nevező legnagyobb közös osztója egynél nagyobb-e. Az előző példában a számlálóra 538461 és a nevezőre 999999 adódik, amelyek legnagyobb közös osztója egyszerűen meghatározható.⇒
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→H2bijektí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.
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:
reflexivitás: H1 ~ H1
(bármely x∈H1 esetén legyen φ(x)=x; az így értelmezett
φ(x) : H1→H1
függvény a H1 halmaz bijektív leképezése önmagára);
szimmetria: H1 ~ H2 akkor és csak akkor teljesül, ha H2 ~ H1
(ha
φ(x) : H1→H2
bijektív leképezés, akkor a
φ−1(x) : H2→H1
inverz függvény⇒ szintén bijektív leképezés);
tranzitivitás: H1 ~ H2 és H2 ~ H3 teljesüléséből
H1 ~ H3 következik
(ha
φ(x) : H1→H2
és
ψ(x) : H2→H3
bijektív leképezések, akkor az
η(x)=(ψ∘φ)(x) : H1→H3
összetett függvény⇒ szintén bijektív leképezés).
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.
Az azonos ekvivalenciaosztályokból választott osztályreprezentánsok kardinális száma megegyezik.
A különböző ekvivalenciaosztályokból választott osztályreprezentánsok kardinális száma különböző.
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 kis elemszámú halmazok elemeinek elnevezése és "megszámlálása"), mind pedig a véges halmazok kardinális számának a fogalma (az "azonos elemszám" felismerése) alkalmas a természetes számok fogalmának bevezetésére. Azonban a tizes számrendszert alapul véve az első 10-12 szám (a decimális számjegyek, esetleg a 10-es szám stb.) bevezetése után mindkét esetben előbb-utóbb 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 későbbiekben 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
az 'A' halmaz számosságilag ekvivalens a 'B' halmaz egy valódi Bs⊂B részhalmazával (azaz A~Bs, ill. |A|=|Bs| teljesül) és
az 'A' halmaz számossága különbözik a 'B' halmaz számosságától (azaz |A|≠|B|).
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:
irreflexivitás: |A|≮|A| (vagyis egy halmaz sosem kisebb számosságú, mint önmaga);
aszimmetria: ha |A|<|B| teljesül, akkor ebből |B|≮|A| teljesülése következik;
tranzitivitás: ha |A|<|B| és |B|<|C| teljesül, akkor ebből |A|<|C| teljesülése következik.
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ő ekvivalenciaosztá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:
a természetes számok halmaza (ℕ)
a páros számok halmaza
a hárommal osztható számok halmaza
a néggyel osztható számok halmaza
...
a primszámok halmaza
a pozitív természetes számok halmaza (ℕ+)
egy sn:ℕ+→ℝ szigorúan monoton növekvő (vagy csökkenő) számsorozat⇒ értékkészlete (azaz az Rng(sn)⊂ℝ halmaz)
(Mivel a számsorozat elemei között azonosak is lehetnek, tetszőleges sorozat esetén csak annyit állíthatunk, hogy értékkészlete megszámlálható, azaz véges vagy megszámlálhatóan végtelen.)
az egész számok halmaza (ℤ)
a racionális számok halmaza (ℚ)
Példák nem megszámlálhatóan végtelen halmazokra:
a valós számok halmaza (ℝ) (a valós számok halmazának számosságát kontinuum számosságnak nevezzük; bizonyítható, hogy
|ℕ|≠|ℝ| (emiatt |ℕ|<|ℝ|), valamint
|2ℕ|=|ℝ|,
azaz a valós számok számossága megegyezik a természetes számok hatványhalmazának a számosságával⇒);
egy egyenes (szakasz, kör stb.) pontjainak halmaza.
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:
Egy véges és egy megszámlálhatóan végtelen halmaz uniója megszámlálhatóan végtelen halmaz.
Véges számú véges és egy megszámlálhatóan végtelen halmaz uniója megszámlálhatóan végtelen halmaz.
Két megszámlálhatóan végtelen halmaz uniója megszámlálhatóan végtelen halmaz.
Véges számú megszámlálhatóan végtelen halmaz uniója megszámlálhatóan végtelen halmaz.
Két megszámlálhatóan végtelen halmaz direkt szorzata megszámlálhatóan végtelen halmaz.
Véges számú megszámlálhatóan végtelen halmaz direkt szorzata megszámlálhatóan végtelen halmaz.
Egy megszámlálhatóan végtelen 'A' halmaz elemeiből összeállítható összes véges sorozatok (azaz az 'A' halmaz véges An hatványainak⇒) 'S' halmaza megszámlálhatóan végtelen halmaz (vö. Dringó-Kátai 1986: 114-115).
É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:
A1={a11,a12,a13,...}
A2={a21,a22,a23,...}
A3={a31,a32,a33,...}
...
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
s1=a11
s2=a12
s3=a21
s4=a31
s5=a22
s6=a13
s7=a14
s8=a23
s9=a32
...
Megállapíthatjuk a következőket:
Az 'A' halmaz az sn számsorozat értékkészlete, azaz
A=Rng(sn)
teljesül.
Mivel az sn számsorozat egy részsorozata az A1 halmaz elemeiből áll, amely megszámlálhatóan végtelen, továbbá A1⊆A teljesül, az 'A' halmaz számossága nem lehet kisebb, mint A1 számossága.
Ha az Ai halmazok diszjunktak, akkor sn bijektív leképezést valósít meg ℕ+ és az 'A' halmaz között, tehát 'A' számossága megegyezik ℕ+ számosságával. 'A' tehát megszámlálhatóan végtelen halmaz.
Ha az A1, A2, A3, ... halmazoknak vannak azonos elemei, akkor az
sn
számsorozat elemeinek meghatározásakor⇒ egyszerűen hagyjuk ki az ismétlődő elemeket, vagyis azokat a sorozatelemeket, amelyek egy korábbi elemmel megegyeznek. Az így kapott sorozat értékkészlete megegyezik az 'A' halmazzal (mivel egy halmaznak nincsenek azonos elemei), és mivel a sorozat elemei különbözőek, sn bijektív leképezést valósít meg ℕ+ és az 'A' halmaz között.
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.
A természetes számok véges halmazok számosságai. (Szendrei 1975: 47)
Két véges halmaz számosságát (vagyis elemszámát, az elemek "darabszámát") kölcsönösen egyértelmű leképezésekkel hasonlíthatjuk össze.
A természetes szám fogalmának megalapozásához legfontosabb a korábban bevezetett Σ halmazrendszeren⇒ értelmezett "ugyanannyi eleme van" reláció megállapítása különböző módon kiválasztott (véges) halmazokra (vö. Bonifert-Kovácsné Győri 1987: 59).
Az ugyanannyi elemmel rendelkező véges halmazok számosság szerint azonos ekvivalenciaosztályba tartoznak. Tehát a számosság az azonos ekvivalenciaosztályokba tartozó halmazok közös tulajdonsága. Ha eltekintünk a halmazok egyéb tulajdonságaitól, egy absztrakciót hajtunk végre. Így vezethetjük be a természetes számokat mint a halmazok kardinális számát.⇒
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.
Az egyes halmazelemeket elrendezzük és az elemeket megszámozzuk, azaz sorszámot rendelünk hozzájuk.
A természetes számok bevezetése sorszámként elősegíti a természetes számok elnevezésének és sorrendjének a megtanulását.
A halmaz számosságát a rendezett halmaz utolsó elemének a sorszáma adja.
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)
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.
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.
Obádovics J. Gyula 1972. Matematika. Középiskolai, technikumi tanulók, egyetemi hallgatók és technikusok számára, gyakorlati alkalmazásokkal. Budapest: Műszaki K.
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.
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ó.
