Ferramentas do usuário
Teorema de Ramsey
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 \}$
Sejam $n\in \omega$ e $\mu$ um cardinal. Uma $n$-coloração de $X$ com $\mu$ cores é uma função $c:[X]^n \rightarrow \mu$.
Seja $c$ uma $n$-coloração sobre $X$ com $\mu$ cores. Dizemos que $H\subset X$ é $c$-homogêneo (ou só homogêneo) de cor $i\in \mu$ se $c$ é constante em $[H]^n$.
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$.
1 Mostre que $\aleph_0 \rightarrow (\aleph_0)^1_m$, $m\in \omega$.
2 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$.
2.1 Defina $x_0 = 0$.
2.2 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$.
2.3 Defina $x_1 = \min A_0$.
2.4 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$.
2.5 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$.
2.6 Encontre o $H$ homogêneo infinito.
3 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,\ldots,x_n) = c(a_k,x_1,\ldots,x_n)$.
3.1 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?).
3.2 Considere $A=\{a_k:k\in \omega\}$. Note que ele é infinito.
3.3 Considere $\{a_{k_0},\ldots,a_{k_n}\} \subset A$ com $k_0 < k_1 < \ldots<k_{n}$. Qual é o valor de $c(a_{k_0},\ldots,a_{k_n})$? (Com relação às $i_k$'s)
3.4 Construa uma subsequência de $A$ que seja c-homogênea.
4 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$. Dica
5 Conclua que $\aleph_0 \rightarrow (\aleph_0)^n_m$ para todos $n,m\in \omega$.
O último item é o teorema de Ramsey (a versão infinita dele - a versão finita está abaixo). Dele segue o seguinte corolário.
6 Mostre que toda sequência de números reais tem uma sequência estritamente crescente, estritamente decrescente ou constante. Dica
Antes de continuar, talvez seja melhor você conhecer o Lema de König (tem nesta lista).
7 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$.
7.1 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.
7.2 Note que $\mathbb P$ é infinita.
7.3 Mostre que $\mathbb P$ contém um ramo infinito e obtenha uma contradição com o Teorema de Ramsey infinito.
Ferramentas da página
