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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (37)

Cours associés (6)

Séances de cours associées (27)

Efficient second-order methods for model compression

Sidak Pal Singh

Second-order information, in the form of Hessian- or Inverse-Hessian-vector products, is a fundamental tool for solving optimization problems. Recently, there has been a tremendous amount of work on u

2020

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

MATH-318: Set theory

Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an

Estimation linéaire MM SE COM-406: Foundations of Data Science

Couvre les principes de l'estimation linéaire MM SE et de la minimisation des erreurs en régression linéaire.

Mélanger les changements de temps des flux d'azote

Déplacez-vous dans le mélange des changements de temps dans les flux nuls, en soulignant la nature délicate du mélange et sa dépendance à l'égard des singularités.

Analyse avancée-ii MATH-105(a): Advanced analysis II

Explore l'unicité des solutions aux équations différentielles, en mettant l'accent sur les solutions globales et la linéarité des équations scalaires de second ordre.

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.

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, , and over functions from to . The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.

vignette|Symboles mathématiques des deux quantificateurs logiques les plus courants.|236px En mathématiques, les expressions « pour tout » (ou « quel que soit ») et « il existe », utilisées pour formuler des propositions mathématiques dans le calcul des prédicats, sont appelées des quantifications. Les symboles qui les représentent en langage formel sont appelés des quantificateurs (ou autrefois des quanteurs). La quantification universelle (« pour tout ... » ou « quel que soit ... ») se dénote par le symbole ∀ (un A à l'envers).