Halmazrendszerek geometriája/Feladatok

Tartalomjegyzék

Feladatok

- megoldásokkal -

E lapon egy kidolgozottfeladat-gyűjtemény található a Halmazrendszerek geometriája c. könyvhöz.

1. fej. (Halmazrendszerek és hipergráfok)

Diszkrét intervallumok

Fejezzük az alábbi halmazokat diszkrét intervallumok és véges sok halmazműveleti jel (unió, metszet, különbség) segítségével (N használata is megengedett):
1. {2, 3, 4, 5, 6, ...}
2. {10, 11, 12, ..., 20}
3. {2, 4, 6, 8, 10, 12}
Bizonyítsuk be (pl. mat.-i indukcióval):
1. 0,n = {x∈N | 0≤x≤n}; azaz hogy tetszőleges x∈N esetén x∈0,n akkor és csak akkor igaz, ha 0≤x≤n;
2. hogy 0,n⊆0,m akkor és csak akkor teljesül, ha n≤m.

Megoldások:

1. fa.
1. Egyszerű megoldás: N-0,1
2. A legegyszerűbb megoldás: 1,20-1,9
3. Egyszerű megoldások: 1,13-{3,5,7,9,11} de lehet trükközni is: 1,12-2·0,5+1
2. fa.
1. Az n-re vonatkozó teljes indukcióval bizonyítunk. 1). Ha n=0, akkor x∈0,0 := {0} azt jelenti, x=0, azaz valóban 0≤x≤0. 2). Ha valamely n-re igaz az állítás, hogy „x∈0,n akkor és csak akkor, ha 0≤x≤n”, enek megfelelője n+1-re: „x∈0,n+1 akkor és csak akkor, ha 0≤x≤n+1”, ami ugyanaz, mint „x∈0,n∪{n+1} akkor és csak akkor, ha 0≤x≤n+1”. Ez igaz: Ha - az indukciós feltevést kihasználva - 2a). x∈0,n∪{n+1} = {x∈N | 0≤x≤n}∪{n+1} := A, akkor x∈{x∈N | 0≤x≤n+1} = A, ugyanis ha x az unió első tagjának eleme, azaz 0≤x≤n, akkor n≤n+1 és ≤ tranzitivitása miatt 0≤x≤n+1 is (x≤n és n≤n+1 következménye x≤n+1) ha pedig x az unió második tagjának eleme, azaz x=n+1, ekkor x=n+1≤n+1 miatt igaz 0≤x≤n+1 (≤ ún. reflexív tulajdonsága). 2b). Ha pedig, fordítva, 0≤x≤n+1, akkor vagy x = n+1, ez esetben x∈0,n+1 = 0,n∪{n+1} (az unió második tagjában van az x), vagy pedig x<n+1, azaz x≤n (más lehetőség nincs, a ≤ reláció ún. gyanis ha x az unió első tagjának eleme, azaz 0≤x≤n, akkor n≤n+1 és ≤ trichotom tulajdonsága miatt), és az indukciós feltevést kihasználva ekkor x∈0,n ⊆ 0,n∪{n+1} = 0,n+1, azaz mindkét megvizsgált és minden lehetőséget kimerítő esetben x∈0,n+1.
2. Az előző tételből következik. x∈0,n = {z | 0≤z≤n}, és x∈0,m = {z | 0≤z≤m}, ha az első halmaz része a másodiknak, akkor az első halmaz „utolsó” eleme, n (is), a másodikba esik, azaz 0≤n≤m, ha fordítva, ez utóbbi egyenlőtlenség teljesül, akkor n a második halmazba esik, és ekkor a ≤ tranzitivitása miatt minden nála kisebb természetes szám is, azaz az egész 0,n halmaz. Q.E.D.

Megoldás: Halmazrendszerek geometriája/1#Diszkrét intervallumok

Sorbarendezések

Bizonyítsuk be, hogy véges halmaz minden részhalmaza is véges! (megjegyzés: nem nehéz, de annyira idegölős, favágós jellegű a célzott korosztály számára, hogy valószínűleg halálfejetr kap) Megoldás: Legyen A véges, ekkor létezik olyan n,f hogy A-t f bijektíven képezi 1,n-re. Legyen R⊆A, ekkor van egy legkisebb m, hogy m<n, de f(m) nem eleme R-nak.

Részhalmaz karakterisztikus függvénye

Bizonyítsuk, hogy ha egy halmaz hatványhalmazának (részhalmazai halmazának) minden eleméhez hozzárendeljük a halmaz felett értelmezett karakterisztikus függvényét, akkor egy bijektív leképezést kapunk!

Részhalmaz karakterisztikus vektora

