HALMAZELMÉLET feladatsor 1.
Egy (H, ∨, ∧) algebrai struktúra háló, ha (H, ∨) és (H, ∧) kommutatív félcsoport, és teljesül az ún. elnyelési tulajdonság: ∀A, B ∈ H :
A ∨ (A ∧ B) = A ,
A ∧ (A ∨ B) = A .
A (H, ∨, ∧) háló korlátos, ha ∀A ∈ H: ∃!1 ∈ H : A ∧ 1 = A ,
∃!∅ ∈ H : A ∨ ∅ = A .
(1 a (H, ∧) félcsoport egységeleme, ∅ a (H, ∨) félcsoport zéruseleme.) A (H, ∨, ∧) háló disztributív, ha: ∀A, B, C ∈ H : A∨(B ∧C) = (A∨B)∧(A∨C) , A∧(B ∨C) = (A∧B)∨(A∧C) .
Egy (H, ∨, ∧) korlátos hálóban értelmezhet® egy elem komplementuma: ∀A ∈ H ∃!A :
A∨A=1 ,
A∧A=∅ .
Ekkor a hálót komplementumos hálónak nevezzük. Egy (H, ∨, ∧) hálót Boole-algebrá nak nevezünk, ha korlátos, disztributív és komplementumos. Legyen E egy halmaz, összes részhalmazainak halmazát E szimbólummal jelöljük. Tekintve a halmazok közötti unió- illetve metszetképzést, (E, ∪, ∩) Boole-algebra (egységeleme E , zéruseleme a ∅ üres halmaz). 1. Bizonyítsuk be (csupán a fenti de níciót használva), hogy bármely A, B, C halmazok esetén: (a) (b) (c) (d) (e) (f) (g) (h) (i) (j)
∅=E , E=∅, A=A. A∩∅=∅ , A∪E =E , A∪A=A , A∩A=A . A ∪ B = A ∩ B , A ∩ B = A ∪ B (de Morgan-azonosságok) * (A ∪ B) ∩ A = A ∩ B A \ (B ∩ C) = (A \ B) ∪ (A \ C) A \ (B ∪ C) = (A \ B) \ C A4B = B4A , A4(B4C) = (A4B)4C * A4A = ∅ , A4∅ = A , A4E = A A4(A4B) = B A ∪ B = A ∩ B ⇐⇒ A = B
2. Fejezzük ki a \ m¶veletet a 4 és ∩ segítségével! * 3. Fejezzük ki az ∪ m¶veletet a 4 és ∩ segítségével! * 4. Igazoljuk, hogy ∅ = 6 {∅}. 5. Bizonyítsuk be, hogy egy E halmaz részhalmazai egységelemes gy¶r¶t alkotnak, ha az összeadást a 4, a szorzást pedig a ∩ jelenti. Mi lesz a kivonás? * Az A és B halmazok különbségé n az A\B := A∩B , szimmetrikus dierenciá ján az A4B := (A \ B) ∪ (B \ A) halmazt értjük. 1
HALMAZELMÉLET feladatsor 2.
Megtartva az el®z® feladatsor jelöléseit, egy A halmaznak részhalmaz a a B halmaz, ha A∩B =B vagy A∪B =A . Ebben az esetben az B ⊂ A jelölést használjuk. 1. A Boole-algebra axiómáit és a fenti de níciót (részhalmaz) felhasználva igazolja az alábbi állításokat: (a) (b) (c) (d)
A ⊂ (B ∪ C) ⇐⇒ (A ∩ B) ⊂ C (A ∩ B) ⊂ C ⇐⇒ A ⊂ (B ∪ C) (A \ B) ∪ B = A ⇐⇒ B ⊂ A
Ha minden n ∈ N-re B ⊂ An teljesül, akkor B ⊂
S
An .
n∈N
2. Oldjuk meg az alábbi egyenletrendszert, ahol A, B, C tetsz®leges halmazok, és B ⊂ A ⊂ C , A∩X =B A∪X =C
. **
3. Tetsz®leges eszközöket felhasználva mutassa meg, hogy egy n elem¶ halmaznak 2n db részhalmaza van! Az A1 , A2 , . . . , An halmazok direkt (Descartes-) szorzat án az A1 × . . . × An := {(a1 , . . . , an ) | a1 ∈ A1 , . . . an ∈ An }
halmazt értjük. Az A és B halmazok elemei közötti binér reláció nak nevezzük az A × B tetsz®leges R részhalmazát. E reláció értelmezési tartománya a DR = {a ∈ A | (a, b) ∈ R}, értékkészlete RR = {b ∈ B | (a, b) ∈ R}. Egy R reláció inverz én az R−1 = {(b, a) ∈ B × A | (a, b) ∈ A × B} relációt értjük. (A binér relációhoz hasonlóan értelmezhet® n-ér reláció, ha n ∈ N.) Egy R1 ⊂ A × B és egy R2 ⊂ B × C reláció kompozíciója szintén reláció: R2 ◦ R1 := {(a, c) ∈ A × C | (a, b) ∈ R1 , (b, c) ∈ R2 } .
Egy f ⊂ A × B binér reláció A-ból B -be képez® függvény, amennyiben Df = A és tetsz®leges a ∈ A, b1 , b2 ∈ B elemekre fennáll, hogy (a, b1 ), (a, b2 ) ∈ f
⇒
b1 = b2 .
Függvények esetén a szokásos jelölés: f : A → B . Az f függvény injektív, ha minden b ∈ Rf elem esetén pontosan egy olyan a ∈ A létezik, hogy (a, b) ∈ f . Az f szürjektív, ha Rf = B . Az f bijektív, ha injektív és szürjektív. 1. Bizonyítsa be, hogy léteznek olyan A, B, C halmazok, hogy A × (B × C) 6= (A × B) × C . 2
2. Adja meg a DR , RR , R−1 , R ◦ R, R ◦ R−1 és R−1 ◦ R halmazokat, ha (a) R = {(x, y) | x, y ∈ N, y osztója x-nek} * (b) R = {(x, y) | x, y ∈ R, x + y ≤ 0} * 3. Legyen f függvény. Milyen feltételek mellett lesz f −1 függvény? 4. Legyen U nemüres, rögzített halmaz, A részhalmaza U -nak. Az A halmaz karakterisztikus függvénye: χU A (x) =
1, ha x ∈ A 0, ha x ∈ /A
Bizonyítsa be, hogy χUU \A (x) = 1 − χUA (x) ! A *-jel nélküli feladatok 1 pontot, a *-jellel ellátott feladatok 2 pontot érnek. A ** jelzés 3 pontot ér® feladatot mutat.
3
HALMAZELMÉLET feladatsor 3.
1. Állapítsa meg, hogy a következ® függvények közül melyik injektív, szürjektív (illetve bijektív)! (a) Legyen f : Z+ → N, f (x) := 8x3 + 3x2 + 121x + 1. (b) Az f függvény minden x0 ∈ R számhoz hozzárendeli az y = cos x0 x+ (sin x0 − x0 cos x0 ) egyenlet¶ egyenest. A függvény képtere legyen R2 minden egyenesét tartalmazó halmaz. (c) Adott egy G görbe a síkon, jelöljük egy p görbepont érint®egyenesét ep -vel. Legyen R := {(p, q) | p ∈ G, q ∈ ep }, és f : (p, q) ∈ R 7→ p ∈ G. (d) Tekintsük az els® n természetes szám alkotta halmaz összes részhalmazát. Legyen f az a függvény, amely egy részhalmazhoz hozzárendeli annak összes részhalmazainak a számát. A függvény képtere legyen {1, 2, 3, . . . , 2n }. (e) Legyen f : x ∈ [1, 10]∩N 7−→ f (x) := (x osztóinak halmaza), a képtér legyen P ([1, 10] ∩ N). (f) Dobjunk fel két pénzérmét egyszerre, és jelöljük F -fel, ha fejet, I vel, ha írást dobtunk. Egy x az el®bb leírt eseményt jelöli (pl. x = (F, I)), az összes esemény halmaza legyen X . Jelölje V az események lehetséges valószín¶ségének halmazát. Legyen f : x 7→ vx ∈ V . (g) Legyen P (x) a (valós együtthatós) polinomok halmaza. Ekkor az f : p(x) ∈ P (x) 7−→ p0 (x) ∈ P (x). 2. Mutasson (az eddigiekt®l eltér®) példát injektív, de nem szürjektív függvényre! 3. Mutasson (az eddigiekt®l eltér®) példát szürjektív, de nem injektív függvényre! 4. Adjon meg bijektív függvényt N és Z között! * 5. Szorgalmi feladat otthoni kidolgozásra: Adjon meg bijektív függvényt R és C között! *
4
HALMAZELMÉLET feladatsor 4.
Egy A nemüres halmazon értelmezett R binér reláció re exív, ha (x, x) ∈ R, minden x ∈ A-ra; irre exív, ha (x, x) ∈ / R, minden x ∈ A-ra; szimmetrikus, ha (x, y) ∈ R ⇒ (y, x) ∈ R, minden x, y ∈ A-ra; antiszimmetrikus, ha (x, y), (y, x) ∈ R ⇒ x = y, minden x, y ∈ A-ra; tranzitív, ha (x, y), (y, z) ∈ R ⇒ (x, z) ∈ R, minden x, y, z ∈ A-ra. Az R reláció ekvivalenciareláció, ha re exív, szimmetrikus és tranzitív; részbenrendezés/parciális rendezés, ha re exív, antiszimmetrikus és tranzitív (szokásos jelölése: ≤); rendezés/teljes (vagy lineáris) rendezés, ha részbenrendezés, és bármely két eleme összehasonlítható, azaz (x ≤ y vagy y ≤ x) teljesül tetsz®leges x, y ∈ A esetén. 1. Legyen A a sík összes egyeneseinek halmaza. Ekvivalenciareláció-e a párhuzamosság? És a mer®legesség? 2. Legyen ((a, b), (c, d)) ∈ R ⇐⇒ a + d = b + c. Mutassa meg, hogy R ekvivalenciareláció! 3. Legyen (a, b) ∈ R ⇐⇒ a | b, a, b ∈ N. Mutassa meg, hogy R részbenrendezés! 4. Bizonyítsa be, hogy ha R1 és R2 re exív reláció, akkor R1 ◦ R2 is az! 5. Bizonyítsa be, hogy ha R1 és R2 irre exív reláció, akkor R1 ◦ R2 nem biztos, hogy irre exív! 6. Bizonyítsa be, hogy R1 és R2 szimmetrikus relációk R1 ◦ R2 szorzata pontosan akkor szimmetrikus, ha R1 ◦ R2 = R2 ◦ R1 ! 7. Bizonyítsa be, hogy minden olyan reláció, ami egyszerre szimmetrikus és antiszimmetrikus, egyúttal tranzitív is! 8. Igazolja, hogy egy A halmazon adott R reláció pontosan akkor ekvivalenciareláció és részbenrendezés, ha R = iA ! (iA (x) = x, minden x ∈ A-ra.) 9. Lássuk be, hogy minden véges halmaz rendezhet®! * 10. Adjon meg olyan binér relációt, amely re exív, szimmetrikus, de nem tranzitív! * 11. Adjon meg olyan binér relációt, amely re exív, antiszimmetrikus, de nem tranzitív! * 12. Adjon meg olyan binér relációt, amely re exív, tranzitív, de nem szimmetrikus! *
5
HALMAZELMÉLET feladatsor 5.
1. Bizonyítsa be, hogy ha létezik A-ból B -re (szürjektív) leképezés, akkor |B| ≤ |A|. 2. Mutassa meg, hogy megszámlálhatóan végtelen halmaz minden részhalmaza véges vagy megszámlálhatóan végtelen. 3. Mekkora az irracionális számok halmazának számossága? 4. Igaz-e, hogy ]0, 1[∼ R ? 5. Igazolja, hogy ]0, 1[∼ [0, 1]. 6. Bizonyítsa be, hogy (a) az egész együtthatós, egyváltozós polinomok halmaza megszámlálható. (b) az algebrai számok halmaza megszámlálható. (c) létezik transzcendens szám. 7. Bizonyítsa be, hogy egy szakasz és egy négyzet pontjainak halmaza ekvivalens. 8. Mutassa meg, hogy a valós számegyenes páronként diszjunkt, nemüres, nyílt intervallumainak tetsz®leges rendszere megszámlálható. 9. Igazolja, hogy tetsz®leges f : R −→ R monoton függvény szakadási helyei megszámlálhatóak. 10. Szorgalmi feladat (3 pontért): Igazolja, hogy a természetes számokból álló megszámlálható sorozatok halmazának számossága, valamint a 0 − 1 sorozatok számossága kontinuum.
6
