Liste des théories du premier ordre - List of first-order theories

En logique mathématique , une théorie du premier ordre est donnée par un ensemble d'axiomes dans une langue. Cette entrée répertorie certains des exemples les plus courants utilisés dans la théorie des modèles et certaines de leurs propriétés.

Préliminaires

Pour chaque structure mathématique naturelle, il existe une signature σ listant les constantes, les fonctions et les relations de la théorie avec leurs arités , de sorte que l'objet est naturellement une structure σ . Étant donné une signature σ, il existe un langage unique du premier ordre L _σ qui peut être utilisé pour capturer les faits exprimables du premier ordre concernant la structure σ.

Il existe deux façons courantes de spécifier des théories:

1. Énumérez ou décrivez un ensemble de phrases dans la langue L _σ , appelées axiomes de la théorie.
2. Donner un ensemble de σ-structures, et définir une théorie comme l'ensemble des phrases de L _{σ présentes} dans tous ces modèles. Par exemple, la «théorie des champs finis» comprend toutes les phrases dans le langage des champs qui sont vraies dans tous les champs finis.

Une théorie L _σ peut:

• être cohérent: aucune preuve de contradiction n'existe;
• être satisfiable: il existe une σ-structure pour laquelle les phrases de la théorie sont toutes vraies (par le théorème de complétude , la satisfiabilité équivaut à la cohérence);
• être complet: pour toute affirmation, elle ou sa négation est prouvable;
• avoir l'élimination des quantificateurs ;
• éliminer les imaginaires ;
• être finement axiomatisable ;
• être décidable : il existe un algorithme pour décider quelles déclarations sont prouvables;
• être axiomatisable récursivement;
• être le modèle complet ou le sous-modèle complet;
• être κ-catégorique : Tous les modèles de cardinalité κ sont isomorphes;
• être stable ou instable;
• être ω-stable (identique à totalement transcendantal pour les théories dénombrables );
• être superstable
• avoir un modèle atomique ;
• avoir un modèle de premier ordre ;
• avoir un modèle saturé .

Théories identitaires pures

La signature de la théorie de l'identité pure est vide, sans fonctions, constantes ou relations.

La théorie de l'identité pure n'a pas d'axiomes (non logiques). C'est décidable.

L'une des rares propriétés intéressantes que l'on puisse affirmer dans le langage de la théorie de l'identité pure est celle d'être infini. Ceci est donné par un ensemble infini d'axiomes indiquant qu'il y a au moins 2 éléments, il y a au moins 3 éléments, et ainsi de suite:

• ∃ x ₁ ∃ x ₂ ¬ x ₁ = x ₂ , ∃ x ₁ ∃ x ₂ ∃ x ₃ ¬ x ₁ = x ₂ ∧ ¬ x ₁ = x ₃ ∧ ¬ x ₂ = x ₃ , ...

Ces axiomes définissent la théorie d'un ensemble infini .

La propriété opposée d'être fini ne peut être énoncée dans la logique du premier ordre pour toute théorie qui a des modèles finis arbitrairement grands: en fait, une telle théorie a des modèles infinis par le théorème de compacité . En général, si une propriété peut être énoncée par un nombre fini de phrases de logique du premier ordre, alors la propriété opposée peut également être énoncée en logique du premier ordre, mais si une propriété a besoin d'un nombre infini de phrases, alors sa propriété opposée ne peut pas être déclarée dans la logique du premier ordre.

