Dehornoy - Logique du premier ordre

Thierry Poma
Modifié (June 2024) dans Fondements et Logique
Bonjour tout le monde,
Voici une reproduction extraite de son fameux livre, page 222 :
J'avoue humblement ne rien comprendre en l'affirmation mise en gras : On pourra noter que les clauses pour $\exists\,x_i$ et $\forall\,x_i$ ne sont correctes (sic) que pour $i\leqslant{}p$ [ça, je le comprends !] ; dans le cas $i>p$, il faudrait remplacer $\Psi^{\mathcal{S},\,p}(a_1,\,\cdots,\,a_{i-1},\,x,\,\,a_{i+1},\,\cdots,\,a_p)$ par\[\Psi^{\mathcal{S},\,i}(a_1,\,\cdots,\,a_{i-1},\,\hat{a}_i,\,\,a_{i+1},\,\cdots,\,a_p,\,x,\,\cdots,\,x)\]où seul le dernier $x$ compte. Outre le symbole $\hat{a}_i$ dont je ne trouve pas sa définition dans le livre (mais peut-être ai-je mal lu !), toute cette dernière partie me trouble profondément ; je ne vois pas où Patrick Dehornoy voulait en venir. Je vous remercie pour vos commentaires.
Cordialement,
Thierry
Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).

