vignette|Le raisonnement par récurrence est comme une suite de dominos. Si la propriété est vraie au rang n0 (i. e. le premier domino de numéro 0 tombe) et si sa véracité au rang n implique celle au rang n + 1 (i. e. la chute du domino numéro n fait tomber le domino numéro n + 1) alors la propriété est vraie pour tout entier (i. e. tous les dominos tombent).
En mathématiques, le raisonnement par récurrence (ou par induction, ou induction complète) est une forme de raisonnement visant à démontrer une propriété portant sur tous les entiers naturels. Le raisonnement par récurrence consiste à démontrer les points suivants :
la propriété est satisfaite par un entier n0 (généralement 0 ou 1) ;
chaque fois que cette propriété est satisfaite par un certain nombre entier naturel n ≥ n0, elle est également satisfaite par son successeur, c'est-à-dire par le nombre entier n + 1.
Une fois cela établi, on en conclut que cette propriété est vraie pour tous les nombres entiers naturels supérieurs ou égaux à n0.
Le raisonnement par récurrence établit une propriété importante des entiers naturels : celle d'être construits à partir d'un entier n0 en itérant le passage au successeur. Dans une présentation axiomatique des entiers naturels, il est directement formalisé par un axiome. Moyennant certaines propriétés des entiers naturels, il est équivalent à d'autres propriétés de ceux-ci, en particulier l'existence d'un minimum à tout ensemble non vide (bon ordre), ce qui permet donc une axiomatisation alternative reposant sur cette propriété.
Certaines formes de ce raisonnement se généralisent d'ailleurs naturellement à tous les bons ordres infinis (pas seulement celui sur les entiers naturels), on parle alors de récurrence transfinie, ou de récurrence ordinale (tout bon ordre est isomorphe à un ordinal) ; le terme d’induction est aussi souvent utilisé dans ce contexte. Le raisonnement par récurrence peut se généraliser enfin aux relations bien fondées.
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.
Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
En mathématiques, un entier naturel est un nombre permettant fondamentalement de compter des objets considérés comme des unités équivalentes : un jeton, deux jetons... une carte, deux cartes, trois cartes... Un tel nombre entier peut s'écrire avec une suite finie de chiffres en notation décimale positionnelle (sans signe et sans virgule). L’étude des entiers naturels est l’objet de l’arithmétique, branche des mathématiques, constituée dès l'Antiquité grecque.
vignette|Giuseppe Peano En mathématiques, les axiomes de Peano sont des axiomes pour l'arithmétique proposés initialement à la fin du par Giuseppe Peano, et qui connaissent aujourd'hui plusieurs présentations qui ne sont pas équivalentes, suivant la théorie sous-jacente, théorie des ensembles, logique du second ordre ou d'ordre supérieur, ou logique du premier ordre. Richard Dedekind avait proposé une formalisation assez proche, sous une forme non axiomatique.
La logique mathématique ou métamathématique est une discipline des mathématiques introduite à la fin du , qui s'est donné comme objet l'étude des mathématiques en tant que langage. Les objets fondamentaux de la logique mathématique sont les formules représentant les énoncés mathématiques, les dérivations ou démonstrations formelles représentant les raisonnements mathématiques et les sémantiques ou modèles ou interprétations dans des structures qui donnent un « sens » mathématique générique aux formules (et parfois même aux démonstrations) comme certains invariants : par exemple l'interprétation des formules du calcul des prédicats permet de leur affecter une valeur de vérité'.
Unsupervised template induction over email data is a central component in applications such as information extraction, document classification, and auto-reply. The benefits of automatically generating