Toute déclaration de la théorie pure d'identité est équivalent soit σ ( N ) ou à ¬σ ( N ) pour un certain fini sous - ensemble N des nombres entiers non négatifs , où σ ( N ) est l'affirmation selon laquelle le nombre d'éléments est en N . Il est même possible de décrire toutes les théories possibles dans ce langage comme suit. Toute théorie est soit la théorie de tous les ensembles de cardinalité en N pour un sous- ensemble fini N des entiers non négatifs, soit la théorie de tous les ensembles dont la cardinalité n'est pas dans N , pour un sous- ensemble fini ou infini N du non-négatif entiers. (Il n'y a pas de théories dont les modèles sont exactement des ensembles de cardinalité N si N est un sous-ensemble infini des nombres entiers.) Les théories complètes sont les théories des ensembles de cardinalité n pour certains n finis , et la théorie des ensembles infinis.

Un cas particulier de ceci est la théorie incohérente définie par l'axiome ∃ x ¬ x = x . C'est une théorie parfaitement bonne avec de nombreuses bonnes propriétés: elle est complète, décidable, finement axiomatisable, etc. Le seul problème est qu'il n'a pas du tout de modèles. D'après le théorème de complétude de Gödel, c'est la seule théorie (pour une langue donnée) sans modèle. Ce n'est pas la même chose que la théorie de l' ensemble vide (dans les versions de logique du premier ordre qui permettent à un modèle d'être vide): la théorie de l'ensemble vide a exactement un modèle, qui n'a pas d'éléments.

Relations unaires

Un ensemble de relations unaires P _i pour i dans un ensemble I est dit indépendant si pour tous les deux sous-ensembles finis disjoints A et B de I il y a un élément x tel que P _i ( x ) est vrai pour i dans A et faux pour i dans B . L'indépendance peut être exprimée par un ensemble d'instructions de premier ordre.

La théorie d'un nombre dénombrable de relations unaires indépendantes est complète, mais n'a pas de modèles atomiques . C'est aussi un exemple de théorie superstable mais pas totalement transcendantale .

Relations d'équivalence

La signature des relations d'équivalence a un symbole de relation d'infixe binaire ~, pas de constantes et pas de fonctions. Les relations d'équivalence satisfont les axiomes:

• Réflexif ∀ x x ~ x ;
• Symétrique ∀ x ∀ y x ~ y → y ~ x ;
• Transitif : ∀ x ∀ y ∀ z ( x ~ y ∧ y ~ z ) → x ~ z .

Certaines propriétés de premier ordre des relations d'équivalence sont:

• ~ a un nombre infini de classes d'équivalence ;
• ~ a exactement n classes d'équivalence (pour tout entier positif fixe n );
• Toutes les classes d'équivalence sont infinies;
• Toutes les classes d'équivalence ont une taille exactement n (pour tout entier positif fixe n ).

La théorie d'une relation d'équivalence avec exactement 2 classes d'équivalence infinies est un exemple facile d'une théorie qui est ω-catégorique mais non catégorique pour tout cardinal plus grand .

La relation d'équivalence ~ ne doit pas être confondue avec le symbole d' identité '=': si x = y alors x ~ y , mais l'inverse n'est pas nécessairement vrai. Les théories des relations d'équivalence ne sont pas si difficiles ou intéressantes, mais donnent souvent des exemples faciles ou des contre-exemples pour diverses déclarations.

Les constructions suivantes sont parfois utilisées pour produire des exemples de théories avec certains spectres ; en fait , en les appliquant à un petit nombre de théories explicites T on obtient des exemples de théories dénombrables complètes avec tous les spectres innombrable possible. Si T est une théorie dans un langage, nous définissons une nouvelle théorie 2 ^T en ajoutant une nouvelle relation binaire au langage, et en ajoutant des axiomes indiquant qu'il s'agit d'une relation d'équivalence, de sorte qu'il existe un nombre infini de classes d'équivalence qui toutes sont des modèles de T . Il est possible d'itérer cette construction de manière transfinie : étant donné un ordinal α, définir une nouvelle théorie en ajoutant une relation d'équivalence E _β pour chaque β <α, ainsi que des axiomes indiquant que chaque fois que β <γ alors chaque classe d'équivalence E _γ est l'union de un nombre infini de E _ß classes d' équivalence, et chaque E ₀ classe d'équivalence est un modèle de T . De manière informelle, on peut visualiser les modèles de cette théorie comme des arbres infiniment branchés de hauteur α avec des modèles de T attachés à toutes les feuilles.

Ordres

La signature des ordres n'a ni constantes ni fonctions, et un symbole de relation binaire ≤. (Il est bien sûr possible d'utiliser à la place ≥, <ou> comme relation de base, avec les changements mineurs évidents des axiomes.) Nous définissons x ≥ y , x < y , x > y comme des abréviations pour y ≤ x , x ≤ y ∧¬ y ≤ x , y < x ,

Quelques propriétés de premier ordre des commandes:

• Transitive : ∀ x ∀ y ∀ z x ≤ y ∧ y ≤ z → x ≤ z
• Réflexif : ∀ x x ≤ x
• Antisymétrique : ∀ x ∀ y x ≤ y ∧ y ≤ x → x = y
• Partiel : Transitif ∧ Réflexif ∧ Antisymétrique;
• Linéaire (ou total ): partiel ∧ ∀ x ∀ y x ≤ y ∨ y ≤ x
• Dense : ∀ x ∀ z x < z → ∃ y x < y ∧ y < z ("Entre 2 éléments distincts, il y a un autre élément")
• Il y a un plus petit élément: ∃ x ∀ y x ≤ y
• Il existe un élément le plus grand: ∃ x ∀ y y ≤ x
• Chaque élément a un successeur immédiat: ∀ x ∃ y ∀ z x < z ↔ y ≤ z

La théorie DLO des ordres linéaires denses sans extrémités (c'est-à-dire pas d'élément le plus petit ou le plus grand) est complète, ω-catégorielle, mais non catégorique pour tout cardinal indénombrable. Il existe trois autres théories très similaires: la théorie des ordres linéaires denses avec a:

• Élément le plus petit mais pas le plus grand;
• Élément le plus grand mais pas le plus petit;
• Élément le plus grand et le plus petit.

Être bien ordonné ("tout sous-ensemble non vide a un élément minimal") n'est pas une propriété de premier ordre; la définition habituelle implique la quantification de tous les sous-ensembles .

Treillis

Les réseaux peuvent être considérés soit comme des sortes spéciales d'ensembles partiellement ordonnés, avec une signature constituée d'un symbole de relation binaire ≤, soit comme des structures algébriques avec une signature constituée de deux opérations binaires ∧ et ∨. Les deux approches peuvent être liées en définissant a ≤ b comme signifiant a ∧ b = a .

Pour deux opérations binaires, les axiomes d'un réseau sont:

Lois commutatives :		${\ displaystyle \ forall a \ forall b \; a \ vee b = b \ vee a}$		${\ displaystyle \ forall a \ forall b \; a \ wedge b = b \ wedge a}$
Lois associatives :		${\ displaystyle \ forall a \ forall b \ forall c \; a \ vee (b \ vee c) = (a \ vee b) \ vee c}$		${\ displaystyle \ forall a \ forall b \ forall c \; a \ wedge (b \ wedge c) = (a \ wedge b) \ wedge c}$
Lois d'absorption :		${\ displaystyle \ forall a \ forall b \; a \ vee (a \ wedge b) = a}$		${\ displaystyle \ forall a \ forall b \; a \ wedge (a \ vee b) = a}$

Pour une relation ≤ les axiomes sont:

• Les axiomes indiquant ≤ est un ordre partiel, comme ci-dessus.
• ${\ displaystyle \ forall a \ forall b \ exists c \; c \ leq a \ wedge c \ leq b \ wedge \ forall d \; d \ leq a \ wedge d \ leq b \ rightarrow d \ leq c}$ (existence de c = a∧b)
• ${\ displaystyle \ forall a \ forall b \ exists c \; a \ leq c \ wedge b \ leq c \ wedge \ forall d \; a \ leq d \ wedge b \ leq d \ rightarrow c \ leq d}$ (existence de c = a∨b)

Les propriétés de premier ordre comprennent:

• ${\ displaystyle \ forall x \ forall y \ forall z \; x \ vee (y \ wedge z) = (x \ vee y) \ wedge (x \ vee z)}$ ( treillis distributifs )
• ${\ displaystyle \ forall x \ forall y \ forall z \; x \ vee (y \ wedge (x \ vee z)) = (x \ vee y) \ wedge (x \ vee z)}$ ( treillis modulaires )

Les algèbres de Heyting peuvent être définies comme des treillis avec certaines propriétés supplémentaires de premier ordre.

L'exhaustivité n'est pas une propriété de premier ordre des treillis.

Graphiques

La signature des graphes n'a ni constantes ni fonctions, et un symbole de relation binaire R , où R ( x , y ) est lu comme "il y a une arête de x à y ".

Les axiomes de la théorie des graphes sont

• Symétrique : ∀ x ∀ y R ( x , y ) → R ( y , x )
• Anti-réflexif : ∀ x ¬ R ( x , x ) ("pas de boucles ")

La théorie des graphes aléatoires a les axiomes supplémentaires suivants pour chaque entier positif n :

• Pour deux ensembles finis disjoints de taille n , il y a un point joint à tous les points du premier ensemble et à aucun point du second ensemble. (Pour chaque n fixe , il est facile d'écrire cette instruction dans le langage des graphes.)

La théorie des graphes aléatoires est ω catégorique, complète et décidable, et son modèle dénombrable est appelé le graphe de Rado . Un énoncé dans le langage des graphes est vrai dans cette théorie si et seulement si la probabilité qu'un graphe aléatoire de n -vertex modélise l'énoncé tend vers 1 dans la limite alors que n va vers l'infini.

Algèbres booléennes

Il existe plusieurs signatures et conventions utilisées pour les algèbres booléennes :

1. La signature a deux constantes, 0 et 1, et deux fonctions binaires ∧ et ∨ ("et" et "ou"), et une fonction unaire ¬ ("pas"). Cela peut prêter à confusion car les fonctions utilisent les mêmes symboles que les fonctions propositionnelles de la logique du premier ordre.
2. En théorie des ensembles , une convention courante est que le langage a deux constantes, 0 et 1, et deux fonctions binaires · et +, et une fonction unaire -. Les trois fonctions ont la même interprétation que les fonctions de la première convention. Malheureusement, cette convention se heurte mal à la convention suivante:
3. En algèbre , la convention habituelle est que le langage a deux constantes, 0 et 1, et deux fonctions binaires · et +. La fonction · a la même signification que ∧, mais a + b signifie a ∨ b ∧¬ ( a ∧ b ). La raison en est que les axiomes d'une algèbre booléenne ne sont alors que les axiomes d'un anneau avec 1 plus ∀ x x ² = x . Malheureusement, cela se heurte à la convention standard de la théorie des ensembles donnée ci-dessus.

Les axiomes sont:

• Les axiomes pour un réseau distributif (voir ci-dessus)
• ∀a a ∧¬ a = 0, ∀a a ∨¬ a = 1 (propriétés de négation)
• Certains auteurs ajoutent l'axiome supplémentaire ¬0 = 1, pour exclure l'algèbre triviale avec un élément.

Tarski a prouvé que la théorie des algèbres booléennes est décidable.

Nous écrivons x ≤ y comme une abréviation pour x ∧ y = x , et atome ( x ) comme une abréviation pour ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = x , lu comme " x est un atome ", en d'autres termes un élément non nul sans rien entre lui et 0. Voici quelques propriétés du premier ordre des algèbres booléennes:

• Atomique : ∀ x x = 0 ∨ ∃ y y ≤ x ∧ atome ( y )
• Sans atome : ∀ x ¬atom ( x )

La théorie des algèbres booléennes sans atome est ω-catégorique et complète.

Pour toute algèbre booléenne B , il existe plusieurs invariants définis comme suit.

• l'idéal I ( B ) se compose d'éléments qui sont la somme d'un élément atomique et d'un élément sans atome (un élément sans atome en dessous).
• Les algèbres quotientes B ⁱ de B sont définies inductivement par B ⁰ = B , B ^{k +1} = B ^k / I ( B ^k ).
• L'invariant m ( B ) est le plus petit entier tel que B ^{m +1} est trivial, ou ∞ si aucun entier n'existe.
• Si m ( B ) est fini, l'invariant n ( B ) est le nombre d'atomes de B ^{m ( B )} si ce nombre est fini, ou ∞ si ce nombre est infini.
• L'invariant l ( B ) est 0 si B ^{m ( B )} est atomique ou si m ( B ) est ∞, et 1 sinon.

Alors deux algèbres booléennes sont élémentairement équivalentes si et seulement si leurs invariants l , m et n sont les mêmes. En d'autres termes, les valeurs de ces invariants classent les complétions possibles de la théorie des algèbres booléennes. Les théories complètes possibles sont donc:

• L'algèbre triviale (si cela est autorisé; parfois 0 ≠ 1 est inclus comme axiome.)
• La théorie avec m = ∞
• Les théories avec m un entier naturel, n un entier naturel ou ∞, et l = 0 ou 1 (avec l = 0 si n = 0).

Groupes

La signature de la théorie des groupes a une constante 1 (l'identité), une fonction d'arité 1 (l'inverse) dont la valeur sur t est notée t ⁻¹ , et une fonction d'arité 2, qui est généralement omise des termes. Pour tout entier n , t ⁿ est une abréviation du terme évident pour la n ième puissance de t .

Les groupes sont définis par les axiomes

• Identité : ∀ x 1 x = x ∧ x 1 = x
• Inverse : ∀ x x ⁻¹ x = 1 ∧ xx ⁻¹ = 1
• Associativité : ∀ x ∀ y ∀ z ( xy ) z = x ( yz )

Certaines propriétés des groupes qui peuvent être définies dans la langue de premier ordre des groupes sont:

• Abélien : ∀ x ∀ y xy = yx .
• Sans torsion : ∀ x x ² = 1 → x = 1, ∀ x x ³ = 1 → x = 1, ∀ x x ⁴ = 1 → x = 1, ...
• Divisible : ∀ x ∃ y y ² = x , ∀ x ∃ y y ³ = x , ∀ x ∃ y y ⁴ = x , ...
• Infini (comme dans la théorie de l'identité)
• Exposant n (pour tout entier positif fixe n ): ∀ x x ⁿ = 1
• Nilpotent de classe n (pour tout entier positif fixe n )
• Résoluble de classe n (pour tout entier positif fixe n )

La théorie des groupes abéliens est décidable. La théorie des groupes abéliens infinis divisibles sans torsion est complète, tout comme la théorie des groupes abéliens infinis d'exposant p (pour p premier ).

La théorie des groupes finis est l'ensemble des énoncés du premier ordre dans le langage des groupes qui sont vrais dans tous les groupes finis (il existe de nombreux modèles infinis de cette théorie). Il n'est pas complètement banal de trouver une telle affirmation qui ne soit pas vraie pour tous les groupes: un exemple est "étant donné deux éléments d'ordre 2, soit ils sont conjugués, soit il y a un élément non trivial qui fait la navette avec les deux".

Les propriétés d'être fini, ou libre , ou simple , ou de torsion ne sont pas du premier ordre. Plus précisément, la théorie du premier ordre de tous les groupes avec l'une de ces propriétés a des modèles qui n'ont pas cette propriété.

Anneaux et champs

La signature des anneaux (unitaux) a deux constantes 0 et 1, deux fonctions binaires + et ×, et, éventuellement, une fonction de négation unaire -.

Anneaux

Axiomes: L'addition fait de l'anneau un groupe abélien, la multiplication est associative et a une identité 1, et la multiplication est distributive à gauche et à droite.

Anneaux commutatifs

Les axiomes des anneaux plus ∀ x ∀ y xy = yx .

Des champs

Les axiomes des anneaux commutatifs plus ∀ x (¬ x = 0 → ∃ y xy = 1) et ¬ 1 = 0. Beaucoup d'exemples donnés ici n'ont que des axiomes universels ou algébriques . La classe de structures satisfaisant une telle théorie a la propriété d'être fermée sous sous-structure. Par exemple, un sous-ensemble d'un groupe fermé sous les actions de groupe de multiplication et inverse est à nouveau un groupe. Puisque la signature des champs n'inclut généralement pas l'inverse multiplicatif et additif, les axiomes pour les inverses ne sont pas universels, et donc une sous-structure d'un champ fermé sous addition et multiplication n'est pas toujours un champ. Cela peut être résolu en ajoutant des fonctions inverses unaires au langage.

Pour tout entier positif n, la propriété que toutes les équations de degré n ont une racine peut être exprimée par une seule phrase du premier ordre:

• ∀ a ₁ ∀ a ₂ ... ∀ a _n ∃ x (... (( x + a ₁ ) x + a ₂ ) x + ...) x + a _n = 0

Champs parfaits

Les axiomes pour les champs, plus les axiomes pour chaque nombre premier p indiquant que si p  1 = 0 (c'est-à-dire que le champ a la caractéristique p ), alors chaque élément de champ a une p ième racine.

Champs algébriquement fermés de caractéristique p

Les axiomes pour les champs, plus pour chaque n positif l'axiome que tous les polynômes de degré n ont une racine, plus les axiomes fixant la caractéristique. Les exemples classiques de théories complètes. Catégorique dans tous les cardinaux innombrables. La théorie ACF _p a une propriété de domaine universel , en ce sens que toutes les structures N satisfaisant les axiomes universels de ACF _p est une sous - structure d'un assez grand champ algébriquement fermé , et en outre deux quelconques de ces encastrements N → M induisent une automorphismes de M . ${\ displaystyle M \ models ACF_ {0}}$

Champs finis

La théorie des champs finis est l'ensemble de tous les énoncés du premier ordre qui sont vrais dans tous les champs finis. Des exemples significatifs de telles déclarations peuvent, par exemple, être donnés en appliquant le théorème de Chevalley – Warning , sur les champs premiers . Le nom est un peu trompeur car la théorie a beaucoup de modèles infinis. Ax a prouvé que la théorie est décidable.

Champs formellement réels

Les axiomes des champs plus, pour tout entier positif n , l'axiome:

• ∀ a ₁ ∀ a ₂ ... ∀ a _n a ₁ a ₁ + a ₂ a ₂ + ... + a _n a _n = 0 → a ₁ = 0∧ a ₂ = 0∧ ... ∧ a _n = 0.

Autrement dit, 0 n'est pas une somme de carrés non triviale.

De vrais champs fermés

Les axiomes pour les champs formellement réels plus les axiomes:

• ∀ x ∃ y ( x = yy ∨ x + yy = 0);
• pour tout entier positif impair n , l'axiome indiquant que tout polynôme de degré n a une racine.

La théorie des champs fermés réels est efficace et complète et donc décidable (le théorème de Tarski-Seidenberg ). L'ajout d'autres symboles de fonction (par exemple, la fonction exponentielle, la fonction sinus) peut modifier la décidabilité .

champs p -adiques

Ax & Kochen (1965) ont montré que la théorie des champs p -adiques est décidable et ont donné un ensemble d'axiomes pour elle.

Géométrie

Les axiomes pour divers systèmes de géométrie utilisent généralement un langage typé, les différents types correspondant à différents objets géométriques tels que des points, des lignes, des cercles, des plans, etc. La signature sera souvent constituée de relations d'incidence binaire entre des objets de types différents; par exemple, la relation entre un point et une ligne. La signature peut avoir des relations plus compliquées; par exemple, la géométrie ordonnée peut avoir une relation ternaire "entre deux points" pour 3 points, qui dit si l'un se situe entre deux autres, ou une relation "congruence" entre 2 paires de points.

Voici quelques exemples de systèmes axiomatisées de la géométrie comprennent ordonné la géométrie , la géométrie absolue , la géométrie affine , la géométrie euclidienne , la géométrie projective et géométrie hyperbolique . Pour chacune de ces géométries, il existe de nombreux systèmes d'axiomes différents et inéquivalents pour différentes dimensions. Certains de ces systèmes d'axiomes incluent des axiomes de «complétude» qui ne sont pas du premier ordre.

À titre d'exemple typique, les axiomes de la géométrie projective utilisent 2 types, points et lignes, et une relation d'incidence binaire entre les points et les lignes. Si les variables de point et de ligne sont indiquées par des lettres minuscules et majuscules, et qu'un incident à A est écrit comme aA , alors un ensemble d'axiomes est

• ${\ displaystyle \ forall a \ forall b \; \ lnot a = b \ rightarrow \ exists C \; aC \ land bC}$ (Il y a une ligne passant par 2 points distincts a , b ...)
• ${\ displaystyle \ forall a \ forall b \ forall C \ forall D \; \ lnot a = b \ land aC \ land bC \ land aD \ land bD \ rightarrow C = D}$ (... qui est unique)
• ${\ displaystyle \ forall a \ forall b \ forall c \ forall d \ forall e \ forall G \ forall H \; aH \ land bH \ land eH \ land cG \ land dG \ land eG \ rightarrow \ existe f \ existe I \ existe J \; aI \ land cI \ land fI \ land bJ \ land dJ \ land fJ}$ (Axiome de Veblen: si ab et cd se trouvent sur des lignes qui se croisent, alors ac et bd .)
• ${\ displaystyle \ forall A \ exists b \ exists c \ exists d \; bA \ land cA \ land dA \ land \ lnot b = c \ land \ lnot b = d \ land \ lnot c = d}$ (Chaque ligne a au moins 3 points)

Euclide n'a pas énoncé explicitement tous les axiomes de la géométrie euclidienne, et la première liste complète a été donnée par Hilbert dans les axiomes de Hilbert . Ce n'est pas une axiomatisation du premier ordre car l'un des axiomes de Hilbert est un axiome de complétude du second ordre. Les axiomes de Tarski sont une axiomatisation de premier ordre de la géométrie euclidienne. Tarski a montré que ce système d'axiomes est complet et décidable en le reliant à la théorie complète et décidable des champs fermés réels.

Algèbre différentielle

• La théorie DF des champs différentiels .

La signature est celle des champs (0, 1, +, -, ×) avec une fonction unaire ∂, la dérivation. Les axiomes sont ceux pour les champs avec

${\ displaystyle \ forall u \ forall v \, \ partial (uv) = u \, \ partial v + v \, \ partial u}$

${\ displaystyle \ forall u \ forall v \, \ partial (u + v) = \ partial u + \ partial v \.}$

Pour cette théorie on peut ajouter la condition que la caractéristique est p , un premier ou zéro, pour obtenir la théorie DF _p des champs différentiels de caractéristique p (et de même avec les autres théories ci-dessous).

Si K est un champ différentiel alors le champ des constantes. La théorie des champs différentiellement parfaits est la théorie des champs différentiels avec la condition que le champ des constantes soit parfait; en d'autres termes, pour chaque premier p il a l'axiome: ${\ displaystyle k = \ {u \ in K: \ partial (u) = 0 \}.}$

${\ displaystyle \ forall u \, \ partial (u) = 0 \ land p1 = 0 \ rightarrow \ exists v \, v ^ {p} = u}$

(Il est inutile d'exiger que tout le champ soit un champ parfait , car en caractéristique non nulle, cela implique que le différentiel est de 0.) Pour des raisons techniques liées à l' élimination des quantificateurs , il est parfois plus pratique de forcer le champ constant être parfait en ajoutant un nouveau symbole r à la signature avec les axiomes

${\ displaystyle \ forall u \, \ partial (u) = 0 \ land p1 = 0 \ rightarrow r (u) ^ {p} = u}$

${\ displaystyle \ forall u \, \ lnot \ partial (u) = 0 \ rightarrow r (u) = 0.}$

• La théorie des champs différentiellement fermés (DCF) est la théorie des champs différentiellement parfaits avec des axiomes disant que si f et g sont des polynômes différentiels et que le séparant de f est non nul et que g ≠ 0 et f a un ordre supérieur à celui de g , alors il est un x dans le champ avec f ( x ) = 0 et g ( x ) ≠ 0.

Une addition

La théorie des nombres naturels avec une fonction successeur a une signature constituée d'une constante 0 et d'une fonction unaire S ("successeur": S ( x ) est interprétée comme x +1), et a des axiomes:

1. ∀x ¬ Sx = 0
2. ∀x∀y Sx = Sy → x = y
3. Soit P ( x ) une formule du premier ordre avec une seule variable libre x . Alors la formule suivante est un axiome:

( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

Le dernier axiome (induction) peut être remplacé par les axiomes

• Pour chaque entier n > 0, l'axiome ∀x SSS ... Sx ≠ x (avec n copies de S )
• ∀x ¬ x = 0 → ∃y Sy = x

La théorie des nombres naturels avec une fonction successeur est complète et décidable, et est κ-catégorique pour indénombrable κ mais pas pour dénombrable κ.

L'arithmétique de Presburger est la théorie des nombres naturels sous addition, avec une signature constituée d'une constante 0, d'une fonction unaire S et d'une fonction binaire +. Il est complet et décidable. Les axiomes sont

1. ∀x ¬ Sx = 0
2. ∀x∀y Sx = Sy → x = y
3. ∀xx + 0 = x
4. ∀x∀yx + Sy = S (x + y)
5. Soit P ( x ) une formule du premier ordre avec une seule variable libre x . Alors la formule suivante est un axiome:

( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

Arithmétique

Beaucoup des théories du premier ordre décrites ci-dessus peuvent être étendues pour compléter des théories cohérentes énumérables récursivement. Ce n'est plus vrai pour la plupart des théories suivantes; ils peuvent généralement encoder à la fois la multiplication et l'addition de nombres naturels, ce qui leur donne assez de puissance pour s'encoder eux-mêmes, ce qui implique que le théorème d'incomplétude de Gödel s'applique et que les théories ne peuvent plus être à la fois complètes et récursivement énumérables (à moins qu'elles ne soient incohérentes).

La signature d'une théorie de l'arithmétique a:

• La constante 0;
• La fonction unaire , la fonction successeur , désignée ici par le préfixe S , ou par le préfixe σ ou postfixe ′ ailleurs;
• Deux fonctions binaires , désignées par infixe + et ×, appelées «addition» et «multiplication».

Certains auteurs considèrent que la signature contient une constante 1 au lieu de la fonction S , puis définissent S de manière évidente comme St = 1 + t .

Arithmétique de Robinson (également appelée Q ). Les axiomes (1) et (2) gouvernent l'élément distingué 0. (3) assure que S est une injection . Les axiomes (4) et (5) sont la définition récursive standard de l'addition; (6) et (7) font de même pour la multiplication. L'arithmétique de Robinson peut être considérée comme l'arithmétique de Peano sans induction. Q est une théorie faible pour laquelle le théorème d'incomplétude de Gödel est valable. Axiomes:

1. ∀ x ¬ S x = 0
2. ∀ x ¬ x = 0 → ∃ y S y = x
3. ∀ x ∀ y S x = S y → x = y
4. ∀ x x + 0 = x
5. ∀ x ∀ y x + S y = S ( x + y )
6. ∀ x x × 0 = 0
7. ∀ x ∀ y x × S y = ( x × y ) + x .

IΣ _n est l'arithmétique Peano du premier ordre avec récurrence restreinte à Σ _n formules (pour n = 0, 1, 2, ...). La théorie IΣ ₀ est souvent notée IΔ ₀ . Il s'agit d'une série de fragments de plus en plus puissants de l'arithmétique Peano. Le cas n  = 1 a à peu près la même force que l'arithmétique récursive primitive (PRA). L'arithmétique des fonctions exponentielles (EFA) est IΣ ₀ avec un axiome indiquant que x ^y existe pour tous les x et y (avec les propriétés usuelles).

Arithmétique Peano de premier ordre , PA . La théorie "standard" de l'arithmétique. Les axiomes sont les axiomes de l' arithmétique de Robinson ci-dessus, ainsi que le schéma d'axiomes de l'induction:

• ${\ displaystyle \ phi (0) \ wedge (\ forall x \ phi (x) \ rightarrow \ phi (Sx)) \ rightarrow (\ forall x \ phi (x))}$ pour toute formule φ dans la langue de PA . φ peut contenir des variables libres autres que x .

L'article de 1931 de Kurt Gödel a prouvé que PA est incomplet et n'a pas de complétions récursivement énumérables cohérentes.

Arithmétique complète (aussi connu comme vrai arithmétique ) est la théorie du modèle standard de l' arithmétique, les nombres naturels N . Il est complet mais n'a pas un ensemble d'axiomes récursivement énumérables.

Pour les nombres réels , la situation est légèrement différente: le cas qui inclut juste l'addition et la multiplication ne peut pas coder les entiers, et donc le théorème d'incomplétude de Gödel ne s'applique pas . Des complications surviennent lors de l'ajout de symboles de fonction supplémentaires (par exemple, l'exponentiation).

Arithmétique du second ordre

L'arithmétique du second ordre peut faire référence à une théorie du premier ordre (malgré le nom) avec deux types de variables, considérées comme variant sur des entiers et des sous-ensembles d'entiers. (Il existe également une théorie de l'arithmétique en logique du second ordre qui est appelée arithmétique du second ordre. Elle n'a qu'un seul modèle, contrairement à la théorie correspondante en logique du premier ordre, qui est incomplète.) La signature sera typiquement la signature 0, S , +, × d'arithmétique, avec une relation d'appartenance ∈ entre les entiers et les sous-ensembles (bien qu'il existe de nombreuses variations mineures). Les axiomes sont ceux de l' arithmétique de Robinson , ainsi que les schémas d'axiomes d' induction et de compréhension .

Il existe de nombreuses sous-théories différentes de l'arithmétique du second ordre qui diffèrent dans les formules autorisées dans les schémas d'induction et de compréhension. Par ordre croissant de résistance, cinq des systèmes les plus courants sont

• ${\ displaystyle {\ mathsf {RCA}} _ {0}}$ , Compréhension récursive
• ${\ displaystyle {\ mathsf {WKL}} _ {0}}$ , Le lemme de Weak König
• ${\ displaystyle {\ mathsf {ACA}} _ {0}}$ , Compréhension arithmétique
• ${\ displaystyle {\ mathsf {ATR}} _ {0}}$ , Récursivité transfinie arithmétique
• ${\ displaystyle \ Pi _ {1} ^ {1} {\ mbox {-}} {\ mathsf {CA}} _ {0}}$ , compréhension ${\ displaystyle \ Pi _ {1} ^ {1}}$

Celles-ci sont définies en détail dans les articles sur l' arithmétique du second ordre et les mathématiques inverses .

Définir des théories

La signature habituelle de la théorie des ensembles a une relation binaire ∈, aucune constante et aucune fonction. Certaines des théories ci-dessous sont des "théories de classe" qui ont deux sortes d'objets, d'ensembles et de classes. Il existe trois façons courantes de gérer cela dans la logique du premier ordre:

1. Utilisez une logique de premier ordre avec deux types.
2. Utilisez la logique ordinaire du premier ordre, mais ajoutez un nouveau prédicat unaire "Set", où "Set ( t )" signifie de manière informelle " t est un ensemble".
3. Utilisez la logique ordinaire du premier ordre, et au lieu d'ajouter un nouveau prédicat au langage, traitez "Set ( t )" comme une abréviation pour "∃ y t ∈ y "

Certaines théories des ensembles de premier ordre incluent:

• Théories faibles manquant de pouvoirs :
  • S ' (Tarski, Mostowski et Robinson, 1953); (finement axiomatisable)
  • Théorie des ensembles de Kripke – Platek ; KP;
  • Théorie des ensembles de poche
  • Théorie générale des ensembles , GST
  • Théorie constructive des ensembles , CZF
• Théorie des ensembles de Mac Lane et théorie des topos élémentaires
• Théorie des ensembles de Zermelo ; Z
• Théorie des ensembles de Zermelo – Fraenkel ; ZF, ZFC;
• Théorie des ensembles de Von Neumann – Bernays – Gödel ; NBG; (finement axiomatisable)
• Théorie des ensembles d'Ackermann ;
• Théorie des ensembles de Scott-Potter
• Nouvelles fondations ; NF (finement axiomatisable)
• Théorie des ensembles positive
• Théorie des ensembles de Morse – Kelley ; MK;
• Théorie des ensembles de Tarski – Grothendieck ; TG;

Certains axiomes supplémentaires du premier ordre qui peuvent être ajoutés à l'un de ceux-ci (généralement ZF) incluent:

• axiome de choix , axiome de choix dépendant
• Hypothèse du continuum généralisé
• L'axiome de Martin (généralement avec la négation de l'hypothèse du continuum), le maximum de Martin
• ◊ et ♣
• Axiome de constructibilité (V = L)
• axiome de forçage approprié
• déterminabilité analytique , déterminabilité projective , Axiome de déterminabilité
• De nombreux grands axiomes cardinaux

Voir également

• Glossaire des domaines des mathématiques
• Liste des théories mathématiques

Les références

Lectures complémentaires

• Chang, CC; Keisler, H.Jerome (1989), Model Theory (3 éd.), Elsevier , ISBN   0-7204-0692-7
• Hodges, Wilfrid (1997), Une théorie des modèles plus courte , Cambridge University Press , ISBN   0-521-58713-1 CS1 maint: paramètre découragé ( lien )
• Marker, David (2002), Model Theory: An Introduction , Graduate Texts in Mathematics , 217 , Springer, ISBN   0-387-98760-6