Arithmétique du premier ordre - First-order arithmetic

En théorie des ensembles et en logique mathématique, l' arithmétique du premier ordre est un ensemble de systèmes axiomatiques formalisant des nombres naturels et des sous-ensembles de nombres naturels. C'est un choix pour la théorie axiomatique comme base pour de nombreuses mathématiques, mais pas toutes. L'axiome primaire du premier ordre est l'arithmétique de Peano , créée par Giuseppe Peano :

  • : 0 est un nombre naturel.
  • : L'égalité est réflexive .
  • : L'égalité est symétrique .
  • : L'égalité est transitive .
  • : Les nombres naturels sont fermés par égalité.
  • : Les nombres naturels sont fermés sous S (l'opération successeur).
  • : S est une injection .
  • : Il n'y a pas d'entier naturel dont le successeur est zéro.
  • : Si K est un ensemble tel que 0 est dans K, et pour tout entier naturel n, n étant dans K implique que S(n) est dans K, alors K contient tout entier naturel.

L'arithmétique de Peano a un ordinal théorique de preuve de .

En savoir plus sur l'arithmétique de Peano

Les différentes axiomatisations de l'arithmétique de Peano sont très différentes, mais équivalentes. Alors que certaines axiomatisations, telles que celle décrite récemment (la définition d'origine) utilisent une signature contenant uniquement des symboles de 0, successeur, addition et multiplication, d'autres axiomatisations utilisent le langage semi-anneau ordonné, y compris un symbole de relation d'ordre supplémentaire. Une telle axiomatisation commence par les axiomes suivants qui décrivent un semi-anneau discrètement ordonné :

  1. , c'est-à-dire que l'addition est associative .
  2. , c'est-à-dire que l'addition est commutative .
  3. , c'est-à-dire que la multiplication est associative.
  4. , c'est-à-dire que la multiplication est commutative.
  5. , c'est-à-dire que la multiplication se distribue sur l'addition.
  6. , c'est-à-dire que zéro est une identité pour l'addition et un élément absorbant pour la multiplication.
  7. , c'est-à-dire que l'un est une identité pour la multiplication.
  8. , c'est-à-dire que l'opérateur '<' est transitif .
  9. , c'est-à-dire que l'opérateur '<' est irréflexif .
  10. , c'est-à-dire que l'ordre satisfait à la trichotomie .
  11. , c'est-à-dire que l'ordre est conservé sous ajout du même élément.
  12. , c'est-à-dire que l'ordre est conservé sous multiplication par le même élément positif.
  13. , c'est-à-dire étant donné deux éléments distincts, le plus grand est le plus petit plus un autre élément.
  14. , c'est-à-dire que zéro et un sont distincts et qu'il n'y a aucun élément entre eux.
  15. , c'est-à-dire que zéro est l'élément minimum.

Ces axiomes sont appelés PA ; la théorie PA est obtenue en ajoutant le schéma d'induction du premier ordre . Une caractéristique importante de PA est que toute structure satisfaisant cette théorie a un segment initial (ordonné par ) isomorphe à . Les éléments de ce segment sont appelés éléments standard, tandis que les autres éléments sont appelés éléments non standard.

arithmétique de Robinson Q

L'arithmétique de Robinson est un fragment axiomatisé du premier ordre de l'arithmétique de Peano (PA), produit pour la première fois en 1950 par RM Robinson . Il est souvent appelé Q. Q est presque identique à PA sans le schéma d'axiome d'induction mathématique (PA ). Q est plus faible que PA, mais leur langage est le même et les deux théories sont toutes les deux incomplètes . La logique d'arrière-plan de Q est la logique du premier ordre avec identité, notée infixe '='. Les individus, appelés nombres naturels, sont membres d'un ensemble appelé N avec un membre distingué 0, appelé zéro. Il y a trois opérations sur N :

  • Une opération unaire appelée successeur et notée par le préfixe S ;
  • Deux opérations binaires, addition et multiplication, notées respectivement infixe + et ·.

Les axiomes sont :

  • : 0 n'est le successeur d'aucun nombre.
  • : Si le successeur de x est identique au successeur de y, alors x et y sont identiques.
  • Chaque nombre naturel est soit 0, soit le successeur d'un certain nombre.

L'arithmétique de Robinson a un ordinal théorique de preuve de .

Définitions inductives itérées

Le système de définitions inductives itérées est une hiérarchie de systèmes mathématiques solides développés par le mathématicien allemand Wilfried Buchholz, bien connu pour avoir créé la fonction psi de Buchholz . ID ν étend PA de ν itéré points les moins fixes d'opérateurs monotones. Si ν = ω, les axiomes sont :

  • Les axiomes de l'arithmétique de Peano
  • pour chaque L ID -formule F(x)

Pour ν ≠ ω, les axiomes sont :

  • Les axiomes de l'arithmétique de Peano
  • pour chaque L ID -formule F(x) et tout u < ν

