Quelle est la relation entre la logique du premier ordre et la théorie du premier ordre?

Je pensais que tout FOT est un sous-ensemble de FOL, mais cela ne semble pas être le cas, car FOL est complet (chaque formule est soit valide soit invalide), tandis que certains FOT (comme l'arithmétique d'entier linéaire) ne sont pas complets.

Alors, FOL est-il plus expressif que n'importe quel FOT? Ou incomparable?

En outre, la déclaration "il existe des déclarations qui sont valides dans LIA mais ne peuvent pas être prouvées en utilisant des axiomes de LIA" est bizarre. Comment la déclaration peut-elle être valable si nous ne pouvons pas prouver sa validité? J'ai toujours pensé que si vous ne pouvez pas prouver la validité de la déclaration, vous ne pouvez pas prétendre qu'elle est valide.

logic first-order-logic Ayrat
la source

Je pense que la déclaration "il y a des déclarations qui sont valables en LIA mais ne peuvent pas être prouvées en utilisant des axiomes de LIA" est fausse. Le théorème d'exhaustivité de godel garantit qu'une déclaration valide peut éventuellement être prouvée dans un laps de temps fini. Je pense que vous confondez la validité logique avec la vérité logique. Ce sont deux choses différentes. Le sens d'exhaustivité utilisé dans le théorème d'exhaustivité de godel et celui utilisé dans le théorème d'incomplétude n'est pas le même.

rotia

Réponses:

La logique du premier ordre est un sujet mathématique qui définit de nombreux concepts différents, tels que la formule du premier ordre , la structure de premier ordre , la théorie du premier ordre , et bien d' autres. L'un de ces concepts est la théorie du premier ordre : c'est un ensemble de formules du premier ordre. Nous considérons souvent la théorie du premier ordre générée par un nombre fini d'axiomes et de schémas d'axiomes. Une telle théorie est fermée en ce qui concerne les dérivations logiques , et nous ne considérons généralement que les théories satisfaisant à cette condition.

Une théorie du premier ordre est complète si pour chaque instruction , elle contient soit soit sa négation. Toutes les théories ne sont pas complètes. En effet, le théorème d'incomplétude de Gödel met en évidence le fait que de nombreuses théories intéressantes du premier ordre sont nécessairement incomplètes. $\sigma$ $\sigma$

Un modèle de théorie du premier ordre est une interprétation valide de la théorie (nous laissons la définition exacte des manuels). Par exemple, la théorie du premier ordre des groupes comprend toutes les déclarations qui découlent des axiomes de groupe. Chaque groupe est un modèle de la théorie du premier ordre des groupes.

Pour chaque modèle donné, une phrase très donnée est vraie ou fausse. Le théorème de complétude de Gödel déclare que si une phrase du premier ordre est vraie dans tous les modèles d'une théorie du premier ordre, alors elle peut être prouvée à partir d'un nombre fini de phrases dans la théorie. Par exemple, chaque énoncé de premier ordre dans le langage des groupes qui vaut pour tous les groupes est prouvable à partir des axiomes de groupe.

LIA est (vraisemblablement) une théorie du premier ordre qui est suffisamment intéressante pour être incomplète en raison du théorème d'incomplétude de Gödel. Cependant, dans le modèle standard - les "vrais" entiers - chaque phrase est soit vraie soit fausse. En particulier, si est une déclaration telle que ni ni n'appartiennent à LIA, alors ou est valable pour les vrais entiers, mais ce fait n'est pas prouvable dans LIA. $\sigma$ $\sigma$ $\lnot \sigma$ $\sigma$ $\lnot \sigma$

Yuval Filmus
la source

Quelle est la particularité des théories «complètes»? pourquoi sont-ils intéressants? «bien sûr», de nombreuses théories sont incomplètes, car le défaut d'exhaustivité demande si une phrase est vraie pour tous les modèles. Sur l'incomplétude: dans le "modèle des entiers standard", nous ne nous soucions pas de tous les modèles qui satisfont les axiomes, nous n'en avons qu'un, "modèle des entiers standard". Le théorème d'incomplétude n'indique-t-il pas que la façon dont nous définissons la validité (en particulier notre examen de tous les modèles qui satisfont les axiomes) n'est pas appropriée?

