Ekvivalencia, megszámlálhatóan végtelen és kontinuum számosságú halmazok

Feladat: Adjunk bijekciót az alábbi halmazok között:

Definíció: Az elõzõ feladatban szerepõ halmazok és azok, amik itt szereplhetnének a megszámlálhatóan végtelen halmazok. Tehát H megszámlálhatóan végtelen, ha a természetes számok halmazával ekvivalens.

Definíció: Egy H halmaz megszámlálható, ha véges vagy megszámlálhatóan végtelen.

Definíció: Elõször egy {C_n} halmazsorozatot definiálunk. C₀=[0,1]. Megelõlegezzük, hogy mindegyik C_i véges sok diszjunkt zárt intervallum uniója (a definíció része, hogy ezt ellenõrizzük mikor lezárul a leírás!). C_i+1 legyen az a halmaz, amit C_i-bõl úgy kapunk,hogy diszjunkt zárt intervallumok uniójaként felírva, minden zárt intervallumból elhagyjuk, a középsõ nyilt harmadát. Például

C₁=[0,1/3]U[2/3,1], C₂=[0,1/9]U[2/9,1/3]U[2/3,7/9]U[8/9,1].

Legyen C a Cantor-halmaz a C_i halmazok (i=0,1,2,,3,...) metszete.

Feladat: Adjunk bijekciót az alábbi halmazok között:

Definíció: Az elõzõ feladatban szerepõ halmazok és azok, amik itt szereplhetnének a kontinuum számosságú halmazok. Tehát H kontinuum számosságú, ha a valós számok halmazával ekvivalens.

Feladat:

1. Definiáljuk a síkon az O betût, mint egy zárodó, folytonos, önmagát nem metszõ görbe. Két O betû diszjunkt, ha mint görbék ponthalmaza diszjunkt. Hány O betût tudunk elhelyezni a síkra, ha csak arra vigyázunk, hogy páronként diszjunktak legyenek?
2. Definiáljuk a 8-as számjegyet a fenti feladat mintájára. Hány 8-ast tudunk elhelyezni a síkra, ha csak arra vigyázunk, hogy páronként diszjunktak legyenek?

Feladat:

1. Igazoljuk, hogy két megszámlálhatóan végtelen halmaz uniója is megszámlálhatóan végtelen.
2. Igazoljuk, hogy megszámlálhatóan végtelen sok megszámlálhatóan végtelen halmaz uniója is megszámlálhatóan végtelen.

Feladat:

1. Igazoljuk, hogy két kontinuum számosságú halmaz uniója is kontinuum számosságú.
2. Igazoljuk, hogy kontinuum sok kontinuum számosságú halmaz uniója is kontinuum számosságú.

Feladat: Legyen I egy végtelen halmaz. Ekkor

1. I U {u} ~ I.
2. I U M ~ I, ahol M egy megszámlálható halmaz.

Feladat: Bizonyítsuk be, hogy

1. Tegyük fel, hogy A₁~A₂ és B₁~B₂. Ekkor A₁× B₁ ~ A₂× B₂,
2. A× B ~ B× A,
3. A× (B× C) ~ (A× B)× C,
4. A× (B U C) = (A×B) U (A× C),

Definíció: A, B, C halmazok esetén A× B× C={(a,b,c): a A egy eleme, b B egy eleme, c C egy eleme}

A₁, A₂,..., A_n halmazok esetén A₁× A₂×...×A_n = {(a₁,a₂,...,a_n): a_i A_i egy eleme i=1,2,...,n esetén}

Jelölés: A és B halmazok esetén legyen

Feladat:

1. Tegyük fel, hogy A₁~A₂ és B₁~B₂. Ekkor ^A₁B₁ ~ ^A₂B₂,
2. ^A(B× C)~^AB×^AC,
3. ^A×BC~ ^A(^BC)

Feladat: Definiáljuk a síkra írt T betût.

Hány T betût tudunk elhelyezni a síkra, ha csak arra vigyázunk, hogy páronként diszjunktak legyenek? (Válaszunk persze függ a definíciónktól. Egy megoldás esetén módosíthatjuk definíciónkat úgy, hogy megoldásunk ötlete ne múködjön és a módosított definícióval újból gondolkozhatunk a második kérdésen.)

