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. L'arithmétique du second ordre permet la quantification non seulement sur les nombres entiers naturels, comme l'arithmétique de Peano, mais aussi sur les ensembles d'entiers naturels. Elle comprend en particulier une version du schéma d'axiomes de compréhension restreinte aux ensembles d'entiers naturels, qui est exprimable grâce à ces nouvelles quantifications. Le raisonnement par récurrence s'exprime par un seul axiome.
Elle permet en particulier de traiter les nombres réels, qui peuvent être représentés comme des ensembles infinis d'entiers, et de développer l'analyse usuelle. Pour cette raison, les logiciens l'appellent également « analyse »[1].
L'arithmétique de second ordre peut aussi être considérée comme une version faible de la théorie des ensembles dans laquelle chaque élément est soit un entier naturel, soit un ensemble d'entiers naturels. Bien qu'elle soit plus faible que la théorie des ensembles de Zermelo-Fraenkel, au sens où il existe des énoncés de l'arithmétique du second ordre démontrables en théorie des ensembles, mais pas en arithmétique du second ordre, elle permet de prouver l'essentiel des résultats des mathématiques classiques exprimables dans son langage.
L'arithmétique du second ordre, et surtout certains de ses sous-systèmes, construits essentiellement à partir de restrictions des schémas d'axiomes de compréhension et de récurrence, jouent un rôle important pour les mathématiques à rebours.
Définition
modifierSyntaxe
modifierLe langage de l'arithmétique du second ordre traite deux sortes d'objets : les termes d'individus, dont les variables sont généralement désignées par des lettres minuscules et interprétés par des nombres entiers, et les « variables d'ensemble », « variables de classe » ou même « prédicats » (il n'y a généralement pas d'autres termes que les variables au niveau des ensembles) qui sont habituellement désignées par des majuscules et interprétés par des sous-ensembles d'entiers, éventuellement de uples d'entiers, ou de façon équivalentes de prédicat sur les entiers. Les individus et les variables fixes peuvent être quantifiés universellement ou existentiellement. Une formule du langage sans variables d'ensemble liées (c'est-à-dire sans quantifications portant sur les ensembles d'entiers) est appelée arithmétique. Une formule arithmétique peut avoir des variables d'ensemble libres et des variables d'individu liées.
Par exemple, dans le langage de signature , , est une formule arithmétique : elle a une variable d'ensemble libre X et une variable d'individu n liée, tandis que est une formule qui n'est pas arithmétique, ayant une variable d'ensemble liée X.
Sémantique
modifier
Il existe deux sémantiques courantes de la logique du second ordre, et donc de l'arithmétique du second ordre. La première en apparence la plus intuitive est dite « sémantique standard », ou « sémantique des modèles pleins ». Le domaine d'interprétation des variables d'ensembles est celui de toutes les parties du domaine d'interprétation des individus, à priori l'ensemble des entiers naturels. La quantification universelle du second ordre portera alors sur tous les sous-ensembles d'entiers naturels. Il ne peut exister de théorème de complétude pour cette sémantique. Dit autrement il n'y a pas d'axiomatisation satisfaisante pour une telle sémantique.
Une sémantique plus générale autorise des modèles où les variables d'ensembles sont interprétées sur un ensemble quelconque de parties du domaine d'interprétation des individus, pourvu qu'il satisfasse le schéma d'axiomes de compréhension. Un exemple est celui des modèles pleins, mais il existe aussi des modèles où le domaine d'interprétation des variables d'ensemble est un sous-ensemble strict du domaine d'interprétation des variables (Shapiro 1991, p. 74-75), il peut par exemple être dénombrable. Leon Henkin (en) a démontré le théorème de complétude pour cette sémantique.
Axiomes
modifierLes axiomes suivants sont connus sous le nom d'axiomes de base, ou parfois axiomes de Robinson. La théorie du premier ordre résultante, connue sous le nom d'arithmétique de Robinson, est essentiellement l'arithmétique de Peano sans l'induction. Le domaine du discours pour les variables quantifiées est les entiers naturels, notés N, y compris le membre , appelé « zéro ».
Les fonctions primitives sont la fonction successeur unaire, notée par le préfixe Et deux opérations binaires, l'addition et la multiplication, notées « + » et « » respectivement. Il existe également une relation binaire primitive notée « < ».
Axiomes régissant la fonction successeur et zéro:
- 1. (« Le successeur d'un entier naturel n'est jamais nul »)
- 2. (« La fonction successeur est injective »)
- 3. (« Chaque entier naturel est zéro ou un successeur »)
![{\displaystyle \forall m[Sm=0\rightarrow \bot ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0a8f3ffca8c5cc849df18690f46bf1e8d2bab3b)
![{\displaystyle \forall m\forall n[Sm=Sn\rightarrow m=n].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df7fdd8e9d172deeab2412d40a53bc1091cd7839)
![{\displaystyle \forall n[0=n\lor \exists m[Sm=n]].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17a818e8072d48fb1e448d64e9d227434cb3e9ba)
Addition définie récursivement:
- 4.
- 5.
![{\displaystyle \forall m[m+0=m].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ffd7e3100e9303ccb01ab4a4be980abc190cc80)
![{\displaystyle \forall m\forall n[m+Sn=S(m+n)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e474ea6efcfdc12cdcab571a6cdf942c61b4852a)
Multiplication définie récursivement:
- 6.
- 7.
![{\displaystyle \forall m[m\cdot 0=0].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caef550c2bcd17efe0cc5f98fff865def039f2e0)
![{\displaystyle \forall m\forall n[m\cdot Sn=(m\cdot n)+m].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/065e803bdf6d53602cffad597a7d1385762ee4ed)
Axiomes régissant la relation d'ordre « < »:
- 8. (« Aucun entier naturel n'est inférieur à zéro »)
- 9.
- 10. (« Tout entier naturel est égal ou supérieur à zéro »)
- 11.
![{\displaystyle \forall m[m<0\rightarrow \bot ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d037a9e910a8abefe6e02931e8f7a0a56214e74)
![{\displaystyle \forall n\forall m[m<Sn\leftrightarrow (m<n\lor m=n)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/207a5708c22334f5f5f0a08f69521964025cb0ac)
![{\displaystyle \forall n[0=n\lor 0<n].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30c04b939d04aad652f928d0bc933a7cd4f5a4e5)
![{\displaystyle \forall m\forall n[(Sm<n\lor Sm=n)\leftrightarrow m<n].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03b25b287ebba2d74f3889b3038f48e8907e6867)
Ces axiomes sont tous des énoncés de premier ordre. De plus, il n'y a qu'un quantificateur existentiel, dans l'axiome 3. Les axiomes 1 et 2, ainsi qu'un schéma d'axiome d'induction, forment la définition de Peano-Dedekind de N.
Propriétés
modifier Notes et références
modifier- Par exemple Sieg 2013, p. 291.
Bibliographie
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Second-order arithmetic » (voir la liste des auteurs).
- Burgess, J. P. (2005), Fixing Frege, Princeton University Press.
- Buss, S. R. (1998), Handbook of proof theory, Elsevier. (ISBN 0-444-89840-9)
- Friedman, H. (1976), "Systems of second order arithmetic with restricted induction, " I, II (Abstracts). Journal of Symbolic Logic, v. 41, p. 557– 559. JStor
- (en) Girard, Lafont et Taylor, Proofs and types, Cambridge University Press, (ISBN 0-521-37181-3, lire en ligne)
- Hilbert, D. and Bernays, P. (1934), Grundlagen der Mathematik, Springer-Verlag. MR 0237246
- (en) Wilfried Sieg, Hilbert's Programs and Beyond, New York, Oxford University Press, , 439 p. (ISBN 978-0-19-537222-9, lire en ligne)
- Shapiro, S. (1991), Foundations without foundationalism, Oxford University Press. (ISBN 0-19-825029-0)
- (en) Stephen G. Simpson, Subsystems of second order arithmetic, Cambridge University Press, coll. « Perspectives in Logic », , 2e éd., 444 p. (ISBN 978-0-521-88439-6, MR 2517689, lire en ligne)
- Takeuti, G. (1975) Proof theory (ISBN 0-444-10492-5)
- Woodin, W. H. (2001), "The Continuum Hypothesis, Part I", Notices of the American Mathematical Society, v. 48 n. 6.
