Fonction successeur - Successor function

En mathématiques , la fonction successeur ou l' opération successeur envoie un nombre naturel au suivant. La fonction successeur est notée S , donc S ( n ) = n  + 1. Par exemple, S (1) = 2 et S (2) = 3. La fonction successeur est l'un des composants de base utilisés pour construire une primitive récursive fonction .

Les opérations successeurs sont également appelées zation dans le contexte d'une hyperopération zéro : H 0 ( a , b ) = 1 +  b . Dans ce contexte, l'extension de la zération est l' addition , qui est définie comme une succession répétée.

Aperçu

La fonction successeur fait partie du langage formel utilisé pour énoncer les axiomes de Peano , qui formalisent la structure des nombres naturels. Dans cette formalisation, la fonction successeur est une opération primitive sur les nombres naturels, en fonction de laquelle les nombres naturels standard et l'addition sont définis. Par exemple, 1 est défini comme étant S (0), et l'addition sur les nombres naturels est définie récursivement par :

m + 0 = m ,
m + S ( n ) = S ( m + n ).

Cela peut être utilisé pour calculer l'addition de deux nombres naturels quelconques. Par exemple, 5 + 2 = 5 + S (1) = S (5 + 1) = S (5 + S (0)) = S ( S (5 + 0)) = S ( S (5)) = S (6) = 7.

Plusieurs constructions des nombres naturels au sein de la théorie des ensembles ont été proposées. Par exemple, John von Neumann construit le nombre 0 comme l' ensemble vide {}, et le successeur de n , S ( n ), comme l'ensemble n  { n }. L' axiome de l'infini garantit alors l'existence d'un ensemble contenant 0 et fermé par rapport à S . Le plus petit de ces ensembles est noté N et ses membres sont appelés nombres naturels.

La fonction successeur est le fondement de niveau 0 de la hiérarchie infinie de Grzegorczyk des hyperopérations , utilisée pour construire l' addition , la multiplication , l' exponentiation , la tétration , etc. Elle a été étudiée en 1986 dans une enquête impliquant la généralisation du modèle pour les hyperopérations.

C'est aussi l'une des fonctions primitives utilisées dans la caractérisation de la calculabilité par les fonctions récursives .

Voir également

Les références

  • Paul R. Halmos (1968). Théorie des ensembles naïf . Pas de brin.