Feladat: Van-e olyan szakasz, amely nem tartalmaz olyan pontot, amely mindkét koordinátája racionális? Ha igen, akkor lehet-e tetszõleges a meredeksége? Mi a helyzet egyenessel?

Feladat: Adjunk egy-egy értelmû leképezéseket a következõ halmazok között:

1. a természetes számok részhalmazai,
2. A természetes számokon értelmezett 0-1 értékû függvények,
3. a természetes számokból álló számpárok halmazának részhalmazai,
4. a természetes számpárok permutációi,
5. a természetes számok halmazának osztályozásai.

Megjegyzés: Ha két halmaz között mindkét irányban létezik egy-egy értelmû leképezés, akkor bijekció is van köztük. Ennek ismeretében néha technikailag könnyebben tudunk ekvivalenciát igazolni. A fenti feladatban szereplõ halmazok mindegyike kontinuum számosságú.

Feladat: Adjunk egy-egy értelmû leképezéseket a következõ halmazok között:

1. valós számok,
2. valós számpárok,
3. a sík egyenesei,
4. a sík pontjai,
5. a sík körlapjai,
6. a sík háromszögei.

Feladat: A sík egész koordinátájú pontjainak valamelyikén egy nyúl van. Tudjuk, hogy a nyúl egyenletes vonalú egyenletes ugrálást végez. Mozgását egy v egész koordinátájú sebességvektor írja le. Minden óraütésnél a nyúl hozzáadja v-t a jelenlegi pozíciójához és odaugrik. Egy vadász csak a fentieket tudja a nyúlról (v-t, vagy kezdõpozícióját nem ismeri). Minden óraütésnél az egyik egész koordinátájú pontra rálõhet. Ajánlhatunk-e neki olyan lövési stratégiát, amivel biztos eltalálja a nyulat?

Feladat: Az U halmaz bizonyos részhalmazainak halmazát Boole-algebrának hívjuk, ha zárt az unió, metszet és komplementer képzésre. (Ilyen például az összes részhalmaz halmaza.)

• Legyen H az U bizonyos részhalmazainak egy halmaza. Igazoljuk, hogy van olyan H⁺ Boole-algebra, ami tartlmazza H elemeit és ezen feltételek mellett a legszûkebb.
• Tegyük fel H-ról, hogy megszámlálható halmaz. A fenti pont alapján egyértelmûen leírt H⁺ Boole-algebra megszámlálható elemszámú.

Feladat: Egy G csoport minden R részhalmazához van olyan részcsoport, ami R-et tartalmazza és ezen tulajdonságok mellett a legszûkebb. Ez az R által generált részcsoport. Igazoljuk, hogy ha R megszámlálható, akkor a generált részcsoport is az.

Feladat: H a természetes számok halmazának bizonyos részhalmazait tartalmazza. Az alábbiakban H-ra vonatkozó tulajdonságokat írunk le. Milyen sok eleme lehet H-nak a megfelelõ feltétel teljesülése esetén?

1. H elemei végesek.
2. H elemei végtelenek.
3. H elemei páronként diszjunktak.
4. H elemei páronként tartalmazkodóak. (Két halmaz tartalmazkodó, ha egyik a másik részhalmaza.)
5. H elemei páronként majnem diszjunktak. (Két halmaz majdnem diszjunkt, ha véges sok közös elemük van.)
6. H bármely két különbözõ elemének legfeljebb 2010 közös eleme van.
7. H bármely két különbözõ elemére teljesül, hogy metszete és mindkét irányú különbsége végtelen.

Feladat: Egy cirkalmas T betû legyen három közös végponttal rendelkezõ, de különben diszjunkt "szép" folytonos görbe ponthalmaza. Hány cirkalmas T betût tudunk elhelyezni a síkra, ha csak arra vigyázunk, hogy páronként diszjunktak legyenek? (Válaszunk persze függhet a szépség definíciójától.)