est une version affaiblie de . Dans le système de , un ensemble est plutôt appelé défini inductivement si pour un opérateur monotone , est un point fixe de , plutôt que le point le moins fixe. Cette différence subtile rend le système considérablement plus faible : , tandis que .

est encore plus affaibli. Dans , non seulement il utilise des points fixes plutôt que des points moins fixes, mais il n'a également d'induction que pour les formules positives. Cette différence encore une fois subtile rend le système encore plus faible : , tandis que .

est la plus faible de toutes les variantes de , basée sur les types W. La quantité d'affaiblissement par rapport aux définitions inductives itérées régulières est identique à la suppression de l'induction de barre étant donné un certain sous - système d' arithmétique du second ordre . , tandis que .

est un renforcement de "déploiement" de . Ce n'est pas exactement un système arithmétique du premier ordre, mais capture ce que l'on peut obtenir par un raisonnement prédicatif basé sur des définitions inductives généralisées itérées fois. Le montant de l'augmentation de la force est identique à l'augmentation de à : , tandis que .

est un automorphisme de . , mais est toujours plus faible que .

est un automorphisme de . , mais est toujours plus faible que .

est un automorphisme de . , où est la hiérarchie de Veblen avec les points les moins fixes itérés de manière dénombrable.

Autres systèmes de premier ordre

PA -

PA - est la théorie du premier ordre de la partie non négative d'un anneau discrètement ordonné. Un anneau est un ensemble muni de deux opérations binaires : (addition) et (multiplication) satisfaisant les trois ensembles d'axiomes suivants, appelés axiomes d'anneau :

  • est associatif, est commutatif, est l' identité additive et est l' inverse additif de .
  • est associatif, et est l' identité multiplicative .
  • pour tous , et en .
  • pour tous , et en .

PA - a un ordinal de la théorie de la preuve de .

RFA

RFA est une fonction arithmétique rudimentaire . Une fonction rudimentaire est une fonction qui peut être obtenue à partir des opérations suivantes :

  • est rudimentaire
  • est rudimentaire
  • est rudimentaire
  • Toute composition de fonctions rudimentaires est rudimentaire
  • est rudimentaire

Pour tout ensemble M, soit rud( M ) le plus petit ensemble contenant M { M } fermé sous les opérations rudimentaires. RFA est une version de l'arithmétique basée sur des fonctions rudimentaires. RFA a un ordinal de la théorie de la preuve de ω 2 .

0 / IΣ 1

0 et IΣ 1 sont des calculs de base avec récurrence pour les prédicats Δ 0 - et Σ 1 -, respectivement. Notez que lorsque les gens se réfèrent à IΔ 0 , IΔ 0 est une arithmétique de base avec induction pour Δ 0 -prédicats, mais sans axiome affirmant que l'exponentiation est totale , tandis que IΔ 0 avec un tel axiome est appelé IΔ 0 + . IΔ 0 n pour 1 < n < ω est IΔ 0 + augmenté d'un axiome assurant que chaque élément du n -ième niveau de la hiérarchie de Grzegorczyk est total. IΔ 0 a un ordinal de la preuve théorique de ω 2 . IΔ 0 + . a un ordinal de la preuve théorique de 3 . IΔ 0 n a un ordinal de la preuve théorique de ω n . IΣ 1 a un ordinal de la preuve théorique de ω ω .

AGE

L'EFA est l'arithmétique des fonctions élémentaires. Sa langue contient :

  • deux constantes 0, 1,
  • trois opérations binaires +, ×, exp, avec exp( x , y ) généralement écrite sous la forme x y ,
  • un symbole de relation binaire < (Ceci n'est pas vraiment nécessaire car il peut être écrit en fonction des autres opérations et est parfois omis, mais est pratique pour définir des quantificateurs bornés).

Les quantificateurs bornés sont ceux de la forme ∀(x<y) et ∃ (x<y) qui sont des abréviations pour ∀ x (x<y)→... et ∃x (x<y)∧... manière. Les axiomes de l'EPT sont

  • Les axiomes de l' arithmétique de Robinson pour 0, 1, +, ×, <
  • Les axiomes pour l'exponentiation : x 0 = 1, x y +1 = x y × x .
  • Induction pour les formules dont tous les quantificateurs sont bornés (mais qui peuvent contenir des variables libres).

PRA

PRA est une arithmétique récursive primitive, une formalisation sans quantificateur des nombres naturels . Le langage de PRA consiste en :

Les axiomes logiques de la PRA sont les suivants :

Les règles logiques de la PRA sont le modus ponens et la substitution de variables .

Les axiomes non logiques sont :

et des équations de définition récursives pour chaque fonction récursive primitive comme souhaité.

Les références

  1. ^ van Heijenoort, Jean (1967). De Frege à Gödel . p. 83. ISBN 978-0-67-432449-7.
  2. ^ Kaye, Richard (1991). Modèles d'arithmétique de Peano . p. 16–18.