Matematické Fórum

Andrejka3 · 06. 01. 2013 11:57

Dobrý den.
Přemýšlím nad příkladem z knihy Kapitoly z diskrétní matematiky od vážených autorů Matoušek, Nešetřil.

Dokaž, že existuje konečná částečně uspořádaná množina, jíž nelze vnořit do $(\mathbb{R}^3,\preceq)$ , kde
$(a_1,a_2,a_3) \preceq (b_1,b_2,b_3) \iff a_i \leq b_i,\; i=1,2,3 \;.$

Nemohu přijít na řešení. Ani v analogickém dvoudimenzionálním případě $(\mathbb{R}^2,\preceq)$ .
Nakonec mi zůstal jediný nápad. Protože každou uspořádanou množinu $(X,\leq)$ lze vnořit do $(P(X),\subset)$ , a protože složení vnoření je vnoření, musí existovat $n \in \mathbb{N}$ a $\mathcal{B}_n = (P(\boldsymbol{n}),\subset)$ , že $\mathcal{B}_n$ nelze vnořit do usp. mn. ze zadání. To se mi zdá ale složité.

( $\boldsymbol{n}=\{1, \dots ,n\}$ )
Díky za rady.

anes · 06. 01. 2013 14:24 — Editoval anes (06. 01. 2013 14:26)

Ahoj, myslím, že pro R2 bych něco viděl. Rozmysli si, jak vypadá nějakých n prvků, které jsou při tom uspořádání $\preceq$ vzájemně nesrovnatelné. To bude množina $\{(u_i, v_i) \ : \ i = 1\ldots n\}$ taková, že $\forall i \neq j$ buď $u_i<u_j, \, v_i>v_j$ , nebo $u_i>u_j, \, v_i<v_j$ . To je ale dost velké omezení, které ovlivní, jak si tato n-tice prvků může stát ve srovnání s ostatními.

Dokončení (spoiler)

Autor skryl část textu. Zobrazit/skrýt!

Pro R3 jsem si protipříklad konstruovat nezkoušel, tam to bude trochu pracnější, ale jsem si celkem jistý, že analogická úvaha půjde použít i tam. Ale to mé řešení je jen takové vyrobené na koleně, tak tě třeba hned napadne nějaká obecnější formulace toho, co jsem tu popsal.

Andrejka3 · 06. 01. 2013 14:38

↑ anes:
Děkuji za odpověď. Můj první nápad byl, že asi neexistuje nekonečný antiřetězec, ale pak jsem jej sestrojila :D
Promyslím si Tvou radu.

Andrejka3

↑ anes:

Takže je to kousek $\mathcal{B}_3$ - bez minima a maxima. Dík, ještě si to projdu.

pf · 06. 01. 2013 15:14 — Editoval pf (06. 01. 2013 15:17)

K původní otázce: $(P(\{1,2,3,4\}),\subseteq)$ (tj. $\mathcal{B}_4$ ).

Andrejka3

↑ pf:
Díky, asi to je analogické tomu předchozímu, že?
A pak to taky svádí k tomu, že do
$(\mathbb{R}^n,\preceq_n)$ nelze vnorit $(P(\boldsymbol{n}),\subseteq)$ ...

pf · 06. 01. 2013 15:24 — Editoval pf (06. 01. 2013 15:27)

Andrejka3 napsal(a):
A pak to taky svádí k tomu, že do
$(\mathbb{R}^n,\preceq_n)$ nelze vnorit $(P(\boldsymbol{n}),\subseteq)$ .

Malá oprava: do $(\mathbb{R}^n,\preceq_n)$ nelze vnořit $(P(\boldsymbol{n+1}),\subseteq)$ .

Andrejka3 · 06. 01. 2013 15:28

↑ pf:
Super, tak to je hezké.
Kdybyste chtěli pokračovat zajímavostmi, pište dál :)
Já děkuji a teď si to pomalu zpracuji.

anes · 06. 01. 2013 16:49

↑ Andrejka3:
Jo. Tak, jak jsem to já napsal, by bylo ještě prohozené $e$ , $f$ , což je úplně fuk. A za promyšlení to ještě možná stojí. Kromě toho, že se tu udělá dost snadno chyba (což snad v tom mém předchozím příspěvku není, ale...), já jsem vycházel z toho, že množina nesrovnatelných prvků má nějaký speciální tvar (který by se mohl pro vyšší dimenze komplikovat).
Přitom by asi bylo výhodnější řešit to (aspoň teď, když už tušíme, jak na to) "odshora". Mohli jsme začít naložením podmínek

