Concept
Arithmétique de Robinson
Concepts associés (15)
Arithmétique du second ordre
En logique mathématique, l'arithmétique du second ordre est une théorie des entiers naturels et des ensembles d'entiers naturels. Elle a été introduite par David Hilbert et Paul Bernays dans leur livre Grundlagen der Mathematik. L'axiomatisation usuelle de l'arithmétique du second ordre est notée Z2. L'arithmétique de second ordre a pour conséquence les théorèmes de l'arithmétique de Peano (du premier ordre), mais elle est à la fois plus forte et plus expressive que celle-ci.
Modèle non standard de l'arithmétique
En logique mathématique, un modèle non standard de l'arithmétique est un modèle non standard de l'arithmétique de Peano, qui contient des nombres non standards. Le modèle standard de l'arithmétique contient exactement les nombres naturels 0, 1, 2, etc. Les éléments du domaine de tout modèle de l'arithmétique de Peano sont ordonnés linéairement et possèdent un segment initial isomorphe aux nombres naturels standards. Un modèle non standard est un modèle qui contient également des éléments en dehors de ce segment initial.
Théorie complète
En logique mathématique, une théorie complète est une théorie qui est équivalente à un ensemble maximal cohérent de propositions ; ceci signifie qu'elle est cohérente et que toute extension propre ne l'est plus. Pour des théories logiques qui contiennent la logique propositionnelle classique, ceci équivaut à la condition que pour toute proposition φ du langage de la théorie, soit elle contient φ, soit elle contient sa négation ¬φ.
Arithmétique de Presburger
En logique mathématique, l'arithmétique de Presburger est la théorie du premier ordre des nombres entiers naturels munis de l'addition. Elle a été introduite en 1929 par Mojżesz Presburger. Il s'agit de l'arithmétique de Peano sans la multiplication, c’est-à-dire avec seulement l'addition, en plus du zéro et de l'opération successeur. Contrairement à l'arithmétique de Peano, l'arithmétique de Presburger est décidable. Cela signifie qu'il existe un algorithme qui détermine si un énoncé du langage de l'arithmétique de Presburger est démontrable à partir des axiomes de l'arithmétique de Presburger.
Gentzen's consistency proof
Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction (i.e. are "consistent"), as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms.
Equiconsistency
In mathematical logic, two theories are equiconsistent if the consistency of one theory implies the consistency of the other theory, and vice versa. In this case, they are, roughly speaking, "as consistent as each other". In general, it is not possible to prove the absolute consistency of a theory T. Instead we usually take a theory S, believed to be consistent, and try to prove the weaker statement that if S is consistent then T must also be consistent—if we can do this we say that T is consistent relative to S.
Construction des entiers naturels
Il existe plusieurs méthodes classiques de construction des entiers naturels, mais on utilise aujourd’hui le plus souvent celle due à von Neumann . Dans la théorie des ensembles, on définit les entiers par récurrence, en construisant explicitement une suite d'ensembles à partir de l'ensemble vide (la théorie des ensembles postule qu'il existe au minimum un tel ensemble vide).
Théorèmes d'incomplétude de Gödel
Les 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.
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.
Demi-anneau
En mathématiques, un demi-anneau, ou semi-anneau, est une structure algébrique qui a les propriétés suivantes : constitue un monoïde commutatif ; forme un monoïde ; est distributif par rapport à + ; 0 est absorbant pour le produit, autrement dit: pour tout . Ces propriétés sont proches de celles d'un anneau, la différence étant qu'il n'y a pas nécessairement d'inverses pour l’addition dans un demi-anneau. Un demi-anneau est commutatif quand son produit est commutatif ; il est idempotent quand son addition est idempotente.