Axiomes des ordres denses

[nash06]

Bonjour à tous, j'ai un exercice à faire dans lequel je dois axiomatiser la classe des ordres denses avec premier et dernier élément (en logique du premier ordre), avec un langage réduit à {<}

La définition que l'énoncé donne d'un ordre est "un ordre dense est un ensemble, avec au moins deux éléments, muni d'un ordre strict tel que pour toute paire d'éléments distincts il existe un élément se trouvant strictement entre ces deux éléments".

Alors donc j'ai écrit les deux axiomes des ordres stricts, une formule pour la densité de l'ordre et une pour l'existence d'un plus petit et une autre pour l'existence d'un plus grand élément. Il me reste donc à écrire une formule pour impliquer l'existence d'au moins 2 éléments, mais je n'y arrive pas.

En effet, j'ai d'abord pensé à un truc du genre "Il existe x il existe y (x<y ou y<x)" mais cette formule impose que l'ordre considéré ne soit pas vide. Par exemple, l'ensemble {a,b} muni d'une relation < vide (a n'est pas en relation avec b ni b avec a) me semble être un modèle des ordres denses mais ne vérifierait pas la formule précédente.

Bref, je sèche... mais je finis même par me demander si c'est possible de trouver une formule qui impose l'existence de deux éléments distincts.

Voilà voilà, si quelqu'un sait faire ça, ce serait sympa de m'aider.
-----

[nash06]

