Гёделева нумерация

Гёделева нумерация — это метод отображения объектов формальной системы (символов, формул, последовательностей формул) на натуральные числа, при котором каждому объекту сопоставляется единственное число (гёделев номер), а по числу однозначно восстанавливается исходный объект. Предложена австрийским логиком и математиком Куртом Гёделем в 1931 году в работе «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» для доказательства теорем о неполноте. Является одним из основополагающих понятий теории доказательств, теории алгоритмов и математической логики, позволяющим свести метаматематические утверждения о свойствах формальных теорий к арифметическим утверждениям о натуральных числах.

Принцип построения

Идея гёделевой нумерации заключается в кодировании синтаксической структуры формального языка с помощью натуральных чисел. Для этого используется факт единственности разложения натурального числа на простые множители (основная теорема арифметики). Процесс построения включает следующие шаги:

• каждому базовому символу формального языка (например, переменным, логическим связкам, кванторам, скобкам) ставится в соответствие натуральное число (код символа) — как правило, нечётное число, чтобы отличать от кодов последовательностей;
• последовательность символов (формула) кодируется перемножением степеней последовательных простых чисел, где основание — простое число, а показатель степени — код символа;
• последовательность формул (доказательство) кодируется аналогичным образом, где показатель степени — гёделев номер формулы.

Например, если символу A присвоен код 2, символу B — код 3, то формула AB будет закодирована числом 2² × 3³ = 4 × 27 = 108. По числу 108, разложив его на простые множители (2² × 3³), можно однозначно восстановить последовательность символов.

Существуют и другие схемы нумерации (например, по основанию системы счисления), однако классическая схема Гёделя, основанная на разложении на простые множители, обеспечивает взаимную однозначность и простоту доказательства базовых свойств.

Свойства

Гёделева нумерация обладает рядом ключевых свойств, позволяющих эффективно передавать метаматематические рассуждения на арифметический язык:

• Однозначность и обратимость: каждому выражению формальной системы соответствует ровно один гёделев номер, и наоборот — по номеру можно восстановить исходное выражение.
• Рекурсивность: множество гёделевых номеров всех формул, аксиом и правил вывода является примитивно рекурсивным, то есть существует алгоритм, позволяющий для любого натурального числа определить, является ли оно гёделевым номером корректного выражения (или доказательства).
• Существование предиката доказательства: существует арифметический предикат Proof(x, y), выражающий, что число x является гёделевым номером доказательства формулы с гёделевым номером y.
• Арифметизация синтаксиса: все синтаксические свойства (является ли выражение формулой, аксиомой, является ли последовательность формул доказательством) выражаются в формальной арифметике (например, в арифметике Пеано) с помощью примитивно рекурсивных функций и предикатов.

Применение

Доказательство теорем Гёделя о неполноте

Гёделева нумерация является ключевым инструментом в доказательстве первой и второй теорем Гёделя о неполноте. Основная идея:

1. С помощью нумерации формулируется утверждение, которое «говорит» о своей собственной недоказуемости: строится формула G, которая в арифметической интерпретации означает, что не существует числа x, являющегося гёделевым номером доказательства формулы с гёделевым номером g (где g — гёделев номер самой формулы G).
2. Если G доказуема, то она утверждает, что недоказуема — противоречие. Если G недоказуема, то она истинна, но недоказуема — система неполна.
3. С помощью нумерации доказывается, что некоторая система не может доказать собственную непротиворечивость.

Теория алгоритмов и вычислимость

Гёделева нумерация широко используется в теории рекурсивных функций и теории вычислимости для:

• эффективной нумерации частичных рекурсивных функций (нумерация Клини);
• сведения алгоритмических проблем к арифметическим утверждениям;
• определения неразрешимых проблем, в частности, проблемы остановки (через самоприменимость).

Математическая лингвистика и компьютерные науки

В компьютерных науках и математической лингвистике нумерация Гёделя применяется для:

• кодирования синтаксиса формальных языков (в теории формальных грамматик);
• построения интерпретаторов и компиляторов при символьных вычислениях;
• реализации процедур доказательства теорем в автоматическом доказательстве.

Модификации и обобщения

Существуют различные модификации гёделевой нумерации:

• Нумерация по системе счисления: для языков с ограниченным алфавитом последовательности символов кодируются как числа в базе, равной количеству символов в алфавите (например, для алфавита из 10 символов — десятичная запись).
• Нумерация Клини: используется для эффективного кодирования рекурсивных функций.
• Полиномиальная нумерация: кодирование с помощью значений многочленов от нескольких переменных (используется в работах Ю. В. Матиясевича и других по неразрешимости диофантовых уравнений).
• Синтаксическая нумерация с деревьями: для формул со сложной структурой используется кодирование с помощью пар чисел, представляющих бинарные деревья разбора (нумерация Тарского).

Критические замечания и ограничения

• Гёделева нумерация существенно опирается на основную теорему арифметики (единственность разложения на простые множители), поэтому она работает только в системах, где эта теорема доказуема. В более слабых арифметиках (например, в арифметике с делением, но без единственности разложения) нумерация может быть не столь эффективной.
• При кодировании произвольных формальных систем, особенно с континуумом символов (несчётные языки), классическая нумерация на натуральных числах не работает — требуется другой подход (например, нумерация на ординалах).
• В компьютерных приложениях гёделева нумерация неэффективна для хранения и обработки формул, так как даже короткие формулы порождают колоссально большие числа (экспоненциальный рост). В современных реализациях используются более компактные схемы кодирования (например, деревья с индексами).

Пример: кодирование простого языка

Рассмотрим минимальный формальный язык с символами:

• Переменные: x, y
• Логическая связка: →
• Скобки: (, )
• Знак равенства: =

Присвоим коды: x — 1, y — 2, → — 3, = — 4, ( — 5, ) — 6.

Тогда формула (x = y) → x кодируется так:

• Последовательность: (, x, =, y, ), →, x
• Коды: 5, 1, 4, 2, 6, 3, 1
• Гёделев номер: 2⁵ × 3¹ × 5⁴ × 7² × 11⁶ × 13³ × 17¹

Вычисление этого числа даёт огромное значение (порядка 10²²), что иллюстрирует быстрый рост размеров гёделевых номеров.

Источники

• Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38, 173–198.
• Клини С. К. Введение в метаматематику. — М.: Иностранная литература, 1957.
• Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971.
• Успенский В. А., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
• Nagel E., Newman J. R. Gödel’s Proof. — New York University Press, 1958.
• Boolos G., Burgess J. P., Jeffrey R. C. Computability and Logic. — Cambridge University Press, 2007.