Halmazelmélet, matematika (? )

Az A egy halmaz, a C és D részhalmazok, B pedig részhalmazok halmaza.

Nézzük, mit lehet tudni egy szűrőről (B). Nézzük a B halmaz legkevesebb elemből álló elemét (illetve ha több olyan is van, azok közül egyiket), ez legyen a C. A III) tulajdonság miatt ez a C elem olyan, hogy ha hozzádjuk az A halmaz bármelyik elemét, mondjuk a₁-et, akkor D = C ∪ {a₁} is eleme B-nek. Ugyanígy bármely további elemet hozzáadva a D-hez az a halmaz is eleme kell legyen B-nek. Magyarul C össze lehetséges bővítése szintén eleme B-nek.

Nevezzük ezt a legkisebb elemszámú C halmazt a B magjának. Ha kihagyjuk a B-ből a C magot, valamint C mindegyik bővítését, akkor a bentmaradó elemek közül a legkisebb elemszámú (nevezzük C₂-nek) megint egy mag kell legyen. Vagyis annak is az összes bővítése eleme az eredeti B-nek.

Milyenek ezek a C és C₂ magok? A II) tulajdonság miatt C∩C₂ ∈ B. Viszont két különböző halmaz metszete részhalmaza mindkettőnek, vagyis pl.

C∩C₂ ⊂ C

De C a legkevesebb elemszámú halmaz volt B-ben, vagyis C∩C₂ nem létezhet, nem lehet ilyen elem B-ben. Lehetne még az is, hogy C∩C₂ az üres halmaz, de az I) tulajdonság miatt ez nem lehet eleme B-nek, vagyis ez az eset nem lehetséges. Mindebből az következik, hogy egy B szűrőnek egyetlen C magja van.

Vagyis szűrőt lehet generálni egy C részhalmazból mint magból úgy, hogy generáljuk C minden lehetséges bővítését (beleértve a teljes A halmazt is). Ezen halmazok adják a B szűrő elemeit.

Az így generált szűrő kielégíti mindhárom tulajdonságot, a másodikat is: két tetszőleges elem metszete vagy a C mag lesz (ami eleme B-nek), vagy a mag valamelyik bővítése (ami szintén eleme B-nek).

Mi van az ultraszűrőkkel?

Akkor nem tartalmaz egy C szűrőt egy másik, ha nincs olyan halmaz, aminek C a bővítése lenne (vagyis nincs olyan mag, amiből generált szűrő tartalmazná a C-ből generáltat is). Azok a C-k pedig az 1 elemű halmazok. Vagyis az ultraszűrők olyan szűrők, amiknek a magja 1 elemű.

Most már a kérdésekre könnyű a válasz, próbáld megválaszolni. Ha elakadsz, szólj.

Hosszan volt leírni, de valójában nagyon egyszerű. Nézzünk egy példát:

A = {1, 2, 3, 4, 5}

A mag a kiinduló részhalmaz, amihez hozzáadunk elemeket.

Mondjuk a mag legyen ez a részhalmaz: {2, 4, 5}

Akkor a szűrőben ezek vannak benne: {{2,4,5},{2,4,5,1},{2,4,5,3},{2,4,5,1,3}}

Vagyis a 2,4,5-höz hozzáadogattam az A halmaz többi elemét.

(Persze lehetett volna növekvő sorrendben is írni, de tök mindegy)

Ellenőrizd le, hogy tényleg igazak rá az I, II, III tulajdonságok.

Ultraszűrő pl. ez:

A kiinduló részhalmaz (mag) egy elemű.

A mag legyen mondjuk az {1}, a teljes szűrő pedig: {{1},{1.2},{1,3},{1,4},{1,5},{1,2,3},{1,2,4},{1,2,5},... jó sok további}

Szóval az összes olyan részhalmaz benne van, ahol az 1 is elem.

A kérdések:

a)

Ha 5 elemű az A:

Mivel bármelyik részhalmaz lehet mag (kivéve az üres halmazt), és részhalmazból 2⁵ darab van (beleértve az üres halmazt is), ezért 2⁵-1 = 31 szűrő lehet.

Ha n elemű az A:

2ⁿ-1

b)

Ha 5 elemű az A:

Mivel az ultraszűrők olyanok, hogy a magjuk 1 elemű, ezért 5 ultraszűrő van.

Ha n elemű az A:

n darab ultraszűrő van.

Érted? Olvasd újra az első válaszomat is...

----

Hol tanulsz egyébként, ahol ilyen feladatokat adnak?