Ayrat

Les théories complètes sont spéciales car elles donnent une valeur de vérité définie pour chaque déclaration. C'est quelque chose que vous aimeriez avoir. Le reste de vos questions appartient au domaine de la philosophie. Cela dit, le théorème de complétude de Gödel assimile la validité dans tous les modèles à la prouvabilité.

Yuval Filmus

ne voyez toujours pas l'utilité - considérez FOL, qui est complet: supposons que vous vouliez vérifier si F est valide ou non: 'exhaustivité' n'aide pas beaucoup si F n'est pas valide, car la validité de FOL est semi-décidable. Dois-je manquer quelque chose?

Ayrat

L'énoncé «la logique du premier ordre est terminée» est dénué de sens ou faux.

Yuval Filmus

Il n'est pas vrai qu'une théorie du premier ordre soit un ensemble cohérent de phrases du premier ordre. La bonne chose à dire est: une théorie du premier ordre est un ensemble de formules du premier ordre qui est fermé sous déduction. Je peux parfaitement formuler une théorie incohérente. Il faudra peut-être des années avant de découvrir qu'il est incohérent. Et une théorie peut contenir des formules, pas seulement des phrases (qui sont des formules fermées).

Andrej Bauer

L'expression "logique du premier ordre" a deux significations:

C'est un chapitre de la logique mathématique dans lequel nous étudions certains types de systèmes formels et tout ce qui s'y rapporte.
Il s'agit d'un type particulier de théorie du premier ordre, à savoir celle générée par une signature vide et un ensemble vide d'axiomes.

Votre question se réfère au deuxième sens, mais pour comprendre cela, nous devons construire les choses:

Il existe un certain langage formel appelé langage de la logique du premier ordre . Parlant de manière informelle, c'est ce que vous pouvez construire à partir de variables, d'égalité, , , , , et . Ce truc est connu sous le nom de formules de premier ordre . $\land$ $\lor$ $\lnot$ $\Rightarrow$ $\forall$ $\exists$
Il existe un certain système formel appelé logique du premier ordre qui nous dit ce que cela signifie que nous prouvons une formule du premier ordre. Le système est donné comme un ensemble de règles d'inférence.
Une théorie du premier ordre $\mathcal{T}$ est donnée par:
- une signature $\Sigma_{\mathcal{T}}$ qui consiste en un ensemble de constantes, symboles de fonction et symboles de relation. Considérez-les comme des extensions du langage de base de la logique du premier ordre. Nous l'appelons le langage de $\mathcal{T}$ .
- un ensemble déductivement fermé de formules de premier ordre écrites dans la langue étendue par la signature.

Un ensemble de formules est dit être fermé par déduction le cas échéant l' application de règles d'inférence de la logique du premier ordre à des formules dans donne les formules qui sont à nouveau dans . En d'autres termes, contient toutes ses conséquences logiques. Une façon courante de créer un tel ensemble est de commencer par un ensemble choisi de formules et d'y ajouter toutes ses conséquences logiques et les conséquences de ces conséquences, etc. On appelle cela la fermeture déductive de . Nous appelons souvent les formules axiomes . $S$ $S$ $S$ $S$ $S$ $A$ $A$ $A$

Une théorie peut être complète ou non. Il n'est pas important de savoir ce que signifie "complet" ici, mais il est important de savoir que ce qui suit peut se produire: nous pouvons avoir deux ensembles de formules et , telles que , la fermeture déductive de est un théorie complète, et la fermeture déductive de n'est pas une théorie complète. $A$ $B$ $A \subseteq B$ $A$ $B$

Nous sommes maintenant prêts à répondre à votre question. Soit la théorie dont la signature est vide et dont l'ensemble de formules est la fermeture déductive de l'ensemble vide. Soit la théorie dont la signature est celle de l'arithmétique de Peano (constante , opération unaire , opérations binaires et ) et les formules sont la fermeture déductive des axiomes de Peano. C'est un fait que $T$ $P$ $0$ $S$ $+$ $\times$