Re-bonjour, j'espère qu'on ne m'en voudra pas trop pour ce deuxième post, je n'ai pas trouvé la fonction Edit (s'il y en a une)).

En fait, l'existence d'un premier et d'un dernier élément, je n'y arrive pas non plus.
J'avais mis :
Il existe x Pour tout y non y<x (pour le dernier élément) mais ça il me semble que ce n'est vrai que si l'ordre est total. Or, si un élément a n'est pas en relation avec x, ni dans un sens ni dans l'autre il vérifie bien cette formule. Pourtant dans l'idée du dernier élément il y a l'idée que tout élément autre que ce dernier est strictement inférieur à ce dernier élément.


Sauf que comme le langage ne contient pas l'égalité, je ne peux pas écrire simplement :
Il existe un x Pour tout y (x=y ou y<x).

Bon, sinon, j'ai résolu ma question initiale en fait, puisque l'existence d'un premier et d'un dernier élément fait que la formule que je proposais est correcte (et donc le "modèle" pathologique que je proposais n'en est pas un).

Mais donc reste le problème des premier et dernier éléments... si quelqu'un a une idée, ça m'aiderait

[nash06]

Bon, sinon, j'ai résolu ma question initiale en fait, puisque l'existence d'un premier et d'un dernier élément fait que la formule que je proposais est correcte (et donc le "modèle" pathologique que je proposais n'en est pas un).

En fait, les formules que j'ai mises ne montrent l'existence d'un premier et d'un dernier élément que si il y a effectivement au moins 2 éléments et que l'ordre est total. (Je me sens nul ce soir à changer d'avis aussi souvent.)



Donc pour résumer, j'ai toujours ces deux problèmes :

Comment imposer qu'il y ait au moins deux éléments ?
Comment imposer l'existence d'un premier élément (ou d'un dernier, mais ça doit être similaire) ?

Voilà, j'espère que ce troisième post à la suite était mon dernier

[taladris]

Alors donc j'ai écrit les deux axiomes des ordres stricts, une formule pour la densité de l'ordre et une pour l'existence d'un plus petit et une autre pour l'existence d'un plus grand élément. Il me reste donc à écrire une formule pour impliquer l'existence d'au moins 2 éléments, mais je n'y arrive pas.

Quelle est ta definition de plus grand element? D'apres Wikipedia, un plus grand element est comparable a tous les autres elements et leur est superieur. Contrairement a element maximal qui est un element qui est plus grand que tous les elements qui lui sont comparables. C'est cette definition qu'on utilise pour les treillis par exemple, mais j'imagine qu'elle peut varier.

Avec la definition de Wikipedia, un ensemble E strictement ordonne avec plus grand element M et plus petit element m, m et M sont toujours comparables s'ils sont distincts (s'ils sont egaux, E n'a qu'un seul element) et m<M. Donc tu peux rajouter l'axiome .

Cordialement

PS: on ne peut editer ses messages sur le forum que pendant quelques minutes (3?). Les doubles ou triples posts, s'ils apportent du contenu, sont acceptes.

[A voir en vidéo sur Futura]

[Médiat]

Alors donc j'ai écrit les deux axiomes des ordres stricts, une formule pour la densité de l'ordre et une pour l'existence d'un plus petit et une autre pour l'existence d'un plus grand élément. Il me reste donc à écrire une formule pour impliquer l'existence d'au moins 2 éléments, mais je n'y arrive pas.

Bonjour,

Pouvez-vous nous écrire (en Latex, c'est beaucoup mieux) tous vos axiomes ...

Pour compléter la réponse de taladris, les axiomes :



Permettent de garantir l'existence d'au moins deux éléments.

[nash06]

Bonjour,
Merci pour vos réponses. Effectivement, le problème de l'existence d'au moins deux éléments est réglé.

Voilà donc les axiomes que j'ai : (désolé je ne sis pas comment utiliser le lateX et encore moins où le trouver sur ce forum)

Pour tout x Pour tout y Pour tout z (x < y et y < z) -> x < z
Pour tout x Non(x<x)
Il existe x Il existe y (x<y)
Pour tout x Pour tout y (x<y) -> Il existe z (x<z Et z<y)

Voilà, donc il me manque des axiomes pour dire qu'il y a un premier et un dernier élément. (D'ailleurs, l'énoncé parle de "premier" et "dernier" éléments, pas de "plus grand" élément ou d'élément "maximum", je ne sais pas trop à quoi ça correspond)

Voilà voilà, encore désolé pour ma non-utilisaiton du lateX (oui j'ai très honte^^).

[Médiat]

Bonjour,

Utiliser Latex est très facile, il existe des milliers de tutos sur le Net, mais il suffit de regarder un message qui contient du latex (en appuyant sur "Répondre avec citation").

Exemple :








Premier et Dernier correspondent à Plus Grand et Plus Petit

[taladris]

Question annexe: le langage ne contient pas d'egalite. En utilisant les axiomes d'ordre dense de Mediat, est-il possible de definir "="?

[Médiat]

Question annexe: le langage ne contient pas d'egalite. En utilisant les axiomes d'ordre dense de Mediat, est-il possible de definir "="?

C'est la bonne question, mais les axiomes sont ceux de nash06, je n'ai fait que les traduire en Latex

[invite179e6258]

Question annexe: le langage ne contient pas d'egalite. En utilisant les axiomes d'ordre dense de Mediat, est-il possible de definir "="?

est-ce que cette définition ferait l'affaire? deux éléments x et y sont égaux ssi il n'existe pas d'élément z tel que x<z et z<y ni d'élément z tel que y<z et z<x

[Médiat]

Bonjour,

Cela marche à condition d'avoir l'axiome qui dit que l'ordre est total (qui s'écrit usuellement avec l'égalité), sinon un modèle en Y vérifie bien les axiomes ci-dessus, mais votre axiome ne définit pas l'égalité.

Avec l'axiome de totalité, il suffit d'écrire :

[taladris]

C'est la bonne question, mais les axiomes sont ceux de nash06, je n'ai fait que les traduire en Latex

J'avais saute un message. Toutes mes excuses a Nash06.

Bonjour,

Cela marche à condition d'avoir l'axiome qui dit que l'ordre est total (qui s'écrit usuellement avec l'égalité),

Par consequent, on a l'equivalence "definition de l'egalite" "ordre total"?

[Médiat]

Bonjour,

Soit .

En notant et , on définit :

Il est facile de démontrer que cette relation vérifie les 4 axiomes déjà vus ci-dessus.
Soit :
, sauf erreur de calcul, avec votre définition de l'égalité, on obtient
, autrement dit votre égalité n'est pas transitive ...

[nash06]

Bonjour à tous et encore merci pour vos réponses.

Alors en fait, c'était juste un oubli de l'enseignant qui avait oublié de préciser que le langage était supposé égalitaire... du coup, ça règle complètement le problème.

Après évidemment, ça reste très intéressant d'essayer de voir si sans égalité on peut axiomatiser les ordres denses d'au moins 2 éléments avec premier et dernier élément, mais bon, de mon côté, je vais arrêter d'y réfléchir.

Bonne journée à tous !

[Médiat]

Bonjour,

D'un côté cela me rassure car je ne vois pas comment se passer de l'égalité, si quelqu'un a une idée, cela m'intéresse.

Sinon cette théorie est intéressante car on peut démontrer assez facilement qu'elle est -catégorique, donc complète, mais non -catégorique.

[nash06]

Sinon cette théorie est intéressante car on peut démontrer assez facilement qu'elle est -catégorique,

Etes-vous sûr ?
Il me semble que si on considère par exemple les modèles suivants :

*M: Les rationnels compris entre -1 et 2, avec l'ordre usuel
*N: Les rationnels compris entre -1 et 2, avec un ordre défini par : x<y si |x|<|y|

ils vérifient tous les deux la théorie (l'ordre est strict, dense, il y a un premier et un dernier élément dans chaque cas) mais qu'on ne peut pas faire d'isomorphisme de M sur N.
(En particulier l'image réciproque de -1 sera nécessairement strictement inférieure ou strictement supérieure à l'image réciproque de 1 alors que dans N 1 et -1 ne sont pas en relation)

[Médiat]

*N: Les rationnels compris entre -1 et 2, avec un ordre défini par : x<y si |x|<|y|

Ne vouliez-vous pas un ordre total ?

En relisant le fil, je m'aperçois que la totalité n'est apparu dans les échanges que "par hasard", la théorie dont je parlais dans mon post précédent est la théorie des ordres totaux, denses, avec premier et dernier élément.

[invitee65b1c3d]

Alors en fait, c'était juste un oubli de l'enseignant qui avait oublié de préciser que le langage était supposé égalitaire... du coup, ça règle complètement le problème.

En théorie des modèles, il est fréquent de considérer le "=" comme un symbole logique disponible en plus des symboles du langage. Cela permet de toujours imposer que = soit interprété par la vraie égalité.
Tout est en fait question de définition : comment ont été définies les formules ?

[invitee65b1c3d]

La définition que l'énoncé donne d'un ordre est "un ordre dense est un ensemble, avec au moins deux éléments, muni d'un ordre strict tel que pour toute paire d'éléments distincts il existe un élément se trouvant strictement entre ces deux éléments".

Cette définition impose que l'ordre est total, car elle impose que deux éléments distincts quelconques sont comparables.

Pour tout x Pour tout y (x<y) -> Il existe z (x<z Et z<y)

Cet axiome dit pour toute paire d'éléments distincts ET COMPARABLES il existe un élément se trouvant strictement entre ces deux éléments. Il ne correspond pas à lénoncé.

[Médiat]

En théorie des modèles, il est fréquent de considérer le "=" comme un symbole logique disponible en plus des symboles du langage. Cela permet de toujours imposer que = soit interprété par la vraie égalité.

Ce n'est pas obligatoire, la manière la plus saine car la moins ambigu est de préciser que le langage est égalitaire, ce qui signifie, non seulement que = fait partie du langage mais qu'on dispose des axiomes qui vont bien. D'ailleurs on peut très bien développer une théorie des modèles sans = cf. Oki Neswan par exemple

[invitee65b1c3d]

Je vous concède aisément que fréquent et obligatoire sont deux adjectifs dont les sens sont différents.

Pour les modèles égalitaire, disposer des "axiomes qui vont bien" est insuffisant. Au premier ordre, il est impossible de distinguer par des axiomes l'égalité d'une relation d'équivalence compatible avec tous les symboles du langage.
Quand on fait de la théorie des modèles égalitaire, on suppose de plus que le symbole "=" est interprété par la vraie égalité.

En particulier, si on se pose des questions sur la cardinalité des modèles, ça change tout : sans imposer que "=" est interprétée par l'égalité, la seule contrainte qu'on peut mettre sur le cardinal, c'est qu'il vaut au minimum une certaine valeur. Dans les modèles égalitaire, on peut avoir des théories dont tous les modèles finis sont de cardinalité paire par exemple, ou dont tous les modèles ont un cardinal non-premier, etc.

Ce sont finalement deux mondes très différents. On peut passer de l'un à l'autre en quotientant un modèle non-égalitaire par la relation d'équivalence par laquelle le symbole "=" est interprété.

[Médiat]

Quand on fait de la théorie des modèles égalitaire, on suppose de plus que le symbole "=" est interprété par la vraie égalité.

On peut passer de l'un à l'autre en quotientant un modèle non-égalitaire par la relation d'équivalence par laquelle le symbole "=" est interprété.

C'est là où je voulais en venir ; par contre je n'arrive plus à me souvenir du nom des modèles où = est la "vraie" égalité.