Írjuk fel az U = {a,b,c,d} halmaz összes részhalmazainak karakterisztikus vektorait, ha a sorbarendezés (d, b, a, c}! Megoldás ...

Hatványhalmaz

Ne örülj, lesz.

Hipergráfok

Mekkora egy véges U halmaz feletti nem üres hipergráfok száma?
Mekkora egy véges U halmaz feletti olyan hipergráfok száma, amelyek nem tartalmazzák élként az üres halmazt? Megoldás: ld. később

Boole-vektor

Gyakorló feladatok

Bizonyítsuk be, hogy egy véges, legalább két elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyek minden éle két elemű, négyzetszám! ^[1]
Bizonyítsuk be, hogy véges, legalább n elemű U halmazt véve, az olyan U feletti hipergráfok száma, melyeknek minden éle n elemű, n-edik hatvány! (megjegyzés: üres hipergráfot is megengedünk).
Adjunk képletet egy véges, n elemű U halmaz azon hipergráfjainak számára, melyek minden éle v-elemű (v∈0,n) ^[2]
Legyen az U feletti H hipergráf Boole-vektora b(H), a J hipergráfé pedig b(J). (Milyen) halmazművelettel keletkezik a b^-1(b(H)@b(J)) hipergráf a H,J hipergráfokból, ha @ a modulo 2 összeadás, a szorzás, a kivonás, a minimumképzés, a maximumképzés?
Hogyan néz ki egy U feletti hipergráfnak az U hatványhalmazára vonatkozó komplementerének Boole-vektora?

További feladatok

Egy, az u 1,2,...,n változókon értelmezett n-változós f logikai függvény hipergráfjának nevezzük az {u_i | i=1,2,...,n} halmaz azon halmazcsaládját, amely U pontosan azon R részhalmazait tartalmazza, melyekre χ(R,u_i)=f(u_i) minden i-re teljesül. Mit jelent a logikai függvény hipergráfjára nézve az, hogy az u₁ változó fiktív (fiktívnek nevezünk egy független függvényváltozót, hogyha a többi változó rögzített értéke mellett értéke bárhogy is változik, a függvényérték állandó marad)?

Nehezebb feladatok

Általánosítsuk a Boole-vektor fogalmát végtelen halmazokra! A jólrendezési tétel használata megengedett.

Rendszám

Bizonyítsuk be, hogy adott U halmaz felett az O_U,ν(...) leképezés kölcsönösen egyértelmű megfeleltetést létesít az U feletti hipergráfok {U}×℘(℘(U)) halmaza és a ${\mbox{ }}_{\underline {0,2^{2^{n}}-1}}$ diszkrét intervallum között;

Valószínűségszámítást kedvelőknek:

Véletlenszerűen választunk két n-edrendű hipergráfot (ugyanabból az U halmazból). Mekkora a valószínűsége, hogy a nagyobb rendszámú hipergráf több elemet fog tartalmazni?
Írjuk fel annak az eseménysorozatnak a valószínűségeloszlását (ha lehet, adjunk képletet), hogy egy k rendszámú és n-edrendű hipergráf (n rögzített, k nem) több elemet tartalmaz, mint az összes őt megelőző rendszámú! Készítsünk grafikont!

Számelméletkedvelőknek

Feladatok számelméletkedvelőknek:
1. Válasszunk egy (lehetőleg háromnál nagyobb) n természetes számot, és egy n elemű U halmazt. Hogyan jellemezhetőek szerkezetileg azok az U feletti hipergráfok, amelyekre igaz, hogy rendszámuk többszöröse valamely Fermat-számnak?
2. Lássuk be, hogy adott U halmaz és ν sorbarendezés mellett a ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right):\wp \left(\wp \left(U\right)\right)\to {\underline {1,2^{2^{n}}}};}$ ${\mbox{ }}_{P_{U,\nu }\left({\mathcal {H}}\right)\ :=\ \log _{2}\left(\prod _{k=0}^{2^{|U|}}2^{k}\cdot \chi _{\mathcal {H}}\left(o_{U,\nu }^{-1}\left(\mathbf {k} \right)\right)\right)}$ függvény nem jelent bijektív leképezést!
3. Mi az értékkészlete a fenti leképezésnek?

Eztnetöröldmígametárólnemválaszolnak

Dear Meta User[1]! This edit link doesn't work :

Sectiontitle

Lap teteje

↑ Gráfelméleti nyelven: Legalább két elemű halmaz felett mindig négyzetszámnyi sok gráf található.
↑ Ezek az ún. n-edrendű v-uniform hipergráfok.

[1] Gráfelméleti nyelven: Legalább két elemű halmaz felett mindig négyzetszámnyi sok gráf található.

[2] Ezek az ún. n-edrendű v-uniform hipergráfok.

[1]

[2]