Gödel-numerointi

Gödel-numerointi on funktio g , joka antaa jokaiselle jonkin muodollisen kielen objektille sen numeron. Sitä voidaan käyttää seuraavien kieliobjektien eksplisiittiseen luettelemiseen: muuttujat, objektivakiot, funktiosymbolit, predikaattisymbolit ja niistä rakennetut kaavat. Gödel-numeroinnin rakentamista teorian kohteille kutsutaan teorian aritmetisoinniksi - sen avulla voit kääntää väitteitä, aksioomia, lauseita, teorioita aritmeettisiksi kohteiksi . Luettelon g on oltava tehokkaasti laskettavissa ja mille tahansa luonnolliselle luvulle voidaan määrittää, onko se luku vai ei, ja jos on, niin rakentaa vastaava kielen objekti. Gödel-numerointi on hyvin samanlainen kuin merkki merkiltämerkkijonojen koodaus numeroilla, mutta sillä erolla, että kirjainnumerosarjojen koodaamiseen ei käytetä samanpituisten numeroiden ketjuttamista , vaan aritmeettisen peruslauseen .

Gödel käytti Gödel - numerointia työkaluna muodollisen aritmeettisen epätäydellisyyden todistamiseen .

Muunnelma ensimmäisen asteen muodollisen teorian Gödel-numeraatiosta

Olkoon ensimmäisen asteen teoria , joka sisältää muuttujat , objektivakiot , funktiosymbolit ja predikaattisymbolit , jossa on funktionaalisen tai predikaattisymbolin luku ja ariteetti . $\mathrm{K}$ $x_1,x_2,...$ $a_{1},a_{2},...$ $f_{k}^{n}$ $A_{k}^{n}$ $k$ $n$

Jokainen mielivaltaisen ensimmäisen asteen teorian symboli liitetään sen Gödel-numeroon seuraavasti: [1] $u$ $\mathrm{K}$ $g(u)$

$g(()=3;\ g())=5;\ g(,)=7;\ g(\neg )=9;\ g(\to )=11;$

$g(x_{k})=5+8k,\k=1,2,...;$

$g(a_{k})=7+8k,\k=1,2,...;$

$g(f_{k}^{n})=9+8\cdot 2^{n}3^{k},\ k,n\geqslant 1;$

$g(A_{k}^{n})=11+8\cdot 2^{n}3^{k},\ k,n\geqslant 1.$

Mielivaltaisen lausekesarjan Gödel-luku määritellään seuraavasti: . $e_{0},...,e_{r}$ $g(e_{0},...,e_{r})=2^{{g(e_{0})}}\cdot 3^{{g(e_{1})}}\cdot ... \cdot p_{r}^{{g(e_{r})}}$

On myös muita muodollisen aritmeettisen Gödel-numeroinnin.

Esimerkki

$g(A_{1}^{2}(x_{1},x_{2}))=2^{{g(A_{1}^{2})}}\cdot 3^{{g(() }}\cpiste 5^{{g(x_{1})}}\cpiste 7^{{g(,)}}\cpiste 11^{{g(x_{2})}}\cpiste 13^{{ g())}}=2^{{107}}\cpiste 3^{{3}}\cpiste 5^{{13}}\cpiste 7^{{7}}\cpiste 11^{{21}} \cdot 13^{{5}}$

Yleistykset

Yleisesti ottaen joukon numerointia kutsutaan kaikkialla määritellyksi surjektiiviseksi kartoitukseksi . Jos , niin sitä kutsutaan objektin numeroksi . Erityistapaukset - kielet ja teoriat. $F$ $\nu :{\mathbb {N}}\to F$ $\nu(n)=f$ $n$ $f$ $F$

Muistiinpanot

↑ Mendelssohn, 1971 , § 4. Aritmetisointi. Gödel-luvut, s. 151-152.

Kirjallisuus

Klini S.K. Johdatus metamatematiikkaan . - M .: IL, 1957. - 526 s.
Mendelsohn E. Johdatus matemaattiseen logiikkaan . - M . : "Nauka", 1971. - 320 s.

Katso myös

Godelin epätäydellisyyslause