Modèle logique des prédicats

[invite74e0de32]

Bonjour,
Je me permets de vous solliciter à nouveau pour avoir une confirmation à propos d'un exercice sur les modèles en logique des prédicats.

L'énoncé est le suivant :
Soit L = { R² } et ø un énoncé de L : ø = (∀x∃y Rxy ∧ ∀z¬Rzz) Existe t'il des L-structure dont le domaine d'interprétation est fini et qui sont des modèles de ø ? Si oui, donnez un exemple, si non expliquez pourquoi.

Il me semble que oui et je donnerai l'exemple suivante.
L = { R² , a, b, c }
I(R) = { <a, b> ; <b, c> ; <c, a >}

Pensez vous que ma solution est correcte ou je fais fausse route ?

Par ailleurs, il y a une deuxième question qui est :
Soit L = { R² }, ø = (∀x∃y Rxy ∧ ∀z¬Rzz) et ψ = ∀x∀y∀z ((Rxy ∧ Ryz) --> Rxz).
Montrez qu'il existe des modèles de ø qui sont des modèles de ψ.

Pour cette question, je donnerai l'exemple :
L = { R² , a, b, c }
I(R) = { <a, b> ; <b, c> ; <a, c >}

Qu'en pensez vous ? Et (par curiosité) pensez vous qu'il existe des modèles de ø qui ne sont pas des modèles de ψ ?

Merci d'avance !
-----

[Médiat]

L'énoncé est le suivant :
Soit L = { R² } et ø un énoncé de L : ø = (∀x∃y Rxy ∧ ∀z¬Rzz) Existe t'il des L-structure dont le domaine d'interprétation est fini et qui sont des modèles de ø ? Si oui, donnez un exemple, si non expliquez pourquoi.

Il me semble que oui et je donnerai l'exemple suivante.
L = { R² , a, b, c }
I(R) = { <a, b> ; <b, c> ; <c, a >}

Pensez vous que ma solution est correcte ou je fais fausse route ?

Correct

Par ailleurs, il y a une deuxième question qui est :
Soit L = { R² }, ø = (∀x∃y Rxy ∧ ∀z¬Rzz) et ψ = ∀x∀y∀z ((Rxy ∧ Ryz) --> Rxz).
Montrez qu'il existe des modèles de ø qui sont des modèles de ψ.

Pour cette question, je donnerai l'exemple :
L = { R² , a, b, c }
I(R) = { <a, b> ; <b, c> ; <a, c >}

Non, car il faut que Rcy pour un y

[invite74e0de32]

Super merci !

Ah oui, je n'avais pas fait attention...
L = { R² , a, b, c }
I(R) = { <a, b> ; <b, c> ; <a, c > ; <c, b>}
Cette fois ça doit être mieux je pense, non ?

[Médiat]

Non car vous avez Rbc et Rcb mais pas Rbb (ni Rcc)

[A voir en vidéo sur Futura]

[invite74e0de32]

Mais il me semble que je ne peux pas mettre Rbb et Rcc à cause de ∀z¬Rzz dans ø = (∀x∃y Rxy ∧ ∀z¬Rzz)...

[Médiat]

Donc il faut trouver autre chose ou démontrer que c'est impossible

[invite74e0de32]

J'ai l'impression qu'il n'est pas possible de fournir un modèle fini car à chaque fois que je rajoute un élément, celui-ci doit être en relation avec un autre... et si je le mets en relation avec un élément déjà présent, je transgresse ∀z¬Rzz.
Mais est-il possible de fournir un modèle infini ? Et si oui, comment le note t'on ? je n'ai jamais appris ça...

[Médiat]

J'ai l'impression qu'il n'est pas possible de fournir un modèle fini car à chaque fois que je rajoute un élément, celui-ci doit être en relation avec un autre... et si je le mets en relation avec un élément déjà présent, je transgresse ∀z¬Rzz.

, c'est exactement cela

Mais est-il possible de fournir un modèle infini ? Et si oui, comment le note t'on ? je n'ai jamais appris ça...

Oui, un modèle très simple : (IN, <)

∀x∃y Rxy : Pas de plus grand élément dans IN pour l'ordre strict usuel
∀z¬Rzz : l'ordre strict usuel n'est pas réflexif
∀x∀y∀z ((Rxy ∧ Ryz) --> Rxz) : l'ordre strict usuel est transitif

[invite74e0de32]

Cela me parait tellement évident maintenant que vous l'avez dit... merci beaucoup !

[Médiat]

Pas de quoi cher HowardDur (private joke pour les logiciens)

[invite74e0de32]

Haha pas mal
Et juste pour pousser la curiosité jusqu'au bout... Existe t'il une (ou des) relation d'ordre qui ne sont pas transitives ?

[gg0]

Bonjour.

La transitivité fait partie de la définition de "relation d'ordre". Mais on parle aussi "d'ordre strict" pour <.

Cordialement.

[invite74e0de32]

Bonjour,
Merci pour votre réponse. Je ne savais pas.

Toutefois j'aimerai savoir par curiosité c'est s'il existe des modèles de ø qui ne sont pas des modèles de ψ.
Sachant que ma structure est la suivante :
Soit L = { R² }, ø = (∀x∃y Rxy ∧ ∀z¬Rzz) et ψ = ∀x∀y∀z ((Rxy ∧ Ryz) --> Rxz).

Cordialement

[Médiat]

Facile ça :
I(R) = { <a, b> ; <b, a> }