Matematické Fórum

Olin · 02. 01. 2010 16:48 — Editoval Olin (02. 01. 2010 16:50)

Zdravím kolegy,

jako přípravu na blížící se zkoušku si cvičně dokazuji tvrzení, která jsou v mém sešitě nebo v Kapitolách z diskrétní matematiky. Prosím o kontrolu:

1. Každá konečná částečně uspořádaná množina má minimální prvek.
Důkaz zcela vymyšlený mnou, dost krkolomný. Nevím, jestli v něm není nějaký kruh.

Sporem: nechť $(X, \preceq)$ je konečná částečně uspořádaná množina, která nemá žádný minimální prvek, tj. $\forall x \in X \exists y \in X: \, y \prec x$ , kde $\prec$ je ostrá verze $\preceq$ . Nechť tedy $f$ je zobrazení v $X$ takové, že $\forall x \in X:\, f(x) \prec x$ . Označme $f^n = \overbrace{f \circ f \circ \dots \circ f}^n$ . Zřejmě je $\{|f^n(X)|\}_{n \in \mathbb{N}}$ nerostoucí posloupnost přirozených čísel, existuje tedy taková $n_0,\, k \in \mathbb{N}$ , že $\forall n \geq n_0:\, |f^n(X)| = k$ . Protože k-prvkových podmnožin $X$ je jen konečně mnoho, existují taková $s > r \geq n_0$ , že $f^r(X) = f^s(X)$ . Z toho plyne, že $f^{s-r}$ je bijekce (permutace) na množině $f^r(X)$ . Existuje tedy takové $m \in \mathbb{N} \setminus \{1\}$ a $z \in f^r(X)$ , že $$f^{s-r}$^m (z) = f^{m \cdot (s-r)}(z) = f^{s-r}(z)$ , jelikož permutace vždy obsahuje cyklus (na požádání dokážu :-) ). Protože ale $f$ zobrazí každý prvek na nějaký ostře "menší", platí $f^{s-r}(z) \succ f^{s-r+1}(z) \succ \dots \succ f^{m \cdot (s-r)}(z)$ , což je spor s tím, že $f^{m \cdot (s-r)}(z) = f^{s-r}(z)$ .

2. Pro každé částečné uspořádání na konečné množině $(X, \preceq)$ existuje lineární uspořádání $(X, \leq)$ takové, že $\preceq \subseteq \leq$ , tj. každé částečné uspořádání lze na konečné množině zúplnit na lineární.
V mém sešitě je důkaz proveden indukcí podle velikosti $X$ , a tak jsem ji zvolil také.

1. Pro $|X| = 1$ zřejmé (každé uspořádání na 1 prvku je lineární).
2. Víme pro $|X| = n$ , chceme pro $|X| = n+1$ . Nechť $m \in X$ je nějaký minimální prvek v uspořádání $\preceq$ . Označme $\tilde{X} = X \setminus \{m\},\, \tilde{\preceq} = \preceq \cap $\tilde{X} \times \tilde{X} $$ Jelikož $\| \tilde{X} \| = n$ , existuje podle indukčního předpokladu lineární uspořádání $$\tilde{X},\tilde{\leq}$$ tak, že $\tilde{\preceq} \subseteq \tilde{\leq}$ . Uspořádání $(X, \leq)$ definujeme jako $\leq\, =\, \tilde{\leq} \cup $\{m\} \times X$$ . Jde zřejmě o lineární uspořádání s nejmenším prvkem $m$ . Zbývá ověřit $\preceq \subseteq \leq$ . Nechť $x, y \in X$ , $x \preceq y$ . Pokud $x, y \in \tilde{X}$ , pak $x \leq y$ , protože $(x, y) \in \tilde{\preceq} \subseteq \tilde{\leq} \subseteq \leq$ . Pokud $x = m$ a $y \neq m$ , je $x \leq y$ podle definice $\leq$ . Alternativa $x \neq m$ , $y = m$ nemůže nastat, protože $m$ je minimální prvek. Konečně pokud $x = y = m$ , je platnost zřejmá.

Dost pravděpodobně přidám brzy ještě další důkazy.

Kondr · 02. 01. 2010 17:08

↑ Olin: Oba důkazy vypadají OK. Nebylo by i to první rychlejší indukcí?
Pro |X|=1 platí.
Pro |X|=k+1 vybereme prevek a, uspořádání redukované na $X\setminus\{a\}$ má dle IP minimální prvek b. Pokud je a<b, je a minimální prvek na X, pokud je b<a nebo jsou a,b neporovnatelné, je b minimální prvek na X.

