Ferramentas do usuário
Essa é uma revisão anterior do documento!
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 \textbf{$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$ é \textbf{$c$-homogêneo} (ou só \textbf{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 Mostre que $\aleph_0 \rightarrow (\aleph_0)^n_2 \Rightarrow \aleph_0 \rightarrow (\aleph_0)^{n+1}_2$, para todo $n\in \omega$.
2.1 Seja $c$ uma $(n+1)$-coloração em $\omega$ com $2$ cores. Defina $a_0=0$ e $A_0=\omega$. Para todo $i\in \omega$ defina $I_i = \{n\in \omega: n\leq a_i\}$.
- Suponha definidos $A_k$ e $a_k$. Defina $c_k: [\omega \setminus I_k]^n \rightarrow 2$ dada por $c_k(x_1,\ldots,x_n) = c(a_k,x_1,\ldots,x_n)$.
Defina $A_{k+1} \subset \omega \setminus I_k$ como sendo um conjunto $c_k$-homogêneo de cor $i_k$ e $a_{k+1} = min(A_{k+1})$. Tome $A=\{a_k:k\in \omega\}$.
- Seja $\{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)
- Construa uma subsequência de $A$ que seja c-homogênea.
3 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
4 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, também há a versão finita). Dele segue o seguinte corolário.
5 Mostre que toda sequência de números reais tem uma sequência estritamente crescente, estritamente decrescente ou constante. Dica
Ferramentas da página
