Théories arithmétiques

[Tiky]

Bonjour,

En m'intéressant aux théories arithmétiques, j'ai plusieurs questions ou pour certaines simplement des doutes.
Dans la suite on peut considérer que mes questions ne concernent que l'arithmétique de Peano si c'est plus simple.

1. J'ai pu lire de temps à autre qu'on parle d'entier standard dans un modèle quelconque de AP. Pour moi un entier standard était un élément
du modèle standard . Je pense donc qu'un entier standard dans un certain modèle M de est l'interprétation d'un
terme de la forme (ou s est la fonction successeur) dans ce modèle ?
Je note pour tout entier n, .

2. Est-il vrai que si une formule vérifie pour un certain entier n, ,
Alors ?

3. Juste pour être sûr, une définition correcte de -incohérence dans une théorie
de l'arithmétique T serait qu'il existe une formule telle que :
- pour tout entier n,
-

PS : désolé pour les symboles Latex. Je ne connais pas d'alternatives à \models et \lnot qui fonctionnent sur ce forum :/
-----

[Médiat]

Bonjour

En m'intéressant aux théories arithmétiques, j'ai plusieurs questions ou pour certaines simplement des doutes.
Dans la suite on peut considérer que mes questions ne concernent que l'arithmétique de Peano si c'est plus simple.

1. J'ai pu lire de temps à autre qu'on parle d'entier standard dans un modèle quelconque de AP. Pour moi un entier standard était un élément
du modèle standard . Je pense donc qu'un entier standard dans un certain modèle M de est l'interprétation d'un
terme de la forme (ou s est la fonction successeur) dans ce modèle ?

Exact. Je vous rappelle que est le modèle premier de AP, il est donc normal de le trouver dans tous les modèles.

Je note pour tout entier n, .

2. Est-il vrai que si une formule vérifie pour un certain entier n, ,
Alors ?

Oui, puisque est une constante définissable.

3. Juste pour être sûr, une définition correcte de -incohérence dans une théorie
de l'arithmétique T serait qu'il existe une formule telle que :
- pour tout entier n,
-

Oui.
Seriez-vous en train de lire la démonstration originale du théorème d'incomplétude de Gödel ?

PS : pour \models, je vous ai mis un workaround, pour \lnot, vous devriez utiliser \neg

[Tiky]

Merci pour votre aide.

Oui j'ai lu une partie de la thèse de Gödel il y a quelques temps.

Qu'entendez-vous par constante définissable ? je ne connais pas cette notion.

Concernant l'-cohérence, je suis pratiquement sûr qu'il y a une erreur sur Wikipédia dans le dernier paragraphe de la page suivante :
http://fr.wikipedia.org/wiki/Raisonn...%C3%A9currence

Pour moi T est -cohérente si pour toute formule de T telle que : pour tout entier n,
On a alors
Bref c'est tout simplement la négation de l'-incohérence.

Pour finir j'ai lu que l'-cohérence implique la cohérence (au sens usuel). La démonstration me semble évidente :
Soit T une théorie arithmétique -cohérente et une formule de T. Soit une variable n'ayant aucune occurrence libre dans .
Si je suppose que . Alors on a évident pour tout entier n, .
Donc par -cohérence, on n'a que (on suppose que y n'a aucune occurrence libre dans ).
Or . D'où .

[Médiat]

Bonjour,

Je n'ai pas beaucoup de temps aujourd'hui, je vais essayer de répondre par petits bouts, sinon je finaliserai pendant le week-end.

Qu'entendez-vous par constante définissable ? je ne connais pas cette notion.

C'est une notion très simple, qui correspond à un élément dans chaque modèle qui soit le seul à vérifier une formule donnée (autrement dit on pourrait ajouter un symbole de constante dans le langage, et la formule comme axiome, sans changer la théorie (dans le sens où on aurait les mêmes théorèmes).

L'exemple simple est bien sûr , puisque , est le seul élément (dans chaque modèle) qui vérifie la formule : , avec application de .

Néanmoins, il faut faire attention avec cette formule, car elle ne marche que pour un seul , par exemple la formule pour définir n'est pas la même que la formule pour définir .

Pour comprendre cette notion, je vais donner un exemple basique, afin que tous les lecteurs y trouvent l'information :
dans AP, 0 est une constante du langage, mais pas 1, par contre je peux définir , bien sur on peut aussi définir , et pour chaque on peut définir une nouvelle constante , par contre on ne peut pas écrire une formule qui soit vérifiée par tous les entiers standard et uniquement par les entiers standard.

[A voir en vidéo sur Futura]

[Tiky]

Ok, je connais la notion d'ensemble définissable dans un modèle mais je ne faisais pas le lien. Donc en fait une constante définissable n'est ni plus ni moins la même chose
qu'un ensemble (à un élément) définissable dans le langage de la théorie en question.

[Médiat]

Concernant l'-cohérence, je suis pratiquement sûr qu'il y a une erreur sur Wikipédia dans le dernier paragraphe de la page suivante :
http://fr.wikipedia.org/wiki/Raisonn...C3%A9currence.

Je suppose que la phrase qui vous gène est :

Ainsi, il ne suffit pas de démontrer que pour tout n, P(n) [soit P(0), P(1), P(2), ... ] pour démontrer ∀n P(n), comme arrive à le faire le principe de récurrence

Je l'aurais effectivement, plutôt écrite
Ainsi, il ne suffit pas, pour tout n, de démontrer , P(n) [soit P(0), P(1), P(2), ... ] pour démontrer ∀x P(x), comme arrive à le faire le principe de récurrence.

[Tiky]

Non non il s'agit de la phrase suivante (à la fin de la page) :
Une théorie dans laquelle pour tout prédicat P,
Pour tout n, implique
est dite ω-cohérente...

[Médiat]

Je suis d'accord avec vous, je viens de relire le texte de Gödel et la définition de -consistance (et non cohérence, mais c'est pareil) est bien celle que vous donnez et non celle de wikipedia.

[Tiky]

Ok . J'aurais d'autres questions sans doute par la suite mais après demain j'aurai mon premier cours de logique, je pourrais harceler un autre logicien donc ^^.
Merci pour ton aide.

[Médiat]

après demain j'aurai mon premier cours de logique

La porte du paradis va s'ouvrir

[inviteea028771]

La porte du paradis va s'ouvrir

Et, alors que tu étais au paradis, tu va te retrouver au purgatoire en la franchissant

(ceci est une pique gratuite et totalement non fondée )