Нумерация Гёделя
В теории формальных чисел нумерация Гёделя - это функция, которая присваивает каждому символу и формуле некоторого формального языка уникальное натуральное число, называемое числом Гёделя (ЧГ). Впервые это понятие было использовано Куртом Гёделем для доказательства его теоремы о неполноте.
Нумерация Гёделя может быть интерпретирована как кодировка, в которой каждому символу математической нотации присваивается число, и поток натуральных чисел может представлять некоторую форму или функцию. Нумерация множества вычислимых функций может быть представлена потоком чисел Гёделя (также называемых эффективными числами). Теорема эквивалентности Роджерса устанавливает критерии, по которым нумерации множества вычислимых функций являются нумерациями Гёделя.
Определение
Учитывая счетное множество S, нумерация Гёделя - это инъективная функция
f : S → N {\displaystyle f:S\to \mathbb {N} } 
причем и f, и f - 1{\displaystyle f^{-1}} 
(обратная f) являются вычислимыми функциями.
Примеры
Базовая нотация и строки
Одна из простейших схем нумерации Гёделя используется каждый день: Соответствие между целыми числами и их представлениями в виде строк символов. Например, последовательность 2 3 по определенному набору правил соответствует числу двадцать три. Аналогично, строки символов из некоторого алфавита из N символов могут быть закодированы путем идентификации каждого символа с числом от 0 до N и чтения строки как представления целого числа по основанию N+1.
Вопросы и ответы
В: Что такое нумерация Гёделя?
О: Нумерация Гёделя - это функция, которая присваивает каждому символу и формуле формального языка уникальное натуральное число, называемое числом Гёделя (ЧГ).
В: Кто впервые использовал концепцию нумерации Гёделя?
О: Курт Гёдель впервые использовал концепцию нумерации Гёделя для доказательства своей теоремы о неполноте.
В: Как мы можем интерпретировать нумерацию Гёделя?
О: Мы можем интерпретировать нумерацию Гёделя как кодировку, в которой каждому символу математической нотации присваивается номер, а поток натуральных чисел может представлять некоторую форму или функцию.
В: Как мы называем натуральные числа, присвоенные нумерацией Гёделя?
О: Натуральные числа, присваиваемые нумерацией Гёделя, называются числами Гёделя или эффективными числами.
В: Что утверждает теорема эквивалентности Роджерса?
О: Теорема эквивалентности Роджерса устанавливает критерии, по которым те нумерации множества вычислимых функций являются нумерациями Гёделя.
В: Что представляет собой поток чисел Гёделя?
О: Нумерация множества вычислимых функций может быть представлена потоком чисел Гёделя.
В: Почему нумерация Гёделя важна в формальной теории чисел?
О: Нумерация Гёделя важна для формальной теории чисел, поскольку она обеспечивает способ представления математических формул и функций в виде натуральных чисел, что позволяет доказать такие важные теоремы, как теорема о неполноте.
