Gödelnumrering en

Författare: Leandro Alegsa

21-02-2022

Inom formell talteori är en Gödelnumrering en funktion som tilldelar varje symbol och formel i ett formellt språk ett unikt naturligt tal som kallas Gödelnummer (GN). Begreppet användes för första gången av Kurt Gödel för att bevisa sin ofullständighetssats.

En Gödel-nummering kan tolkas som en kodning där varje symbol i en matematisk notation tilldelas ett nummer, och en ström av naturliga tal kan då representera någon form eller funktion. En numrering av mängden beräkningsbara funktioner kan då representeras av en ström av Gödel-nummer (även kallade effektiva nummer). Rogers ekvivalenssats anger kriterier för vilka numreringar av mängden beräkningsbara funktioner som är Gödel-nummer.

Definition

Givet en räknebar mängd S är en Gödel-nummering en injektiv funktion

f : S → N {\displaystyle f:S\till \mathbb {N} } $f:S\to \mathbb {N}$

med både f och f - 1{\displaystyle f^{-1}} $f^{-1}$ (inversen av f) är beräkningsbara funktioner.

Exempel

Basnotation och strängar

Ett av Gödels enklaste numreringssystem används dagligen: Korrespondensen mellan heltal och deras representationer som symbolsträngar. Till exempel är sekvensen 2 3 enligt en särskild uppsättning regler en motsvarighet till talet tjugotre. På samma sätt kan symbolsträngar från ett alfabet med N symboler kodas genom att identifiera varje symbol med ett tal från 0 till N och läsa strängen som bas N+1-representationen av ett heltal.

Frågor och svar

F: Vad är en Gödel-numrering?

S: En Gödel-numrering är en funktion som tilldelar ett unikt naturligt tal till varje symbol och formel i ett formellt språk, kallat ett Gödel-nummer (GN).

F: Vem använde först begreppet Gödel-numrering?

S: Kurt Gödel använde först begreppet Gödel-numrering för att bevisa sitt ofullständighetsteorem.

F: Hur kan vi tolka Gödels numrering?

S: Vi kan tolka Gödels numrering som en kodning där varje symbol i en matematisk notation tilldelas ett tal, och en ström av naturliga tal kan representera någon form eller funktion.

F: Vad kallar vi de naturliga tal som tilldelats av en Gödel-numrering?

S: De naturliga tal som tilldelas genom en Gödel-numrering kallas Gödel-tal eller effektiva tal.

F: Vad säger Rogers ekvivalenssats?

S: Rogers ekvivalenssats anger kriterier för vilka numreringar av mängden beräkningsbara funktioner som är Gödel-numreringar.

F: Vad representeras av en ström av Gödel-tal?

S: En numrering av mängden beräkningsbara funktioner kan representeras av en ström av Gödeltal.

Fråga: Varför är Gödels numrering viktig i formell talteori?

S: Gödels numrering är viktig inom formell talteori eftersom den ger ett sätt att representera matematiska formler och funktioner som naturliga tal, vilket gör det möjligt att bevisa viktiga satser som ofullständighetssatsen.