Diszkr´et matematika I. (2007. szept. 4. 14-17) 1 Dr. Cz´ edli G´ abor, egyetemi tan´ ar 2007. szeptember 12.
1 Az
el˝oad´ as ”nyers” v´ altozata, sajt´ ohib´ ak lehets´egesek (´es az is lehets´eges, hogy hetekkel, h´ onapokkal k´es˝obb jav´ıtok ki egy-egy sajt´ohib´ at). Figyelem: csak r´eszben (b´ar nagyr´eszt) tartalmazza az el˝oad´ ason elhangzottakat! Az el˝ oad´ as f˝ ok´ent az al´abbi k¨ onyveken ´ alapul: Szendrei Agnes: Diszkr´et matematika ´es Szab´ o L´ aszl´ o: Bevezet´es a line´ aris algebr´ aba. Ez a f´ ajl a f´ oli´ akra tagolt el˝oad´ as automatikusan oldalakra t¨ ordelt v´ altozata, az automatikus a´tt¨ ordel´es sz´amos eszt´etikai hib´ aj´ aval.
1 el˝ oad´ as Tudnival´ ok a tant´ argyr´ ol http://www.math.u-szeged.hu/∼czedli/ Itt olvashat´o az el˝oad´asok teljes anyaga” (pl. ez is), a´ltal´aban az el˝oad´ast k¨ovet˝o napon, az el˝oad´asok v´azlata, a ” z´arthelyi dolgozatokkal, a vizsg´aval kapcsolatos tudnival´ok (id˝opont, pontoz´as), vizsgafeladatsor-mint´ak, az egyes vizsganapok statisztik´aja (a m´ ult f´el´eviek is), s˝ot a vizsgaid˝oszakban az o¨sszes kor´abbi vizsga-feladatsorok is, az anyag folyamatosan friss¨ ul.
Hogyan lehet a ´tmenni a vizsg´ an?
6 kredit = 180 munka´ora ! — k¨ozepes k´epess´egekkel k¨ozepes ´erdemjegyhez! De ha valaki csak annyit tesz, hogy r´esztvesz minden ´or´an (14 · 4 = 56 o´ra), k´et teljes napot tanul a zhra (20 o´ra) ´es m´eg o¨t teljes napot a vizsgaid˝oszakban (50 o´ra), azaz o¨sszesen 126 munka´or´at ford´ıt a t´argyra, ´es m´egis a´tmegy, akkor vagy kor´abban m´ar tanult hasonl´ot, vagy kiemelked˝oen tehets´eges, vagy egy val´osz´ın˝ utlen esem´eny k¨ovetkezett be. Tov´abb´a: (a magol´os” t´argyakkal ellent´etben) az u ´j fogalmakat, m´odszereket meg kell ´erteni, haszn´alatukat be kell gyako” rolni, erre az o´r´ak l´atogat´as´an t´ ul, rendszeresen id˝ot kell ford´ıtani; a vizsgaid˝oszakban m´ar k´es˝o hozz´afogni. A vizsg´an f˝oleg
feladatok lesznek! CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Az el˝oad´asokon is sok-sok feladatot fogunk megoldani! (T¨obbet, mint a gyakorlaton.) A gyakorlaton max. 50, a vizsg´an max. 60 pontot lehet szerezni. El´egs´eges ⇐⇒ a kett˝o o¨sszege legal´abb 50, de a 20 alatti esz!!! =⇒ aki f´el´ev k¨ozben nem ´eri el a 20 pontot, annak — ha a´t akar menni — biztosan t¨ obbet gyakorlati pontsz´am elv´ kell dolgoznia (´es t¨obbsz¨or vizsg´aznia), mintha f´el´ev k¨ozben szorgalmas lett volna. A pontoz´as (bonyolult) r´eszletei a honlapomon. K¨ otelez˝ o-e el˝ oad´ asra, gyakorlatra j´ arni? Ha most kong a terem az u¨ress´egt˝ol, j¨ov˝ore nem kapom meg. abb egyharmada jelen legyen! Ez esetben viszonz´asul az Ez´ert elv´arom, hogy minden alkalommal a hallgat´os´ag legal´ al´abbiakat ny´ ujtom: (1) Az el˝oad´as anyag´at t¨om¨orebb (nem kivet´ıt´esre nagy´ıtott) form´aban is k¨ozz´eteszem. (2) A tavaszi ara. f´el´evben is meghirdetem a t´argyat csak vizsg´ Ellenkez˝o esetben nem — ´es a statisztika szerint ez legink´abb hi´anyz´oknak lesz h´atr´anyos. Aki pedig gyakorlatra nem j´ar ´es ott nem szerez 20 pontot, arra a kor´abban mondottak szerinti t¨obbletmunka v´ar. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
1
N´eh´any mintafeladat megold´as´ara (vagy annak egyes r´eszleteire) nem jut(ott) id˝o az o´r´an, ezek lila sz´ınnel szerepelnek; tanulm´anyoz´asuk nagym´ert´ekben k¨onny´ıti a vizsg´ara val´o felk´esz¨ ul´est. A mintafeladatokat lesz´am´ıtva lila sz´ınnel csak olyan megjegyz´eseket ´es ´erdekess´egeket adok k¨ozre, amelyeket (b´ar a dolgok meg´ert´es´et n´eha k¨onny´ıthetik) NEM KELL megtanulni!!!, s˝ot gyakran nem is ´erdemes.
Teljes indukci´ o Az indukci´ o alapvet˝o r´esze a gondolkod´asunknak: sok azonos esetb˝ol arra k¨ovetkeztet¨unk, hogy most m´ar mindig u´gy lesz. Ez azonban m´eg a mindennapi ´eletben sem ´alja meg a hely´et, a matematik´aban pedig m´eg kev´esb´e! 0 1 2 3 P´eld´aul Pierre Fermat (1601-1665) megvizsg´alta az al´abbi sz´amokat: 22 + 1 = 3, 22 + 1 = 5, 22 + 1 = 17, 22 + 1 = 257, 4 ´gy tal´alta, hogy ezek a sz´amok mind pr´ımsz´amok. (Az´ota is Fermat-pr´ımeknek nevezik ezeket.) Indukt´ıvan 22 + 1 = 65537, ´es u n armely n ≥ 0 eg´esz kitev˝ore a 22 + 1 sz´am pr´ım. A helyzet ezzel szemben az, hogy t´evedett, gondolkodva u ´gy v´elte, hogy b´ 5 hiszen m´ar a k¨ovetkez˝o sz´am sem pr´ım: 22 + 1 = 4294967297 = 641 · 6700417, s˝ot egyetlen olyan n ≥ 5 eg´esz sz´am sem n ismeretes, amelyr˝ol tudn´ank, hogy 22 + 1 pr´ım. Itt ´es a f´el´ev sor´an a tov´abbiakban lila sz´ınnel ´ırt r´eszek is el˝ofordulnak. A lila sz´ınnek k´etf´ele jelent´ese lehet. Egyr´eszt lila sz´ınben jelennek meg a tananyaghoz kapcsol´od´o olyan ismeretek ´es ´erdekess´egek, amelyeket a vizsg´an nem k´erek sz´amon. Ezeket — b´ar esetenk´ent az anyag meg´ert´es´et k¨onny´ıthetik — nem kell megtanulni. M´asr´eszt n´eh´any kidolgozott feladat is lila sz´ınben ker¨ ul k¨ozl´esre — csak ´ır´asban, sz´oban nem. Minthogy a vizsg´ara ´es a gyakorlatra val´o felk´esz¨ ul´eshez elengedhetetlen nagysz´am´ u feladat megold´asa, a lila feladatok eset´en tan´acsos a feladat o¨n´all´o megold´asa ´es az itt k¨oz¨olt megold´assal val´o o¨sszehasonl´ıt´asa. Teh´at ez a fajta, sok esetb˝ol az o¨sszes esetre k¨ovetkeztet˝o” indukci´o bizony´ıt´asi m´odszerk´ent nem ´allja meg a hely´et! (Arra ” unk valamit, amit szerencs´es esetben valahogy be is lehet bizony´ıtani.) viszont kiv´al´oan alkalmas, hogy megsejts¨ ´ Alland´o jel¨ol´es: a pozit´ıv eg´esz sz´amok {1, 2, 3, . . .} halmaz´at N, a nemnegat´ıv eg´esz sz´amok {0, 1, 2, 3, . . .} halmaz´at N0 fogja jel¨olni. Eredetileg az N jel¨ol´es a natural number”, azaz a term´eszetes sz´am kezd˝obet˝ uj´eb˝ol ered, de a hib´as iskolai ok” tat´as k´et´ertelm˝ uv´e tette a term´eszetes sz´am” elnevez´est, ez´ert az el˝oad´ason ker¨ ulni fogjuk minden olyan esetben, amikor ” nem mindegy, hogy N-r˝ol vagy N0 -r´ol van sz´o. Szem´elyes ´all´aspontom szerint a nulla nem term´eszetes sz´am, hiszen az emberis´eg csak ´evezredekkel a pozit´ıv t¨ortekkel val´o sz´amol´asi rutin ut´an vezette be a nulla fogalm´at, de vannak m´ask´ent v´eleked˝ok is. ot haszn´aljuk. A Matematikai bizony´ıt´ask´ent az indukci´os gondolkod´as helyett a (matematikai) teljes indukci´ ıt´ asi m´ odszer. Legyen H(n) egy n-t˝ol f¨ugg˝o matematikai a´ll´ıt´as. P´eld´aul H(n) jel¨olheti teljes indukci´o teh´at egy bizony´ 2
azt, hogy az els˝o n pozit´ıv eg´esz sz´am o¨sszege n(n + 1)/2”. A teljes indukci´o minden n-re H(n)” szerkezet˝ u ´all´ıt´asok ” ” bizony´ıt´as´ara szolg´al. A konkr´et p´elda eset´en teh´at a minden n pozit´ıv eg´esz sz´amra az els˝o n pozit´ıv eg´esz sz´am o¨sszege ” n(n+1)/2” az az a´ll´ıt´as, amely teljes indukci´oval bizony´ıthat´o. M´eg nem mondtuk meg, mi a teljes indukci´o (csak azt, hogy mire val´o), de el˝orebocs´atjuk, hogy az al´abbi t´etelen alapul: 1. T´ etel. B´armely nem¨ ures, term´eszetes sz´amokb´ ol ´all´ o halmaznak van legkisebb eleme. Szeml´eletesen ez a t´etel evidens: ha H egy ilyen halmaz, akkor — mivel nem¨ ures — vehet¨ unk bel˝ole egy k elemet. Az 1,2,. . . , k sz´amok csak v´eges sokan vannak, ´ıgy lesz k¨ozt¨ uk egy legels˝o, amelyik H-ban van. Ez lesz H legkisebb eleme. ´ armely, a ∃ a l´ etezik Erdemes m´ar most bevezetni a k¨ovetkez˝o (egyel˝ore gyors´ır´asi jelk´ent haszn´alt) jeleket. A ∀ a b´ r¨ovid´ıt´ese lesz. A ∀ az angol All, Any”, a ∃ pedig az Exists” kezd˝obet˝ uj´enek elforgatottja. Ezt a k´et jelet kvantoroknak ” ” is szok´as nevezni. Gyakran haszn´alt szinon´ım´ak a ∀ u ´n. univerz´ alis kvantorra: minden”, mindegyik”, b´armely”, ” ” ” tetsz˝oleges”. ” Gyakran haszn´alt szinon´ım´ak a ∃ u ´n. egzisztenci´ alis kvantorra: l´etezik olyan”, van olyan”, tal´alhat´o olyan. ” ” ” Teh´at a teljes indukci´o ∀ n-re H(n)” szerkezet˝ u ´all´ıt´asok bizony´ıt´as´ara val´o. Az al´abbi t´etel nemcsak t´etel, hanem egy´ uttal ” azt is megmondja, hogyan kell teljes indukci´oval bizony´ıtani. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
2. T´ etel. Legyen H(n) egy n-t˝ol f¨ ugg˝o ´all´ıt´as. Ha egyr´eszt H(1) igaz, m´asr´eszt b´armely n ∈ N-re H(n) teljes¨ ul´es´eb˝ol k¨ ovetkezik H(n + 1) teljes¨ ul´ese, akkor igaz a ∀n ∈ N-re H(n)” ´all´ıt´as. ” Megjegyz´es: N helyett az N0 halmaz vagy ak´ar mondjuk a {7, 8, 9, . . .} halmaz is szerepelhetett volna a fenti t´etelben, de ekkor persze H(1) helyett H(0)-at, illetve H(7)-et (azaz a legkisebb ´ertelmes esetet) kellett volna mondanunk. 3. T´ etel. (A teljes indukci´o m´asik alakja) Legyen H(n) egy n-t˝ol f¨ ugg˝o a´ll´ıt´as. Ha b´ armely n ∈ N eset´en H(1), H(2), . . ., H(n − 1) egy¨ uttes teljes¨ ul´es´eb˝ol k¨ ovetkezik H(n) teljes¨ ul´ese, akkor igaz a ∀n ∈ N-re H(n)” ´ all´ıt´as. ” Ezen ut´obbi t´etel bizony´ıt´asa Ha a felt´etel ellen´ere ∀n ∈ N-re H(n)” m´egsem lenne igaz, akkor az A = {n ∈ N : H(n) ” hamis} halmaz nem lenne u ¨res. Ez´ert lenne legkisebb eleme, jel¨olje azt k. Ekkor az i = 1, 2, . . . , k − 1 elemekre (ezek sz´ama 3
0 is lehet) i ∈ / A, ´ıgy ezekre H(i) teljes¨ ul, ez´ert (n = k szereposzt´asban) a t´etel felt´etel´eb˝ol kapjuk, hogy H(k) is teljes¨ ul. Ez azonban ellentmond k ∈ A-nak. Q.e.d. (A Q.e.d. a quod erat demonstrandum” r¨ovid´ıt´esek´ent a bizony´ıt´as v´eg´et jelzi.) ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A fenti k´et t´etel a teljes indukci´os bizony´ıt´as k´et form´aj´at fogalmazza meg, hol az egyiket, hol a m´asikat tudjuk alkalmazni. Most l´assunk k´et konkr´et p´eld´at. Feladat: Bizony´ıtsuk be, hogy tetsz˝oleges n term´eszetes sz´amra n3 + 5n oszthat´o 6-tal. uk, Megold´ as: A feladatb´ol nem der¨ ul ki, hogy ∀n ∈ N-re vagy ∀n ∈ N0 -ra vonatkozik-e a feladat — most az ut´obbit tekintj¨ mert egyr´eszt u ´gy t¨obbet bizony´ıtunk, m´asr´eszt u ´gy k¨onnyebb a bizony´ıt´as. Els˝o l´ep´es: a legkisebb esetre bel´atjuk. Ez evidens, hiszen 03 + 5 · 0 = 0, ami csakugyan oszthat´o 6-tal. os) l´ep´es: Legyen n ∈ N0 tetsz˝oleges, ´es tegy¨uk fel, hogy n3 + 5n oszthat´o 6-tal. (Ez az u´n. M´asodik (az u ´n. indukci´ indukci´ os hipot´ ezis.) Az indukci´os hipot´ezist felhaszn´alva azt kell bel´atnunk, hogy (n + 1)3 + 5(n + 1) oszthat´o 6-tal. Sz´amoljunk: (n + 1)3 + 5(n + 1) = n3 + 3n2 + 3n + 1 + 5n + 5 = (n3 + 5n) + 3n(n + 1) + 6. os hipot´ ezis miatt oszthat´o 6-tal. A m´asodik tag, a 3n(n + 1) pedig az´ert, mert n ´es n + 1 Itt az els˝o tag az indukci´ k¨oz¨ ul az egyik p´aros. A harmadik tag ´eppen 6, ami oszthat´o hattal. Mivel hattal oszthat´o sz´amok o¨sszege is hattal oszthat´o, bel´attuk, hogy az a´ll´ıt´as n + 1-re is igaz. Q.e.d. n−1 Feladat: Bizony´ıtsuk be, hogy b´armely n pozit´ıv eg´esz sz´amra az n-edik pr´ımsz´am legfeljebb 22 . Megold´ as: Itt a teljes indukci´o m´asodik alakj´at alkalmazzuk (az els˝ovel el´eg rem´enytelen lenne). Az i-edik pr´ımsz´amot 1−1 uk fel, hogy p1 ≤ 22 , jel¨olje pi . Teh´at p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, stb. Legyen n ∈ N tetsz˝oleges, ´es tegy¨ 2−1 (n−1)−1 (most ez az indukci´os hipot´ezis). (Vigy´azat ´es k´es˝obb ne feledj¨ uk: ha n = 1, akkor az indukci´os p2 ≤ 22 , . . ., pn−1 ≤ 22 hipot´ezis u ¨res”, azaz semmit se mond. Azaz most sem ker¨ ulhetj¨ uk el, hogy n = 1-re az a´ll´ıt´ast igazoljuk.) Azt kell az indukci´os ” n−1 hipot´ezis felhaszn´al´as´aval bel´atnunk, hogy pn ≤ 22 . Eddig nem kellett semmif´ele ¨otlet, de most kelleni fog: Tekints¨ uk az m := p1 p2 . . . pn−1 + 1 sz´amot, ´es jel¨olje q az m egyik pr´ımoszt´oj´at. (A kor´abbi tanulm´anyok szerint m pr´ımt´enyez˝ok szorzat´ara bonthat´o, teh´at van ul¨onbs´ege, azaz az 1 = m − p1 p2 . . . pn−1 is oszthat´o pr´ımoszt´oja.) Ha q = p1 lenne, akkor m is ´es p1 p2 . . . pn−1 is, teh´at ezek k¨ lenne q-val, ami nem lehets´eges. Teh´at q = p1 . Hasonl´oan kapjuk, hogy q = p2 , . . ., q = pn−1 . Ez´ert q a pn , pn+1 , . . . tov´abbi
4
pr´ımsz´amok k¨oz¨ ul ker¨ ul ki, teh´at pn ≤ q ≤ m. Az indukci´os hipot´ezist a most k¨ovetkez˝o sz´amol´asban fogjuk haszn´alni: pn ≤ m = p1 p2 . . . pn−1 + 1 ≤ (t´enyez˝onk´ent az ind. hip.-t alkalmazva) 1−1 2−1 (n−1)−1 +1= ≤ 22 · 22 · · · · 22 20 21 2n−2 + 1 = (azonos alap´ u hatv´anyok szorz´asa:) 2 · 2 ··· · 2 0 1 n−2 = 22 +2 +···+2 + 1 = (m´ertani sor o¨sszege:) n−1 22 −1 + 1 ≤ (most az 1-et n¨ovelem, l. () lent) n−1 n−1 22 −1 + 22 −1 = n−1 n−1 ≤ 2 · 22 −1 =22 . (): Ellen˝orizni kell a fenti gondolatmenetben, hogy n = 1 eset´en is m˝ uk¨odik-e (amikor az indukci´os hipot´ezis semmitmond´o): n−1 n−1 n−1 igen, mert az u ¨resszorzat = 1 ≤ 22 −1 ´es 1 ≤ 22 −1 . Ezzel pn ≤ 22 −1 igazol´ast nyert. Q.e.d. Feladat o ¨n´ all´ o gyakorl´ asra: Mutassuk meg teljes indukci´oval, hogy 1 · 4 + 2 · 7 + · · · + n(3n + 1) = n(n + 1)2 . (Az ilyen t´ıpus´ u feladatokat u ´gy kell ´ertelmezni, hogy b´armely n ∈ N-re!) Feladat o ¨n´ all´ o gyakorl´ asra: Mutassuk meg teljes indukci´oval, hogy ha egy pozit´ıv eg´esz sz´am 3n egyforma sz´amjegyb˝ol ´all, akkor ez a sz´am oszthat´o 3n -nel.
Rekurz´ıv defin´ıci´ o Gyakran nem bizony´ıtani, hanem defini´alni akarunk valamit. A teljes indukci´o p´arja a rekurz´ ıv defin´ıci´ o. Ez a k¨ovetkez˝ot jelenti: minden n ∈ N-re szeretn´enk egy n-t˝ol f¨ ugg˝o fogalmat — jel¨olje azt F (n) — defini´alni. Ehhez defini´aljuk a fogalmat n = 1-re, azaz defini´aljuk F (1)-et, majd ezt k¨ovet˝oen megadjuk azt, hogy tetsz˝oleges n-re hogyan kapjuk F (n + 1)-et F (n)-b˝ol (´es n-b˝ol). Term´eszetesen a rekurz´ıv defin´ıci´onak is megvan a m´asik alakja, amikor nem az el˝oz˝o fogalom felhaszn´al´as´aval defini´aljuk osszes el˝ oz˝ o felhaszn´al´as´aval. Tov´abb´a — ´ertelemszer˝u m´odos´ıt´assal — N helyett N0 -at is monda k¨ovetkez˝ot, hanem az ¨ hattunk volna. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
5
P´ elda Legyen f1 = 1, f2 = 1, ´es n > 1 eset´en fn+1 = fn−1 + fn . Ezzel rekurz´ıv m´odon defini´altuk fn -et minden n ∈ Nre, azaz rekurzi´oval defini´altunk egy f1 , f2, f3 , . . . v´egtelen sz´amsorozatot. Csakugyan, f3 = f1 + f2 = 2, f4 = f2 + f3 = 3, ugg´es birtok´aban ak´armeddig folytathatn´ank, a sorozat ak´armelyik tagj´at f5 = 5, f6 = 8, stb. L´athat´o, hogy a rekurz´ıv o¨sszef¨ egy´ertelm˝ uen kisz´am´ıthatn´ank, teh´at a sorozatot t´enyleg defini´altuk. Ez a h´ıres-nevezetes Fibonacci-sorozat.
Informatikai vonatkoz´ asok Rekurzi´o n´elk¨ ul (trivi´alis eseteket lesz´am´ıtva) nem lehet programozni! CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Bizony´ıt´as n´elk¨ ul gyakran nem lehet el˝ ore tudni valamit! M´arpedig j´o lenne. Pl. legyen an egy valamilyen (m´eg meg nem ´ırt) program fut´asideje n m´eret˝ u input eset´en. A hosszas (ak´ar h´onapokig tart´o) program´ır´as el˝ott ´erdemes sz´amolgatni, n ul nagy (pl. an ≥ 104 ), akkor hozz´a se fogjunk programot ´ırni, u ´gy becsl´est v´egezni, hogy kb. mekkora is lehet an ? Hiszen ha t´ se fut le. Ink´abb jobb algoritmust keress¨ unk a probl´em´ara. Teh´at a programoz´assal egy¨ utt j´ar az el˝ozetes becsl´es, sz´amol´as, ´es annak egyik kell´eke a teljes indukci´os bizony´ıt´as.
Didaktikai megjegyz´ esek 6
El˝oad´ason nem az´ert bizony´ıtunk be egy-k´et dolgot, mert k´etelked¨ unk el˝odeink (Euklidesz, Fermat, Euler, Gauss, stb.) eredm´enyeiben, hanem hogy gyakoroljuk az u ´jonnan megismert fogalmakat, t´eteleket, hogy hozz´aszokjunk azok haszn´alat´ahoz. ´ M´asr´eszt — ha egyszer meg´ertett¨ uk — a bizony´ıt´as seg´ıt majd a t´eteleket, defin´ıci´okat felid´ezni, pontosan felid´ezni. Es persze a bizony´ıt´asokban megismert fog´asok gyakran kellenek a feladatok megold´as´ahoz. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
M˝ uveletek halmazokkal A halmaz az axiomatikus halmazelm´elet alapfogalom (´epp´ ugy, mint a geometri´aban a pont), nem defini´alj´ak — de az axiomatikus halmazelm´elet t´ ul bonyolult a jelen kurzushoz. Ez´ert mi a szeml´eletes, u ´n. na´ıv halmazfogalommal ismerked¨ unk meg — a legt¨obb c´elra ez elegend˝o a matematik´aban, ´es minden c´elra elegend˝o a matematika alkalmaz´asaiban. Halmazon elemek egy´ ertelm˝ uen meghat´ arozott ´es nem t´uls´agosan nagy ¨ osszess´ eg´ et ´ertj¨uk. Azt nem defini´aljuk — ez az axiomatikus halmazelm´elet dolga lenne — hogy mi sz´am´ıt t´ uls´agosan nagynak. Pl. az o¨sszes halmazb´ol a´ll´o o¨sszess´eg t´ uls´agosan nagy. A mi o¨sszess´egeink sose lesznek t´ uls´agosan nagyok, ez´ert a k´es˝obbiekben ezzel a k´erd´essel nem t¨or˝od¨ unk. √ armely x-re (a kismacsk´at´ol a 2-ig, a tavalyi jelesre vizsg´azott hallgat´okt´ol a leghosszabb Fontos, hogy b´ ford´ıt´oprogramig, teh´at b´armire), objekt´ıven meghat´arozott legyen, hogy x eleme-e vagy nem eleme a k´erd´eses ¨osszess´egnek! Pl. a jelenlev˝ok k¨oz¨ ul a szorgalmas hallgat´ok o¨sszess´ege nem alkot halmazt, hiszen a szorgalom meg´ıt´el´ese szubjekt´ıv, mindenki m´ast ´es m´ast ´ert alatta. Az ”egy´ertelm˝ uen meghat´arozott” az objektivit´asra utal, teh´at arra, hogy mindenki pontosan ugyanazon x-eket tekintse a ¨osszess´eg elemeinek. Ez persze nem jelenti azt, hogy minden egyes x eset´en t´enylegesen el tudjuk (most vagy k´es˝obb) d¨onteni, hogy x eleme-e a k´erd´eses halmaznak. P´eld´aul legyen A azon (i, j) eg´esz koordin´at´aj´ u pontok o¨sszess´ege, amelyekre 1 ≤ i ≤ 8, 1 ≤ j ≤ 2 ´es kezd˝ol´ep´esk´ent az i-edik oszlopbeli gyaloggal j-t l´epve vil´agosnak a sakkban nyer˝o strat´egi´aja van. Ekkor A halmaz, de pl. az x = (4, 2)-r˝ol nem tudjuk jelenleg eld¨onteni, hogy hozz´atartozik-e A-hoz. Jel¨ ol´ es: x ∈ A jel¨oli azt, hogy x eleme az A halmaznak (azaz x hozz´atartozik A-hoz). Ahogy kor´abban is, a halmazt t¨obbnyire a {, } z´ar´ojelek seg´ıts´eg´evel adjuk meg. Erre p´eld´ak: {2, 3, 5, 7} az egyjegy˝ u pr´ımsz´amok halmaza. {2, 3, 4, 5, . . .} az 1-n´el nagyobb eg´esz sz´amok halmaza. Legal´abb ilyen gyakori, hogy a halmazt u´n. ´altal´anos elem ´es defini´al´o tulajdons´ag seg´ıts´eg´evel adjuk meg. P´eld´ak: {x ∈ N : ∃y ∈ N, hogy x = 3y} a h´arommal oszthat´o pozit´ıv eg´eszek halmaza. u egys´egk¨or bels˝o pontjainak halmaza. {(x, y) : x ´es y val´os sz´am ´es x2 + y 2 < 1} az orig´o k¨oz´eppont´ 7
K´et halmazt akkor ´es csak akkor tekint¨ unk egyenl˝ onek, ha pontosan ugyanazok az elemeik. Ebben az is benne van, am´ıt. P´eld´aul {1, 2, 3, 1, 2, 2} ´es {1, 2, 3} ugyanazok a halmazok. hogy halmaz eset´en minden elem csak egyszer sz´ ´ Alland´ o jel¨ol´es n´eh´any fontosabb halmazra:N, N0 : m´ar l´attuk. Z = {0, 1, −1, 2, −2, 3, −3, . . .} az eg´esz sz´amok halmaza. R a val´os sz´amok halmaza. ¨ reshalmazt ∅ jel¨oli. Ennek nincs eleme. Fel´ırhat´o sokf´elek´eppen, pl. {x ∈ R : x2 = −1}. Az im´ent a hat´arozott Az u ¨ reshalmaz van. Csakugyan, b´armelyik k´et u¨res halmaznak ugyanan´evel˝ot az´ert haszn´alhattuk, mert csak egyetlen u zok az elemei (tudniillik nincsenek), ez´ert a kor´abbiak szerint b´armely k´et u ¨reshalmaz egyenl˝o. eszhalmaza A-nak — ennek jel¨ol´ese: Defin´ıci´ o: Legyenek A ´es B tetsz˝oleges halmazok. Akkor mondjuk, hogy B r´ odi r´ eszhalmazr´ ol B ⊆ A —, ha b´armely B-beli elem egy´ uttal A-nak is eleme. Ha B ⊆ A ´es emellett A = B, akkor val´ besz´el¨ unk; ennek jel¨ol´ese: B ⊂ A. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Az mindig igaz, hogy ∅ ⊆ B ´es B ⊆ B. B-t ´es az u ¨reshalmazt a B halmaz trivi´ alis r´ eszhalmazainak nevezz¨uk. Tov´abbi p´eld´ak: N ⊆ N0 , N ⊆ R, Z ⊆ R. Az al´abbi t´etel a defin´ıci´ok k¨ozvetlen k¨ovetkezm´enye: 4. T´ etel. Legyen A, B ´es C tetsz˝ oleges halmaz. Ekkor (1) ha A ⊆ B ´es B ⊆ C, akkor A ⊆ C. (´ un. tranzitivit´ as) (2) ha A ⊆ B ´es B ⊆ A, akkor A = B. (´ un. antiszimmetria)
uveletekkel kapunk: Adott A, B halmazokb´ol u ´jabbakat az u ´n. halmazm˝ ´ ni´ oja, m´as sz´oval egyes´ıt´ese. Itt ´es a matematik´aban a´ltal´aban A ∪ B := {x : x ∈ A vagy x ∈ B}, ez a k´et halmaz u a vagy” sz´ot nem a h´etk¨oznapi kiz´ar´o vagy” ´ertelm´eben haszn´aljuk, hanem matematikai ´ertelemben, teh´at most azt jelenti, ” ” hogy x ∈ A ´es x ∈ B k¨oz¨ ul legal´abb az egyik teljes¨ ul, teh´at ak´ar mindkett˝o is teljes¨ ulhet egyszerre! Ha tetsz˝oleges X halmazra am´ at, akkor az u´ni´o ´ıgy is defini´alhat´o: |X| jel¨oli az X elemsz´ A1 ∪ A2 = {x : |{i : x ∈ Ai}| ≥ 1}. Szok´as a halmazokat s´ıkbeli tartom´anyokkal, azaz u ´n. Venn-diagrammokkal szeml´eltetni.(Ez nagyon helyes, csak tudnunk kell, hogy nem mindegyik halmaz f´er el a s´ıkon”, ´es m´eg ha el is f´er, a Venn-diagramm nem mindig szeml´elteti ” az a´ltal´anoss´agot, teh´at Venn-diagrammokkal egzakt bizony´ıt´as nem adhat´o!) Az u ´ni´o m˝ uvelete Venn-diagrammal ´ıgy szeml´eltethet˝o:
8
A B
A∪B A metszet vagy m´as sz´oval k¨ oz¨ os r´ esz defin´ıci´oja: A B
A ∩ B = {x : x ∈ A ´es x ∈ B} A k´et halmaz k¨ ul¨ onbs´ eg´ enek defin´ıci´ oja ´ es jel¨ ol´ ese:
A B A \ B = {x : x ∈ A, x ∈ / B} CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A k´et halmaz szimmetrikus differenci´ aja: A B
AB = (A \ B) ∪ (B \ A), amely persze u ´gy is defini´alhat´o, mint azon elemek halmaza, amelyek a k´et halmaz k¨oz¨ ul pontosan egyben vannak benne. A halmazm˝ uveletek sz´amos azonoss´agnak tesznek eleget. Ezek egy r´esze olyan, mint a sz´amokra vonatkoz´o o¨sszead´as ´es szorz´as azonoss´agai, de vannak ett˝ol elt´er˝oek is: 9
5. T´ etel. Tetsz˝oleges A, B, C halmazokra ´erv´enyesek az al´abbi azonoss´agok: A ∪ B = B ∪ A, A ∩ B = B ∩ A, AB = BA (kommutativit´as); (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C), (AB)C = A(BC) (asszociativit´ as); A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (BC) = (A ∩ B)(A ∩ C) (disztributivit´ as); A ∩ (A ∪ B) = A, A ∪ (A ∩ B) = A (abszorptivit´ as). Ismeretes, hogy a sz´amok k¨or´eben a szorz´as disztribut´ıv az o¨sszead´asra: a · (b + c) = (a · b) + (a · c). (Sz´and´ekosan tett¨ unk ki olyan z´ar´ojeleket, amelyeket a k¨ozmeg´allapod´as ´ertelm´eben el szoktunk hagyni.) Ennek mint´aj´ara mondjuk (a t´etel ul a metszet a szimmetrikus szerint), hogy a metszet disztribut´ıv az egyes´ıt´esre, az egyes´ıt´es disztribut´ıv a metsz´esre, ´es v´eg¨ differenci´ara is disztribut´ıv. (Viszont a szimmetrikus differencia nem disztribut´ıv a metsz´esre, egyes´ıt´esre, ´es az uni´o sem a szimmetrikus differenci´ara.) Megfigyelhet˝o az is, hogy — ha a szimmetrikus differenci´at tartalmaz´o azonoss´agokat elhagyjuk, akkor — a t´etelben felsorolt azonoss´agokban a metszet ´es az egyes´ıt´es szerepe szimmetrikus, azaz ha egy azonoss´agban a kett˝ot k¨ovetkezetesen felcser´elj¨ uk, akkor tov´abbra is egy, a t´etelben felsorolt azonoss´aghoz jutunk. Kett˝on´el t¨obb halmaz metszet´et ´es egyes´ıt´es´et is defini´aljuk. Legyen I tetsz˝oleges indexhalmaz (teh´at tetsz˝oleges nem¨ ures halmaz, amelynek elemeit indexel´esre haszn´aljuk), ´es minden egyes i ∈ I-re legyen adott egy Ai halmaz. Ekkor
Ai := {x : ∀i ∈ I-re x ∈ Ai }
(metszet),
i∈I
Ai := {x : ∃i ∈ I, hogy x ∈ Ai }
(uni´o).
i∈I
Ha I = {1, 2, . . . , n}, akkor a fenti helyett az al´abbi jel¨ol´esek is szok´asosak: n
Ai ,
A1 ∪ · · · ∪ An .
vagy
i=1 CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
10
A t´etelben szerepl˝o azonoss´agok, tov´abb´a egy´eb azonoss´agok bizony´ıt´asa, ´erv´enyess´eg¨ uknek a eld¨ont´ese tant´argyi k¨ovetelm´eny. Gyakorl´ask´ent megoldunk k´et feladatot. Feladat: Mutassuk meg, hogy a (k´ettag´ u) ∪ egyes´ıt´es disztribut´ıv az ak´arh´anytag´ u metszetre, azaz tetsz˝oleges A ´es Bi halmazok eset´en A ∪ Bi = (A ∪ Bi ). i∈I
i∈I
Megold´ as: Jel¨olje L ´es R a bizony´ıtand´o egyenl˝os´eg bal-, illetve jobboldal´at. Figyelj¨ uk meg, hogy R = R — az ut´obbi a val´os sz´amok halmaza ´es m´as bet˝ ut´ıpus! El´eg bel´atni (´es ez a szok´asos elj´ar´as), hogy L ⊆ R ´es R ⊆ L. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Az L ⊆ R bizony´ıt´asa: legyen x ∈ L = A ∪ i∈I Bi . Az uni´o defin´ıci´oja miatt x ∈ A vagy x ∈ i∈I Bi . Ha x ∈ A, akkor / A, akkor x ∈ i∈I Bi , teh´at a metszet defin´ıci´oja miatt minden i ∈ I-re x ∈ Bi , minden egyes i ∈ I-re x ∈ A ∪ Bi . Ha pedig x ∈ ´es innen megintcsak x ∈ A ∪ Bi k¨ovetkezik. Teh´at minden esetben ∀i ∈ I-re x ∈ A ∪ Bi , ´es innen x ∈ i∈I (A ∪ Bi ) = R. Megmutattuk, hogy tetsz˝oleges x ∈ L-re x ∈ R, azaz L ⊆ R. Az R ⊆ L bizony´ıt´asa: legyen x egy tetsz˝oleges eleme R = i∈I (A ∪ Bi )-nek. Ekkor minden i ∈ I-re x ∈ A ∪ Bi . Ha x ∈ A, unk ut´an feltehetj¨ uk, hogy x ∈ / A. Ekkor x ∈ A ∪Bi -b˝ol akkor x ∈ A ∪ i∈I Bi = L, ´es nincs tov´abbi tennival´onk. Ezen ´eszrev´etel¨ x ∈ Bi k¨ovetkezik. Mivel i tetsz˝oleges volt, x ∈ i∈I Bi , ´es innen x ∈ L ad´odik. Ezzel bel´attuk, hogy R ⊆ L. Q.e.d. Tulajdonk´eppen meglett¨ unk volna az L ⊆ R ´es R ⊆ L eml´ıt´ese n´elk¨ ul is, hiszen val´oj´aban azt mutattuk ki, hogy L-nek ´es R-nek ugyanazok az elemei. De k¨onnyebben meg tudtuk a bizony´ıt´ast fogalmazni L ⊆ R ´es R ⊆ L emleget´es´evel. Feladat: Mutassuk meg t´etel¨ unk azon a´ll´ıt´as´at, hogy a metszet disztribut´ıv a szimmetrikus differenci´ara. 1. Megold´ as: Legyenek A, B ´es C tetsz˝oleges halmazok, vezess¨ uk be az L := A ∩ (BC) ´es az R := (A ∩ B)(A ∩ C) jel¨ol´est.Most (mivel nincs olyan sok v´altoz´o a bizony´ıtand´o azonoss´agban) m´as utat v´alasztunk, mint az el˝obb. Azt kell megmutatnunk, hogy tetsz˝oleges x-re x ∈ L pontosan akkor teljes¨ ul, amikor x ∈ R. K¨ ul¨onb¨oztess¨ unk meg o¨sszesen nyolc esetet annak megfelel˝oen, hogy az A, B, C halmazok k¨oz¨ ul az x melyiknek eleme. (K´ek sz´ınnel:)
11
A
B
C
B C
L
A B
A
C
R
A t´abl´azatban az ∈, illetve ∈ /u ´gy ´ertend˝o, hogy x eleme, illetve nem eleme az oszlopfejl´eck´ent ´ırt halmaznak. A gondos kit¨olt´es ut´an l´athat´o, hogy x ∈ L pontosan akkor teljes¨ ul, ha x ∈ R. Teh´at L = R. 2. Megold´ as: Venn-diagram seg´ıts´eg´evel! A Venn-diagram seg´ıts´eg´evel! ? ? ? Eml´ıtett¨ uk, hogy a Venn-diagram nem mindig ad korrekt bizony´ıt´ast, de most a bizony´ıt´asunk m´egis korrekt lesz, hiszen l´enyeg´eben az el˝oz˝o bizony´ıt´asunkat ism´etelj¨ uk meg szeml´eletesebb form´aban. A korrekts´eg azon m´ ulik, hogy olyan s´ıkidomokkal reprezent´alt halmazokat vegy¨ unk fel az ´abr´an, hogy az el˝oz˝o nyolc eset mindegyike fell´epjen, azaz (pongyol´an fogalmazva) a h´arom s´ıkidom metszeteik´ent el˝oa´ll´o nyolc s´ıktartom´any egyike se legyen u ¨res. Ha erre u ¨gyel¨ unk, akkor gyorsabban c´elt ´er¨ unk, mint az el˝oz˝o t´abl´azattal, de ´eppen ebben van a vesz´ely: nagyobb a t´eved´es lehet˝os´ege is. L´assuk a megfontol´as l´ep´eseit: z¨old sz´ınnel a bal-, pirossal a jobboldalt sz´amoljuk” ki, ´es l´athat´o, hogy a v´eg´en ugyanazt kapjuk. ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
B
B
CB
A C
C A B( B C 12
C)
A B A C ( A BB )
(A C )
C Most m´ar csak az van h´atra, hogy — az el˝orebocs´atottak szerint meggy˝oz˝odj¨ unk arr´ol, hogy a Venn-diagramjaink t´enyleg nyolc tartom´anyra osztj´ak a s´ıkot:
1
2
5 4
8
76 3
´es t´enyleg. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Gyakran egy r¨ogz´ıtett U halmaz r´eszhalmazaival foglalkozunk. Ezen U-t alaphalmaznak vagy univerzumnak nevezz¨ uk. Pl. a geom´eterek gyakran a s´ık pontjait v´alasztj´ak univerzumnak, a sz´amelm´eletben az univerzum lehet pl. Z, a kalkulusban pedig R. anak nevezz¨uk, ´es A-sal jel¨olj¨uk. Defin´ıci´ o: Ha A ⊆ U, akkor az U \ A halmazt az A halmaz komplementer halmaz´ (A komplementer term´eszetesen f¨ ugg az alaphalmaz v´alaszt´as´at´ol, de az r¨ogz´ıtett.) Az eddigi halmazm˝ uveletekkel (∪, ∩, , \, ) rengeteg tov´abbi azonoss´agot lehet fel´ırni — ezek egy r´esze a gyakorlaton ´es a vizsg´an feladatk´ent t˝ uzhet˝o ki. Mi most csak egy fontos nevezetes azonoss´agot eml´ıt¨ unk. 13
6. T´ etel. Ha A ´es B az U univerzum tetsz˝oleges r´eszhalmazai, akkor ´erv´enyesek az u ´n. de Morgan-azonoss´ agok: A ∪ B = A ∩ B,
A ∩ B = A ∪ B.
Bizony´ıt´as helyett a k´et azonoss´ag k¨oz¨ ul a m´asodikat Venn-diagrammal szem´eltetj¨ uk. (A kor´abban mondottak mint´aj´ara az al´abbi a´bra teljes ´ert´ek˝ u bizony´ıt´ass´a tehet˝o, ezzel azonban nem t¨oltj¨ uk az id˝ot.) Az a´br´ak maguk´ert besz´elnek:
A
A B
A
B
A
B
B
B
A
A
B
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Descartes-szorzat A s´ıkot a Descartes-f´ele k¨ozismert koordin´atarendszerrel is le´ırhatjuk. Ebben minden pontnak egy sz´amp´ar felel meg. Innen ered az al´abbi konstrukci´o neve. ar Defin´ıci´ o Tetsz˝oleges a ´es b matematikai objektumra (azaz elemekre) ´ertelmezz¨ uk a bel˝ol¨ uk k´epezett (a, b) elemp´ fogalm´at. Ha (a1, b1 ) ´es (a2, b2 ) egy-egy (rendezett) elemp´ar, akkor pontosan akkor tekintj¨ uk o˝ket egyenl˝onek, ha a1 = b1 ´es ´n. komponensek sorrendje fontos, teh´at (az a = b esetet lesz´am´ıtva) (a, b) = (b, a). Ezzel szemben halmazok a2 = b2). Az u eset´eben a sorrend l´enyegtelen, teh´at {a, b} = {b, a}. uk. Az A ´es B halmaz Legyen A ´es B halmaz. Ekkor Descartes-szorzatukon az {(a, b) : a ∈ A, b ∈ B} halmazt ´ertj¨ Descartes-szorzat´at A × B jel¨oli. A koordin´atageometri´anak az a l´enyege, hogy a s´ık azonos´ıthat´o az R × R Descartes-szorzattal. any az A × A pedig Az azonos t´enyez˝ok szorzat´at most is hatv´anynak nevezz¨ uk, teh´at pl. az A2 Descartes-hatv´ Descartes-szorzatot jel¨oli. 14
Van m´eg egy tov´abbi m´od arra, hogy ismert halmazokb´ol u ´jabbakat k´epezz¨ unk. Legyen A halmaz. Az A hatv´ anyhalmaz´ an az A ¨osszes r´eszhalmaz´ab´ol a´ll´o halmazt ´ertj¨uk, ´es ezt P (A) jel¨oli. Teh´at P (A) = {X : X ⊆ A}. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Feladat: H´any elem˝ u a P (P (∅)) × P (P (P (∅))) halmaz? Adjuk meg a szok´asos explicit” alakban is! ” Megold´ as: Mivel minden halmaz r´eszhalmaza saj´at mag´anak, ∅ ⊆ ∅. Az u ¨res halmaznak m´as r´eszhalmaza nincs. Teh´at P (∅) = {∅}, ami egyelem˝ u. Ennek m´ar k´et r´eszhalmaza van: az u ¨reshalmaz ´es ¨onmaga. Teh´at A := P (P (∅)) = {∅, {∅}}, ami k´etelem˝ u. Tetsz˝oleges k´etelem˝ u halmaznak n´egy r´eszhalmaza van: az u ¨reshalmaz, k´et darab egyelem˝ u r´eszhalmaz ´es ¨onmaga. Ezek szerint (v´altott sz´ınekkel, hogy k¨onnyebb legyen a n´egy elemet megsz´amolni): B := P (A) = {∅, {∅},{{∅}}, {∅, {∅}}}. Ezek ut´an A × B = { (∅, ∅), (∅, {∅}), (∅, {{∅}}), (∅, {∅, {∅}}), ({∅}, ∅), ({∅}, {∅}), ({∅}, {{∅}}), ({∅}, {∅, {∅}}) }. A keresett halmaz a fenti, ´es nyolcelem˝ u. ”A semmib˝ol egy u ´j, m´as vil´agot teremtettem.” ´ırta 1823. november 3.-´an Bolyai J´anos (1802-1860) ´edesapj´ahoz ´ırt level´eben. Mi persze csak nagyon apr´o dolgot tett¨ unk a fenti feladat megold´as´aval, de ´erdemes megeml´ıteni, hogy axiomatikus t´argyal´asban az eg´esz matematika fel´ep´ıthet˝o a semmib˝ol, azaz az u ¨res halmazb´ol kiindulva. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Rel´ aci´ ok
Defin´ıci´ o: Legyen A ´es B halmaz. Az A × B r´eszhalmazait A-b´ol B-be t¨ort´en˝o megfeleltet´ eseknek nevezz¨uk. Egy aci´ onak nevezz¨uk. ilyen megfeleltet´esnek A az indul´asi halmaza, B az ´erkez´esi halmaza. Ha A = B, akkor a megfeleltet´est rel´ Megjegyz´es: Sokan a rel´aci´o sz´ot a megfeleltet´es helyett haszn´alj´ak, teh´at A = B eset´en is, de mi nem. A rel´aci´o, illetve a megfeleltet´es fenti defin´ıci´oja a matematika szintj´en ragadja meg a rel´aci´o (pl. rokons´agi rel´aci´o) fogalm´at: megadjuk a rel´aci´oban, azaz viszonyban a´ll´o p´arok halmaz´at. P´ eld´ ak: µ := {(a, b) ∈ N × N : a | b} — oszthat´os´agi rel´aci´o N-en. κ := {(a, b) ∈ R × R : a < b} — a kisebb” rel´aci´o a val´os sz´amok halmaz´an. ” 15
A k¨ovetkez˝o p´eld´aban a s´ık pontjait azonos´ıtjuk a sz´amp´arokkal ´es egy´ uttal azok helyvektoraival (hogy ´ertelme legyen az ¨osszead´asnak): ulypontja” megfeleltet´es, amely tetsz˝oleges (A, B, C) ρ := {((A, B, C), S) ∈ (R2 )3 × (R)2 : A + B + C = S + S + S} — a s´ ” h´aromsz¨ogh¨oz annak a S s´ ulypontj´at felelteti meg. ıldiagrammal szeml´eltethetj¨uk, amelynek az a l´enyege, hogy az (a, b) p´art egy a-b´ol b-be A megfeleltet´eseket pl. ny´ ir´any´ıtott ny´ıllal a´br´azoljuk. Egy m´asik lehet˝os´eg: az A×B Descartes-szorzatot u ´gy a´br´azoljuk, mintha koordin´atarendszerben ” lenn´enk”, ´es valamilyen m´odon megjel¨olj¨ uk a r´eszhalmazba tartoz´o elemeket. Az A = {1, 2, . . . , n} halmaz feletti” rel´aci´okat ” aban (azaz az A× r´eszhalmazait) az informatik´ gyakran a bitm´atrixukkal adjuk meg: aszerint ´ırunk 1-et illetve 0-t a m´atrix (azaz sz´amt´abl´azat) i-edik sor´anak j-edik hely´ere, hogy (i, j) benne van-e vagy nincs benne a rel´aci´oban. L´assunk p´eld´at mindh´aromra: az {1, 2, 3, 4, 5} halmaz feletti {(a, b) ∈ {1, 2, 3, 4, 5}2 : a + 1 osztja b-t} rel´aci´ot adjuk meg ily m´odon. 5 5 4 3 2 1
5 4 3
4 3
2
2
1
1
(5,1) 1
2
3
4
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
1 0 1 0 0
0 0 0 1 0
5
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Ha egy ρ ⊆ A × A rel´aci´ot ny´ıldiagrammal a´br´azolunk, akkor term´eszetesen nem musz´aj az A halmazt k´et p´eld´anyban lerajzolni. Ez´ert az el˝obbi {(a, b) ∈ {1, 2, 3, 4, 5}2 : a + 1 osztja b-t} rel´aci´o az al´abbi ir´any´ıtott gr´affal is a´br´azolhat´o: 3 4
2
5
1
16
´ Ha ρ ⊆ A × B egy megfeleltet´es, akkor (a, b) ∈ ρ helyett gyakran az aρb jel¨ol´est alkalmazzuk. Altal´ aban ez jellemz˝o a j´ol ismert rel´aci´okra: pl. azt ´ırjuk, hogy a ≤ b ahelyett hogy (a, b) ∈≤. A megfeleltet´esek k¨oz¨ ul k¨ ul¨on¨osen fontosak az u ´gynevezett lek´epez´esek. Egy f ⊆ A × B megfeleltet´est A-b´ol B-be t¨ort´en˝o
lek´ epez´ esnek
nevez¨ unk, ha b´armely a ∈ A-ra l´etezik egy ´es csakis egy b ∈ B, hogy (a, b) ∈ f. A ny´ıldiagrammon ez azt jelenti, hogy az indul´asi halmaz minden pontj´ab´ol indul ki ny´ıl, ´es csak egy ny´ıl indul ki. Ha uggv´ enyeknek is nevezik. Ha egy rel´aci´ot mindk´et halmaz sz´amokb´ol a´ll (s˝ot n´eha m´askor is), akkor a lek´epez´eseket f¨ bitm´atrixxal adunk meg, akkor a k´erd´eses rel´aci´o pontosan akkor lek´epez´es, ha minden sorban pontosan egy darab 1-es van.
Ha f ⊆ A × B egy lek´epez´es A-b´ol B-be, akkor ennek a t´enynek a kifejez´es´ere az f : A → B jel¨ol´est alkalmazzuk. ertelmez´ esi tartom´ anynak nevezz¨ uk. Ha (a, b) ∈ f, azaz a f b ´es Lek´epez´es eset´en az indul´asi halmazt (azaz A-t) ´ ıllal fel´ırva: f : a → b vagy csak a → b. (L´athat´o: lek´epez´es f lek´epez´es, akkor azt ´ırjuk, hogy af = b. Ugyanez talpas ny´ eset´en igyeksz¨ unk elker¨ ulni a megfeleltet´esekre vonatkoz´o jel¨ol´eseket.) A matematik´aban rengeteg m´odon jel¨olik a lek´epez´eseket; l´assunk n´eh´any p´eld´at! CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
sin : R → R, x → sin x. (Nincs z´ar´ojel, a lek´epez´es jel´et balr´ol ´ırjuk.) exp : R → R, x → ex . (Nincs√z´ar´ojel, az elemet a kitev˝obe ´ırjuk.) √ :{x ∈ R : x ≥ 0} → R, x → x. f : R → R, x → f(x). (Van z´ar´ojel, a lek´epez´est balr´ol ´ırjuk.) A lek´epez´esek tulajdons´agai nemcsak a kalkulus tant´argy sor´an fontosak. ıvnek nevez¨unk, ha b´armely a1, a2 ∈ A eset´en ha a1f = a2f, akkor a1 = a2 . Egy f : A → B lek´epez´est injekt´ A ha U, akkor V ” t´ıpus´ u mondat matematikai ´ertelm´evel kapcsolatban a´lljunk meg egy pillanatra. Az ilyen mondat ” (ak´arcsak a h´etk¨oznapi besz´edben) nem jelenti azt, hogy U igaz. Csup´an annyit a´ll´ıtunk, hogy amennyiben U igaz, akkor V is igaz, de semmit sem mondunk arra az esetre, amikor U hamis. Ez´ert pl. helyesek ´es igazak az al´abbi kijelent´esek: Ha ” az ´evfolyam t¨obbs´ege holdutaz´ason vesz r´eszt, akkor mindenki els˝ore a´tmegy a 2007. ´evi diszkr´et matematika vizsg´an”, ´es ugyancsak ´erv´enyes a k¨ovetkez˝o kett˝o is: Ha 2 + 2 = 5, akkor csak v´eges sok pr´ımsz´am van.”, illetve Ha 2 + 2 = 5, akkor ” ” v´egtelen sok pr´ımsz´am van.” Visszat´erve az injekt´ıv lek´epez´es fogalm´ara, az injektvit´as azt jelenti, hogy k¨ ul¨onb¨oz˝o elemek k´epe sz¨ uks´egk´eppen k¨ ul¨onb¨oz˝o. M´as sz´oval, ha k´et elem k´epe egyenl˝o, akkor maguk a kiindul´asi elemek is egyenl˝oek. u lek´epez´es” (amelyet viszont egyesek m´as ´ertelemben Az injekt´ıv lek´epez´es” szinon´ım´aja: k¨olcs¨on¨osen egy´ertelm˝ ” ” 17
haszn´alnak, ez´ert ker¨ ulni fogom). Ny´ıldiagrammon az injekt´ıv lek´epez´es onnan ismerhet˝o fel, hogy lek´epez´es ´es B minden elem´ebe legfeljebb egy ny´ıl ´erkezik. Bitm´atrixos megad´as eset´en pedig onnan, hogy lek´epez´es (azaz minden sorban pontosan egy 1 van) ´es minden oszlopban legfeljebb egy 1 van. urjekt´ıv lek´ epez´ esnek vagy m´as sz´oval r´ ak´ epez´ esnek nevezz¨uk, ha b´armely b ∈ B Az f : A → B lek´epez´est sz¨ ose”, azaz van olyan a ∈ A elem, hogy b = f(a). M´as sz´oval, ha B minden eleme k´epelem. elemnek van ˝ ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Az {f(a) : a ∈ A} halmazt az f : A → B lek´epez´es ´ ert´ ekk´ eszlet´ enek nevezz¨ uk. Ezek szerint a sz¨urjektivit´as azt jelenti, hogy az ´erkez´esi halmaz egyenl˝o az ´ert´ekk´eszlettel. Ny´ıldiagrammon a sz¨ urjekt´ıv lek´epez´es onnan ismerhet˝o fel, hogy lek´epez´es ´es B minden elem´ebe megy ny´ıl. Bitm´atrixos megad´as eset´en pedig onnan, hogy lek´epez´es ´es minden oszlopban van 1. A tulajdons´agok sor´at a bijekci´o defin´ıci´oja z´arja. Egy f : A → B lek´epez´est
bijekci´ onak
bijekt´ıv lek´ epez´ esnek
vagy
nevez¨ unk, ha f injekt´ıv ´es sz¨ urjekt´ıv. Szokt´ak a bijekt´ıv lek´epez´es” helyett a k¨olcs¨on¨osen egy´ertelm˝ u ” ” r´ak´epez´es” elnevez´est is haszn´alni. (F´elre´erthet˝os´eg csak egyesek azon gyakorlat´ab´ol sz´armazik, hogy nem k¨otik ki, hogy a ak´epez´es legyen.) lek´epez´es r´ Mi a tov´abbiakban csak az injekt´ıv, sz¨ urjekt´ıv ´es bijekt´ıv jelz˝oket haszn´aljuk.
18
2. (2007.szept.11.) el˝ oad´ as P´ elda: A husz´arezred elvonul az emelv´eny el˝ott. Legyen A a lovak, B a husz´arok halmaza. Legyen f := {(x, y) ∈ A × B : y az x h´at´an u ¨l} megfeleltet´es. Ekkor f : A → B bijekt´ıv lek´epez´es. (Term´eszetesen a k´ezenfekv˝o k¨or¨ ulm´enyeket felt´etelezz¨ uk, pl. a husz´ar u ¨l a lovon ´es nem ford´ıtva, stb.) B´armilyen trivi´alis is a fenti p´elda, messzehat´o k¨ovetkezm´enyei lesznek a k´es˝obbiekben. Csak hogy ´erz´ekeltess¨ uk: puszt´an az f bijekci´o ´eszlel´ese alapj´an a sz´amolni nem tud´o o´vod´as is tudhatja, hogy ugyanannyi l´o van, mint husz´ar. Feladat V´alogassuk ki az al´abbi megfeleltet´esek k¨oz¨ ul a lek´epez´eseket, az injekt´ıv lek´epez´eseket, a sz¨ urjekt´ıv lek´epez´eseket ´es a bijekci´okat! (a) f = {(x, 6x + 1) : x ∈ N, ´es x p´aros} ∪ {(x, 6x − 1) : x ∈ N, ´es x p´aratlan} ⊆ N × N; (b) f = {(x, y) : y 2 = x} ⊆ R × R; (c) f = {(x, y) : y 3 = x} ⊆ R × R; (d) f = {(x, y) : x2 = y} ⊆ R × R; (e) f = {(x, y) : x2 + y 2 = 1} ⊆ R × R; (f) f = {(x, y) : x2 + y 2 = 1} ⊆ {0, 1} × {0, 1}; Megold´ as: f = {(x, 6x + 1) : x ∈ N, ´es x p´aros} ∪ {(x, 6x − 1) : x ∈ N, ´es x p´aratlan} ⊆ N × N eset´en: ´ni´o els˝o tagj´aban van, ´es ´ıgy y1 = 6x + 1 = y2. Hasonl´oan Legyen (x, y1), (x, y2) ∈ f. Ha x p´aros, akkor mindk´et p´ar az u epe van. Ha x ∈ N, akkor van k´ epe l´athat´o y1 = y2 az x p´aratlan esetben is. Teh´at tetsz˝oleges x-nek legfeljebb egy k´ x-nek, hiszen a 6x ± 1 is eg´esz sz´am ´es pozit´ıv (≥ 5). Teh´at f : N → N lek´epez´es. Az f = {(x, 6x + 1) : x ∈ N, ´es x p´aros} ∪ {(x, 6x − 1) : x ∈ N, ´es x p´aratlan} ⊆ N × N teh´at lek´epez´es. Ha x1 p´aros ´es ul¨onb¨oz˝o parit´ as´ uak), akkor x1f 6-tal osztva 1-et, x2f pedig 6-tal osztva 5-¨ot ad marad´ekul, teh´at ezen x2 p´aratlan (azaz k¨ esetben a k´epelemek k¨ ul¨onb¨oznek. Ez´ert ha feltessz¨ uk, hogy az y1 := x1 f ´es y2 := x2 f egyenl˝oek, akkor m´aris tudjuk, hogy x1 ´es x2 azonos parit´as´ uak. Ha mindkett˝o p´aros, akkor 6x1 + 1 = x1f = x2f = 6x2 + 1-b˝ol x1 = x2 ad´odik. Ha pedig mindkett˝o p´aratlan, akkor 6x1 − 1 = x1f = x2f = 6x2 − 1-b˝ol szint´en k¨ovetkezik x1 = x2. Teh´at ha a k´epelemek azonosak, akkor az o˝s¨ok is. Azaz f injekt´ıv. K´erd´es, hogy sz¨ urjekt´ıv-e? Azaz k´epelem-e minden pozit´ıv eg´esz sz´am? Nyilv´an nem, pl. a 2 sem az, hiszen nem a´ll el˝o 6x ± 1 alakban. Teh´at f nem sz¨ urjekt´ıv, ´es ez´ert nem is bijekt´ıv. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
(b) f = {(x, y) : y 2 = x} ⊆ R × R? 19
Az els˝o k´erd´es az, hogy tartozik-e minden x-hez y? Nem, hiszen a negat´ıv x-ek nem ´allnak el˝o n´egyzet alakban. Teh´at f nem lek´epez´es. De az is lehet az els˝o k´erd´es (hiszen mindenki m´ask´ent gondolkodik), hogy igaz-e, hogy tetsz˝oleges x-hez csak egy y tartozik? ´ ´altal´aban is, minden pozit´ıv x-hez kett˝o y is tartozik.) Innen is az ad´odik, Ez sem igaz, hiszen ha (1, −1) ∈ f ´es (1, 1) ∈ f. (Es hogy f nem lek´epez´es. A defin´ıci´ok ismeret´eben nemigen kellett az els˝o k´et feladaton gondolkodni, azok ismerete n´elk¨ ul pedig el se lehet kezdeni. A defin´ıci´okat hasonl´o jelleg˝ u feladatok k´erik sz´amon a vizsg´an. (c) f = {(x, y) : y 3 = x} ⊆ R × R? √ Mivel az a k´erd´es, hogy vajon egy tetsz˝oleges x meghat´aroz-e egy y-t ´es azt egy´ertelm˝ uen teszi-e, fejezz¨ uk ki y-t: y = 3 x. Minden x-hez pontosan egy y l´etezik, teh´at f¨ uggv´enyr˝ol van sz´o: Minden val´os ´ert´eket felvesz ´ıgy sz¨ urjekt´ıv, ´es (a monotonit´as miatt) mindegyiket csak egyszer, ´ıgy injekt´ıv. Teh´at bijekt´ıv.
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
2
(d) f = {(x, y) : x = y} ⊆ R × R? Ez lek´epez´es, hiszen minden egyes x val´os sz´amhoz pontosan egy y tartozik: az x n´egyzete. A f¨ uggv´eny nem sz¨ urjekt´ıv (mert negat´ıv val´os sz´amokat nem vesz fel ´ert´ekk´ent), ´es nem injekt´ıv (mert pl. a −1 ´es az 1 helyen azonos ´ert´ekeket vesz fel). Mindez egy pillanat alatt leolvashat´o a grafikonr´ol:
20
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
´ azoljuk az f rel´aci´ohoz tartoz´o (x, y) pontp´arokat a koordin´atarendszerben, (e) f = {(x, y) : x2 + y 2 = 1} ⊆ R × R? Abr´ ´es r¨ogt¨on kider¨ ul, hogy f nem f¨ uggv´eny, mert pl. x = 2-h¨oz nincs y, x = 0-hoz pedig kett˝o is van:
21
(f) f = {(x, y) : x2 + y 2 = 1} ⊆ {0, 1} × {0, 1}? Mivel f = {(0, 1), (1, 0)}, ez´ert j´ol l´athat´o, hogy f f¨ uggv´eny ´es bijekci´o. Az el˝obbi feladat tanuls´aga: fontos megjegyezn¨ unk, hogy a megfeleltet´esek, rel´aci´ok ´es lek´epez´esek megad´asa nem csak erkez´ esi ´es az indul´ asi halmaz megad´as´at is! az elemp´arok halmaz´anak megad´as´at jelenti, hanem az ´ Ennek ´erz´ekeltet´es´ere tekints¨ uk a k¨ovetkez˝o k´et lek´epez´est: f : {x ∈ R : x ≥ 0} → {x ∈ R : x ≥ 0}, x → x2 , g : {x ∈ R : x ≥ 0} → R, x → x2. egsem tekint¨ uk o ˝ket Mint elemp´arok halmaza, a k´et lek´epez´es megegyezne, de az im´enti megjegy´es¨ unk f´eny´eben m´ egyenl˝ oeknek. M´ar csak az´ert sem, mert f bijekt´ıv, g pedig nem (hiszen nem sz¨urjekt´ıv). Teh´at a lek´epez´esek (f¨ uggv´enyek) tulajdons´agai nemcsak a hozz´arendel´esi szab´alyt´ol, a k´eplett˝ol f¨ uggnek, azaz nemcsak az elemp´arok halmaz´at´ol, hanem az indul´asi ´es ´erkez´esi halmaz megv´alaszt´as´at´ol. Hasonl´o meg´allap´ıt´as ´erv´enyes a rel´aci´okra, megfeleltet´esekre is. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Sz´ amoss´ agok Tal´an jobb lenne m´eg a lek´epez´esek ´es rel´aci´ok tulajdons´again´al id˝ozni alapoz´ask´ent — de ezt k´es˝obbre halasztjuk. A sz´amoss´agok t´emak¨ore t´ ul ´erdekes ahhoz, hogy v´arjon! amolhatjuk. Pl. a balkez¨unk ujjainak halmaza eset´en azt mondjuk, hogy ennek a A v´eges halmazok elemeit megsz´ halmaznak az elemsz´ama 5. Vagy pl. az {x : x ∈ N, ´es x osztja a 6-ot} halmaz eset´en az elemsz´am 4. Esetenk´ent sokat kell ama. sz´amolni ´es/vagy gondolkodni, de minden v´eges halmaznak van egy ´es csakis egy j´olmeghat´arozott elemsz´ Per pillanat nem defini´aljuk, hogy mit nevez¨ unk v´eges halmaznak. Nem t´ ul prec´ız defin´ıci´o lehet pl. az al´abbi: egy halmaz v´eges, ha elemeit — az N0 elemeinek felhaszn´al´as´aval — meg tudjuk sz´amolni. Ism´etelten felh´ıvom a figyelmet arra, hogy ezzel a lila sz´ınnel (1) egyr´eszt n´eh´any mintafeladat (vagy annak r´esze) szerepel, amelyre nem jut(ott) id˝o — ezek tanulm´anyoz´asa nagym´ert´ekben k¨onny´ıti a vizsg´ara val´o felk´esz¨ ul´est, (2) m´asr´eszt pedig lila sz´ınnel olyan megjegyz´eseket ´es ´erdekess´egeket adok k¨ozre, amelyeket NEM KELL megtanulni!!! CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A v´egtelen halmazok elemeit is meg szeretn´enk sz´amolni! Ekkor persze nem kaphatunk term´eszetes sz´amokat, ez´ert nem amoss´ ag elnevez´est fogjuk haszn´alni. haszn´alhat´o az elemsz´am” elnevez´es. Ehelyett a sz´ ” amoss´ ag az elemsz´am megfelel˝oje. Majd tetsz˝oleges halmaznak lesz sz´amoss´aga, amely v´eges halmaz eset´en Teh´at a sz´ persze az elemsz´ammal fog megegyezni. M´as sz´oval: a v´eges sz´amoss´agok pontosan a nemnegat´ıv eg´esz sz´amok lesznek. 22
Aki nem t¨orekszik a dolgok bonyol´ıt´as´ara, az be´eri ennyivel: a sz´amoss´agok: 0,1,2, . . . , ∞. ´Igy nem lenne semmi gond — ´es semmi hasznunk nem lenne bel˝ole. De van m´as lehet˝os´eg¨ unk is — azt v´alasztjuk:
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Az ´og¨or¨og mitol´ogia szerint lent, az el´erhet˝o vil´agban ´eltek az emberek, a fenti vil´agban az istenek. Az istenek olyan csod´alatos tulajdons´agokkal is rendelkeztek, amelyekkel az emberek nem. Az istenek k¨onnyed´en hajtottak v´egre az emberek vil´ag´aban olyan tetteket, amelyeket az emberek nem tudtak, vagy csak nagyon nehezen tudtak volna megtenni. Hamarosan l´atni fogjuk, hogy a v´eges elemsz´amok vil´aga f¨ol¨ott ott van a sz´amoss´agok vil´aga. A sz´amoss´agok olyan tulajdons´agokkal (is) rendelkeznek, amelyekkel a term´eszetes sz´amok nem. A sz´amoss´agok seg´ıts´eg´evel olyan probl´em´ak is k¨onnyed´en megoldhat´ok a v´eges sz´amok vil´ag´aban, amelyek sz´amoss´agok n´elk¨ ul csak nagyon nehezen vagy egy´altal´an nem lenn´enek megoldhat´ok. Miel˝ott a v´egtelen sz´amoss´agokat defini´aln´ank, gondolkodjunk el a term´eszetes sz´amok fogalm´anak kialakul´as´an. Mit jelent az, hogy kett˝o”? Hogy egy halmaz k´etelem˝ u? El˝obb azt kell meggondolni (annak a fogalomnak kellett kialakulnia), hogy mit ” ama egyenl˝ o” jelent az, hogy k´et halmaznak ugyanannyi eleme van”? M´as sz´oval, mit jelent az, hogy k´et halmaz elemsz´ ” ” ?
23
Defin´ıci´ o: Legyen A ´es B halmaz. Akkor mondjuk, hogy az A ´ es B elemsz´ ama egyenl˝ o, ha l´ etezik A → B bijekt´ıv lek´ epez´ es . Ezzel megoldottuk az els˝o feladatot. Egy kor´abbi p´eld´ara visszautalva, a lovak ´es husz´arok halmaz´anak elemsz´ama egyenl˝o, mert a rajta u ¨l” lek´epez´es bijekci´o a k´et halmaz k¨oz¨ott. ” A k¨ovetkez˝o l´ep´es: kiv´alasztunk bizonyos halmazokat. Ezek egyike pl. a jobb kez¨ unk ujjainak halmaza. Majd a kiv´alasztott halmazzal egyenl˝o elemsz´am´ u halmazokat elnevezz¨ uk valahogy (eset¨ unkben ¨otelem˝ ueknek”). Teh´at (legal´abbis az o˝skorban, ” illetve a mai el˝oad´ason) nem mondjuk meg, mi az, hogy ¨ot”, hanem csak annyit mondunk meg, mi az, hogy ¨otelem˝ u” halmaz. ” ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Ezt k¨ovet˝oen az ¨ot” nem m´as, mint az o¨telem˝ u halmazok k¨oz¨os tulajdons´aga. (Azaz az ¨ot” fogalm´at absztrakci´oval ” ” defini´altuk — az ilyenfajta absztrakci´o teljesen megszokott az emberi gondolkod´asban.) Ha jobb keze ujjainak halmaza ´es az elejtett mammutok halmaza k¨oz¨ott az o˝sember bijekci´ot tudott l´etes´ıteni, akkor azt mondta, hogy ¨ot”, ´es el´egedett volt, ´es nem elm´elkedett olyan hi´abaval´o k´erd´esen, hogy mit jelent az ¨ot”. ” ” Hasonl´oan j´arunk el a sz´amoss´agok fogalm´anak kialak´ıt´asakor is: es B sz´ amoss´ aga egyenl˝ o, ha l´ etezik Defin´ıci´ o: Legyen A ´es B halmaz. Akkor mondjuk, hogy az A ´ A → B bijekt´ıv lek´ epez´ es . es B ekvivalens. Most Megjegyz´es: ahelyett, hogy A ´es B sz´amoss´aga egyenl˝o, azt is szok´as mondani, hogy A ´ elnevez¨ unk egy sz´amoss´agot (annak mint´aj´ara, ahogy a jobbkez¨ unk ujjainak halmaz´aval kapcsolatban egy sz´amot elnevezt¨ unk ¨otnek”): ” aml´ alhat´ oan v´ egtelennek nevezz¨uk ´es ℵ0-lal Defin´ıci´ o: A pozit´ıv eg´esz sz´amok halmaz´anak sz´amoss´ag´at megsz´ jel¨olj¨ uk. (Kiejtve alef null”; ℵ a h´eber ´ab´ec´e els˝o bet˝ uje). ” Egy X halmaz sz´amoss´ag´at (amely v´eges halmaz eset´en az elemsz´am) |X| fogja jel¨olni. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Egy hallgat´o u ´gy v´elte enn´el a pontn´al, hogy minden igyekezet ellen´ere nem defini´altuk a sz´amoss´ag fogalm´at, nem mondtuk meg pl. hogy mi is az az ℵ0 . Erre ez a v´alasz: azt sem tudjuk jobban, hogy mik azok a term´eszetes sz´amok, hogy mi az hogy ¨ot”? Lehet egy k´ezen ¨ot ujj, ” lehet egy utc´aban o¨t h´az, lehet egy nap o¨t ´etkez´es, de mi az, hogy o¨t? Ha j´ol belegondolunk, pontosan ugyanannyira mondtuk meg, hogy mit az hogy ℵ0 , mint amennyire megmondhat´o, vagy amennyire az o´vod´aban megmondt´ak, hogy mi az hogy ¨ot”. ” u” halmaz. Teh´at tudjuk (sok ´eve) hogy mi az hogy ¨otelem˝ u halmaz”, ´es mostant´ol azt is tudjuk, hogy mi az hogy ℵ0 -elem˝ ” ”
24
Mindk´et esetben egy tulajdons´agot defini´alunk, ´es ´erj¨ uk be azzal, hogy el tudjuk d¨onteni, hogy mely objektumok (jelen esetben halmazok) rendelkeznek ezen tulajdons´aggal. Ez az u ´n. absztrakci´oval val´o defini´al´as” j´ol megfelel az emberi gondolkod´asnak. ” Sz´amos k´erd´es ´es probl´ema mer¨ ul fel. Egyr´eszt a fogalom kialak´ıt´asa korrekt volt-e, azaz igaz-e, hogy tetsz˝oleges A, B ´es C halmazokra as), (1) A ´es A azonos sz´amoss´ag´ u (reflexivit´ (2) Ha A ´es B azonos sz´amoss´ag´ u, akkor B ´es A is azonos sz´amoss´ag´ u (szimmetria), as). (3) Ha A ´es B azonos sz´amoss´ag´ u, tov´abb´a B ´es C is azonos V, akkor A ´es C azonos sz´amoss´ag´ u (tranzitivit´ Mivel az X ´es Y azonos elemsz´am´ u” a defin´ıci´o szerint azt jelenti, hogy l´etezik X → Y bijekci´o, a fenti h´arom k´erd´es ” megv´alaszol´as´ahoz a lek´epez´esekkel kell tov´abb foglalkoznunk. Egy m´asik, egy´altal´an nem trivi´alis k´erd´es az, hogy vajon ℵ0 az egyetlen v´egtelen sz´amoss´ag, vagy van m´asik is. Erre a k´erd´esre az al´abbi t´etel ad v´alaszt. Eml´ekezz¨ unk vissza arra, hogy P (A) az A halmaz hatv´anyhalmaz´at (azaz o¨sszes r´eszhalmaz´anak halmaz´at) jel¨oli. 7. T´ etel. Tetsz˝oleges (v´eges vagy v´egtelen) halmaz sz´amoss´aga Azaz b´ armely A halmazra |A| = |P (A)|.
nem egyenl˝ o
a hatv´ anyhalmaz´anak sz´ amoss´ag´ aval.
A t´etelt indirekt m´ odon bizony´ıtjuk. Az indirekt bizony´ıt´as (a teljes indukci´o mellett) a matematikai bizony´ıt´asok fontos t´ıpusa. L´enyege: a bizony´ıtand´o a´ll´ıt´ast tagadjuk. (Ez az indirekt feltev´es.) Ezut´an az indirekt feltev´esb˝ol ellentmond´ast vezet¨ unk le. A kapott ellentmond´asb´ol k¨ovetkeztet¨ unk a bizony´ıtand´o a´ll´ıt´asra. Bizony´ıt´ as: Indirekt m´odon tegy¨ uk fel, hogy van olyan halmaz, amelynek sz´amoss´aga megegyezik a hatv´anyhalmaz´anak sz´amoss´ag´aval. Legyen A egy ilyen halmaz. Ekkor teh´at |A| = |P (A)|. Ez´ert l´etezik egy ϕ : A → P (A) bijekci´o. T¨obb ilyen ϕ is lehet, de egyet ler¨ogz´ıt¨ unk. Ekkor az A elemei k´etf´el´ek lehetnek. Nevezz¨ unk egy a ∈ A elemet beleval´o elemnek, ha a ∈ aϕ. Azaz ha a eleme annak a r´eszhalmaznak, amit ϕ az a-hoz hozz´arendel. A nembeleval´o elemeket pedig nevezz¨ uk pl. k´ıv¨ ul´all´oaknak. Nyilv´an az A halmaz minden eleme vagy beleval´o, vagy k´ıv¨ ul´all´o, de csak egyik f´ele. Jel¨olje K a k´ıv¨ ul´all´o elemek halmaz´at! Ez r´eszhalmaza A-nak, azaz eleme P (A)-nak. (Az is lehet, hogy K = ∅ is, de sebaj). Mivel a ϕ : A → P (A) lek´epez´es bijekt´ıv ´es ez´ert sz¨ urjekt´ıv, K-nak is van ˝ose. Azaz van olyan c ∈ A, hogy cϕ = K. Tudjuk, hogy — mint minden eleme A-nak — c vagy beleval´o, vagy k´ıv¨ ul´all´o. Ha c beleval´o lenne, akkor eleme lenne cϕ = K-nak, holott K a defin´ıci´oja szerint csak k´ıv¨ ul´all´o elemeket tartalmaz. Teh´at c nem lehet beleval´o. 25
Az eddigiek szerint c k´ıv¨ ul´all´o. Azaz c ∈ / cϕ = K. De ez ellentmond´as, hiszen K az o¨sszes k´ıv¨ ul´all´o elem halmazak´ent c-t is k¨oteles tartalmazni. Q.e.d. ˝ a halmazelm´elet megalap´ıt´oja. Amit l´attunk, az Georg Ferdinand Ludwig Philipp Cantor (1845–1918) bizony´ıt´asa. O u, ´es nyilv´an P (N) is Most m´ar tudjuk, hogy nem ℵ0 = |N| az egyetlen v´egtelen sz´amoss´ag, hiszen P (N) elt´er˝o sz´amoss´ag´ v´egtelen halmaz (mert m´ar az egyelem˝ u r´eszhalmazai is v´egtelen sokan vannak.) ele ´ atl´ os m´ odszer. [0, 1) a val´os {x ∈ R : 0 ≤ x < 1} intervallumot Az al´abbi megfontol´as a h´ıres-nevezetes Cantor-f´ fogja jel¨olni. (Nem tudom, hogy az al´abbi a´ll´ıt´as mekkora meglepet´est okoz azt k¨ovet˝oen, hogy N ⊂ R . . . ) 8. T´ etel. |N| = |R|. Bizony´ıt´ as: Indirekt tegy¨ uk fel, hogy |N| = |R|. Ekkor l´etezik egy ϕ : N → R bijekci´o. Defini´alunk egy b val´os sz´amot, u v´egtelen tizedest¨ort, amelynek a tizedesvessz˝o ut´ani amelynek a t´ızes sz´amrendszerbeli alakja 0, b1 b2b3 . . .. (Teh´at 0 eg´eszr´esz˝ sz´amjegyei, azaz a tizedesjegyei b1 , b2 , . . .). A bn -ek (n ∈ N) defin´ıci´oja: ha az nϕ val´os sz´amban az n-edik tizedesjegy 4, akkor legyen bn = 5, ellenkez˝o esetben pedig legyen bn = 4. M´armost ϕ : N → R bijekt´ıv, ez´ert sz¨ urjekt´ıv, s ´ıgy b-nek is van o˝se. Azaz valamely n ∈ N-re b = nϕ. De ez azonnal ellentmond´asra vezet: ha nϕ n-edik tizedesjegye 4, akkor b n-edik tizedesjegye 5 ´es ez´ert b = nϕ, ha pedig nϕ n-edik tizedesjegye nem 4, akkor b n-edik tizedesjegye 4 ´es megintcsak b = nϕ. Q.e.d. A sz´amoss´agokkal val´o ismerked´est k´es˝obb folytatjuk. Miel˝ott a lek´epez´esek ´es rel´aci´ok kev´esb´e ´erdekes de fontos t´emak¨or´ehez visszat´ern´enk, k´et k´es˝obbi ´erdekess´eget helyez¨ unk kil´at´asba. A sz´am´ıt´og´epes programokkal kapcsolatban is gyakran meg kell valamit sz´amolni. Pl. hogy h´any l´ep´esig fog futni egy program, hiszen ha t´ ul sok l´ep´esig, pl´ane ha v´egtelen sok l´ep´esig, akkor az adott algoritmust k´ar is programozni. Goodsteint˝ol ered a k¨ovetkez˝o p´elda (ld. http://en.wikipedia.org/wiki/Goodstein%27s theorem ). A p´elda meg´ert´es´ehez csup´an egy pozit´ıv eg´esz sz´am ¨or¨okletesen n alap´ u alakja” fogalm´ara van sz¨ uks´eg. Ez azt jelenti, ” hogy fel´ırjuk a sz´amot n alap´ u sz´amrendszerben, majd az n kitev˝oit szint´en, az ott fell´ep˝o kitev˝oket szint´en, stb. P´eld´aul n = 2 2 u alakja: eset´en az x = 35 ´ıgy fest ebben az alakban: 22 +1 + 2 + 1. Ha pedig n = 3, akkor a x = 35 o¨r¨okletesen 3-mas alap´ 3 3 + 2 · 3 + 2. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
26
Egy tervezett P program inputk´ent pozit´ıv eg´esz sz´amokat olvas be. Minden ilyen beolvasott x sz´ammal a k¨ovetkez˝ot csin´alja. Az els˝o l´ep´esben x-et fel´ırja ¨or¨okletesen kettes alap´ u alakban”. Legyen p´eld´aul az x = 35 a beolvasott sz´am, ezt ” 2 22 +1 + 2 + 1 alakba ´ırja. A k¨ovetkez˝o l´ep´esben program a kettes alapot (minden le´ırt esetben) h´armas alapra cser´eli ki , a 3 3 kapott sz´amb´ol levon 1-et, ´es ¨or¨okletesen h´armas alap´ u alakban ´ırja fel az eredm´enyt. Ekkor a (33 +1 + 3 + 1) − 1 = 33 +1 + 3 sz´amhoz jut, amely mellesleg a t´ızes sz´amrendszerben 22876792454964. A k¨ovetkez˝o l´ep´esben a program a 3-as alapot 4-re cser´eli, levon 1-et, ´es ¨or¨okletesen 4-es alap´ u alakba ´ırja fel a kapott 44 +1 44 +1 +4−1 = 4 + 3, amely egy 154-jegy˝ u sz´am a t´ızes sz´amrendszerben. (Nincs ennyi atommag a tizen¨otmilli´ard sz´amot: 4 f´eny´evre bel´athat´o vil´agegyetemben.) A k¨ovetkez˝o l´ep´esben a program a 4-es alapot 5-re cser´eli, levon 1-et, ´es ¨or¨okletesen 5-¨os alap´ u alakba ´ırja fel a kapott 5 5 ´ ´ıgy tov´abb: minden l´ep´esben a u sz´am a t´ızes sz´amrendszerben. Es sz´amot: (55 +1 + 3) − 1 = 55 +1 + 2, ami egy 2184-jegy˝ program a kor´abbi alakban eggyel n¨oveli az alapot, levon egyet, majd fel´ırja a sz´amot o¨r¨okletesen az ´eppen most n¨ovelt alap´ u alakban. A folyamat akkor ´er v´eget, ha a sok-sok n¨ovel´es (´es 1-es levon´asa) ut´an valamikor null´at kapunk. A tekintett p´elda kapcs´an a k¨ovetkez˝o l´ep´esben 36306-jegy˝ u, azt k¨ovet˝oleg pedig 695975-jegy˝ u sz´amot kapunk (a t´ızes sz´amrendszerben). A sz´ed¨ uletesen gyorsan n¨ovekv˝o sz´amsorozat ut´an sz´am´ıthatunk-e arra, hogy el´erj¨ uk a null´at ´es a program le´all? Sz´am´ıthatunk-e a program le´all´as´ara, ha nagyobb inputot, ha tetsz˝olegesen nagy inputot adunk meg? CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Bizony´ıtott (de messze nem trivi´alis) t´eny, hogy term´eszetes sz´amok szok´asos axi´omarendszer´eben, teh´at a v´eges vil´agban maradva a fenti k´erd´est nem tudjuk eld¨onteni! ( Kirby–Paris-t´etel.) Viszont a v´egtelen sz´amoss´agok csod´ara k´epesek — mi nem jutunk el addig, de ha az el˝oad´as k´et-h´arom h´onappal tov´abb tartani, akkor v´egtelen sz´amoss´agokra t´amaszkodva mi is igen k¨onnyen igazolhatn´ank, hogy a program b´armilyen nagy input eset´en v´eges l´ep´esben meg´all. Mi a sz´amoss´agokkal csak egy kisebb csod´at fogunk tenni: kimutatjuk a transzcendens sz´amok l´etez´es´et. Defin´ıci´ o Legyen α A-b´ol B-be, β pedig B-b˝ol C-be val´o megfeleltet´es. (Azaz α ⊆ A × B ´es β ⊆ B × C; speci´alis esetben az A, B, C halmazok azonosak is lehetnek.) Defini´aljuk a k´et megfeleltet´es szorzat´at:
αβ := {(a, c) ∈ A × C : ∃b ∈ B hogy (a, b) ∈ α ´ es (b, c) ∈ β} ⊆ A × C.
27
Ny´ıldiagramm seg´ıts´eg´evel a megfeleltet´esek szorzata u ´gy szeml´eltethet˝o, hogy pontosan azon (a, c) ∈ A × C elemp´arok vannak a szorzat-megfeleltet´esben, amelyekre a-b´ol ir´any´ıtott u ´ton” el lehet jutni c-be. ´Ime egy p´elda: ”
e
a
q
f
b c d
p
g
r h
A
B
s C
Itt α = {(a, e), (b, f), (b, h), (d, e)}, β = {(e, s), (f, p), (g, q), (g, s)}, ´es a szorzatuk αβ = {(a, s), (b, p), (d, s)}. Az α ´es β megfeleltet´esek szorzat´at αβ helyett α ◦ β is jel¨olheti. (M´as sz´oval: karika jel¨oli, de azt gyakran elhagyjuk.) CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
2
Feladat: Legyen α = {(x, y) ∈ Z × Z : |x − y| < 3} ⊆ Z × Z. Hat´arozzuk meg α -et (azaz az αα rel´aci´ot). Megold´as: (x, y) ∈ α (vagy m´as jel¨ol´essel x α y) azt jelenti, hogy a sz´amegyenesen az x ´es y eg´esz sz´amok t´avols´aga 0, 1, vagy 2. Teh´at a ny´ıldiagramon a nyilak hossza 0, 1, vagy 2. (Term´eszetesen ezen nyilak balra is ´es jobbra is mehetnek.) Ha k´et ilyen nyilat egym´as ut´an f˝ uz¨ unk”, akkor olyan nyilat kapunk, amelynek a hossza legfeljebb 4, ´es nyilv´an minden ilyen nyilat ” megkapunk k´et α-ny´ıl egym´as ut´an f˝ uz´es´evel. Ezek szerint az eredm´eny: α2 = {(x, y) ∈ Z × Z : |x − y| ≤ 4} Megjegyz´es: a feladat nem volt teljesen egy´ertelm˝ uen fogalmazva, mert nem mondtuk meg, hogy mit jelent α2 ” meghat´aroz´asa”. P´eld´aul a sz˝orsz´alhasogat´ok ilyen eredm´enyt is kihozhattak volna: α2 = α3 \ {(x, y) ∈ Z × Z : |x − y| ∈ {5, 6} }, amely szint´en korrekt. De a feladat — hallgat´olagosan — u ´gy ´ertend˝o, hogy az eredm´enyt min´el egyszer˝ ubb alakban adjuk meg. Persze ≤ 4” helyett < 5” is ´ırhat´o lett volna. ” ” Megjegyz´es: tipikus vizsgafeladat: n´eh´any, a fentihez hasonl´o k´eplet k¨oz¨ ul kell kiv´alasztani (beixelni) azokat, amelyek α2 -et adj´ak meg. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
28
A megfeleltet´esekkel kapcsolatban egy m´asik m˝ uveletet is ´ertelmez¨ unk: Defin´ıci´ o Az α ⊆ A × B megfeleltet´es
inverz´ en
az
α−1 = {(x, y) : (y, x) ∈ α} ⊆ B × A B-b˝ol A-ba val´o megfeleltet´est ´ertj¨ uk. A ny´ıldiagrammon ezt u ´gy kapjuk, hogy minden nyilat megford´ıtunk. Az al´abbiakban fontos rel´aci´otulajdons´agokat defini´alunk. Defin´ıci´ o: Legyen α ⊆ A × A (= A2), azaz legyen α egy rel´aci´o az A halmazon. Azt mondjuk, hogy α
reflex´ıv , ha b´armely x ∈ A-ra (x, x) ∈ α. szimmetrikus , ha b´armely x, y ∈ A-ra ha (x, y) ∈ α, akkor (y, x) ∈ α. tranzit´ıv , ha b´armely x, y, z ∈ A-ra ha (x, y), (y, z) ∈ α, akkor (x, z) ∈ α. ekvivalencia(rel´ aci´ o) , ha egyszerre reflex´ıv, szimmetrikus ´es tranzit´ıv. antiszimmetrikus , ha b´armely x, y ∈ A-ra ha (x, y), (y, x) ∈ α, akkor x = y. dichotom , ha b´armely x, y ∈ A-ra (x, y) ∈ α vagy (y, x) ∈ α. r´ eszbenrendez´ es , ha reflex´ıv, antiszimmetrikus ´es tranzit´ıv, rendez´ es , ha reflex´ıv, antiszimmetrikus, tranzit´ıv ´es dichotom. any´ıtott gr´ afnak is szok´as h´ıvni. Pontosabban: ir´ any´ıtott gr´ afon egy A ny´ıldiagrammal megadott rel´aci´ot ir´ 2 (A, ρ) rendezett p´art ´ert¨ unk, ahol A halmaz, az u ´n. sz¨ogponthalmaz, ρ ⊆ A pedig egy rel´aci´o az A halmazon (´es ρ elemeit ´eleknek nevezz¨ uk). Az ir´any´ıtott gr´af fogalom t´agabb ´ertelemben is haszn´alatos, amikoris k´et sz¨ogpont k¨oz¨ott t¨obb ´el is mehet — ezzel most nem foglalkozunk. N´ezz¨ uk meg a fenti rel´aci´otulajdons´agokat az ir´any´ıtott gr´afok nyelv´en.
29
reflexív = minden pontban hurokél
szimmetrikus = minden él kétirányú (a kétirányú él két - eltérő irányítású élet jelent) d tranzitív = bármely két pontra, ha az egyikc ből irányított élek mentén eljuthatunk a másikba, akkor egyetlen irányított él mentén is eljuthatunk. Pl. az a - b - c - d útvonal miatt a b kell hogy legyen él a -ból d -be.
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
antiszimmetrikus = két különböző pont között legfeljebb csak az egyik irányban megy él.
dichotom = bármely két pont között - legalább az egyik irányban - megy él.
Nyilv´anval´o, hogy minden dichotom rel´aci´o egy´ uttal reflex´ıv is (hiszen a b´armely k´et pont” egybe is eshet). ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
P´ eld´ ak, feladatok rel´ aci´ otulajdons´ agokra 30
Feladat A tanultak k¨oz¨ ul mely rel´aci´otulajdons´aggal rendelkeznek az al´abbi rel´aci´ok: 2 α = {(a, b) ∈ Z : a + b = 2} ⊆ Z × Z, β = {(a, b) ∈ N2 : a | b} ⊆ N × N, γ = {(a, b) ∈ Z2 : a ≤ b} ⊆ Z × Z, δ = {(a, b) ∈ Z2 : |a| ≤ |b|} ⊆ Z × Z, µ = {(a, b) ∈ Z2 : |a| = |b|} ⊆ Z × Z, ρ = {(X, Y ) ∈ P (A) : X ⊆ Y } ⊆ P (A) × P (A), ahol A halmaz ´es |A| ≥ 2. Megold´ asok: / α, teh´at NEM reflex´ıv. α = {(a, b) ∈ Z2 : a + b = 2} ⊆ Z × Z. Reflex´ıv? Pl. 3 + 3 = 2, ´ıgy (3, 3) ∈ Szimmetrikus? IGEN, hiszen x + y = 2 akkor ´es csak akkor, ha y + x = 2 (mert az o¨sszead´as kommutat´ıv). Tranzit´ıv? Igaz-e, hogy ha a + b = 2 ´es b + c = 2, akkor a + c = 2? Nyilv´an NEM, hiszen pl. a = c = 0, b = 2 eset´en sem teljes¨ ul. Antiszimmetrikus? Igaz-e, hogy ha a + b = 2 ´es b + a = 2, akkor sz¨ uks´egk´eppen a = b? NEM, pl. a = −1, b = 3 ellenp´elda. Az eddigiekb˝ol: NEM ekvivalencia, NEM r´eszbenrendez´es, ´es NEM rendez´es. V´eg¨ ul NEM dichotom, hiszen pl. (3, 4) ∈ / α ´es (4, 3) ∈ / α. ´n. oszthat´ os´ agi rel´ aci´ o N-en. Nyilv´an reflex´ıv (minden sz´am oszthat´o β = {(a, b) ∈ N2 : a | b} ⊆ N × N. Ez az u ¨onmag´aval) . Antiszimmetrikus, hiszen ha k´et pozit´ıv eg´esz sz´am egym´ast k¨olcs¨on¨osen osztja, akkor egyenl˝oek. Tranzit´ıv is (ha a osztja b-t ´es b osztja c-t, akkor a osztja c-t: csakugyan, ha alkalmas x, y pozit´ıv eg´esz sz´amokra b = xa ´es c = yb, akkor c = yxa, azaz a | c. Nem szimmetrikus, hiszen pl. 2 | 6, de a 6 nem osztja a 2-t. Nem dichotom, hiszen pl. a 3 ´es az 5 sz´amokat tekintve egyik sem osztja a m´asikat. Az ¨osszetett tulajdons´agokra a v´alasz a fentiekb˝ol ad´odik: β r´eszbenrendez´es, de nem rendez´es ´es nem ekvivalencia. γ = {(a, b) ∈ Z2 : a ≤ b} ⊆ Z × Z. Ez a rel´aci´o reflex´ıv, antiszimmetrikus, tranzit´ıv, dichotom, teh´at rendez´es ´es persze r´eszbenrendez´es is. De nem szimmetrikus (pl. (2, 3) ∈ γ, de (3, 2) ∈ / γ), ez´ert nem ekvivalencia. A most vizsg´alt kisebb-egyenl˝o rel´aci´o tipikus p´eld´aja a rendez´esi rel´aci´oknak. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
δ = {(a, b) ∈ Z2 : |a| ≤ |b|} ⊆ Z × Z. Reflex´ıv, tranzit´ıv, dichotom, de nem szimmetrikus ´es nem antiszimmetrikus (mert pl. (1, −1), (−1, 1) ∈ δ, de 1 = −1). Az o¨sszetett tulajdons´agok innen m´ar ad´odnak: nem ekvivalencia, nem r´eszbenrendez´es, ´es akkor persze nem rendez´es.
31
µ = {(a, b) ∈ Z2 : |a| = |b|} ⊆ Z × Z. Reflex´ıv, szimmetrikus, tranzit´ıv, teh´at ekvivalencia. Nem dichotom. Nem antiszimmetrikus (mert pl. (1, −1), (−1, 1) ∈ µ, de 1 = −1). Ez´ert nem r´eszbenrendez´es, ´es akkor persze nem rendez´es. ρ = {(X, Y ) ∈ P (A) : X ⊆ Y } ⊆ P (A) × P (A), ahol A halmaz ´es |A| ≥ 2. A halmazokkal kapcsolatban m´ar ismert(nek kell eszbenrendez´ es. Mivel |A| ≥ 2, nem dichotom (ugyanis pl. lennie), hogy reflex´ıv, antiszimmetrikus ´es tranzit´ıv, teh´at r´ k´et k¨ ul¨onb¨oz˝o egyelem˝ u r´eszalmazt v´eve egyik sem r´eszhalmaza a m´asiknak). Ez´ert nem rendez´es. Nem szimmetrikus (hiszen pl. ∅ ⊆ A de A ⊆ ∅), ez´ert nem ekvivalencia. Feladat Mutassuk meg, hogy tetsz˝oleges α rel´aci´o akkor ´es csak akkor tranzit´ıv, ha αα ⊆ α. Megold´as: Tegy¨ uk fel, hogy α ⊆ A2 tranzit´ıv. Ha (x, z) ∈ αα, akkor a szorz´as defin´ıci´oja miatt van olyan y ∈ A, hogy (x, y), (y, z) ∈ α. De α tranzitivit´asa miatt innen (x, z) ∈ α. Teh´at αα ⊆ α, hiszen a baloldal tetsz˝oleges (x, z) eleme a jobboldalnak is eleme. Most azt tegy¨ uk fel, hogy αα ⊆ α. A tranzitivit´as kimutat´as´ahoz legyen (x, y) ∈ α ´es (y, z) ∈ α. Mivel most x ´es z k¨oz¨ott” ” l´etezik y, kapjuk, hogy (x, z) ∈ αα. A feltev´es szerint ´ıgy (x, z) ∈ α. Ezzel α tranzitivit´as´at igazoltuk. Feladat Mutassuk meg, hogy k´et (ugyanazon halmazon ´ertelmezett) reflex´ıv rel´aci´o szorzata is reflex´ıv. Igaz-e ugyenez, ha reflex´ıv helyett szimmetrikusat mondunk? ´gysz´olv´an trivi´alis. Legyen α ⊆ A2 ´es β ⊆ A2 reflex´ıv. Ekkor b´armely x ∈ A-ra Megold´ as: Az els˝o mondat a´ll´ıt´asa u (x, x) ∈ α ´es (x, x) ∈ β, ez´ert (x, x) ∈ αβ. Teh´at αβ is reflex´ıv. Az viszont nem igaz a´ltal´aban, hogy k´et szimmetrikus rel´aci´o szorzata szimmetrikus. Mert ha megpr´ob´aljuk igazolni, akkor feltessz¨ uk, hogy (x, z) ∈ αβ. Ebb˝ol kapunk egy y elemet, amelyre (x, y) ∈ α ´es (x, y) ∈ β. A k´et rel´aci´o szimmetri´aja szerint (y, x) ∈ α ´es (z, y) ∈ β. Az eddigiekb˝ol kellene kihozni, hogy (z, x) ∈ αβ, azaz kellene egy olyan t ∈ A elem, amelyre (z, t) ∈ α ´es (t, x) ∈ β. De m´eg elindulni sem tudunk, hiszen honnan vegy¨ unk olyan t-t, amelyre (z, t) ∈ α? Az persze, hogy egy bizony´ıt´asi k´ıs´erlet nem siker¨ ult, az m´eg nem mond semmit. (Lehet, hogy u ¨gyetlenek voltunk.) De legal´abb megmutatta az utat: olyan ellenp´eld´at keress¨ unk, amelyre mondjuk x = 1, y = 2, z = 3 ´es t´enyleg nincsen t! P´eld´aul ha A = {1, 2, 3}, α = {(1, 2), (2, 1)} ⊆ A2 ´es β = {(2, 3), (3, 2)} ⊆ A2, akkor ez a k´et rel´aci´o szimmetrikus, de (1, 3) ∈ αβ ´es (3, 1) ∈ αβ miatt a szorzatuk nem. Feladat Mutassuk meg, hogy tetsz˝oleges α ⊆ A2 rel´aci´o akkor ´es csak akkor szimmetrikus, ha α ⊆ α−1 . Megold´as: Tegy¨ uk fel, hogy α szimmetrikus. Ekkor α−1 = {(x, y) : (y, x) ∈ α}, de a szimmetria miatt ez = {(x, y) : (x, y) ∈ α} = α. Teh´at α = α−1 , ´es ´ıgy ann´al ink´abb α ⊆ α−1 . ul. De az inverz Ford´ıtva, most tegy¨ uk fel, hogy α ⊆ α−1 . Ha (x, y) ∈ α, akkor a feltev´es szerint (x, y) ∈ α−1 is teljes¨ defin´ıci´oja miatt ez azt jelenti, hogy (y, x) ∈ α. Teh´at ha (x, y) ∈ α, akkor (y, x) ∈ α. Azaz α szimmetrikus. 32
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
2
Feladat Mutassuk meg, hogy ha az α, β ⊆ A rel´aci´ok r´eszbenrendez´esek, akkor az α ∩ β is az. Igaz-e ugyanez, ha r´eszbenrendez´es helyett rendez´est mondunk? Megold´as: Mivel b´armely a ∈ A eset´en (a, a) ∈ α ´es (a, a) ∈ β, ez´ert (a, a) ∈ α ∩ β. Teh´at a metszet reflex´ıv. Legyen (a, b), (b, a) ∈ α ∩ β tetsz˝oleges. Ekkor speciel (a, b), (b, a) ∈ α, ´es az α antiszimmetri´aja miatt a = b. Teh´at a metszet antiszimmetrikus. Legyen (a, b), (b, c) ∈ α ∩ β tetsz˝oleges. Ekkor (a, b), (b, c) ∈ α, ´es ´ıgy α tranzitivit´as´ab´ol (a, c) ∈ α. Hasonl´oan, (a, b), (b, c) ∈ β, ´es ´ıgy β tranzitivit´as´ab´ol (a, c) ∈ β. ´Igy (a, c) ∈ α ∩β. Teh´at a metszet tranzit´ıv. Ezzel bel´attuk, hogy α ∩β r´eszbenrendez´es. Rendez´esekre a feladat a´ltal´aban nem igaz. Pl. α = {(0, 0), (0, 1), (1, 1)} (a kisebb-egyenl˝o rel´aci´o a {0, 1} halmazon), β = {(0, 0), (1, 0), (1, 1)} (a nagyob-egyenl˝o rel´aci´o ugyanott) rendez´esek, de α ∩ β = {(0, 0), (1, 1)} (az egyenl˝os´egrel´aci´o”) nem ” dichotom, ´es ez´ert nem rendez´es. Megjegyz´es: term´eszetesen vehett¨ uk volna a Z-n ´ertelmezett ≤Z ´es ≥Z rel´aci´okat is.) Feladat: Legyen A = {0, 1, . . . , 9} ´es α = {(x, y) ∈ A2 : x < y − 1}. Ekvivalencia-e az α−1 ∩ (α−1 αα) rel´aci´o? Megold´ as: Nem, mert tetsz˝oleges x ∈ A-ra (b´ar az is elegend˝o lenne, hogy l´etezik ilyen x ∈ A) (x, x) ∈ / α miatt (x, x) ∈ / α−1 , teh´at (x, x) nem eleme a metszet els˝o t´enyez˝oj´enek, ez´ert a metszetnek sem. Teh´at a k´erd´eses rel´aci´o nem reflex´ıv, ´ıgy nem ekvivalencia. A megfeleltet´esekre tanult k´et m˝ uvelet k¨oz¨ott ´erv´enyes az al´abbi k´et o¨sszef¨ ugg´es. 9. T´ etel. Ha α ⊆ A × B, β ⊆ B × C ´es γ ⊆ C × D megfeleltet´esek, akkor (αβ)γ = α(βγ), ahol mindk´et oldalon A-b´ol D-be men˝o megfeleltet´es ´all (αβ)−1 = β −1 α−1 (mindk´et oldal C-b˝ol A-ba val´o megf.)
(asszociativit´ as), ´es
Figyelj¨ uk meg, hogy a szorzat (amely nem kommutat´ıv) invert´al´asakor a t´enyez˝ok sorrendje megfordul. A bizony´ıt´as nem nehezebb az eddigi feladatokn´al; nem r´eszletezz¨ uk.
33
A lek´epez´esek speci´alis megfeleltet´esek, ez´ert mint megfeleltet´esek szorozhat´ok. Megmutathat´o, hogy az ´ıgy defini´alt szorzat szint´en lek´epez´es, ´es megegyezik az al´abbi defin´ıci´oban szerepl˝ovel. (Viszont az al´abbi defin´ıci´ot k´enyelmesebb lesz lek´epez´esek eset´eben haszn´alnunk.) Defin´ıci´ o: Legyen ϕ : A → B ´es ψ : B → C lek´epez´es. Ekkor a szorzatukon a ϕψ : A → C, a → (aϕ)ψ lek´epez´est ´ertj¨ uk. Mi jobbr´ol ´ırjuk a lek´epez´eseket, ´es ennek k¨osz¨onhet˝oen ´erv´enyes a ∈ A eset´en a tetszet˝os a(ϕψ) = (aϕ)ψ formula (amely formailag az asszociativit´asra eml´ekeztet). uggv´enynek nevezik. A Kalkulus tant´argyban a f¨ uggv´enyeket — szint´en lek´epez´esek — balr´ol ´ırj´ak, a szorzatukat o¨sszetett f¨ CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Ha a lek´epez´est mint valamilyen v´egrehajtand´o folyamatot, cselekedetet k´epzelj¨ uk el, akkor a szorz´asuk az egym´as ut´ani v´egrehajt´ast jelenti. Ezen elk´epzel´es nem ´all messze a val´os´agt´ol pl. abban az esetben, amikor ϕ is ´es ψ is egy-egy sz´am´ıt´og´epes program, amely az inputhoz az outputot rendeli — ekkor a szorzatlek´epez´es a k´et program egym´as ut´ani v´egrehajt´as´at jelenti u ´gy, hogy az els˝o outputja a m´asodik inputja. Mivel a lek´epez´esek is megfeleltet´esek, a lek´epez´esek szorz´asa is asszociat´ıv (abban az esetben, ha o¨sszeszorozhat´ok, azaz az ´erkez´esi ´es indul´asi halmazok illeszkednek” az al´abbi t´etelnek megfelel˝oen. ” 10. T´ etel. Legyenek f : A → B, g : B → C ´es h : C → D lek´epez´esek. Ekkor (fg)h = f(gh). (Itt mindk´et oldalon A → D lek´epez´es ´all.) Ahogy a megfeleltet´esekn´el (a feladatok, p´eld´ak tan´ us´aga szerint) ´erdekes ¨osszef¨ ugg´esek vannak a tulajdons´agok ´es a szorz´as k¨oz¨ott, lek´epez´esekn´el is ez a helyzet. Fontos az al´abbi t´etel.
11. T´ etel. Amennyiben a sz´obanforg´ o k´et lek´epez´es ¨osszeszorozhat´ o, akkor (1) K´et injekt´ıv lek´epez´es szorzata injekt´ıv. (2) K´et sz¨ urjekt´ıv lek´epez´es szorzata sz¨ urjekt´ıv. (3) K´et bijekt´ıv lek´epez´es szorzata bijekt´ıv. (4) Ha k´et lek´epez´es szorzata sz¨ urjekt´ıv, akkor a m´ asodik t´enyez˝o sz¨ urjekt´ıv. (5) Ha k´et lek´epez´es szorzata injekt´ıv, akkor az els˝ o t´enyez˝o injekt´ıv.
34
Bizony´ıt´as: Legyen f : A → B ´es g : B → C. (1) Ha mindkett˝o injekt´ıv, akkor tetsz˝oleges x, y ∈ A-ra ha x(fg) = y(fg), akkor (xf)g = (yf)g, a g injektivit´as´at felhaszn´alva innen xf = yf, s most az f injektivit´asa miatt x = y. Teh´at fg injekt´ıv. (2) Ha mindkett˝o sz¨ urjekt´ıv, akkor tetsz˝oleges c ∈ C eset´en (a g sz¨ urjektivit´asa miatt) van olyan b ∈ B, hogy bg = c. Viszont f is sz¨ urjekt´ıv, ez´ert van olyan a ∈ A, amelyre af = b. Ez´ert a(fg) = (af)g = bg = c. Teh´at c-nek van o˝se. Teh´at fg is sz¨ urjekt´ıv. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
(5) Tegy¨ uk fel hogy fg injekt´ıv. Legyen x, y ∈ A tetsz˝oleges. Ha xf = yf, akkor (xf)g = (yf)g. Innen x(fg) = y(fg). A szorzat injektivit´asa szerint x = y. Teh´at f injekt´ıv. (4) Tegy¨ uk fel, hogy fg sz¨ urjekt´ıv. Legyen c ∈ C tetsz˝oleges. A feltev´es miatt van olyan a ∈ A, hogy a(fg) = c. De ekkor az af ∈ B elemre (af)g = a(fg) = c, teh´at c-nek van g melletti o˝se: af. Q.e.d.
Lek´ epez´ es inverze B´armely A halmaz eset´en az A → A, x → x lek´epez´est az A halmaz identikus lek´ epez´ es´ enek nevezz¨uk ´es idA -val jel¨olj¨ uk. Ez az a lek´epez´es, amely nem csin´al semmit”. ” Defin´ıci´ o. Legyenek f : A → B ´es g : B → A lek´epez´esek. Akkor mondjuk, hogy g inverze f-nek, ha fg = idA ´es gf = idB . Vil´agos, hogy ez egy szimmetrikus viszony: g akkor ´es csak akkor inverze f-nek, ha f inverze g-nek. Ny´ıldiagrammal ezt ´ıgy a´br´azolhatjuk:
f A
B
g 35
Az ´abra r´eszben m´ar meg is indokolja, hogy mi´ert igaz az al´abbi t´etel . CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
12. T´ etel. Legyen f : A → B tetsz˝ oleges lek´epez´es. (1) Akkor ´es csakis akkor l´etezik f-nek inverze, ha f bijekt´ıv. (2) Ha f bijekt´ıv, akkor egy ´es csakis egy inverze l´etezik, m´egpedig az a g : B → A lek´epez´es, amely tetsz˝oleges b ∈ B elemhez azt az egy´ertelm˝ uen meghat´arozott a elemet rendeli, amelyre af = b. (Azaz az inverz lek´epez´es minden elemhez annak a kiindul´ asi lek´epez´es szerinti o˝s´et rendeli.) (Azaz tetsz˝ oleges a ∈ A ´es b ∈ B eset´en bg = a akkor ´es csak akkor, ha af = b) Bizony´ıt´ as (R´eszletek): Ha f-nek g inverze, akkor fg = idA , ami bijekt´ıv, teh´at injekt´ıv. Ez´ert a szorzat els˝o t´enyez˝oje, urjekt´ıv, teh´at a szorzat m´asodik t´enyez˝oje, f is sz¨ urjekt´ıv. Ezzel azaz f is injekt´ıv. M´asr´eszt gf = idB , ami bijekt´ıv ´es ez´ert sz¨ bel´attuk, hogy ha f-nek van inverze, akkor f bijekt´ıv. Ha g1 is ´es g2 is inverze f-nek, akkor — azon nyilv´anval´o t´eny szerint, hogy a semmittev˝o identikus lek´epez´essel val´o szorz´as ” nem csin´al semmit” — kapjuk, hogy g1 = g1 idA = g1 (fg2 ) = (g1 f)g2 = idB g2 = g2 . A kapott g1 = g2 egyenl˝os´eg igazolja az ” inverz egy´ertelm˝ us´eg´et. Q.e.d. (r´eszben) 13. T´ etel. Bijekt´ıv lek´epez´es inverze szint´en bijekt´ıv. Bizony´ıt´ as Ha g inverze f-nek, akkor f inverze g-nek. Teh´at g-nek is van inverze, ´es ez´ert az el˝oz˝o t´etel szerint bijekt´ıv. Q.e.d Mivel egy f bijekt´ıv lek´epez´esnek pontosan egy inverze van, annak jel¨ol´es´ere az f −1 jel¨ol´est haszn´aljuk. (A sz¨ovegk¨ornyezet d¨onti el, hogy megfeleltet´es avagy lek´epez´es inverz´er˝ol van-e sz´o! Term´eszetesen a lek´epez´esek maguk is megfeleltet´esek, ´ıgy megfeleltet´es-inverz¨ uk mindig van, viszont lek´epez´esinverz¨ uk csak a bijekt´ıveknek van.) Az al´abb t´etelt — t´ ulpreciz´ırozott bizony´ıt´as helyett — csak az azt k¨ovet˝o a´br´aval szeml´eltetj¨ uk: 14. T´ etel. Legyenek f : A → B ´es g : B → C bijekt´ıv lek´epez´esek. Ekkor az fg : A → C bijekt´ıv lek´epz´es inverze (fg)−1 = g −1 f −1 . CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
36
f
B
A
g C
b
a f -1
c g -1
a(fg) = c miatt c(fg)−1 = a. Tov´abb´a c(g −1 f −1 ) = (cg −1 )f −1 = bf −1 = a. Mivel mindketten C → A lek´epez´esek ´es b´armely c ∈ C-t ugyanoda k´epeznek le, ez´ert (fg)−1 = g −1 f −1 . Q.e.d. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Most, hogy m´ar eleget tudunk a lek´epez´esekr˝ol ´es rel´aci´okr´ol, az ideje, hogy visszat´erj¨ unk a halmazok sz´amoss´ag´ahoz. Az ul sok eleme van (´es az ilyesmi ellentmond´asokhoz vezetne), de ezen u ´gy ¨osszes halmazb´ol a´ll´o o¨sszess´eg nem halmaz mert t´ alyoknak. A rel´aci´o fogalma nemcsak halmazon, hanem — seg´ıt¨ unk, hogy az ilyen t´ ul nagy o¨sszess´egeket elnevezz¨ uk oszt´ minden v´altoztat´as n´elk¨ ul — oszt´alyon is ´ertelmes. 15. T´ etel. Az o¨sszes halmazok H-val jel¨olt oszt´ aly´ an az egyenl˝o sz´amoss´ag´ uak” rel´ aci´ o, azaz az {(A, B) ∈ H2 : |A| = |B|} ” aci´ o. rel´ aci´o ekvivalenciarel´ uk fel, hogy Bizony´ıt´ as: Jel¨olje ρ a k´erd´eses rel´aci´ot. Mivel b´armely A ∈ H-ra idA : A → A bijekci´o, ρ reflex´ıv. Tegy¨ −1 (A, B) ∈ ρ, azaz l´etezik egy ϕ : A → B bijekci´o. Ekkor — m´ar tudjuk — ϕ-nek van lek´epez´esinverze, ´es ϕ : B → A is bijekci´o. Ez´ert (B, A) ∈ ρ. Teh´at ρ szimmetrikus. Most tegy¨ uk fel, hogy (A, B), (B, C) ∈ ρ. Ez azt jelenti, hogy l´eteznek ϕ : A → B ´es ψ : B → C bijekci´ok. Azonban — kor´abbi t´etel¨ unk szerint — bijekci´ok szorzata is bijekci´o. Teh´at ϕψ : A → C bijekci´o, ´es ez´ert (A, C) ∈ ρ. Ez´ert ρ tranzit´ıv. Q.e.d. Most — szemben az el˝oz˝ovel — egy messze-messze nem trivi´alis t´etelt mondunk ki. El˝obb egy amoss´ aga kisebb-egyenl˝ o, mint a B halmaz Defin´ıci´ o: Legyen A ´es B halmaz. Azt mondjuk, hogy az A halmaz sz´ ıv lek´ epez´ es. (Nem meglep˝o hogy) azt mondjuk, hogy az A halmaz sz´amoss´aga, jelben |A| ≤ |B|, ha l´etezik A → B injekt´ 37
sz´ amoss´ aga kisebb, mint a B halmaz sz´amoss´aga, jelben |A| < |B|, ha |A| = |B| (azaz nem l´etezik a k´et halmaz k¨oz¨ott
bijekci´o) ´es |A| ≤ |B| (de l´etezik A → B injekci´o). Az eddigi ismereteink szerint pl. |{1, 2}| < |{1, 2, 3}|, hiszen a {1, 2} → {1, 2, 3}, 1 → 1, 2 → 2 lek´epez´es injekt´ıv, bijekci´o ´ ´altal´aban is, a nemnegat´ıv eg´esz sz´amokra a < tov´abbra is azt jelenti, mint eddig. pedig nyilv´an nem l´etezik. Es Tetsz˝oleges A halmazra |A| < |P (A)|, hiszen m´ar l´attuk, hogy ez a k´et sz´amoss´ag nem egyenl˝o, s tov´abb´a az A → P (A), a → {a} lek´epez´es nyilv´an injekt´ıv. Azt is tudjuk m´ar, hogy |N| < |R|, hiszen m´ar l´attuk, hogy ez a k´et sz´amoss´ag nem egyenl˝o, s tov´abb´a az N → R, n → n lek´epez´es nyilv´an injekt´ıv. Itt a be´ıg´ert t´etel: CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
16. T´ etel. (Antiszimmetria ´es dichotomia) B´armely k´et halmaz sz´amoss´aga o¨sszehasonl´ıthat´ o, azaz b´ armely A ´es B halmazra |A| ≤ |B| vagy |B| ≤ |A|. Tov´abb´a ha |A| ≤ |B| ´es |B| ≤ |A| (azaz mindk´et halmaz injekt´ıv m´ odon lek´epezhet˝o a m´ asikba), akkor |A| = |B| (azaz l´etezik a k´et halmaz k¨oz¨ott bijekci´o). A tov´abbiakban els˝osorban megsz´aml´alhat´oan v´egtelen (azaz ℵ0 sz´amoss´ag´ u) halmazokkal foglalkozunk, hiszen az informatik´aban legink´abb ezek l´epnek fel. (Pl. a rekurz´ıvan felsorolhat´o halmazok, a CF nyelvek, stb.) 17. T´ etel. ℵ0 (azaz a megsz´ aml´ alhat´ oan v´egtelen) a legkisebb v´egtelen sz´amoss´ag. Bizony´ıt´ as: Defin´ıci´o szerint ℵ0 = |N|. Legyen A tetsz˝oleges v´ egtelen halmaz. Azt kell bel´atnunk, hogy ℵ0 ≤ |A|. Azaz azt, hogy l´etezik N → A injekt´ıv lek´epez´es. Rekurz´ıvan megadunk” egy ϕ : N → A injekt´ıv lek´epez´est. ” ul, azaz az A \ {a1} V´alasszunk ki egy a1 ∈ A elemet tetsz˝olegesen, ´es legyen 1ϕ = a1. Ezut´an a marad´ek elemek k¨oz¨ ´ halmazb´ol, v´alasszunk ki egy a2 elemet, ´es legyen 2ϕ = a2. Es ´ıgy tov´abb. Ha 1ϕ = a1, . . ., nϕ = an m´ar defini´alt, akkor ures A \ {a1, . . . , an} halmazb´ol, ´es legyen (n+ 1)ϕ = an+1 . Az A \ {a1, . . . , an} v´alasszunk ki egy tetsz˝oleges an+1 elemet a nem¨ halmaz az´ert nem u ¨res, mert n darab elem´enek elhagy´asa ut´an egy v´egtelen halmaz nem v´alhat u ¨ress´e (hisz ellenkez˝o esetben A-nak legfeljebb n elem lenne). 38
Ezzel rekurz´ıvan minden n-re defini´altuk nϕ-t, azaz megadunk egy ϕ : N → A lek´epez´est. Ha n = k, mondjuk k < n, akkor / {a1 , . . . , ak , . . . , an−1 }, ´es ´ıgy nϕ = an = ak = kϕ. Teh´at ϕ injekt´ıv. Q.e.d. an ∈ A \ {a1, . . . , ak , . . . , an−1 } miatt an ∈ Kritikai megjegyz´es: b´ar — a k´enyelem kedv´e´ert — u ´gy fogalmaztunk, hogy megadunk” egy ϕ-t, val´oj´aban csak azt ” etezik alkalmas ϕ. (Az´ert nem besz´elhet¨unk t´enyleges megad´asr´ol”, mert semmit sem mondtunk arr´ol, mutattuk meg, hogy l´ ” hogy konkr´etan hogyan kell az an+1 elemet a v´egtelen A \ {a1 , . . . , an } halmazb´ol v´alasztani. Mindez azonban nem zavarja a bizony´ıt´ast. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
39
3. (2007.szept.18.) el˝ oad´ as Eml´ ekeztet˝ o: |A| = |B| ⇐⇒ ∃A → B bijekci´o |A| ≤ |B| ⇐⇒ ∃A → B injektv lek´epez´es |A| < |B| ⇐⇒ |A| ≤ |B| ´es |A| = |B|.
Meglepet´ es H´any p´aros pozit´ıv eg´esz sz´am van? A B := {2k : k ∈ N} jel¨ol´essel, |B| =? Azaz mi a B halmaz sz´amoss´aga? Megold´as: Mivel B nyilv´an v´egtelen, ez´ert az el˝oz˝o (a legkisebb ∞ sz´amoss´agra vonatkoz´o t´etel szerint) ℵ0 ≤ |B|. M´asr´eszt a B → N, n → n lek´epez´es injekt´ıv, ez´ert |B| ≤ |N| = ℵ0 . A dichotomia t´etel szerint |B| = ℵ0 = |N|. Khmmmmmmmm! Nincs itt valami hiba? A pozit´ıv eg´eszek fel´et (t.i. a p´aratlanokat) kidobjuk, ´es m´eg mindig ugyanannyi marad? Tal´an rossz a dichotomia t´etel? Vagy rosszul id´eztem? Pr´ob´aljuk an´elk¨ ul! Teh´at B := {2k : k ∈ N} a p´aros pozit´ıv eg´eszek halmaza. Legyen ϕ : B → N, x → x 2 . J´ol l´athat´o, hogy ez bijekci´o. ´ ez m´eg csak a kezdet! Teh´at csakugyan |B| = |N|. Ez van. Es CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
18. T´ etel. Legyen A tetsz˝ oleges halmaz. (1) |A| = ℵ0 akkor ´es csak akkor, ha A ism´ etl´ es n´ elk¨ uli v´ egtelen sorozatba
rendezhet˝ o, azaz megadhat´o egy, az N elemeivel indexelt
a1 , a2 , a3 , a4 , . . . sorozat, amely A minden egyes elem´et pontosan egyszer tartalmazza. egtelen ´es sorozatba szedhet˝ o, azaz megadhat´o egy, az N elemeivel indexelt (2) |A| = ℵ0 akkor ´es csak akkor, ha A v´ a1 , a2 , a3 , a4 , . . . sorozat, amely A minden egyes elem´et tartalmazza (esetleg t¨obbsz¨or is). 40
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Bizony´ıt´ as (1) k¨onnyen ad´odik. Ha A a mondott m´odon sorozatba rendezhet˝o, akkor a ϕ : N → A, n → an lek´epez´es nyilv´an bijekci´o, ´es ez´ert |A| = ℵ0 . Ha pedig |A| = ℵ0 , akkor l´etezik ϕ : N → A bijekci´o; ez esetben az an := nϕ k´eplettel defini´alt sorozat az A ism´etl´es n´elk¨ uli sorozatba rendez´ese. (2) evidens, ha A v´eges. Tegy¨ uk fel, hogy A v´egtelen ´es sorozatba szedhet˝o, teh´at minden eleme szerepel a sorozatban, de esetleg t¨obbsz¨or is. Valahogy ´ıgy: a, b, c, a,c,b,a,d, e, c,b,u, a,v, a,u, . . . A t¨obbsz¨or el˝ofordul´o elemekb˝ol csak az els˝o el˝ofordul´ast megtartva ´es a t¨obbit (eset¨ unkben a k´ek sz´ın˝ ueket) kihagyva: a, b, c, d, e, u, v, . . . az A elemeit ism´etl´es n´elk¨ uli sorozatba rendezt¨ uk. Ez a sorozat v´egtelen, hiszen A is az. Teh´at |A| = ℵ0 . (2) ford´ıtott ir´anyban (1)-b˝ol k¨ovetkezik. Q.e.d. Feladat Mutassuk meg, hogy |Z| = ℵ0 . Megold´ as: ´Ime Z egy sorozatba rendez´ese: 0, 1, −1, 2, −2, 3, −3, 4, −4, 5, −5, 6, −6, . . . Feladat: Mutassuk meg, hogy |Q| = ℵ0 . Megold´ as: A nyilak ment´en haladva sorozatba szedj¨ uk, ld. el˝oz˝o t´etel (2). (Nem baj, hogy a sorozatban minden racion´alis 6 4 sz´am t¨obbsz¨or fell´ep, hiszen pl. 2 = 2 = 3 = · · ·!)
41
- 5/1 - 4/1 - 3/1 - 2/1 - 1/1
0/1
1/1
2/1
3/1
4/1
5/1
- 5/2 - 4/2 - 3/2 - 2/2 - 1/2
0/2
1/2
2/2
3/2
4/2
5/2
- 5/3 - 4/3 - 3/3 - 2/3 - 1/3
0/3
1/3
2/3
3/3
4/3
5/3
- 5/4 - 4/4 - 3/4 - 2/4 - 1/4
0/4
1/4
2/4
3/4
4/4
5/4
- 5/5 - 4/5 - 3/5 - 2/5 - 1/5
0/5
1/5
2/5
3/5
4/5
5/5
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A mai o´ra k¨ovetkezm´enye az al´abbi t´etel. M´ar az o´kori g¨or¨og¨ok is tudt´ak, de a pitagoreusok — Pitagorasz tan´ıtv´anyai — a t´etel felfedez˝oj´et v´ızbe folytott´ak, nehogy kider¨ ulj¨on az igazs´ag. Persze az o´kori g¨or¨og¨ok m´ask´ent okoskodtak, o˝k azt mutatt´ak meg, hogy az egys´egn´egyzet a´tl´oja nem lehet racion´alis sz´am. B´ar az al´abbi megfontol´as csak egy sor, az el˝ok´esz¨ uletek miatt a jelen esetben m´eg nem a´ll´ıthatjuk, hogy a mi megk¨ozel´ıt´es¨ unk az egyszer˝ ubb. 19. T´ etel. L´etezik irracion´alis sz´ am (azaz olyan val´ os sz´ am, amelyik nem racion´ alis). Bizony´ıt´ as:|R| = ℵ0 , |Q| = ℵ0 . Ez´ert R = Q. Q.e.d. A megsz´aml´alhat´oan v´egtelen sz´amoss´aggal (=ℵ0 ) kapcsolatban a legt¨obb feladat k¨onnyen megv´alaszolhat´o az al´abbi t´etel seg´ıts´eg´evel.
20. T´ etel. (Sz´amoss´agaritmetika alapt´etele ´es egyebek) (1) Legfeljebb megsz´ aml´ alhat´ oan v´ egtelen sok legfeljebb megsz´ aml´ alhat´ oan v´ egtelen halmaz uni´ oja is legfeljebb megsz´ aml´ alhat´ oan v´ egtelen. Azaz ha |I| ≤ ℵ0 ´es minden i ∈ I-re |Ai | ≤ ℵ0 , akkor | i∈I Ai| ≤ ℵ0 . 42
(2) Ha 1 < n ∈ N ´es |A1| = · · · = |An | = ℵ0 , akkor |A1 × · · · × An | = ℵ0 . Azaz v´ eges sok megsz´aml´alhat´oan v´egtelen halmaz Descartes-szorzata is megsz´ aml´ alhat´ oan v´egtelen. (3) B´armely A ´es B halmazra |A| ≤ |B| vagy |B| ≤ |A| (dichotomia), ´es ha mindkett˝o teljes¨ ul, akkor |A| = |B| (antiszimmetria). (4) (Sz´ amoss´agaritmetika alapt´etele) Ha A ´es B halmazok ´es legal´abb az egyik v´egtelen, akkor |A ∪ B| = |A × B| = max(|A|, |B|). CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
M´ıg (3) ´es (4) bizony´ıt´asa messze meghaladja a jelen kurzus kereteit, (1)-et ´es (2)-t bel´atjuk (nagyon hasonl´ıt ahhoz, ahogy azt igazoltuk, hogy |Q| = ℵ0 ). (1) Bizony´ıt´ asa: Mivel ℵ0 a legkisebb v´egtelen sz´amoss´ag, ez´ert I ´es az Ai -k mindegyike v´eges vagy megsz´aml´alhat´oan unk szerint v´egtelen. Tegy¨ uk fel, hogy az A := i∈I Ai uni´o v´egtelen, hiszen ellenkez˝o esetben nincs mit igazolni. Kor´abbi t´etel¨ el´eg azt bel´atni, hogy A (ism´etl´est megenged˝o) sorozatba szedhet˝o. Feltehet˝o, hogy I = {i1 , i2, i3, . . .}, tov´abb´a Ai1 = {a11, a12, a13, . . .}, Ai2 = {a21, a22, a23, . . .}, Ai3 = {a31, a32, a33, . . .}, ... azaz hogy a fell´ep˝o halmazok v´egtelen sorozatba vannak szedve (term´eszetesen ism´etl´est megengedve). M´armost a nyilak ment´en
43
a11
a12
a13
a14
a15
a16
a21
a22
a23
a24
a25
a26
a31
a32
a33
a34
a35
a36
a41
a42
a43
a44
a45
a46
a51
a52
a53
a54
a55
a56
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
haladva A-t sorozatba tudjuk szedni. Ezzel (1)-et bel´attuk. (2) n = 2-re hasonl´o a´br´aval is bizony´ıthat´o, de a´brarajzol´as helyett k¨onnyebb (1)-b˝ol sz´armaztatni: ha |A1| = |A2| = ℵ0 , akkor egyr´eszt minden egyes a ∈ A1 -re |A2| = |{(a, b) : b ∈ A2}| (hiszen a b → (a, b) lek´epez´es bijekt´ıv), m´asr´eszt pedig A1 × A2 =
{(a, b) : b ∈ A2}.
a∈A1
Ezzel megvan az n szerinti teljes indukci´o kezdeti l´ep´ese. Ha 2 < n ´es a kisebb ´ert´ekekre (2) igaz, akkor az (A1 × · · · × An−1 ) × An → A1 × · · · × An ,
(a1, . . . , an−1 ), an → (a1 , . . . , an1 , an )
lek´epez´es bijekt´ıv. Mivel az els˝onek eml´ıtett halmaz az indukci´os hipot´ezis szerint (el˝obb n − 1-re, majd 2-re alkalmazva) megsz´aml´alhat´o, a m´asodik halmaz is. Q.e.d. Feladat: H´any nemnegat´ıv eg´esz sz´am van? 1. Megold´ as: Az N0 → N, x → x + 1 lek´epez´es bijekt´ıv. Ez´ert |N0| = |N| = ℵ0 . 44
2. Megold´ as: N0 = N ∪ {0}, ´es az el˝oz˝o t´etel (1) pontja alkalmazhat´o. Feladat: H´any irracion´alis sz´am van? Megold´ as: Jel¨olje x a keresett sz´amoss´agot. Ekkor x = |R \ Q|. Mivel R = Q ∪ (R \ Q), ez´ert a sz´amoss´agaritmetika alapt´etele (=el˝oz˝o t´etel (4) pontja) szerint |R| = max(|Q|, x). M´ar l´attuk, hogy ℵ0 = |Q| < |R|. Ez´ert x = |R|. Azaz ugyanannyi irracion´alis sz´am van, mint val´os sz´am, teh´at t¨obb, mint racion´alis sz´am. A val´os sz´amok halmaz´anak sz´amoss´ag´at kontinuum sz´amoss´agnak nevezik. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Feladat: H´any v´eges hossz´ us´ag´ u bitsorozat van? us´ag´ u bitsorozatok Bi -vel jel¨olt halmaza v´eges. (Mellesleg ´eppen |Bi | = 2i , de ez Megold´ as: Adott i ∈ N0 -ra az i-hossz´ a konkr´et sz´am most nem fontos.) Az ¨osszes bitsorozat halmaza B := i∈N0 Bi . Minthogy |N0| = ℵ0 , az alapt´etel (1) pontja szerint |B| ≤ ℵ0 . De B nyilv´an v´egtelen, tov´abb´a ℵ0 a legkisebb v´egtelen sz´amoss´ag, ez´ert |B| = ℵ0 . amnak nevez¨unk, ha valamely (nem azonosan nulla) racion´alis egy¨utthat´os polinomnak gy¨oke. Egy sz´amot algebrai sz´ √ √ 3 9 x2 Ilyen pl. a 2, amelyik az x2 −2 polinom gy¨oke, ilyen a 3 2 is (az x3 −2 polinom gy¨oke), ´es ilyenek pl. a 2 x5 − 5 x4 + 3 +x−1 polinom gy¨okei (az m´as k´erd´es, hogy ezeket nem ´ırjuk fel explicit alakban). Term´eszetesen minden q racion´alis sz´am algebrai, ti. az x − q racion´alis egy¨ utthat´os polinom gy¨oke. Az is igaz, hogy minden olyan sz´am algebrai, amelyet racion´alis sz´amokb´ol kiindulva a n´egy alapm˝ uvelet (+, −, · ´es /) valamint tetsz˝oleges eg´eszkitev˝os gy¨okvon´as ism´etelt felhaszn´al´as´aval v´eges sz´am´ u l´ep´esben fel´ırhatunk — ezt azonban m´ar nem olyan k¨onny˝ u bel´atni). Lindemann 1882-ben — nagyon neh´ez bizony´ıt´assal — kimutatta, hogy a π nem algebrai sz´am. Ebb˝ol ar´anylag k¨onnyen ad´odik, hogy a k¨or nem n´egysz¨oges´ıthet˝o”. ” amoknak nevezz¨uk. Majd egyszer tanulni fogjuk, hogy egy n-edfok´u A nem algebrai sz´amokat transzcendens sz´ polinomnak legfeljebb n gy¨oke van. (n ≤ 2-re m´ar most is tudjuk.) 21. T´ etel. Az algebrai sz´ amok halmaza megsz´ aml´ alhat´ oan v´egtelen (azaz ℵ0 sz´amoss´ag´ u). Bizony´ıt´ as: A legfeljebb n-edfok´ u racion´alis egy¨ utthat´os polinomok Pn := {an xn + an−1 xn−1 + · · · + a0 : a0, . . . , an ∈ Q} halmaza ´es a Qn+1 halmaz k¨oz¨ott az an xn + an−1xn−1 + · · ·+ a0 → (an , an−1 , . . . , a0) lek´epez´es bijekci´ot l´etes´ıt. Az ut´obbi halmaz az alapt´etel (2) pontja szerint megsz´aml´alhat´oan v´egtelen, ez´ert |Pn | = ℵ0 . Ez´ert az alapt´etel (1) pontja szerint a racion´alis egy¨ utthat´os polinomok P = n∈N Pn halmaza is megsz´aml´alhat´oan v´egtelen. Jel¨olje Ap a p ∈ P polinom gy¨okeinek halmaz´at, 45
ez v´eges. (Ha p az azonosan 0 polinom, akkor Ap legyen az u ¨reshalmaz.) Az algebrai sz´amok halmaza A = p∈P Ap. Ism´et az alapt´etel (1) pontj´ara hivatkozva |A| ≤ ℵ0 , de mivel v´egtelen, ez´ert |A| = ℵ0 . Q.e.d. Az al´abbi t´etelt sz´amoss´agok n´elk¨ ul nem olyan k¨onny˝ u bizony´ıtani, mint ahogy most k¨ovetkezik. (Ezzel bev´altjuk azon ´ıg´eret¨ unket, hogy a sz´amoss´agok j´ok valamire a v´eges vil´agban).
22. T´ etel. L´etezik transzcendens sz´ am. Bizony´ıt´ as: Az algebrai sz´amok halmaz´at A-val jel¨olve |A| = ℵ0 = |R|. Q.e.d. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Feladat: Melyek megsz´aml´alhat´oan v´egtelenek az al´abbi halmazok k¨oz¨ ul? (a) U := {X : X ⊆ N ´es X az o¨sszes pr´ımsz´amot tartalmazza}; (b) V := {X : X ⊆ Q ´es X v´eges}; (c) W := {f | f : N → N sz¨ urjekt´ıv lek´epez´es}; (d) M := {f | f : Q → N injekt´ıv lek´epez´es}? Megold´ asok: (a) U := {X : X ⊆ N ´es X az o¨sszes pr´ımsz´amot tartalmazza}; Legyen B ⊆ N a nempr´ımek halmaza. Ekkor B v´egtelen, ´es ez´ert ℵ0 ≤ |B| < |P (B)|. Mivel P (B) → U, X → X ∪ {¨osszes pr´ımsz´am} injekt´ıv (s˝ot bijekt´ıv is, de erre nincs most sz¨ uks´eg¨ unk), ez´ert |P (B)| ≤ |U|. Teh´at |U| = ℵ0 . (b) V := {X : X ⊆ Q ´es X v´eges}. u r´eszhalmazok halmaz´at. Jel¨olje {x1 < · · · < xn } ∈ Vn azt, hogy {x1, . . . , xn } ∈ Vn ´es x1 < x2 < · · · < Jel¨olje Vn az n-elem˝ xn . M´armost Vn → Qn , {x1 < · · · < xn } → (x1 , . . . , xn ) injekt´ıv lek´epz´es. Ez´ert — az alapt´etel (2)-b˝ol ad´od´o |Q| = ℵ0 -at is kihaszn´alva — |Vn | ≤ |Qn | = ℵ0 . Ez´ert az Alapt´etel (1) szerint |V | = | n∈N Vn | ≤ ℵ0 . Mivel V v´egtelen, |V | = ℵ0 . 46
(c) W := {f | f : N → N sz¨ urjekt´ıv lek´epez´es}. Jel¨olje A a p´aros, B pedig a p´aratlan pozit´ıv eg´eszek halmaz´at. Mivel ℵ0 a legkisebb v´egtelen sz´amoss´ag ´es nyilv´an |A|, |B| ≤ |N|, ez´ert |A| = |B| = ℵ0 . Ez´ert l´etezik egy ϕ : A → N bijekci´o. urjekci´ot (azaz W -beli elemet): x ∈ A-ra legyen xψC := xϕ, , Most minden C ∈ P (B)-hez defini´alunk egy ψC : N → N sz¨ ul x ∈ B \ C-re legyen xψC = 2. x ∈ C-re legyen xψC = 1, ´es v´eg¨ urjekt´ıv, hiszen az eleve sz¨ urjekt´ıv ϕ-t terjesztett¨ uk ki. Teh´at ψC ∈ W . Az is evidens, hogy k¨ ul¨onb¨oz˝o Vil´agos, hogy ψC sz¨ ´ C ∈ P (B)-khez k¨ ul¨onb¨oz˝o ψC -k tartoznak. Ez´ert a P (B) → W , C → ψC lek´epez´es injekt´ıv. Igy ℵ0 = |B| < |P (B)| ≤ |W |, teh´at ℵ0 = |W |. (d) M := {f | f : Q → N injekt´ıv lek´epez´es}? A megold´as azon az a´ltal´anos elven alapul, hogy sz´amoss´agi k´erd´esek eset´en egy halmaz helyett vehet¨ unk egy vele azonos sz´amoss´ag´ u halmazt. Persze ez ´ıgy sz´o szerint nem igaz, pl. ha egy feladatban a pr´ımsz´amok halmaz´ar´ol is ´es az eg´esz sz´amok halmaz´ar´ol is sz´o van, akkor nem biztos, hogy mindkett˝o helyett egyidej˝ uleg tekinthetj¨ uk mondjuk a racion´alis sz´amok halmaz´at — ez´ert ezt az ´altal´anos elvet kell˝o k¨or¨ ultekint´essel lehet csak alkalmazni. Erre fogunk most p´eld´at l´atni. El˝osz¨or az al´abbi feladatot oldjuk meg (Q helyett N-et tekintj¨ uk): CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
(d’) M := {f | f : N → N injekt´ıv lek´epez´es}? / A. (Szok´as χA -t az A karakterisztikus Legyen A ∈ P (N). Legyen χA : N → {0, 1}, n → 1, ha n ∈ A ´es n → 0, ha n ∈ f¨ uggv´eny´enek nevezni.. C´elunk ezzel az, hogy χA mondja meg, milyen sebesen, azaz mekkora ugr´asokkal n¨ovekedjen az al´abb uan monoton (´es ez´ert injekt´ıv) ϕA : N → N lek´epez´est: defini´aland´o ϕA .) Most defini´aljuk rekurzi´oval a szigor´ 1ϕA = 1 + 1χA ,
(n + 1)ϕA := nϕA + 1 + (n + 1)χA .
Vil´agos, hogy A = B eset´en ϕA = ϕB , ugyanis ha k a legkisebb eleme A B-nek, akkor 1ϕA = 1ϕB , . . ., (k−1)1ϕA = (k−1)ϕB , de kϕA = kϕB . Ez´ert a P (N) → M , A → ϕA lek´epez´es injekt´ıv. Ez´ert ℵ0 = |N| < |P (N)| ≤ |M |. (d’) ℵ0 < |M | = |{f | f : N → N injekt´ıv lek´epez´es}| ut´an (d) M := {f | f : Q → N injekt´ıv lek´epez´es} ? uks´eg¨ unk.) Mivel |Q| = ℵ0 = |N|, Megadunk egy g : M → M injekci´ot! (Val´oj´aban bijekci´o lesz, de erre a t´enyre nincs sz¨ r¨ogz´ıts¨ unk egy κ : Q → N bijekci´ot. Legyen g : M → M, ϕ → κϕ. Mivel injekt´ıv lek´epez´esek szorzata injekt´ıv, κϕ ∈ M, teh´at uk fel, hogy ϕ1g = ϕ2 g, azaz hogy κϕ1 = κϕ2 . A g t´enyleg egy M → M lek´epez´es. A g injektivit´as´anak kimutat´as´ahoz tegy¨ 47
bijekt´ıv κ-nak van inverze, azzal szorozzuk meg az el˝obbi egyenl˝os´eget balr´ol: κ−1 (κϕ1 ) = κ−1 (κϕ2). Az asszociativit´as szerint (κ−1 κ)ϕ1 = (κ−1 κ)ϕ2 . Mivel a z´ar´ojelben az idN lek´epez´es ´all, amely nem csin´al semmit”, kapjuk, hogy ϕ1 = ϕ2 . Teh´at g ” injekt´ıv, ´ıgy ℵ0 < |M | ≤ |M|, azaz |M| = ℵ0 . Feladat Legyen A = {0, 1, . . . , 11} ´es α = {(x, y) ∈ A2 : x < y − 1}. Milyen tulajdons´agai vannak az al´abbi rel´aci´onak: β := (α−1 ∪ α) ◦ (α−1 ∪ α) ? Megold´ as: Mivel α = {(x, y) ∈ A2 : y − x ≥ 2} ´es α−1 = {(x, y) ∈ A2 : x − y ≥ 2}, l´athat´o, hogy γ := α−1 ∪ α = {(x, y) ∈ A2 : ´n. teljes rel´ aci´ o. x ´es y t´avols´aga legal´abb 2}. Vegy¨ uk ´eszre, hogy β = γ ◦ γ = A2, az u 2 Val´oban, b´armely (x, z) ∈ A eset´en legfeljebb h´arom A-beli y van x-hez k¨ozel” (azaz 2-n´el kisebb t´avols´agra), legfeljebb ” h´arom van z-hez k¨ozel, ´ıgy biztos van olyan y, amely el´eg t´avol van” x-t˝ol is ´es z-t˝ol is, azaz amelyre (x, y) ∈ γ ´es (y, z) ∈ γ. ” Ez´ert (x, z) ∈ γγ = β. Teh´at A2 ⊆ β, s ´ıgy csakugyan β = A2. Ez´ert β reflex´ıv, szimmetrikus, tranzit´ıv, dichotom, nem antiszimmetrikus, ekvivalencia, nem r´eszbenrendez´es, nem rendez´es. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Ekvivalenciarel´ aci´ ok, oszt´ alyoz´ asok A lesz¨ uretelt term´est (pl. o˝szibarackot) ´ert´ekes´ıt´es el˝ott oszt´ alyozz´ ak (pl. m´eret, ´eretts´eg szerint). Az iskola tanul´oit ´evfolyamuk (´es esetleg tov´abbi szempontok) oszt´alyokba sorolj´ak. A biol´ogusok az ´el˝ol´enyeket sorolj´ak oszt´alyokba. Az eml´ıtett esetek mindegyik´eben arr´ol van sz´o, hogy egy adott halmazt p´aronk´ent diszjunkt (azaz u ¨res metszet˝ u) r´eszhalmazok uni´ojak´ent a´ll´ıtunk el˝o. Ez szolg´al alapul az al´abbihoz. alyoz´ as az A halmazon vagy Defin´ıci´ o: Legyen A tetsz˝oleges halmaz, ´es legyen C ⊆ P (A). Azt mondjuk, hogy C oszt´ alyoz´ asa az A halmaznak, ha m´as sz´oval oszt´ (1) b´armely X ∈ C-re X = ∅, (2) b´armely X, Y ∈ C-re X = Y vagy X ∩ Y = ∅, ´es (3) A = X∈C X alyoknak nevezz¨uk. A defin´ıci´o azt k¨oveteli meg, hogy Amennyiben C oszt´alyoz´asa az A halmaznak, akkor C elemeit oszt´ egyr´eszt az oszt´alyok ne legyenek u ¨resek, m´asr´eszt a k¨ ul¨onb¨oz˝o oszt´alyok legyenek diszjunktak, ´es harmadr´eszt az oszt´alyok fedj´ ek le A-t, azaz b´armely a ∈ A-ra l´etezzen X ∈ C, hogy a ∈ X. ıci´ onak vagy faktorhalmaznak is nevezni. Hamarosan l´atni M´as terminol´ogi´at k¨ovetve szok´as az oszt´alyoz´ast part´ fogjuk, hogy a faktorhalmaz a fogalomk´epz´es egyik fontos eszk¨oze. 48
Feladat: Melyek oszt´alyoz´asok az A adott halmazon az al´abbiak k¨oz¨ ul? (a) C = {X ⊆ {0, 1, . . . , 9} : |X| = 3}, A = {0, 1, . . . , 9}; (b) C = {{1, 3}, {2, 4}, {5}}, A = {1, 2, . . . , 5}; (c) C = {{1, 3}, {2, 4}, {5}}, A = {0, 1, . . . , 5} ? Megold´ as: (a) nem, mert b´ar nem¨ ures ´es A-t lefed˝o halmazokb´ol a´ll C, az oszt´alyok nem diszjunktak. (c) sem, mert az oszt´alyok nem fedik le A-t (a 0 kimarad). (b) igen. Jel¨ ol´ es: Legyen adott egy C oszt´alyoz´as az A halmazon. Vezess¨ uk be az al´abbi ekvialenciarel´aci´ot az A halmazon: ρ = ρC := {(a, b) ∈ A2 : ∃X ∈ C, hogy a, b ∈ X}. o ekvivalenci´anak nevez¨ unk) csakugyan ekvivalencia az A halmazon. 23. T´ etel. A fent defini´ alt ρC (amelyet a C-hez tartoz´ A t´etel igazol´asa hasznos (b´ar meglehet˝osen trivi´alis), egy´eni gyakorl´asra sz´ant feladat. Egy iskola oszt´alyai (mint oszt´alyoz´as) eset´en ρC nem m´as, mint az oszt´alyt´arsak” rel´aci´o. ” CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
Feladat: Az im´ent l´attuk, hogy C = {{1, 3}, {2, 4}, {5}} oszt´alyoz´as az A = {1, 2, . . . , 5} halmazon. ´Irjuk fel a hozz´a tartoz´o ekvivalenci´at! ρC = {(1, 1), (1, 3), (3, 1), (3, 3), (2, 2), (2, 4), (4, 2), (4, 4), (5, 5)}. Figyelj¨ uk meg, hogy sokkal r¨ovidebb volt az oszt´alyoz´ast le´ırni, mint a hozz´a tartoz´o ekvivalenci´at. Nemcsak az oszt´alyoz´asok hat´aroznak meg ekvivalenci´akat, hanem ford´ıtva is. P´eld´aul az a 2007-ben azonos szakra fel” vettek” rel´aci´o az SZTE els˝o´eves hallgat´oinak halmaz´an meghat´arozza az ´evfolyamok halmaz´at, ami oszt´alyoz´as az SZTE els˝o´eveseinek halmaz´an. Defin´ıci´ o: Legyen A halmaz, ρ ekvivalenciarel´aci´o az A-n ´es b ∈ A. Ekkor a bρ∗ := {c ∈ A : (b, c) ∈ ρ} halmazt a b elem ρ szerinti
blokkj´ anak
vagy oszt´ aly´ anak nevezz¨uk.
A ρ blokkjainak A/ρ := {bρ∗ : b ∈ A} halmaz´at az A halmaz ρ szerinti
oszt´ alyoz´ as´ anak
nevezz¨ uk. Jel¨ol´ese:
A/ρ . 49
faktorhalmaz´ anak
vagy ρ szerinti
24. T´ etel. Ha ρ ekvivalencia A-n, akkor A/ρ t´enyleg faktorhalmaz (azaz oszt´ alyoz´as) A-n. Bizony´ıt´ as (r´ eszlet): Ha a, b ∈ A-ra aρ∗ = bρ∗ , akkor be kell l´atnunk, hogy diszjunktak. Ha nem lenn´enek diszjunktak, akkor lenne egy c ∈ aρ∗ ∩ bρ∗ elem. Teh´at (a, c) ∈ ρ ´es (b, c) ∈ ρ. Legyen x ∈ aρ∗ tetsz˝oleges. Ekkor (a, x) ∈ ρ. A szimmetria miatt (c, a) ∈ ρ, ´ıgy a tranzitivit´asb´ol (c, x) ∈ ρ. Ism´et a tranzitivit´astra hivatkozva (b, x) ∈ ρ. Teh´at x ∈ bρ∗. Mivel x ∈ aρ∗ tetsz˝oleges volt, aρ∗ ⊆ bρ∗ . Az a ´es b szerep´et felcser´elve ugyan´ıgy kapjuk, hogy bρ∗ ⊆ aρ∗ . Teh´at bρ∗ = aρ∗ , ami ellentmond´as. Ez´ert az aρ∗ ´es bρ∗ blokkok m´egiscsak diszjunktak. Q.e.d.(r´eszben). Feladat: Adjuk meg a Z halmazon ´ertelmezett ρ = {(x, y) ∈ Z2 : 3 | x − y} ekvivalenci´ahoz tartoz´o oszt´alyoz´ast! Megold´ as: Z/ρ := { {. . . , −12, −9, −6, −3, 0, 3, 6, 9, 12, . . .}, {−11, −8, −5, −2, 1, 4, 7, 10, 13, . . .}, {−10, −7, −4, −1, 2, 5, 8, 11, 14, . . .} }. A kor´abbi p´eld´aval ellent´etben itt a rel´aci´o megad´asa egyszer˝ ubb, mint az oszt´alyoz´as´e. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
L´attuk, hogy az ekvivalenci´ak oszt´alyoz´ast (faktorhalmazt), az oszt´alyoz´asok (faktorhalmazok) pedig ekvivalenci´akat hat´aroznak meg. A k¨ovetkez˝o t´etel l´enyeg´eben azt fejezi ki, hogy — a r¨ogz´ıtett A halmazon ´ertelmezett — ekvivalenci´ak ´es oszt´alyoz´asok l´enyeg´eben ugyanazok: b´armelyiket is adjuk meg, a´tt´erhet¨ unk a m´asikra, ´es ha visszat´er¨ unk, az eredetihez jutunk. Ebben az a j´o, hogy mindig azt haszn´aljuk, ami sz´amunkra k´enyelmesebb: amelyet k¨onnyebb megadni vagy amellyel k¨onnyebb dolgozni. A l´enyeg´eben ugyanazok” nem matematikai fogalom, ez´ert a t´etel kiss´e komolyabb hangz´as´ ura lesz fogalmazva. A kor´abban ” bevezetett jel¨ol´esekre is ´ep´ıt¨ unk. 25. T´ etel. Legyen A tetsz˝ oleges halmaz, jel¨olje Part(A) az A-n ´ertelmezhet˝o oszt´ alyoz´asok (m´ as sz´ oval part´ıci´ok) halmaz´at, Eq(A) pedig az A-n ´ertelmezhet˝o ekvivalenci´ ak halmaz´at. Ekkor Eq(A) → Part(A),
ρ → A/ρ = {bρ∗ : b ∈ A} 50
bijekt´ıv lek´epez´es, amelynek inverze az al´abbi bijekci´o: Part(A) → Eq(A),
C → ρC .
A bizony´ıt´ast — amely hasznos de nem t´ ul r¨ovid gyakorl´o feladatnak is alkalmas — nem r´eszletezz¨ uk. Feladat: H´any ekvivalenciarel´aci´o defini´alhat´o egy h´aromelem˝ u halmazon? Megold´ as: Mivel (az el˝oz˝o t´etel szerint) az ekvivalenci´ak ´es az oszt´alyoz´asok l´enyeg´eben azonosak, c´elszer˝ u a jelen esetben k¨onnyebben kezelhet˝o ut´obbiakat megsz´amolni. Egyetlen olyan van, amelyiknek h´arom oszt´alya van (persze mind a h´arom egyelem˝ u). Egyetlen olyan van, amelyik csak egyetlen oszt´alyb´ol a´ll (ami persze az eg´esz halmaz, amelyet jel¨olj¨on A). A tov´abbiak egy k´etelem˝ u ´es egy egyelem˝ u oszt´alyb´ol a´llnak; az egyelem˝ u oszt´aly elem´et h´aromf´elek´eppen v´alaszthatjuk ki. Teh´at ¨ ot. ¨ h´arom tov´abbi van. Osszesen: CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A feladat nem k´erte, de az A = {1, 2, 3} jel¨ol´es mellett felsoroljuk mind az o¨t oszt´alyoz´ast: C1 = {{1}, {2}, {3}}, C2 = {{1, 2, 3}}, C3 = {{1}, {2, 3}}, C4 = {{2}, {1, 3}}, C5 = {{3}, {1, 2}}. Faktorhalmaz, mint fogalomalkot´ o eszk¨ oz: A fogalmak — nemcsak a matematik´aban, hanem azon k´ıv¨ ul is — gyakran u ´gy alakulnak ki, hogy vesz¨ unk egy ρ ekvivalenciarel´aci´ot egy A halmazon, ´es az A/ρ elemeit elnevezz¨ uk valahogy. P´eld´aul ha A a s´ık egyeneseinek halmaza ´es ρ a p´arhuzamoss´agi rel´aci´o (amelyik ekvivalencia), akkor egy egyenes ρ szerinti blokkj´at szok´as az egyenes ir´any´anak nevezni. Idetartozik az is, amit kor´abban absztrakci´oval val´o defin´ıci´onak mondtunk. Pl. ha A az o¨sszes halmazb´ol a´ll´o o¨sszess´eg ´es (X, Y ) ∈ ρ azt jelenti, hogy l´etezik X → Y bijekci´o, akkor X ρ-szerinti blokkj´at elnevezz¨ uk az X halmaz sz´amoss´ag´anak, ´es az A/ρ elemeit sz´amoss´agoknak. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
51
R´ eszbenrendez´ esek A (r´eszben)rendez´esek a hierarchia fogalm´at ragadj´ak meg matematikailag. Ez a fogalom az informatik´aban is fell´ep, hiszen pl. a szoftverek is hierarchikus rendbe szervezett kisebb egys´egekb˝ol (szubrutin, modul, elj´ar´as, stb.) ´ep¨ ulnek fel. eszbenrendezett halmaznak nevezz¨uk, ha A nem¨ures halmaz, ≤” pedig egy Defin´ıci´ o Az (A; ≤) p´art r´ ” r´eszbenrendez´esi rel´aci´o az A halmazon. Term´eszetesen ≤” helyett ´ırhatn´ank azt is, hogy ρ vagy α, de ≤” a leggyakoribb jel¨ol´es. Vigy´azat, a ≤” jel¨ol´es nem ” ” ” jelenti azt, hogy A elemei sz´amok! Defin´ıci´ o Legyen (A; ≤) egy r´eszbenrendezett halmaz, ´es legyen a, b ∈ A. a < b jel¨olje azt, hogy a ≤ b ´es a = b. a ≺ b (kiolvasva: b k¨oveti a-t) pedig jel¨olje azt, hogy a < b ´es nincs olyan c ∈ A, amelyre a < c ´es c < b. V´eges esetben a r´eszbenrendezett halmazok ´abr´azol´asa az al´abbi t´etelen m´ ulik: abbi k´et felt´etel ekvivalens: 26. T´ etel. Ha (A; ≤) v´eges r´eszbenrendezett halmaz, akkor tetsz˝oleges a, b elem´ere az al´ (1) a ≤ b; (2) l´etezik n ∈ N0 ´es l´eteznek c0 , c1 , . . . , cn ∈ A elemek, hogy a = c0, c0 ≺ c1 , c1 ≺ c2 , . . ., cn−1 ≺ cn , cn = b.
ovet´ esi rel´ aci´ o A t´etelnek az a l´enyege, hogy v´eges (teh´at a sz´amunkra leg´erdekesebb) esetben a ≺ u ´n. k¨ meghat´ arozza a r´ eszbenrendez´ est! Ez´ert ha szeml´eletesen ´abr´azolni akarjuk (A; ≤)-t, akkor helyette a k¨ovet´esi rel´aci´ot a´br´azoljuk.
Hasse-diagramm . Ez e megy mellett, hogy minden ny´ıl felfel´
Erre szolg´al az u ´n.
l´enyeg´eben a k¨ovet´esi rel´aci´onak megfelel˝o ir´any´ıtott gr´af azon
(ez´ert a ny´ılhegyet le se rajzoljuk). A t´etel szerint a ≤ b akkor meg´allapod´as ´es csak akkor, ha a Hasse-diagrammon a-b´ol indulva ´elek ment´en mindig felfel´e haladva eljuthatunk b-be. (Speci´alis esetben: a = b, amikor semmit sem kell haladnunk.) L´assuk az al´abbi h´arom r´eszbenrendezett halmaz Hasse-diagramj´at: Pl. a bal oldali a´br´an: {1} ≤ {1, 2, 3} (m´as sz´oval: {1} ⊆ {1, 2, 3}). De {1} ≤ {2, 3}), hiszen hi´aba van {2, 3} feljebb, nem vezet hozz´a {1}-b˝ol mindv´egig felfel´e halad´o u ´t.
52
{1,2}
{1,2,3} {2,3} {1,3} 6
{1}
{2}
7 6 5 4 3 2
12
{3}
4
3
2
O /
({2, 3, . . . , 7}, ≤)
(P ({1, 2, 3}), ⊆)
({2, 3, 4, 6, 12}, |)
A h´arom r´eszbenrendezett halmaz k¨oz¨ ul csak a jobb sz´els˝o rendezett (mert csak arra teljes¨ ul a dichot´omia: b´armely k´et eleme k¨oz¨ ul az egyik ≤ mint a m´asik.) Egyazon r´eszbenrendezett halmaz Hasse-diagramja t¨obbf´elek´eppen is lerazolhat´o:
{1,2} {1}
{1,2,3} {2,3} {1,3} {2}
{3}
{1,2,3} {1,2} {1,3}
{2,3}
{2}
{1}
O /
O /
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
{3}
{1,2,3} {2,3} {1,3} {1,2}
{1}
{2}
{3}
O / V´ azlat, nem a v´ egleges v´ altozat!
Defin´ıci´ o: Legyen (A, ≤) egy r´eszbenrendezett halmaz ´es b ∈ A. Azt mondjuk, hogy b maxim´ alis eleme A-nak, alis elemnek ha nincs olyan x ∈ A, amelyre b < x. Hasonl´oan, ha nincs olyan x ∈ A hogy x < b, akkor b-t minim´ enek nevezz¨uk. Ha pedig minden x ∈ A-ra nevezz¨ uk. Ha b´armely x ∈ A-ra x ≤ b, akkor b-t A legnagyobb elem´ enek nevezz¨uk. b ≤ x, akkor b-t A legkisebb elem´ alis elem = nincs n´ ala nagyobb, legnagyobb elem = minden m´ asn´ al nagyobb. Teh´at maxim´ ´ All´ıt´ as: Ha (A, ≤)-nek van legnagyobb eleme, akkor pontosan egy van. Legkisebb elemre ugyanez ´erv´enyes. 53
Bizony´ıt´ as: Ha b is ´es c is legnagyobb elem, akkor c ≤ b (mert b legnagyobb elem), b ≤ c (mert c legnagyobb elem). Az antiszimmetria miatt b = c. Megjegyz´ esek: Szok´as a legnagyobb elemet 1-gyel, a legkisebb elemet 0-val jel¨olni - nem biztos,hogy ezek l´eteznek. Maxim´alis, illetve minim´alis elemb˝ol t¨obb is lehet. V´eges esetben legal´abb egy maxim´alis elem ´es legal´abb egy minim´alis elem l´etezik. Ha egy elem legnagyobb elem, akkor sz¨ uks´egk´eppen maxim´alis elem. Ha egy elem legkisebb elem, akkor sz¨ uks´egk´eppen minim´alis elem. N´eh´any p´elda:
max és legnagyobb max
min
min
min
min
max
min
CzG: Diszkr´ et matematika I , SZTE, 2006-2007
max
min
max min és max min V´ azlat, nem a v´ egleges v´ altozat!
(N, ≤) rendezett halmaz. Mint l´attuk (a teljes indukci´oval kapcsolatban), b´armely nem¨ ures r´eszhalmaz´anak van legkisebb eleme. olrendezettnek nevez¨unk, ha b´armely nem¨ures r´eszhalmaz´anak van legkisebb eleme. Egy rendezett halmazt j´ ´ Erdekess´egk´ent eml´ıtj¨ uk a J´ olrendez´ esi t´ etelt: b´armely nem¨ ures A halmaz j´ olrendezhet˝ o, azaz ´ertelmezhet˝o rajta egy olyan rendez´es, hogy j´olrendezett halmazt kapjunk. Ez v´eges A eset´en evidens (tetsz˝oleges rendez´es j´olrendez´es lesz), de v´egtelen esetben t´avolr´ol sem trivi´alis. 1 1 ul¨onb¨ozik az el˝oz˝ot˝ol, {1 − n : P´elda j´olrendezett halmazra: (N, ≤), {1 − n : n ∈ N}, ≤) — l´enyeg´et tekintve” nem k¨ ” 1 n ∈ N} ∪ {1}, ≤) — ez l´enyegesen k¨ ul¨onb¨ozik” az el˝oz˝ot˝ol (hiszen van legnagyobb eleme), {k − n : k, n ∈ N}, ≤) — ez is ” l´enyegesen k¨ ul¨onb¨ozik” az el˝oz˝oekt˝ol. ” Adott r´eszbenrendezett halmaz(ok)b´ol t¨obbf´elek´eppen is gy´arthatunk” u ´jakat. P´eld´aul elhagyunk bel˝ole elemeket, ´es ” meg´allapodunk abban, hogy a marad´ek elemek halmaz´an a ≤” jelentse ugyanazt, mint eddig. (K¨onnyen l´athat´o, hogy ily ” m´odon r´eszbenrendez´est kapunk.) Enn´el azonban ´erdekesebb a direkt szorzat ´es a lexikografikus szorzat. 54
Defin´ıci´ o: Legyen adott az (A1, ≤1 ) ´es az (A2, ≤2 ) r´eszbenrendezett halmaz. Direkt szorzatukat u ´gy kapjuk, hogy enti r´ eszbenrendez´ est defini´aljuk. Azaz a direkt szorzatuk (A1 × A2, ≤), Descartes-szorzatukon a komponensenk´ ahol (a1, a2) ≤ (b1, b2) azt jelenti, hogy a1 ≤1 b1 ´es a2 ≤2 b2 . (Megmutathat´o, hogy ez is r´eszbenrendezett halmaz.) Ha (A1 , ≤1) ´es az (A2, ≤2) rendezett halmaz (teh´at nemcsak r´eszbenrendezett), akkor lexikografikus szorzatukon az (A1 × A2, ≤) rendezett halmazt ´ertj¨uk, ahol a rel´aci´o a lexikografikus rendez´ est jelenti, azaz (a1, a2) ≤ (b1, b2 ) akkor ´es csak akkor, ha a1 <1 b1, vagy a1 = b1 ´es a2 ≤2 b2. (Megmutathat´o, hogy ily m´odon rendezett halmazt kapunk.) ´ Ertelemszer˝ uen t¨obb t´enyez˝o direkt, illetve lexikografikus szorzat´at is defini´alhatn´ank. A lexikografikus szorzat onnan nyerte a nev´et, hogy a lexikonok, sz´ot´arak, n´evsorok is ezen az elven vannak rendezve. Az al´abbi a´br´akon megfigyelhet˝o az az a´ltal´anosan is ´erv´enyes m´odszer, ahogy k´et r´eszbenrendezett halmaz direkt szorzat´anak Hasse-diagramj´at lerajzolhatjuk (persze csak kism´eret˝ u r.r.halmazok eset´en sz´am´ıthatunk ´attekinthet˝o diagramra.) Kb. arr´ol van sz´o, hogy az egyik (mindegy melyik) r.r.halmaz egyik sz¨ogpontj´aba (elem´ebe) rakjuk a m´asik r.r.h. egyik sz¨ogpontj´at, majd ezen m´asik r.r.halmazt az egyik r.r.h. elemi ment´en mindenhova eltoljuk u ´gy, hogy az eltol´as sor´an mindegyik sz¨ogpontj´at ¨osszek¨otj¨ uk az eltoltj´aval. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
A1
1
d
e
f
a
b
c
A2
1
0
0
Keress¨ uk ezen k´et r.r.halmaz direkt szorzat´anak Hasse-diagramj´at. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
55
A1 A1
A2
K¨ozb¨ uls˝o l´ep´es: a k´et r.r.halmaz egy-egy pontj´at fed´esbe hoztuk (legals´o pont), majd A1 -et A2 ment´en eltoltuk. M´ar csak az van h´atra, hogy az ezen eltol´as alkalm´ab´ol az A1 elemeinek p´aly´ait berajzoljuk. (Ezzel ekvivalens fogalmaz´as: hogy A2-t is eltoljuk A1 minden pontj´aba.) CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
(1,1)
A1 X A2 (1,0) (d,0) ,0)
(a,0) ,0)
(d,1) ,1)
(e,0) ,0)
(f,0) ,0)
(b,0) ,0)
(c,0) ,0)
(f,1) ,1)
(e,1) ,1) (a,1) ,1)
(b,1) ,1)
(c,1) ,1)
(0,1)
(0,0)
´Ime a keresett direkt szorzat. Tal´an a´ttekinthet˝obb, ha nem t¨ untetj¨ uk fel az elemek megnevez´es´et:
56
Megjegyz´es: a n´egydimenzi´os kocka k´etdimenzi´os vet¨ ulete — ezt ´ıgy a legk¨onnyebb lerajzolni. Ahhoz, hogy sz´ep ´abr´at kapjunk zavar´o a´tfed´esek n´elk¨ ul — ink´abb m˝ uv´eszet mint tud´as — a kiindul´asi a´br´at gyakran m´odos´ıtjuk. CzG: Diszkr´ et matematika I , SZTE, 2006-2007
V´ azlat, nem a v´ egleges v´ altozat!
V´eg¨ ul ´ıme egy (s˝ot a”) h´aromelem˝ u ´es a k´etelem˝ u rendezett halmaz direkt szorzata: ” A1 X A2
A1
1 a 0
Közbülső lépés A2
1
(1,1)
(1,0)
A1
(a,1) ,1) (a,0) ,0)
A2
0
(0,0)
57
(0,1)
