vnoreni2 [REL]

Martin Koutecký — 2021-10-19 12:36 (443 days ago) — reply

Vnoření jedné uspořádané množiny $(X, \leq)$ do jiné uspořádané množiny $(Y, \preccurlyeq)$ je prosté zobrazení $f: X \to Y$ takové, že $\forall x, x' \in X: x \leq x' \Leftrightarrow f(x) \preccurlyeq f(x')$

Dokažte, že pro každou uspořádanou množinu $(X, \preceq)$ existuje vnoření do uspořádané množiny $(2^X, \subseteq)$

Santa Claus — 2021-10-22 16:05 (440 days ago) — edit — reply

Dokažme tvrzení pro množinu $[|X|] = [n]$ , pro jakokoukoliv jinou množinu už jde jen o přejmenování.

Z množiny $2^{[n]}$ vyberme všechny množiny $[k]$ , kde $k \leq n$ .

Pro každé $a,b, a < b$ platí $[a] \subset [b]$ , protože $[b]$ obsahuje všechny prvky $[a]$ .

Zobrazení, které můžeme použít jako vnoření, by mohlo být takovéto:

$f(x) = [x]$

To, že se jedná o zobrazení, je jasné, to, že je prosté, je taky zřejmé, a to, že z něj lze udělat vnoření jsem dokázal výše.

Martin Koutecký — 2021-11-05 13:29 (426 days ago) — reply

Ahoj - to by fungovalo, pokud by $(X, \leq)$ bylo lineární uspořádání, ale to být nemusí; můžeš si třeba představit, že $X = \{1,\dots, 100\}$ a $\leq$ je uspořádání dělitelností. Co uděláš pak?

Santa Claus — 2021-11-07 22:47 (423 days ago) — edit — reply

Aha, to mě vůbec nenapadlo.

Tak tedy v tom případě jinak:

každému prvku přířadíme jeho vlastní underset sjednocený s jednoprvkovou množinou obsahující samotný prvek (kdyby se jednalo o ostré uspořádání).

Pokud je prvek a pod b, pak underset b obsahuje určitě a, taky je underset a podmnožinou undersetu b (z přednášky).

Naopak pokud x není pod y, pak v množině, kterou přiřadíme y nebude prvek x, takže množina přiřazená prvku x nebude podmnožinou množiny přiřazené prvku y.

Martin Koutecký — 2021-11-08 16:47 (422 days ago) — reply

OK

Points: 4.00

The Postal Owl

Diskrétní matematika

New post (You can use Markdown with KaTeX math here)