Réponses

  • Bonjour @Thierry Poma est-ce que tu pourrais me donner un lien pour télécharger le livre (si c'est légal) ? Merci.
    Mathématiques divines
  • Non, je m'y refuse. Je suis désolé. Je possède trois exemplaires dont une première édition. Je suis peut-être disposé à me séparer de cette première édition, gratuitement. Je vais y réfléchir.
    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • En tout cas, je suis intéressé si tu veux te séparer de la première édition. Tient moi au courant s'il te plait.
    Mathématiques divines
  • marco
    Modifié (June 2024)
    Bonjour,
    Sûrement, tu le sais mais $\phi(x_1,x_2,\hat{x_3},x_4)$ signifie $\phi(x_1,x_2,x_4)$ (on enlève $x_3$). Il doit y avoir une coquille, car la notation $\Psi^{S,i}(a_1, \cdots, a_{i-1}, \hat{a_i}, a_{i+1}, \cdots, a_p, x, \cdots,x)$ implique que $i \leq p$. Or, Patrick Dehornoy se place dans le cas $i>p$.
  • Congru
    Modifié (June 2024)
    Je n'avais pas lu la question.
    Je crois que @marco y a bien répondu.
    Sinon, je rajouterais que pour la substitution dans les termes d'une $L$-structure $M$, il suffit de définir une fonction "substitution" par récursion transfinie.
    Pour la substitution dans les formules d'une $L$-structure $M$, il suffit de définir une fonction "substitution" par récursion transfinie.
    Pour la "fonction valeur de vérité", il vaut mieux travailler avec les formules closes de $L_M$ et définir une fonction valeur de vérité par récursion transfinie.
    Edit. Je ne sais pas pourquoi je parlais d'interprétation des termes clos au début. J'ai été influencé par le texte.
    Edit2. Réflexion faite, mon approche est assez différente de celle exposée ici, je définis d'abord la substitution sur les termes, puis l'interprétation des termes clos (ah voilà pourquoi j'en parlais) puis la subsititution sur les formules et enfin la fonction valeur de vérité.

    Mathématiques divines
  • Congru
    Modifié (June 2024)
    Aussi la notation $t(x_1;...;x_n)$ a fait son temps, il est grand temps de l'abandonner pour le couple $(t;(x_1;...;x_n))$
    Mathématiques divines
  • marco
    Modifié (June 2024)
    Supposons $S=\N$.
    Si $\Phi(x_1)$ est $\exists x_2, x_1=x_2+1$.
    Alors la $1$-valeur de $\Phi(x_1)$ doit être la fonction caractéristique de $\{n\in \N ~|~n\geq 1\}$ (donc une fonction de $\N$ dans $\{0,1\}$).
    Donc la $1$-valeur de $\Phi(x_1)$ en $a_1$ est le maximum de $\Psi^{S,2}(a_1,x)$ pour $x\in \N$ avec $\Psi(x_1,x_2)$ qui est $x_1=x_2+1$.

    Donc il faut lire $\Psi^{S,i}(a_1, \cdots, a_p,x, \cdots,x)$   (avec $i-p$ fois la variable $x$, donc le dernier $x$ est au rang $i$, donc seul le dernier $x$ compte) au lieu de la formule $\Psi^{S,i}(a_1, \cdots, a_{i-1}, \hat{a_i}, a_{i+1},\cdots, a_p, x, \cdots,x)$.
  • Congru
    Modifié (June 2024)
    J'ai retrouvé cette définition de la fonction valeur de vérité par moi même, sans l'avoir lu quelque part.
    Ma petite astuce c'est que tu peux remplace "max" par $\bigcup $ et "min" par $\bigcap $ car $2$ est un ordinal fini.
    Cette astuce où tu peux utiliser la notion de "max" quand tu veux et celle de $\bigcup $ quand tu veux m'aide dans les calculs de valeur de vérité car parfois c'est plus arrangeant de travailler sur des intersections et des unions qu'avec des max et min, il faut s'avoir à quel moment utiliser l'un ou l'autre.

    Edit. Je n'aime pas beaucoup les notations de la page exposée ici.
    N.B: $0=\emptyset$ et $1=\{ \emptyset \} $
    Mathématiques divines
  • marco
    Modifié (June 2024)
    J'aurais peut-être dû choisir comme exemple $\Phi(x_1)$ qui est $\exists x_3, x_1=x_3+1$.
    Alors la $1$-valeur de $\Phi(x_1)$ en $a_1$ est le maximum de $\Psi^{S,3}(a_1,x,x)$ pour $x \in \N$, où $\Psi(x_1,x_2,x_3)$ est $x_1=x_3+1$. On voit que le premier $x$ ne compte pas.
  • @marco : bonjour. Je te remercie beaucoup. Ton explication me rassure et m'éclaire. Peut-être vais-je abuser, mais j'ai encore beaucoup de mal avec le point $(i)$ dans la définition de la reproduction ci-dessous, extraite du livre, page 223 ; à moins qu'il ne s'agisse encore d'une coquille :

    Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
  • marco
    Modifié (June 2024)
    Il faut lire $i_1, \cdots, i_n \leq p$ au lieu de $i_1, \cdots, i_p \leq p$. Cela veut dire que $b$ doit être une suite de longueur $p$ d'éléments de $S$ telle que $p$ est supérieur ou égal à $i_1, \cdots, i_n$.
  • marco
    Modifié (June 2024)
    Exemple: Si $\Phi(x_3,x_4)$ est $x_3+x_4=0$ et si $S=\N$.
    (On a donc $i_1=3$, et $i_2=4$)
    $\Phi^S$ est la fonction indicatrice de $(0,0)$ dans $\N^2$.
    En effet, pour tout $p\geq 4=i_2$ (et donc aussi $p \geq 3=i_1$), et toute suite $b_1, \cdots, b_p$ d'éléments de $\N$, $\Phi^{S,p}(b)$ vaut $1$ si $(b_3, b_4)=(0,0)$ et $0$ si $(b_3,b_4) \neq (0,0)$. Donc, cela ne dépend que de la valeur de $b_3$ et $b_4$. On peut donc définir, pour tout $a_1,a_2 \in \N$, $\Phi^S(a)$ qui vaut $1$ si $(a_1,a_2)=(0,0)$ et  $0$ si $(a_1,a_2) \neq (0,0)$ . Ici $a$ est une suite de longueur $2$ qui vaut $(a_1,a_2)$.
    (Message édité)
    On a $\Phi^S(a):=\Phi^{S,p}(b)$ où $a$ est une suite de longueur $2$ et $b$ est une suite de longueur $p$, telle que $b_{i_1}$ c'est-à-dire $b_3=a_1$ et $b_{i_2}$ c'est-à-dire $b_4=a_2$.
    Autrement dit, si $p=5$, $b=(x,y,a_1,a_2,z)$ avec $x,y,z \in S$ quelconque car le résultat ne dépend que de $a_1, a_2$.
Connectez-vous ou Inscrivez-vous pour répondre.