Teorema di Dilworth

[Sepp]

Scusate se è una sciocchezza!
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]

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.

[Sepp]

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

[piever]

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 $