===== Teorema de Ramsey =====

<WRAP info>
Para um conjunto $X$ e um cardinal $\alpha$ definimos:\\
  * $[X]^{\alpha} = \{ Y \subset X : |Y|=\alpha \}$ \\
  * $[X]^{\leq \alpha} = \{ Y \subset X : |Y|\leq \alpha \}$ \\
  * $[X]^{\geq \alpha} = \{ Y \subset X : |Y|\geq \alpha \}$
</WRAP>

<WRAP info>
Sejam $n\in \omega$ e $\mu$ um cardinal. Uma {{entry>$n$-coloração}} de $X$ com $\mu$ cores é uma função $c:[X]^n \rightarrow \mu$.
</WRAP>

<WRAP info>
Seja $c$ uma $n$-coloração sobre $X$ com $\mu$ cores. Dizemos que $H\subset X$ é {{entry>$c$-homogêneo}} (ou só {{entry>homogêneo}}) de cor $i\in \mu$ se $c$ é constante em $[H]^n$.
</WRAP>


<WRAP info>
Sejam $\kappa$ e $\lambda$ cardinais. Escrevemos $\lambda \rightarrow (\kappa)^n_{\mu}$ se para toda $n$-coloração com $\mu$ cores em $\lambda$ existe um conjunto homogêneo de tamanho $\kappa$.
</WRAP>

**~~#~~** Mostre que $\aleph_0 \rightarrow (\aleph_0)^1_m$, $m\in \omega$.

**~~#~~** Este é um roteiro para mostrar que $\aleph_0 \rightarrow (\aleph_0)^2_k$ para $k \in \omega$. A ideia deste roteiro ajuda nos próximos exercícios. Fixe uma coloração em $k$ cores para $[\omega]^2$.

**~~#.#~~** Defina $x_0 = 0$.

**~~#.#~~** Note que existem $c_0 \in k$ e $A_0 \subset \omega \setminus \{x_0\}$ tais que $A_0$ é infinito e, para todo $\{x_0, a\}$ tal que $a \in A_0$, temos que a cor de $\{x_0, a\}$ é $c_0$.

**~~#.#~~** Defina $x_1 = \min A_0$. 

**~~#.#~~** Note que existem $c_1 \in k$ e $A_1 \subset A_0 \setminus \{x_1\}$ tais que $A_1$ é infinito e, para todo $\{x_1, a\}$ tal que $a \in A_1$, temos que a cor de $\{x_1, a\}$ é $c_1$.

**~~#.#~~** Generalize o processo e obtenha sequências $(x_n)_{n \in \omega}$, $(A_n)_{n \in \omega}$ e $(c_n)_{n \in \omega}$. Note que existe $i \in k$ tal que $c_n = i$ para infinitos $n's$.

**~~#.#~~** Encontre o $H$ homogêneo infinito.


**~~#~~** Este é um roteiro para mostrar que $\aleph_0 \rightarrow (\aleph_0)^n_2 \Rightarrow \aleph_0 \rightarrow (\aleph_0)^{n+1}_2$, para todo $n\in \omega$. Seja $c$ uma $(n+1)$-coloração em $\omega$ com $2$ cores. Defina $a_0=0$ e $A_0=\omega$. Suponha definidos $A_k$ e $a_k$. Defina $c_k: [A_k \setminus \{a_k\}]^n \rightarrow 2$ dada por $c_k(x_1,...,x_n) = c(a_k,x_1,...,x_n)$.

**~~#.#~~** Defina $A_{k+1} \subset A_k \setminus \{a_k\}$ como sendo um conjunto $c_k$-homogêneo de cor $i_k$ e $a_{k+1} = min(A_{k+1})$ ($A_{k + 1}$ sempre existe, certo?). 

**~~#.#~~** Considere $A=\{a_k:k\in \omega\}$. Note que ele é infinito.

**~~#.#~~** Considere $\{a_{k_0},...,a_{k_n}\} \subset A$ com $k_0 < k_1 < ...<k_{n}$. Qual é o valor de $c(a_{k_0},...,a_{k_n})$? (Com relação às $i_k$'s)

**~~#.#~~** Construa uma subsequência de $A$ que seja c-homogênea.

**~~#~~** Mostre que $\aleph_0 \rightarrow (\aleph_0)^n_m \Rightarrow \aleph_0 \rightarrow (\aleph_0)^n_{m+1}$, para todo $n,m\in \omega$, $m\geq 2$. <wrap tip>[[dica:InducaoCores|Dica]]</wrap>

**~~#~~** Conclua que $\aleph_0 \rightarrow (\aleph_0)^n_m$ para todos $n,m\in \omega$.

<WRAP info>
O último item é o teorema de Ramsey (a versão infinita dele - a versão finita está abaixo). Dele segue o seguinte corolário.
</WRAP>

**~~#~~**  Mostre que toda sequência de números reais tem uma sequência estritamente crescente, estritamente decrescente ou constante. <wrap tip>[[dica:SeqCrescDecresc|Dica]]</wrap>

<WRAP tip>
Antes de continuar, talvez seja melhor você conhecer o Lema de König (tem nesta [[lista:Arvores|lista]]).
</WRAP>

**~~#~~** Este é um roteiro para mostrar a versão finita do Teorema de Ramsey: Dados $m, n, r \in \omega$, com $r \geq 1$ e $n \leq m$, temos que existe $N \geq m$ tal que $N \rightarrow (m)^n_r$. 

**~~#.#~~** Suponha que não vale o resultado. Considere $\mathbb P = \{\pi_N: \pi_N$ é uma $n$-coloração de $r$ cores sobre $N$, tal que não existe homogêneo $H \subset N$  com $|H| = m\}$. Sobre $\mathbb P$, defina a relação $\pi_N \leq \pi_M$ se $N \subset M$ e $\pi_M$ estende $\pi_N$. Note que $\mathbb P$ é uma árvore que bifurca finitamente. 

**~~#.#~~** Note que $\mathbb P$ é infinita.

**~~#.#~~** Mostre que $\mathbb P$ contém um ramo infinito e obtenha uma contradição com o Teorema de Ramsey infinito.