Categorical theoryIn mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism). Such a theory can be viewed as defining its model, uniquely characterizing the model's structure. In first-order logic, only theories with a finite model can be categorical. Higher-order logic contains categorical theories with an infinite model. For example, the second-order Peano axioms are categorical, having a unique model whose domain is the set of natural numbers In model theory, the notion of a categorical theory is refined with respect to cardinality.
Élimination des quantificateursEn logique mathématique, ou plus précisément en théorie des modèles, l'élimination des quantificateurs est l'action consistant à trouver une formule sans quantificateur équivalente à une formule donnée contenant éventuellement des quantificateurs dans la théorie considérée d'un certain langage.
Arithmétique de RobinsonL'arithmétique de Robinson introduite en 1950 par Raphael Robinson est une théorie du premier ordre pour l'arithmétique des entiers naturels, qui est finiment axiomatisable. Ses axiomes sont essentiellement ceux de l'arithmétique de Peano sans le schéma d'axiomes de récurrence. L'arithmétique de Robinson suffit pour le théorème d'incomplétude de Gödel-Rosser et pour le théorème de Church (indécidabilité du problème de la décision), au sens où l'arithmétique de Robinson, et même toute théorie axiomatique dans le langage de l'arithmétique qui est récursive et cohérente et qui a pour conséquence les axiomes de l'arithmétique de Robinson, est nécessairement incomplète et indécidable.
Sémantique de KripkeEn logique mathématique, la sémantique de Kripke est une sémantique formelle utilisée pour les logiques non-classiques comme la logique intuitionniste et certaines logiques modales. Elle a été développée à la fin des années 1950 et début des années 1960 par Saul Kripke et est fondée sur la théorie des mondes possibles. Un cadre de Kripke est un couple (W, R), où W est un ensemble de mondes appelés parfois mondes possibles et où R est une relation binaire sur W. L'ensemble W s'appelle parfois l'univers des mondes possibles.
DécidabilitéEn logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L’indécidabilité est la négation de la décidabilité. Dans les deux cas, il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique. Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie.
Théorie axiomatiqueQuand on parle de théorie mathématique, on fait référence à une somme d'énoncés, de définitions, de méthodes de preuve, etc. La théorie de la calculabilité en est un exemple. Par théorie axiomatique, on fait référence à quelque chose de plus précis, des axiomes et leurs conséquences, les théorèmes, énoncés dans un langage précis. Dans la suite on dira le plus souvent théorie pour théorie axiomatique, ce qui est d'usage courant en logique mathématique.
Corps réel closEn mathématiques, un corps réel clos est un corps totalement ordonnable dont aucune extension algébrique propre n'est totalement ordonnable. Les corps suivants sont réels clos : le corps des réels, le sous-corps des réels algébriques, le corps des réels calculables (au sens de Turing), le corps des , le corps des séries de Puiseux à coefficients réels, tout corps superréel (en particulier tout corps hyperréel).
Théorie des modèlesLa théorie des modèles est une branche de la logique mathématique qui traite de la construction et de la classification des structures. Elle définit en particulier les modèles des théories axiomatiques, l'objectif étant d'interpréter les structures syntaxiques (termes, formules, démonstrations...) dans des structures mathématiques (ensemble des entiers naturels, groupes, univers...) de façon à leur associer des concepts de nature sémantique (comme le sens ou la vérité).
Théorèmes d'incomplétude de GödelLes théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »). Ils ont marqué un tournant dans l'histoire de la logique en apportant une réponse négative à la question de la démonstration de la cohérence des mathématiques posée plus de 20 ans auparavant par le programme de Hilbert.
Cohérence (logique)En logique mathématique, la cohérence, ou consistance, d'une théorie axiomatique peut se définir de deux façons, soit par référence à la déduction : il n'est pas possible de tout démontrer à partir des axiomes de la théorie, soit par référence à la sémantique de la théorie : celle-ci possède des réalisations qui lui donnent un sens. La première définition est syntaxique au sens où elle utilise des déductions ou démonstrations, qui sont des objets finis.