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 ». 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.