===== Lema de Kuratowski-Zorn (usando) =====

<WRAP tip>
O enunciado do Lema de Kuratowski-Zorn é equivalente ao princípio da boa ordem - para ver sobre isso, veja esta [[lista:ZornP|lista]].
</WRAP>

<WRAP info> 
Seja $X$ um conjunto ordenado por $\leq$. 


  * $x \in X$ é um {{entry>majorante}} para $Y \subset X$ se, para todo $y \in Y$ temos $y \leq x$;
  * $C \subset X$ é uma {{entry>cadeia}} se todos os elementos de $C$ são comparáveis entre si;
  * $x \in X$ é {{entry>maximal}} se não existe $y \in X$ tal que $x < y$. 
</WRAP> 

<WRAP info>
O {{entry>Lema do Kuratowski-Zorn}} é: Se $X$ é um conjunto ordenado não vazio tal que toda cadeia admite majorante, então $X$ admite elemento maximal. 
</WRAP>

**~~#~~** Seja $X$ um conjunto não enumerável. Considere $F$ o conjunto de todas as funções injetoras com domínio finito contido em $\omega$ e contradomínio $X$. Dizemos que $f, g \in F$ são compatíveis se $f \cup g \in F$ (se esse isso é confuso para você, veja essa [[lista:funcoes|lista]]). Seja $P$ a família de todos os subconjuntos de $F$ formados por funções compatíveis entre si. Isto é $P = \{A \subset F: \forall f, g \in A$ $f$ e $g$ são compatíveis$\}$. Considere sobre $P$ a ordem da inclusão. 

**~~#.#~~** Note que $P \neq \emptyset$.

**~~#.#~~** Mostre que se $A$ é um elemento de $P$, então $\bigcup_{f \in A} f$ é uma função injetora de domínio contido em $\omega$ e contradomínio $X$.

**~~#.#~~** Mostre que se $A$ é um elemento maximal em $P$, então o domínio de $\bigcup_{f \in A} f$ é $\omega$.
 

**~~#.#~~** Mostre que se $\mathcal C \subset P$ é uma cadeia, então $\bigcup_{C \in \mathcal C} C \in P$.

**~~#.#~~** Conclua que existe uma função injetora $f: \omega \to X$.

<WRAP info>
Um dos axiomas que supomos sobre conjuntos é o {{entry>princípio da boa ordem}}: todo conjunto admite uma boa ordem.
</WRAP>

**~~#~~** Este é um roteiro para mostrar que o Lema de Kuratowski-Zorn implica no princípio da boa ordem. A volta pode ser vista nesta [[lista:ZornP|lista]]. Seja $X$ um conjunto. Considere $P$ a família de todas as boas ordens sobre subconjuntos de $X$ - isto é, $(A, \leq) \in P$ se $\leq$ é uma boa ordem sobre $A \subset X$. 

**~~#.#~~** Mostre que $P \neq \emptyset$.

**~~#.#~~** Dados $(A, \leq), (A', \leq') \in P$, definimos $(A, \leq) \preceq (A', \leq')$ se $A \subset A'$, $\leq'$ estende $\leq$ e, dados $a' \in A'\setminus A$ e $a \in A$, temos que $a \leq' a'$. Mostre que $\preceq$ é uma ordem sobre $P$. 

**~~#.#~~** Mostre que $(A, \leq) \in P$ é maximal, então $A = X$.

**~~#.#~~** Seja $\mathcal C$ um cadeia em $P$. Mostre que existe uma boa ordem $\leq'$ sobre $C = \bigcup_{(A, \leq) \in \mathcal C} A$ tal que $(A, \leq) \preceq (C, \leq')$ para todo $(A, \leq) \in \mathcal C$.

**~~#.#~~** Conclua que existe uma boa ordem sobre $X$.

**~~#~~** Para cada $z \in \mathbb Z$, considere $(\mathbb Z_{\geq z}, \leq_z)$ onde $\leq_z$ é a restrição da ordem usual de $\mathbb Z$ em $\mathbb Z_{\geq z}$. Note que não existe uma boa ordem sobre $\mathbb Z$ tal estenda cada uma das $\leq_z$. Olhe o roteiro acima e veja o motivo da ordem lá não ser a que pareceria mais natural num primeiro momento.