Nástupnická funkce - Successor function

V matematiky je funkce nástupce nebo operace nástupce odešle přirozené číslo do další. Nástupnická funkce je označena S , takže S ( n ) = n  + 1. Například S (1) = 2 a S (2) = 3. Nástupnická funkce je jednou ze základních součástí použitých k vytvoření primitivní rekurzivní funkce .

Nástupnické operace jsou také známé jako nulování v kontextu nulové hyperoperace : H 0 ( a , b ) = 1 +  b . V této souvislosti je prodloužení nulování sčítáním , které je definováno jako opakovaná posloupnost.

Přehled

Funkce nástupce je součástí formálního jazyka používaného k vyjádření Peanoových axiomů , které formalizují strukturu přirozených čísel. V této formalizaci je nástupnická funkce primitivní operací na přirozených číslech, ve které jsou definována standardní přirozená čísla a sčítání. Například 1 je definován jako S (0) a sčítání na přirozených číslech je definováno rekurzivně pomocí:

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

To lze použít k výpočtu sčítání jakýchkoli dvou přirozených čísel. Například 5 + 2 = 5 + S (1) = S (5 + 1) = S (5 + S (0)) = S ( S (5 + 0)) = S ( S (5)) = S (6) = 7.

Bylo navrženo několik konstrukcí přirozených čísel v teorii množin. Například John von Neumann sestrojí číslo 0 jako prázdnou množinu {} a nástupce n , S ( n ) jako množinu n  ∪ { n }. Axiom nekonečna pak zaručuje existenci souboru, který obsahuje 0 a je uzavřen s ohledem na S . Nejmenší taková množina je označena N a její členy se nazývají přirozená čísla.

Funkce nástupce je úroveň-0 základem nekonečné Grzegorczyk hierarchie z hyperoperations , použít k vytvoření Navíc , násobení , umocňování , tetration , atd byla studována v roce 1986 v vyšetřování zahrnujícího zobecnění vzorem pro hyperoperations.

To je také jedním z primitivních funkce použité v charakterizaci vyčíslitelnost o rekurzivních funkcí .

Viz také

Reference

  • Paul R. Halmos (1968). Naivní teorie množin . Nostrand.