En lógica matemática , la función β de Gödel es una función que se utiliza para permitir la cuantificación sobre secuencias finitas de números naturales en las teorías formales de la aritmética. La función β se usa, en particular, para mostrar que la clase de funciones definibles aritméticamente está cerrada bajo la recursividad primitiva y, por lo tanto, incluye todas las funciones recursivas primitivas .
La función β se introdujo sin el nombre en la demostración del primero de los teoremas de incompletitud de Gödel (Gödel 1931). El lema de la función β que se da a continuación es un paso esencial de esa demostración. Gödel dio a la función β su nombre en (Gödel 1934).
Definición
La La función toma tres números naturales como argumentos. Se define como
dónde denota el resto después de la división entera de por (Mendelson 1997: 186).
Propiedades
La función β se puede definir aritméticamente de una manera obvia, porque utiliza solo operaciones aritméticas y la función restante, que se puede definir aritméticamente. Por lo tanto, es representable en la aritmética de Robinson y en teorías más fuertes como la aritmética de Peano . Al fijar los dos primeros argumentos de manera apropiada, se puede arreglar que los valores obtenidos variando el argumento final de 0 an se ejecuten a través de cualquier tupla especificada ( n +1) de números naturales (el lema β descrito en detalle a continuación). Esto permite simular la cuantificación sobre secuencias de números naturales de longitud arbitraria, lo que no se puede hacer directamente en el lenguaje de la aritmética, mediante la cuantificación sobre solo dos números, para ser utilizados como los dos primeros argumentos de la función β .
Concretamente, si f es una función definida por recursión primitiva en un parámetro n , por ejemplo por f (0) = c y f ( n +1) = g ( n , f ( n )), a continuación, para expresar f ( n ) = y uno quisiera decir: existe una secuencia a 0 , a 1 ,…, a n tal que a 0 = c , a n = y y para todo i < n uno tiene g ( i , a i ) = a i +1 . Si bien eso no es posible directamente, se puede decir en cambio: existen números naturales a y b tales que β ( a , b , 0) = c , β ( a , b , n ) = y y para todo i < n uno tiene g ( i , β ( a , b , i )) = β ( a , b , i +1).
El lema de la función β
La utilidad de la función β proviene del siguiente resultado, que es el propósito de la función β en la prueba de incompletitud de Gödel (Gödel 1931). Este resultado se explica con más detalle que en la demostración de Gödel en (Mendelson 1997: 186) y (Smith 2013: 113-118).
- lema de la función β . Para cualquier secuencia de números naturales ( k 0 , k 1 , ..., k n ), hay números naturales b y c de tal manera que, para cada número natural 0 ≤ i ≤ n , β ( b , c , i ) = k i .
La demostración del lema de la función β hace uso del teorema del resto chino .
Ver también
Referencias
- Martin Davis , ed. (1965). Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Publicaciones de Dover . ISBN 9-780-48643-2281.
- Kurt Gödel (1931). "Über formal unentscheidbare Sätze der" Principia Mathematica "und verwandter Systeme I". Monatshefte für Mathematik und Physik (en alemán). 28 : 173-198. en (Gödel 1986)
- Kurt Gödel (1934). "Sobre proposiciones indecidibles de sistemas matemáticos formales".Notas tomadas por Stpehen C. Kleene y John B. Rosser durante las conferencias impartidas en el Instituto de Estudios Avanzados. Reimpreso en (Davis 1965)
- Kurt Gödel (1986). Solomon Feferman; John W. Dawson Jr; Stephen C. Kleene; Gregory H. Moore; Robert M. Solovay; Jean van Heijenoort (eds.). Kurt Gödel - Obras completas (en alemán e inglés). I - Publicaciones 1929-1936. Prensa de la Universidad de Oxford . ISBN 0-195-14720-0.
- Elliott Mendelson (1997). Introducción a la lógica matemática (4ª ed.). Prensa CRC . ISBN 0-412-80830-7.
- Wolfgang Rautenberg (2010). Una introducción concisa a la lógica matemática (3ª ed.). Nueva York : Springer Science + Business Media . pag. 244. doi : 10.1007 / 978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
- Peter Smith (2013). Introducción a los teoremas de Gödel (2ª ed.). Reino Unido : Cambridge University Press . ISBN 978-1-107-02284-3.