Inscription / Connexion Nouveau Sujet
Théorème de Dilworth
Bonjour,
Je cherche un contre exemple au théorème de Dilworth, ie je cherche
un ensemble partiellement ordonné avec
et qui possède une antichaîne maximale de longueur
mais pour lequel il n'existe pas de partition en un nombre fini de chaînes.
J'ai d'abord pensé aux entiers naturels munis de la divisibilité, mais l'ensemble des nombres premiers est une antichaîne de longueur infinie!
Si l'un d'entre vous a une idée!
Merci
Bonjour
Je ne connais pas trop le sujet, mais les entiers de la forme munis de la divisibilité ne feraient-ils pas l'affaire?
Hélas non, car étant donnée une antichaîne de longueur p sur ton ensemble, on peut toujours construire une antichaîne de longueyr p+1.
Il suffit de prendre la famille des .
Il faudrait pouvoir prouver qu'une antichaîne est de longueur maximale finie!
Bonjour,
Je cherche un contre exemple au théorème de Dilworth
plaisanterie mise à part :
C'est quoi le théorème de Dilworth ?
Et c'est quoi une antichaîne ?
MM
Je ne comprend pas bien non plus...
le th de Dilworth dit justement que si l'antichaine maximal est de longeur p, alors il y a une partition en p chaine...
Bon j'ai réfléchi... et je suis pas du tous convaincu qu'un tel contre-exemple existe : la condition que toute les anti-chaine soit de cardinal inférieur à n est vraiment contraignante...
Bonjour!
Je l'avoue, je me suis pas très bien exprimé!
Je reformule:
On connaît le théorème de Dilworth qui dit que dans un ensemble partiellement ordonné de cardinal n fini, la longueur maximale d'une antichaîne est égale au nombre minimal de chaînes qu'il faut pour former une partition de l'élément.
Je rappelle aussi les définitions de base:
Ensemble partiellement ordonné: ensemble muni d'une relation d'ordre (en général pas total sinon ça n'est plus très intéressant!)
Chaîne: sous-ensemble totalement ordonné
Antichaîne: sous ensemble dont les éléments ne sont jamais deux à deux comparables
Ici, il s'agit de trouver un contre exemple au théorème pour le cas infini!
Euh... toujours pas capté en ce qui me concerne...
Le début et la fin, ça va à peu près. Là où ça coince c'est "nombre minimal de chaînes qu'il faut pour former une partition de l'élément." Ya pas un bug dans la matrice là? C'est quoi une partition d'un élément?
Je ne comprends pas bien pour quoi ce théorème serait faux dans le cas infini...
Soit X1 ; X2 ; ... , Xq une partition de E en chaînes, qui soit minimale (c'est à dire q minimal).
et soit A={a1;a2;a3 ...} une antichaîne de longueur supérieure à q.
L'incontournable théorème des tiroirs et des chaussettes nous permet d'affirmer qu'il existe i et j différents et k tels que ai et aj appartiennent au même Xk... et sont donc comparables... donc contradiction et donc la longueur maximale de A est q.
Non ?
ou alors où est la faille dans ma démonstration ?
Bonjour,
Oui désolé pour le lapsus: il fallait évidemment lire "partition de l'ensemble"
Je ne pense pas que la question (trouver un contre exemple si on ne considère pas l'hypothèse Card(E)<
) et le raisonnement de MatheuxMatou soient contradictoires.
En gros, en résumé, tu as montré que si une telle partition en q (minimal) chaînes existe, alors une antichaîne maximale a exactement q éléments, et je suis parfaitement d'accord!
Mais moi, je cherche plutôt à montrer qu'on peut avoir une longueur maximale d'antichaine finie q sans toutefois de partition en q chaînes...
Si un tel contre exemple n'existait pas, le théorème de Dilworth marcherait aussi pour les ensembles infinis, et ce n'est pas le cas! (cf: 
).
Voilà je continue mes recherches!
Merci en tout cas!
ben ce n'est pas contradictoire ! si aucune partition finie n'existe, par extension de raisonnement, le nombre minimal de chaînes formant une partition vaut + (au pire, si aucun élément n'est comparable à un autre, chaque chaîne ne comporte qu'un élément et l'antichaîne est E)... et le une antichaîne est fatalement de longueur infinie... mon raisonnement marche encore s'il n'existe aucun "q" fini.
MM
Oui je reste sans voix...
Je mets une copie de mon énoncé:
"Give an example, showing that Dillworth's theorem only holds for finite posets (i.e. find an
infinite poset with finite antichains but no decomposition into finitely many chains)."
En même temps, si le théorème de Dillworth fonctionne avec des ensembles infinis, pourquoi prend-on "fini" comme hypothèse??
Il y a un truc à creuser là!
bon déjà, sur le site Wiki que tu as donné, je lis ceci :
An equivalent way of stating Dilworth's theorem is that, in any partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains.
et mes faibles connaissances en anglais me font dire que dans "any partially ordered set"... je ne vois aucunement mentionné le fait que l'ensemble doit être fini.
Mais bon, on trouve aussi beaucoup de bêtises sur Internet.
maintenant, si on te demande de montrer ce que tu énonces (je présume que c'est posé par un prof spécialiste de la chose, et là je fais confiance), alors effectivement il y a une faille dans mon raisonnement poussé à l'infini.... je l'ai certes fait un peu vite... j'essaye de le rédigezr mieux et je reviens (parfois en trouvant la faille, on trouve un contre exemple)
A bientôt clicli
moi aussi je reste sans voix !
dans l'énoncé du théorème de Dilworth, tu écrivais :
la longueur maximale d'une antichaîne est égale au nombre minimal de chaînes qu'il faut pour former une partition de l'élément
Ce qui veut dire qu'il n'y a rien de contradictoire à avoir une antichaîne de longueur inférieure au nombre minimal de chaînes formant une partition...
bien et dans le cas infini, on te demande de montrer que
find an
infinite poset with finite antichains but no decomposition into finitely many chains)
je ne vois vraiment pas de contrexemple ici ! S'il n'y a pas de partition finie en chaînes, le nombre minimal vaut +
et donc la longueur maximale d'une antichaîne est infinie... donc il peut y en avoir de longueur finie...
je ne comprends vraiment pas où il y a contradiction avec un prolongement aux infinis de ce théorème.
Maintenant si tu veux vraiment un exemple demandé par ton sujet, cela me paraît assez simple :
les entiers munis de la relation d'ordre "divise" : pas de partition finie en chaînes et je te donne une antichaîne de longueur 2 : {2;3}
Clicli : il me semble que ce qui serait vraiment un contrexemple au prolongement infini du théorème de Dilworth serait de trouver un ensemble infini partiellement ordonné dans lequel on a une partition finie en K chaînes... avec K fini, et où on a aussi une antichaîne de longueur (K+1).
Là, oui, cela contredirait ce théorème dans les cas infinis
Bah je sais pas trop quoi penser... Sur le site theoremoftheday, ils disent qu'il faut que l'ensemble soit fini, sur le site Planet Math, ils disent que l'ensemble doit être de largeur finie (ie son antichaîne maximale doit être finie), et le wiki dont je donne le lien commence par "Dilworth's theorem characterizes the width of any finite partially ordered set"
(Mais bon, que Wiki se plante, c'est pas la dernière grande nouvelle!)
Demain j'irai me plonger dans de la vraie littérature sur du bon vieux papier!
Donc je comprends plus rien, et oui mon prof est assez calé dans la matière! Au pire, si on trouve pas d'ici là j'aurai la réponse mercredi!
Courage!
déjà, il faudrait formuler correctement ce que ce théorème dirait dans le cas infini... pour montrer qu'il ne fonctionne pas...
que penses-tu de cette formulation :
Soit E un ensemble infini partiellement ordonné.
S'il existe une partition de E en K chaînes, avec K entier, alors toute antichaîne a une longueur inférieure ou égal à K
Si aucune partition finie de E en chaîne n'existe, alors il existe une antichaîne de longueur infinie.
Es-tu d'accord que cela pourrait constituer un prolongement du théorème de Dilworth à l'infini ?
(en fait le prolongement devrait même dire dans le deuxième cas... toute antichaîne a une longueur inférieure à l'infini... ce qui est une trivialité !)
Je ne comprends pas non plus la question posée !
Ok là je suis d'accord...
Donc on cherche une partition en K chaînes et une antichaîne de longueur supérieure strictement à K (cf ce que tu dis plus haut) voire même infinie.
On devrait pas aller voir du côté d'irrationnels denses dans 
pour lesquels on pourrait trouver des limites...
Je ne sait pas trop mais bon, c'est une idée!
ben oui, mais si on a une partition en K chaînes, mon raisonnement précédent (avec les tiroirs et les chaussettes) marche encore il me semble, donc ce sera difficile de trouver une antichaîne de longueur K+1.
Non, ce n'est vraiment pas clair !
Ah je viens de voir ton exemple avec {2,3} !!!!!
Serait-ce une réponse à la question?? Je pense qu'on peut aussi bien passer sur un forum d'anglais!!
Et donc il semblerait que le théorème de Dilworth, formulé comme ci-dessus, fonctionne aussi avec des ensembles infinis!
Merci
ben je sais pas... c'est vrai que c'est un sujet que je découvre avec ton post (et je t'en remercie)... mais j'ai peur de ne pas saisir toute la subtilité du problème !
L'exemple avec {2;3} fournit une réponse à la question que tu as formulée (en anglais !)... mais est-ce la bonne question ? That is the question !
Bon, écoute, tu me diras après la correction ce que ton prof a dit.... cela m'intéresse fortement.
Amicalement
Alain
"ou alors où est la faille dans ma démonstration ?" >>> La faille, c'est que tu as prouvé qu'une inégalité, il manque l'autre sens. ce que tu as prouvé c'est que la cardinal de toute antichaine est inférieur au cardinal de n'importe quel partition en chaine, ce qui est evident (aussi bien pour des cardinaux fini qu'infini...) le point non trivial du th de Dilworth c'est qu'il existe une partition en chaine et une antichaine de meme cardinal (ce qui etant donné l'inégalité précedente nous assure que l'antichaine est de taille maximal, et la partition de taille minimal...)
"Clicli : il me semble que ce qui serait vraiment un contrexemple au prolongement infini du théorème de Dilworth serait de trouver un ensemble infini partiellement ordonné dans lequel on a une partition finie en K chaînes... avec K fini, et où on a aussi une antichaîne de longueur (K+1). " >>>> ca c'est impossible, à cause de ton argument des tirroires.
Le cas {2^k*3^m} montre qu'il n'existe pas forcement d'antichaine de longeur maximal on a des antichaine de longeur arbitrairement grande, mais toujour fini : dans ce cas toute partition en chaine est infinie, et toute antichaine est fini... on ne peut donc pas donner d'antichaine et de partition en chaine de meme cardinal.
ca fournit donc en un sens un contre exemple au théorème de Dilworth (si c'est une question posé en cours, je pense que c'est ce genre de chose qui est attendu...)
en revanche, il reste une question difficile : est ce que le "sup" des cardinaux des antichaine est egal au min des cardinaux des partiton en chaine... ce problème semble difficile (si c'est vrai, c'est au moins aussi difficile que Dilworth à prouver...) et rien de ce qui à été dit aussi ne permet de conclure...
Ksilver : tu voudrais donc dire qu'il existe une ensemble E infini totalement ordonné dans lequel il n'y a aucune partition finie en chaîne... et où on ne peut pas trouver une antichaîne de longueur infinie... ce serait ça le contrexemple ?
Dans l'énoncé qu'on me fournissait, il était question de longueur maximale... mais pas de valeur maximale des longueurs... ce qui n'est pas la même chose car l'un n'est pas obligé d'être atteint alors que l'autre oui !
J'aimerais que les questions et les énoncés soient clairement formulés car là, j'ai bien peur de ne pas comprendre le problème !
cordialement
MM
Ce que je cherchais moi c'est un ensemble E infini qui comme dans le sujet initial possède une antichaine maximal (au sens du plus grand cardinal pas au sens de l'inclusion) de longeur fini n, et pas de partition en un nombre fini de chaine... (ou alors juste pas de partition en n chaine)
ca donnerai un cas ou le sup des longeur des antichaine serait n (ie toute antichaine et de longeur inférieur ou égal à n) et serait différent du min du cardinal d'une partition en chaine (qui serait infinie, ou au moins strictement supérieur à n...), c'est ce que semblait chercher clicli dans ces premiers messages je crois.
mais si on veux juste qu'il n'y ai pas de maximum au cardinal d'une antichaine, alors l'exemple donné fonctionne tres bien...
le problème est que le problème (justement !) n'est pas bien formulé ! on ne sait pas ce q'on cherche... il faudrait déjà avoir une formulation précise du "théorème" dont on veut montrer qu'il est faux ! là au moins on aurait une idée du type de contrexemple cherché !
mm
"E infini totalement ordonné" >>> partiellement ordoné seulement, sinon toute antichaine est de longeur au plus 1 ^^
"Dans l'énoncé qu'on me fournissait, il était question de longueur maximale..." >>> tout depend de comment on interpréte le "maximal" de l'énoncé : est-ce qu'il est question "d'antichaine maximal" au sens ou elle ne peut pas etre prolongé en une antichaine plus grosse, ou "d'antichaine de cardinal maximal" (chose qui n'existe pas dans {2^m*3^n} ). ce qui ma décidé pour la deuxième interprétation, c'est que le "maximal" qu'on utilise dans l'énoncé du th de Dilworth désigne "de cardinal maximale"...
(oui , lapsus... je voulais évidemment dire "partiellement ordonné !)
bon, attendons donc un énoncé plus précis !
MM
j'objecte, la formulation que j'ai donné est précise. enfin je recommence quand meme :
Conjecture 1 :
Soit E un ensemble Ordoné, alors :
Min card(C) (pour C parcourant l'ensemble des partition de E en chaine) = Sup card(A) pour A parcourant l'ensemble des antichaines.
Rq :un ensemble de cardinaux à toujour un plus petit element, donc c'est bien un Min à gauche et pas un inf... en revanche à droite c'est un Sup comme le montre l'exemple des {2^k*3^m} ou toute antichaines de de cardinal fini, mais le sup des cardinaux vaut card(N) (oui j'ai pas de notation ascii canonique pour les aleph désolé :p )
on à aussi
Conjecture 2 :
Soit E un ensemble ordoné et n un entier, si toute antichaine est de longeur inférieur ou égal à n, alors il existe une partition de E en n chaines.
c'est un cas particulier de la conjecture 1, et c'est ce cas particulier qu'on essai de nier....
derniere remarque : si on suppose E fini, les conjecture 1 et 2 sont toute les deux équivalente au théorème de Dilworth.
Oui Ksilver, je ne parlais pas de ta formulation en parlant d'imprécision, mais de l'auter du topic !
... Comme quoi, j'ai quand même mis le doigt sur un truc... Mais j'avoue que je ne comprends pas vraiment ce que l'on cherche...
Bonjour à tous,
Bon bah la solution de Camélia était correcte:
On prouve:
- que les antichaînes sont toutes finies,
- que leur taille n'est par contre pas bornée, ce qui prouve qu'il n'y a pas de partition finie en chaînes,
Quand à la cohérence de l'énoncé, je vous l'ai retranscris tel quel!!
Merci
Annuler
connectez vous
algèbre en post-bac