$T$ est contenu dans (en fait est contenu dans toute théorie), $P$ $T$
$T$ est complet,
$P$ n'est pas complet.

La théorie est communément appelée "logique du premier ordre", mais il s'agit vraiment d'un terme impropre. Certaines personnes sont un peu plus précises et l'appellent "la théorie pure de la logique du premier ordre". $T$

En résumé, votre question a révélé ce qui suit:

Vous ne saviez pas que la "logique du premier ordre" peut faire référence à la théorie avec une signature vide générée par les axiomes vides.
Une théorie complète peut devenir incomplète lorsque nous l'étendons.
Vous avez utilisé la mauvaise définition de l'exhaustivité. La définition correcte est: une théorie est complète si, chaque phrase ou sa négation est un théorème de la théorie.

NB: une phrase est une formule fermée (celle qui ne contient aucune variable libre).

Enfin, permettez-moi de répondre à votre question sur la validité:

une formule est prouvable s'il y en a une preuve
une formule est valide si elle est vraie dans tous les modèles

Un méta-théorème de base sur la logique du premier ordre est que chaque formule prouvable est valide. L'inverse est également valable et est connu sous le nom de théorème de complétude de Gödel .

Cependant, il arrive souvent que dans une situation particulière, on fasse exprès un décalage entre la validité et la prouvabilité pour une bonne raison. Par exemple, si nous limitons l'attention aux modèles finis , il peut facilement arriver qu'il y ait des déclarations valides sans preuve. Pourquoi ferait-on ça? En informatique, cela peut être pour des raisons algorithmiques ou parce que l'on s'intéresse uniquement à une classe particulière de modèles.

Vous dites que "la seule façon de savoir qu'une peine est valable est de la prouver". Cela peut être le cas à un certain niveau informel (je pense que Dieu ne serait pas d'accord avec vous), mais notez qu'une telle preuve de validité se produit en dehors de la théorie, au niveau méta. En effet, puisque l'établissement de la validité nécessite de parler de tous les modèles, ce n'est certainement pas quelque chose que nous nous attendrions à effectuer à l'intérieur de la théorie.

Andrej Bauer
la source

Vous semblez vous être mêlé au théorème d'exhaustivité de Godel et aux théorèmes d'incomplétude de Godel. Ce que vous appelez le "théorème d'incomplétude de Godel" semble être une négation directe du théorème d'exhaustivité de Godel. Le premier théorème d'incomplétude de Godel concerne les phrases qui ne peuvent être ni prouvées ni réfutées, pas les phrases qui sont valides mais non prouvables.

user2357112 prend en charge Monica

Merci, je viens de supprimer ce bit car il n'ajoute rien à l'explication.

Andrej Bauer

@AndrejBauer pourriez-vous clarifier le «paradoxe» suivant avec «1. est contenu dans »? : Puisque est incomplète alors il existe tel que et . Maintenant, demandez " "? Puisque (fermetures déductives de leurs axiomes), alors il devrait y avoir soit soit , mais tous deux violent l'hypothèse d'existence de tels !

T

$T$

P

$P$

P

$P$

s

$s$

s \notin P

$s \not\in P$

\neg s \notin P

$\neg s \not\in P$

s \in T

$s \in T$

T \subset P

$T \subset P$

s \in T

$s \in T$

\neg s \in T

$\neg s \in T$

s

$s$

Ayrat

une autre question: avez-vous un exemple de déclaration valide qui n'a pas de preuve?

Ayrat

Une petite précision:

Vous pensez peut-être que la théorie avec une signature vide est une théorie vide, c'est-à-dire qu'elle ne contient pas de formules fermées. C'est incorrect. La logique du premier ordre permet de prouver - sans recours aux axiomes - certaines formules fermées appelées tautologies. Ceux-ci sont «vrais» en raison uniquement de leur forme; ils n'ont pas de contenu significatif en tant que tel. Le théorème d'exhaustivité de Godel dit ensuite que la collection de tautologies est complète - c'est-à-dire que toutes les formules fermées qui sont valides (c'est-à-dire «vraies dans tous les modèles») sont en fait dérivables dans la logique du premier ordre. [La preuve est intéressante et résolument non triviale.]

PMar
la source