Olin · 02. 01. 2010 17:43

↑ Kondr:
No jo, samozřejmě že je to tak jednodušší. Úvaha byla: "Je přece blbost, aby nějaká ČUMa neměla minimální prvek. Blbosti vedou ke sporu."

Teď jdu na důkaz věty "o dlouhém a širokém".

Olin · 03. 01. 2010 12:42 — Editoval Olin (03. 01. 2010 12:44)

Tak posílám ten "slibovaný" důkaz.

3. Nechť $(X, \preceq)$ je částečné uspořádání, $\alpha(X, \preceq)$ značí délku maximálního antiřetěžce (nezávislosti, velikost max. nezávislé množiny) a $\omega(X, \preceq)$ délku maximálního řetězce v tomto uspořádání. Pak platí $\alpha(X, \preceq) \cdot \omega(X, \preceq) \geq |X|$ .

Indukcí podle $\omega(X, \preceq)$ :
1. $\omega(X, \preceq) = 1 \Rightarrow \alpha(X, \preceq) = |X|$ .
2. $\omega(X, \preceq) = n+1$ . Nechť $M$ je množina všech minimálních prvků z $(X, \preceq)$ . Jde zřejmě o antiřetěz, protože z minimality všech prvků plyne pro $x, y \in M$ : $x \preceq y \Rightarrow x = y$ . Označme $\tilde{X} = X \setminus M,\, \tilde{\preceq} = \preceq \cap $\tilde{X} \times \tilde{X}$$ . Platí $\omega $ \tilde{X}, \tilde{\preceq} $ = n$ , protože odebráním všech minimálních prvků jsme všechny maximální řetězy v $X$ zkrátili o jeden prvek. Podle IP je $\alpha$\tilde{X}, \tilde{\preceq}$ \cdot \omega$\tilde{X}, \tilde{\preceq}$ \geq \|\tilde{X}\|$ . Rozebereme dva případy:
i) $|M| \leq \alpha$\tilde{X}, \tilde{\preceq}$$ . Potom je $\alpha(X, \preceq) = \alpha$\tilde{X}, \tilde{\preceq}$$ , takže $|X| = \|\tilde{X}\| + |M| \leq \alpha$\tilde{X}, \tilde{\preceq}$ \cdot \omega$\tilde{X}, \tilde{\preceq}$ + \alpha$\tilde{X}, \tilde{\preceq}$ = \alpha(X, \preceq) \cdot $\omega\(\tilde{X}, \tilde{\preceq}$ +1\) = \alpha(X, \preceq) \cdot \omega(X, \preceq)$ .
ii) $|M| > \alpha$\tilde{X}, \tilde{\preceq}$$ . Potom je $\alpha(X, \preceq) = |M|$ , takže $|X| = \|\tilde{X}\| + |M| \leq \alpha$\tilde{X}, \tilde{\preceq}$ \cdot \omega$\tilde{X}, \tilde{\preceq}$ + |M| \leq |M| \cdot \omega$\tilde{X}, \tilde{\preceq}$ + |M| = |M| \cdot $\omega\(\tilde{X}, \tilde{\preceq}$+1\) = \alpha(X, \preceq) \cdot \omega(X, \preceq)$ .

Kondr · 07. 01. 2010 01:52

↑ Olin: Chybu jsem nenašel.

Olin · 07. 01. 2010 12:28

↑ Kondr:
Díky, já taky ne, jen jsem to opět dělal možná zbytečně složitě - je zbytečné diskutovat velikost množiny $M$ , protože vždycky musí platit $\alpha(X, \preceq) \geq \alpha$\tilde{X}, \tilde{\preceq}$$ .

Každopádně teď jsem se vrátil ze zkoušky z diskrétky a snad by to měl být plný počet bodů, takže už asi další důkazy posílat nebudu. Na druhou stranu, kolega Halogan je průkopníkem nového žánru - skripta jako téma na fóru. Že bych se přidal? :-)

Matematické Fórum

#1 02. 01. 2010 16:48 — Editoval Olin (02. 01. 2010 16:50)

Důkazy z diskrétní matematiky

#2 02. 01. 2010 17:08

Re: Důkazy z diskrétní matematiky

#3 02. 01. 2010 17:43

Re: Důkazy z diskrétní matematiky

#4 03. 01. 2010 12:42 — Editoval Olin (03. 01. 2010 12:44)

Re: Důkazy z diskrétní matematiky

#5 07. 01. 2010 01:52

Re: Důkazy z diskrétní matematiky

#6 07. 01. 2010 12:28

Re: Důkazy z diskrétní matematiky

Zápatí