|
Caro Paulo Santa Rita:
Andei pesquisando um pouco ontem à noite e esbarrei num resultado que pode
demonstrar o lema 4 e, portanto, completar a demonstração do teorema de Conway.
Trata-se do TEOREMA DOS CASAMENTOS, que diz o seguinte:
"Sejam B(1), B(2), ..., B(M) conjuntos tais que a união da quaisquer k
deles (1 <= k <= M) contém no mínimo k elementos distintos. Então é
possível selecionar M objetos distintos, sendo um de cada conjunto"
Seja X = { 1, 2, ..., N } e sejam A(1), A(2), ..., A(M) subconjuntos
próprios de X tais que cada par (não ordenado) de elementos de X pertence a
exatamente um destes subconjuntos.
LEMA 4:
Se M <= N, então é possível escolher M elementos DISTINTOS de
X (digamos x(1), x(2), ..., x(M) ) tais que, x(j) não pertence a A(j), 1
<= j <= M.
DEM:
Para cada j, 1 <= j <= M, defina B(j) = X - A(j). Como cada
A(j) é próprio, B(j) <> vazio.
A idéia é provar que os B(j) satisfazem às condições do TEOREMA DOS
CASAMENTOS.
Dado k, com 1 <= k <= M, seja I um subconjunto qualquer de { 1, 2,
..., M } com k elementos.
Pela definição de B(j), e levando em conta que A(j) e B(j) são subconjuntos
de X, teremos:
UNIÃO B(j) = UNIÃO [ X - A(j) ] =
X - INTERSEÇÃO A(j)
j em
I
j em
I
j em I Se k = 1, então, como cada B(j) é não vazio, naturalmente contém 1 ou mais
elementos.
Se k = M, então I = { 1, 2, ..., M }. Assim, INTERSEÇÃO A(j) = vazio.
j em
I
Caso contrário, existiria "a" em X tal que R(a) = M, em
contradição ao LEMA 2.
Assim, | UNIÃO B(j) | = | X | = N >= M.
j em I
Finalmente, se 2 <= k <= M-1, então como cada par de elementos de X
está contido num único A(j), temos que, quisquer que sejam i e j, com 1 <= i
< j <= M, a interseção de A(i) e A(j) é vazia ou unitária.
Assim, se I tem 2 ou mais elementos, então INTERSEÇÃO A(j) é vazia ou
unitária.
j em I
Conclusão: | UNIÃO B(j) | >= N - 1 >= M - 1 >= k.
j em I
Assim, os B(j), 1 <= j <= M, satisfazem às condições do TEOREMA DOS
CASAMENTOS. Portanto, existem M elementos distintos x(1), ..., x(M) tais que
x(j) pertence a B(j), 1 <= j <= M.
Como, para cada j, B(j) = X - A(j), concluímos que existem M elementos
distintos x(1), ..., x(M), pertencentes a X, tais que, para cada j, x(j) não
pertence a A(j) e o LEMA 4 está provado.
***********
Agora, resta esperar para ver a demonstração "mágica", de 1 linha, que o
Conway deu para o teorema original.
Um abraço,
Claudio Buffara.
|