Concept
Cohérence (logique)
Concepts associés (38)
Principe d'explosion
En logique mathématique, le principe d'explosion, énoncé en latin ou encore , ou le principe de Pseudo-Scotus, est une loi de logique classique, de logique intuitionniste et d'autres logiques, selon laquelle n'importe quel énoncé peut être déduit à partir d'une contradiction. Certaines autres logiques comme les logiques non-monotones, qui tentent de gérer des cas particuliers, la logique minimale ou les logiques paracohérentes ne possèdent pas de principes d'explosion et tentent de gérer les contradictions différemment.
Indépendance (logique mathématique)
En logique mathématique, l'indépendance se réfère à la non-prouvabilité d'une proposition relativement à d'autres propositions. Une proposition σ est indépendante d'une théorie de premier ordre donnée T, si T ne prouve pas σ; à savoir, il est impossible de prouver σ à partir de T, et il est également impossible de prouver à partir de T que σ est faux. Parfois, σ est dit être indécidable de T; à ne pas confondre à la « décidabilité », du problème de décision.
Satisfaisabilité
En logique mathématique, la satisfaisabilité ou satisfiabilité et la validité sont des concepts élémentaires de sémantique. Une formule est satisfaisable s'il est possible de trouver une interprétation (modèle), une façon d'interpréter tous les éléments constitutifs de la formule, qui rend la formule vraie. Une formule est universellement valide, ou en raccourci valide si, pour toutes les interprétations, la formule est vraie.
Terme (logique)
Un terme est une expression de base du calcul des prédicats, de l'algèbre, notamment de l'algèbre universelle, et du calcul formel, des systèmes de réécriture et de l'unification. C'est l'objet produit par une analyse syntaxique. Sa principale caractéristique est d'être homogène (il n'y a que des opérations de base et pas d'opérations logiques) et de décrire l'agencement des opérations de base. Un terme est parfois appelé une formule du premier ordre.
Théorème de complétude de Gödel
En logique mathématique, le théorème de complétude du calcul des prédicats du premier ordre dresse une correspondance entre la sémantique et les démonstrations d'un système de déduction en logique du premier ordre. En termes intuitifs le théorème de complétude construit un pont entre vérité et démontrabilité formelle : tout énoncé vrai est démontrable.
Diophantien
L'adjectif diophantien () (du nom de Diophante d'Alexandrie) s'applique à tout ce qui concerne les équations polynomiales à coefficients entiers, également appelées équations diophantiennes. Les notions qui suivent ont été développées pour venir à bout du dixième problème de Hilbert. Il s'agit de savoir s'il existe un algorithme général permettant de dire si, oui ou non, il existe une solution à une équation diophantienne. Le théorème de Matiyasevich prouve l'impossibilité de l'existence d'un tel algorithme.
Théorie oméga-cohérente
En logique mathématique une théorie arithmétique est appelée théorie ω-cohérente (oméga-cohérente) quand, pour toute propriété P des nombres entiers que l'on peut exprimer dans le langage de la théorie, si pour chaque entier n, P(n) est démontrable dans la théorie, alors ¬∀x P(x) n'est pas démontrable dans la théorie (¬ pour la négation, ∀ pour la quantification universelle, « pour tout »). Quand on prend pour P un énoncé clos (qui ne dépend pas de x) on retrouve la définition de la cohérence, appelée parfois dans ce contexte cohérence simple, qui est donc conséquence de l'ω-cohérence.
Substitution (logic)
A substitution is a syntactic transformation on formal expressions. To apply a substitution to an expression means to consistently replace its variable, or placeholder, symbols with other expressions. The resulting expression is called a substitution instance, or instance for short, of the original expression. Where ψ and φ represent formulas of propositional logic, ψ is a substitution instance of φ if and only if ψ may be obtained from φ by substituting formulas for symbols in φ, replacing each occurrence of the same symbol by an occurrence of the same formula.
Primitive recursive arithmetic
Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , as a formalization of his finitistic conception of the foundations of arithmetic, and it is widely agreed that all reasoning of PRA is finitistic. Many also believe that all of finitism is captured by PRA, but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to ε0, which is the proof-theoretic ordinal of Peano arithmetic.
Hilbert's second problem
In mathematics, Hilbert's second problem was posed by David Hilbert in 1900 as one of his 23 problems. It asks for a proof that the arithmetic is consistent – free of any internal contradictions. Hilbert stated that the axioms he considered for arithmetic were the ones given in , which include a second order completeness axiom. In the 1930s, Kurt Gödel and Gerhard Gentzen proved results that cast new light on the problem. Some feel that Gödel's theorems give a negative solution to the problem, while others consider Gentzen's proof as a partial positive solution.