В математической логике , Гёделя β функция является функцией , используемой для разрешения квантификации над конечными последовательностями натуральных чисел в формальных теориях арифметики. Функция β используется, в частности, для демонстрации того, что класс арифметически определяемых функций закрыт относительно примитивной рекурсии и, следовательно, включает в себя все примитивно рекурсивные функции .
Β функция была введена без имени в доказательстве первого из неполноты теорем Геделя (Гёделя 1931). Приведенная ниже лемма о β- функции является важным шагом в этом доказательстве. Гедель назвал β- функцию в (Gödel 1934).
Определение
В функция принимает в качестве аргументов три натуральных числа. Он определяется как
где обозначает остаток от целочисленного деления от (Мендельсон 1997: 186).
Характеристики
Функция β является арифметически определяемой очевидным образом, потому что она использует только арифметические операции и функцию остатка, которая является арифметически определяемой. Поэтому его можно представить в арифметике Робинсона и более сильных теориях, таких как арифметика Пеано . Путем исправления первых двух аргументов соответствующим образом можно организовать, чтобы значения, полученные изменением последнего аргумента от 0 до n, проходили через любой указанный ( n +1) -набор натуральных чисел ( β- лемма подробно описана ниже). Это позволяет моделировать количественную оценку последовательностей натуральных чисел произвольной длины, что невозможно сделать непосредственно на языке арифметики, путем количественной оценки только двух чисел, которые будут использоваться в качестве первых двух аргументов функции β .
Конкретно, если f - функция, определенная примитивной рекурсией по параметру n , скажем, посредством f (0) = c и f ( n +1) = g ( n , f ( n )), то для выражения f ( n ) = у один хотел бы сказать: существует последовательность 0 , 1 , ..., п такое , что 0 = с , п = у , и для всех я < п один имеет г ( я , я ) = а I +1 . Хотя это невозможно напрямую, вместо этого можно сказать: существуют натуральные числа a и b такие, что β ( a , b , 0) = c , β ( a , b , n ) = y и для всех i < n одно имеет g ( i , β ( a , b , i )) = β ( a , b , i +1).
Β функция леммы
Полезность функции β проистекает из следующего результата, который является целью функции β в доказательстве неполноты Гёделя (Gödel 1931). Этот результат объясняется более подробно, чем в доказательстве Гёделя в (Mendelson 1997: 186) и (Smith 2013: 113-118).
- Лемма о β- функции . Для любой последовательности натуральных чисел ( k 0 , k 1 ,…, k n ) существуют такие натуральные числа b и c , что для любого натурального числа 0 ≤ i ≤ n , β ( b , c , i ) = k i .
Доказательство леммы о β- функции использует китайскую теорему об остатках .
Смотрите также
Рекомендации
- Мартин Дэвис , изд. (1965). Неразрешимые - Основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Dover Publications . ISBN 9-780-48643-2281.
- Курт Гёдель (1931). "Суперформальные unentscheidbare Sätze der" Principia Mathematica "und verwandter Systeme I". Monatshefte für Mathematik und Physik (на немецком языке). 28 : 173–198. в (Gödel 1986)
- Курт Гёдель (1934). «О неразрешимых предложениях формальных математических систем».Заметки, сделанные Стпехеном К. Клини и Джоном Б. Россером во время лекций, прочитанных в Институте перспективных исследований. Перепечатано в (Davis 1965)
- Курт Гёдель (1986). Соломон Феферман; Джон У. Доусон младший; Стивен К. Клини; Грегори Х. Мур; Роберт М. Соловей; Жан ван Хейеноорт (ред.). Курт Гёдель - Собрание сочинений (на немецком и английском языках). I - Публикации 1929-1936 гг. Издательство Оксфордского университета . ISBN 0-195-14720-0.
- Эллиотт Мендельсон (1997). Введение в математическую логику (4-е изд.). CRC Press . ISBN 0-412-80830-7.
- Вольфганг Раутенберг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science + Business Media . п. 244. DOI : 10.1007 / 978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
- Питер Смит (2013). Введение в теоремы Гёделя (2-е изд.). Великобритания : Издательство Кембриджского университета . ISBN 978-1-107-02284-3.