Teorema Finito de Ramsey

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Informalmente, este teorema diz que para todo conjunto finito, se tomarmos os subconjuntos de um tamanho fixo, para toda partição deste conjunto, existe um conjunto homogêneo nesta partição.

Notação[editar | editar código-fonte]

  • Para todo conjunto X, denotamos por [X]^r o conjunto de todos os subconjuntos de X que tenham cardinalidade r. Ou seja, [X]^r = \{ Y \in 2^X : |Y| = k \}, onde 2^X é o conjunto das partes de X.
  • Escrevemos n \rightarrow (k)_s^r para dizer que para todo conjunto X de cardinalidade n, dado qualquer partição \{A_i\}_{i=1}^sdo conjunto [X]^r, existe um conjunto H \subset X, tal que |H| \geq k e [H]^r \subset A_k, para algum k entre 1 e s.

Teorema[editar | editar código-fonte]

\forall k, r, s \in \mathbb{N}^*, \ \exists n \in \mathbb{N} : n \rightarrow (k)_s^r [1]


Lema[editar | editar código-fonte]

Antes de demonstrar o teorema, vamos provar o seguinte lema (considerando s = 2):

\forall k, r \in \mathbb{N}^*, \ \exists n \in \mathbb{N} : n \rightarrow (k)_2^r

Demonstração do Lema[editar | editar código-fonte]

Neste caso, dado um conjunto X, todas as partições serão da forma \{A_0, A_1 \} (pois s é a ordem da partição). Vamos fazer uma indução em r.

Caso base - Considere r = 1, então, tome n = k + q -1, onde q é um natural não nulo.

Assim, como [X]^r = [X]^1 = X = A_0 \cup A_1, não podemos ter |A_0| \leq k - 1 e |A_1| \leq q - 1 ao mesmo tempo (pois |A_0| + |A_1| = |X| = n = k + q -1).

Dessa forma, se |A_0| \geq k, tome H = A_0, mas se |A_1| \geq q , tome H = A_1 (escolhendo q \geq k

Hipótese de indução - Assuma que o teorema valha para r arbitrário.


Tese - Vamos mostrar que vale para r + 1. Considere R(k, r) o menor valor de n \rightarrow (k)_2^r.

Seja X tal que |X| = n > 0 (ainda não especificado) e \{A_0, A_1 \} uma partição de [X]^{r+1}.


Referências

  1. Hrbacek, K.; Jech, T. Introduction to set theory. Monographs and textbooks in pure applied mathematics, 1999.

Ver também[editar | editar código-fonte]