Введение
В математической логике, нумерация Гёделя — это функция, которая присваивает каждому символу и правильно сформированной формуле некоторого формального языка уникальное натуральное число, называемое числом Гёделя. Эта концепция была разработана Куртом Гёделем для доказательства его теорем о неполноте. Нумерацию Гёделя можно интерпретировать как кодирование, в котором каждому символу математической записи присваивается число, после чего последовательность натуральных чисел может представлять последовательность символов. Эти последовательности натуральных чисел, в свою очередь, могут быть представлены одним натуральным числом, что облегчает их обработку в формальных теориях арифметики. С момента публикации работы Гёделя в 1931 году термин "нумерация Гёделя" или "код Гёделя" используется для обозначения более общих способов присвоения натуральных чисел математическим объектам.
numberings of the set of computable functions
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his incompleteness theorems. A Gödel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, after which a sequence of natural numbers can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic. Since the publishing of Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects.
Упрощенный обзор
Гёдель отметил, что каждое утверждение в системе может быть представлено натуральным числом (его числом Гёделя). Важность этого заключалась в том, что свойства утверждения – такие как его истинность или ложность – оказывались эквивалентны определению того, обладают ли определенные свойства его число Гёделя. Сами числа могут быть очень большими, но это не является препятствием; главное, что такие числа можно построить. Проще говоря, он разработал метод, с помощью которого каждой формуле или утверждению, которые можно сформулировать в системе, присваивается уникальное число, таким образом, что формулы и числа Гёделя можно механически преобразовывать друг в друга. Существует множество способов это сделать. Простой пример – способ хранения английского языка в виде последовательности чисел в компьютерах с использованием ASCII. Поскольку коды ASCII находятся в диапазоне от 0 до 127, достаточно дополнить их до 3 десятичных цифр и затем объединить: Слово "hello" представлено числом 104101108108111, а логическая формула "p ∧ q" представлена числом 80978111.
The word is represented by The logical formula is represented by .
Кодирование Гёделя
числовые переменные собственные переменные Символ 0 s ¬ ∨ ∀ ( ) x1 x2 x3 P1 P2 P3 Число 1 3 5 7 9 11 13 17 19 23 289 361 529 + оригинальное кодирование Гёделя
Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing. To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:
According to the fundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded). Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof. There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.
Гёдель использовал систему, основанную на разложении на простые множители. Он сначала присвоил уникальное натуральное число каждому базовому символу в формальном языке арифметики, с которым он работал. Для кодирования целой формулы, которая является последовательностью символов, Гёдель использовал следующую систему. Для заданной последовательности положительных целых чисел кодирование Гёделя последовательности представляет собой произведение первых n простых чисел, возведенных в соответствующие степени, указанные в последовательности:
Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing. To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:
According to the fundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded). Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof. There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.
Согласно основной теореме арифметики, любое число (и, в частности, число, полученное таким образом) может быть однозначно разложено на простые множители, поэтому можно восстановить исходную последовательность из её числа Гёделя (для любого заданного числа n символов, которые необходимо закодировать). Гёдель использовал эту схему на двух уровнях: во-первых, для кодирования последовательностей символов, представляющих формулы, и во-вторых, для кодирования последовательностей формул, представляющих доказательства. Это позволило ему установить соответствие между утверждениями о натуральных числах и утверждениями о доказуемости теорем о натуральных числах – ключевое наблюдение в доказательстве. Существуют более сложные (и более компактные) способы построения нумерации Гёделя для последовательностей.
Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing. To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:
According to the fundamental theorem of arithmetic, any number (and, in particular, a number obtained in this way) can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded). Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof. There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.
Пример
В специальной нумерации Гёделя, используемой Нагелем и Ньюманом, число Гёделя для символа "0" равно 6, а число Гёделя для символа "=" равно 5. Следовательно, в их системе число Гёделя формулы "0 = 0" составляет 26 × 35 × 56 = 243 000 000.
Отсутствие уникальности
Бесконечно много различных нумераций Гёделя возможно. Например, предположим, что существует K основных символов, альтернативная нумерация Гёделя может быть построена посредством обратимого отображения этого набора символов (например, с помощью обратимой функции h) на множество цифр в биективной системе счисления по основанию K. Формула, состоящая из строки из n символов, тогда будет отображена в число
Другими словами, если расположить набор из K основных символов в некотором фиксированном порядке, так что i-й символ однозначно соответствует i-й цифре биективной системы счисления по основанию K, то каждая формула может служить просто числовым представлением своего собственного числа Гёделя. Например, в описанной здесь нумерации K=1000.
Рекурсия
Можно использовать нумерацию Гёделя, чтобы показать, что функции, определяемые рекурсией по значению, на самом деле являются примитивно рекурсивными функциями.
Обобщения
В теории вычислимости термин "нумерация Гёделя" используется в более широком контексте, чем описанный выше. Он может относиться к: любому сопоставлению элементов формального языка натуральным числам таким образом, что эти числа можно обрабатывать алгоритмически для имитации манипуляций с элементами формального языка. В более общем смысле, это сопоставление элементов счётного математического объекта, например счётной группы, натуральным числам, позволяющее алгоритмически манипулировать этим объектом. Кроме того, термин "нумерация Гёделя" иногда применяется, когда присваиваемые "числа" фактически являются строками, что необходимо при рассмотрении моделей вычислений, таких как машины Тьюринга, которые оперируют строками, а не числами.
Any assignment of the elements of a formal language to natural numbers in such a way that the numbers can be manipulated by an algorithm to simulate manipulation of elements of the formal language. More generally, an assignment of elements from a countable mathematical object, such as a countable group, to natural numbers to allow algorithmic manipulation of the mathematical object. Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as Turing machines that manipulate strings rather than numbers.
Набор Гёделя
Гёделевы множества иногда используются в теории множеств для кодирования формул и похожи на гёделевы числа, за исключением того, что кодирование выполняется с помощью множеств, а не чисел. В простых случаях, когда для кодирования формул используется наследственно конечное множество, это по существу эквивалентно использованию гёделевых чисел, но несколько проще в определении, поскольку древовидная структура формул может быть смоделирована древовидной структурой множеств. Гёделевы множества также могут использоваться для кодирования формул в инфинитарных языках.