Matematické Fórum

Pavel Brožek

Ahoj, učím se na zkoušku z teorie množin, tak doufám, že mi pomůžete :-). Spíš mě řešení jen zajímá, ke zkoušce ho asi nebudu potřebovat.

Mám dvě dobře ostře uspořádané množiny $\langle a,r\rangle$ a $\langle b,s\rangle$ a funkci definovanou (snadno se ověří, že to je skutečně funkce)

$f=\{\langle v,w\rangle:v\in a\,\wedge\, w\in b\,\wedge\,\langle(\leftarrow,v),r\rangle\cong\langle(\leftarrow,w),s\rangle\}$ .

Mám ukázat, že f zachovává uspořádání, tj. pokud $\langle v_1,w_1\rangle\in f$ , $\langle v_2,w_2\rangle\in f$ a $v_1\, r\,v_2$ , pak $w_1 \,s\, w_2$ .

Značení Zobrazit/skrýt!

V poznámkách k přednášce se tvrdí, že to je „zřejmé z definice“. Mně to ale zřejmé není :-). Při důkazu nemůžu použít skoro nic, předcházely tomu prakticky jen dvě lemmata (která dále uvádím) a základní definice.

Lemmata Zobrazit/skrýt!

Rumburak · 14. 06. 2012 16:34

Ahoj.

Zatím jen nápad: $\langle b,s\rangle$ je dobře uspořádána, odtud mj. plyne, že nastává jedna z možností $w_1 \,s\, w_2$ , $w_2 \,s\, w_1$ , $w_1 \,=\, w_2$ .
Připadá mi, že by se to v tom důkaze mohlo hodit.

OiBobik

↑ Pavel Brožek:

Ahoj,

já bych řekl, že je to důsledek toho, že dobře usp množina není isomorfní žádnému svému poč. úseku a navíc toho, že dobré usp. je lineární...

Vymýšlím to ale sám, v poznámkách mám taky jen nějaké neužitečné "zřejmě to a ono", takže ber to s rezervou:

Nechť $\langle v_2,w_2\rangle, \langle v_1,w_1\rangle\in f$ a $v_1 r v_2$ . Pak $v_1 \in (\leftarrow, v_2)$

Uvažme isomorfismus $\varphi: \langle(\leftarrow,v_2),r\rangle \rightarrow \langle(\leftarrow,w_2),s\rangle$

Pak jeho restrikce $\psi=\varphi \restriction_{(\leftarrow, v_1)}$ je isomorfismus $\psi: \langle(\leftarrow,v_1),r\rangle \rightarrow \langle(\leftarrow,\varphi(v_1)),s\rangle$ (to by mělo jít snadno ověřit)

Dále dobré usp. je lineární - tedy buď $w_2=w_1$ (1) nebo $w_2 s w_1$ (2) nebo $w_1 s w_2$ (3).

(1) kdyby $w_1=w_2$ , pak je $\langle(\leftarrow,v_1),r\rangle \simeq \langle(\leftarrow,w_1),s\rangle = \langle(\leftarrow,w_2),s\rangle \simeq \langle(\leftarrow,v_2),r\rangle$ ... spor (dobře usp. množina není isomorfní svému poč úseku, lemma)

(2) kdyby $w_2 s w_1$ , pak $\varphi(v_1) s w_2 \wedge w_2 s w_1$ implikuje $\varphi(v_1) s w_1$ , no ale pak $\langle(\leftarrow,w_1),s\rangle \simeq \langle(\leftarrow,v_1),r\rangle \simeq \langle(\leftarrow,\varphi(v_1)),s\rangle$ , což je ovšem opět spor s lemmatem, jelikož $\langle(\leftarrow,\varphi(v_1)),s\rangle$ je počáteční úsek množiny $\langle(\leftarrow,w_1),s\rangle$

Zbývá tedy možnost (3), což jsme chtěli.

Ještě pozn: Nevím, jestli o tom víš, kdysi kdesi někdo naTeXoval k Simonově přednášce poznámky

Pavel Brožek

↑ Rumburak:

Díky.

↑ OiBobik:

Projdu si tvůj důkaz. Mám právě stažené naTeXované poznámky k Simonově přednášce, ale je to jiná verze (nebo od někoho jiného), ta co odkazuješ se zdá podrobnější. Díky.

Pavel Brožek · 14. 06. 2012 17:24

↑ OiBobik:

Zdá se mi to v pořádku, tak ještě jednou díky :-). Zřejmé mi to teda pořád nepřijde, možná se tím myslí, že je zřejmé, že by to tak asi mělo být, ale důkaz už tak zřejmý není :-).

OiBobik · 14. 06. 2012 17:28

↑ Pavel Brožek:

To se mi stává u Simona celkem často. : ))

Pavel Brožek · 14. 06. 2012 17:32

↑ OiBobik:

V těch poznámkách, na které odkazuješ, to je rozepsané (bod c důkazu na straně 22) :-).

OiBobik · 14. 06. 2012 17:50

↑ Pavel Brožek:

Aha, no fakt. : ))

Toho jsem si nevšiml (myslel jsem, že a,b,c v důkazu odpovídá a,b,c ve větě a že ty vlastnosti f jsou nějak vynechány).

Tak aspoň je jasné(/-ější), že je to tak správně.

Matematické Fórum

#1 14. 06. 2012 15:59 — Editoval Pavel Brožek (14. 06. 2012 16:01)

TeMno: Důkaz, že funkce zachovává uspořádání

#2 14. 06. 2012 16:34

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#3 14. 06. 2012 17:12 — Editoval OiBobik (14. 06. 2012 17:14)

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#4 14. 06. 2012 17:18 — Editoval Pavel Brožek (14. 06. 2012 17:19)

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#5 14. 06. 2012 17:24

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#6 14. 06. 2012 17:28

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#7 14. 06. 2012 17:32

Re: TeMno: Důkaz, že funkce zachovává uspořádání

#8 14. 06. 2012 17:50

Re: TeMno: Důkaz, že funkce zachovává uspořádání

Zápatí