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.
|