Teorema di Dilworth

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Sepp
Messaggi: 87
Iscritto il: 01 gen 1970, 01:00
Località: Vicenza

Teorema di Dilworth

Messaggio da Sepp » 04 giu 2007, 18:55

Scusate se è una sciocchezza! :oops:
Non ho capito un passo della dimostrazione del Teorema di Dilworth nel video del WC 2007:

$ C $ è l'insieme degli elementi che sono contenuti in un elemento dell'anticatena, $ D $ è l'insieme degli elementi che contengono un elemento dell'anticatena, $ W $ è l'anticatena di cardinalità massima. Perchè $ D \vee C = \varnothing $?

Naturalmente se qualcuno vuole postare la sua dimostrazione...

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 04 giu 2007, 19:40

Uhm, quella dimostrazione durante il wc non ha subito grandi contestazioni (a parte il forte attacco di nausea di post233) per cui dovrebbe essere giusta.

In ogni caso tu chiedi perche' quei due insiemi sono disgiunti.

Supponiamo che un elemento X appartenga a entrambi. Allora esistono due elementi, diciamo A e B, appartenenti all'anticatena, tali che $ A\subset X \subset B $, ma allora $ A\subset B $ che e' assurdo perche' A e B appartengono ad una stessa anticatena.
"Sei la Barbara della situazione!" (Tap)

Sepp
Messaggi: 87
Iscritto il: 01 gen 1970, 01:00
Località: Vicenza

Messaggio da Sepp » 04 giu 2007, 20:18

Ok, ma è stato supposto che la tesi fosse falsa. Perchè ciò implica che uno dei due debba essere vuoto? :?

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 04 giu 2007, 20:47

Ah, scusami, avevo capito male la domanda...

E' stato preso il controesempio con il minor numero di elementi. Visto che W+C+D non e' partizionabile in |W| catene disgiunte, non lo e' neanche uno tra W+C e W+D. Infatti se entrambi gli insiemi fossero partizionabili, potrei "legare" le due partizioni (le "giunture" sarebbero gli elementi di W) e partizionare W+C+D.Quindi possiamo supporre wlog che W+C non e' partizionabile in |W| catene disgiunte. Ora dunque $ |W+C+D|\le |W+C| $ (l'insieme di partenza era il piu' piccolo controesempio) quindi $ |D|\le 0 $ ovverosia $ D=\varnothing $
"Sei la Barbara della situazione!" (Tap)

Rispondi