Teoria di Ramsey

[fields]

In queste dimostrazioni non si possono saltare i dettagli, altrimenti si sbaglia. Se dimostri anche questo, allora la tua prova è ok.

Nell'ordine lessicografico, si ha che $f^{-1}(n) \sub f^{-1}(n+1)$, se $n$ è pari.

Per quanto riguarda l'altro problema, devo ancora capire se ho fatto progressi o no . In sostanza ho ridotto il problema nel trovare una funzione iniettiva $f$ dall'insieme $S_k$ dei sottinsiemi di $S$ con $k$ elementi nell'insieme $S_(k+1)$ dei sottinsiemi di $S$ con $k+1$ elementi (ovviamente quanto $|S_k|<|S_(k+1)|$) tale che $A sub f(A)$ per ogni $A\in S_k$. Però anche dimostrare questo non è così facile.

[TomSawyer]

Ok, è che mi sembra così per definizione. L'ordine lessicografico a cui faccio riferimento (ci sono almeno tre ordini in giro con questo nome) è questo. Esempio per $S={1,2,3}$: ${1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}$. Ogni due elementi si introduce uno nuovo, facendo seguire poi

Tesi: $f^{-1}(n) \sub f^{-1}(n+1)$, se $n$ è pari. Per $n=2$ è vera. Supponiamo sia vera per $n-1$. Allora per $n$ abbiamo già metà dei sottoinsiemi ordinati (per ipotesi induttiva), cioè tutti quelli senza $n$. I prossimi $2^{n-1}$ sottoinsiemi, sono esattamente quelli della prima metà, con aggiunto ${n}$ ad ognuno, non cambiando assolutamente nulla.

Ora veniamo alla tua dimostrazione di una riga .

[fields]

L'ordine lessicografico a cui faccio riferimento (ci sono almeno tre ordini in giro con questo nome) è questo.

E quando pensavi di specificare quale dei tre era il tuo ordinamento lessicografico? Io stavo pensando a tutt'altro ordinamento!

Comunque, ordinamento carino e prova carina.

Io avevo fatto cosi. Fissiamo $s\in S$. Consideriamo la funzione $f: X to P(S\\{s})$ cosi' definita: $f(A)=A\\{s}$. Il codominio di $f$ ha cardinalita' $2^(|S|-1)$, mentre il dominio di $f$ ha cardinalita' maggiore di $2^(|S|-1)$ per ipotesi. Per il pigeonhole principle, esistono due distinti $A,B\in X$ tali che $f(A)=f(B)$; dunque $A\\{s}=B\\{s}$. Chiaramente $s$ non puo' appartenere o non appartenere a entrambi $A$ e $B$, altrimenti $A=B$. WLOG, $s\in B$ e $s\notin A$ e dunque $A=A\\{s}=B\\{s}$ e dunque $A\sub B$.

Ora al lavoro sul problema più difficile!

[vl4d]

Io ho provato un po' sia per induzione sia ragionando sul grafo del reticolo d'ordine... ma o
ero rincitrullito, o la prova non e' molto agevole in quei modi...

[fields]

EDIT: Ragazzi, ma quello che cercavamo di dimostrare è il teorema di Sperner!

http://www.math.cmu.edu/~af1p/Combinato ... es/Ch6.pdf

http://www.cut-the-knot.org/pigeonhole/sperner.shtml