$a,b \preceq d$ , $b,c \preceq e$ , $a,c \preceq f$ , $c,d$ , $a,e$ , $b,f$ nesrovnatelné,

(ze kterých pochopitelně ta nesrovnatelnost a,b,c vyplývá), a pouhým rozepisováním vztahů v jednotlivých složkách dojít ke sporu. To bude asi mnohem lepší postup pro zobecňování...

Jednoduchý návod pro výrobu protipříkladů k vnořitelnosti do $(\mathbb{R}^n,\preceq)$ .

Autor skryl část textu. Zobrazit/skrýt!

A teď proč to sem píšu, když už to řešení asi nějak z předchozí debaty v podstatě vyplynulo:
1) Vidí někdo na první pohled, jestli šel ten tvar problematických množin nějak "uspokojivě" odvodit? Tím zkoumáním v duchu mého prvního příspěvku bych se asi řešení našlo, ale dost pracně. Přitom v této úloze je určitě hromada symetrií, tak by možná nějaký dobrý nápad pomohl.

2) Ta otázka vnořování potenční množiny, k tomu existuje nějaká teorie, která nám s naší úlohou může pomoct, nebo se to tu objevilo jen jako zajímavý důsledek? Tak trochu jsem totiž čekal, že po vykreslení grafu $\mathcal{B}_{n+1}$ bude ta problematická množina odpovídat nějakým dvěma sousedním patrům z prostředka. Přitom je mnohem menší, odpovídá patrům 1 a n-1. Znamená to něco, neumí se to nějak přeformulovat, že by se třeba ukázalo, že je ta úloha ekvivalentní něčemu jinému? Nešel by z toho třeba vytřískat nějaký vyčerpávající popis problematických množin?

Andrejka3

↑ anes:
1) V tomto příkladu mé první pohledy selhaly. Očekávám, že nějakou intuici si vytvořím, jakmile to řešení uspokojivě zapíšu do svých osobních `skript'. Zatím jsem u Tvé myšlenky R2, pak chci nějak posoupit k tem $\mathcal{B}_n$ .
Hromad symetrií se děsím, protože se bojím, že to neuvidím.
2) $\mathcal{B}_3$ nešlo vnořit do $(\mathbb{R}^2,\preceq)$ ,
kolega pf tvrdil, že
$\mathcal{B}_4$ nelze vnořit do $(\mathbb{R}^3,\preceq)$ , odkud mě napadlo to tvrzení pro libovolné $n$ .
Zatím nevím, jak obecně dokázat, ani jak dokázat v případě R3. Protože jste mi ale poskytli návody, řekla jsem si, že to zkusím dokončit :)
Taky jsem si myslela, že problémové usp.mn. jsou prostřední patra $\mathcal{B}_{n+1}$ (ta nejširší).

Nevím, co jde vytřískat, zatím jsi rychlejší než já :) Samozřejmě mě to ale zajímá.
Edit: Snad jsem odpověděla na otázku..

Andrejka3

↑ anes:
Jednoduchý návod pro výrobu pro výrobu problematických množin je hezký. Jak píšeš, odpovídá patrům $\mathcal{B}_{n+1}$ druhému odshora a odpoda. Až teď mi to vše zapadlo do sebe.

Matematické Fórum

#1 06. 01. 2013 11:57

uspořádání, vnoření, příklad

#2 06. 01. 2013 14:24 — Editoval anes (06. 01. 2013 14:26)

Re: uspořádání, vnoření, příklad

#3 06. 01. 2013 14:38

Re: uspořádání, vnoření, příklad

#4 06. 01. 2013 15:06 — Editoval Andrejka3 (06. 01. 2013 15:10)

Re: uspořádání, vnoření, příklad

#5 06. 01. 2013 15:14 — Editoval pf (06. 01. 2013 15:17)

Re: uspořádání, vnoření, příklad

#6 06. 01. 2013 15:15 — Editoval Andrejka3 (06. 01. 2013 15:17)

Re: uspořádání, vnoření, příklad

#7 06. 01. 2013 15:24 — Editoval pf (06. 01. 2013 15:27)

Re: uspořádání, vnoření, příklad

Andrejka3 napsal(a):

#8 06. 01. 2013 15:28

Re: uspořádání, vnoření, příklad

#9 06. 01. 2013 16:49

Re: uspořádání, vnoření, příklad

#10 06. 01. 2013 17:16 — Editoval Andrejka3 (06. 01. 2013 18:00)

Re: uspořádání, vnoření, příklad

#11 06. 01. 2013 19:42 — Editoval Andrejka3 (06. 01. 2013 19:43)

Re: uspořádání, vnoření, příklad

Zápatí