Теорема Тенненбаумса - Википедия - Tennenbaums theorem

Не путать с конструкцией Тенненбаумом вычислимой копии ${ displaystyle omega + omega ^ {*}}$ не имеющий вычислимых бесконечных восходящих или нисходящих цепочек.

Теорема Тенненбаума, названный в честь Стэнли Тенненбаум кто представил теорему в 1959 г., является результатом математическая логика в котором говорится, что нет счетный нестандартная модель первого порядка Арифметика Пеано (PA) может быть рекурсивным (Kaye 1991: 153ff).

Рекурсивные структуры для ПА

А структура ${ displaystyle M}$ на языке ПА это рекурсивный если есть рекурсивный функции + и × из ${ Displaystyle N раз N}$ к ${ displaystyle N}$, рекурсивное двухместное отношение <на ${ displaystyle N}$, и выделенные константы ${ displaystyle n_ {0}, n_ {1}}$ такой, что

${ Displaystyle (N, oplus, otimes, <_ {M}, n_ {0}, n_ {1}) Equ M,}$

куда ${ Displaystyle Equiv}$ указывает изоморфизм и ${ displaystyle N}$ набор (стандартный) натуральные числа. Поскольку изоморфизм должен быть биекцией, каждая рекурсивная модель счетна. Существует множество неизоморфных счетных нестандартных моделей ПА.

Формулировка теоремы

Теорема Тенненбаума утверждает, что никакая счетная нестандартная модель PA не является рекурсивной. Более того, ни сложение, ни умножение такой модели не могут быть рекурсивными.

Доказательство эскиза

Этот набросок следует аргументу, представленному Кэй (Kaye, 1991). Первый шаг в доказательстве - показать, что если M - любая счетная нестандартная модель PA, то стандартная система M (определенная ниже) содержит хотя бы одно нерекурсивное множество S. Второй шаг - показать, что если операция сложения или умножения M были рекурсивными, то этот набор S будет рекурсивным; противоречие.

С помощью методов, используемых для кодирования упорядоченных кортежей, каждый элемент ${ displaystyle x in M}$ можно рассматривать как код для набора ${ displaystyle S_ {x}}$ элементов M. В частности, если мы положим ${ displaystyle p_ {i}}$ быть яй прайм в M, тогда ${ displaystyle z in S_ {x} leftrightarrow M vDash p_ {z} | x}$. Каждый набор ${ displaystyle S_ {x}}$ будет ограничен M, но если Икс нестандартно, то множество ${ displaystyle S_ {x}}$ может содержать бесконечно много стандартных натуральных чисел. В стандартная система модели это коллекция ${ displaystyle {S_ {x} cap N: x in M ​​}}$. Можно показать, что стандартная система любой нестандартной модели ПА содержит нерекурсивное множество, либо обращаясь к теорема о неполноте или непосредственно рассматривая пару рекурсивно неразделимый r.e. наборы (Kaye 1991: 154). Это непересекающиеся т. П. наборы ${ displaystyle A, B substeq N}$ так что нет рекурсивного набора ${ Displaystyle C substeq N}$ с ${ displaystyle A substeq C}$ и ${ Displaystyle B cap C = emptyset}$.

Для последней конструкции начнем с пары рекурсивно неразделимых r.e. наборы А и B. Для натурального числа Икс Существует у такое, что для всех я <х, если ${ displaystyle i in A}$ тогда ${ displaystyle p_ {i} | y}$ и если ${ displaystyle i in B}$ тогда ${ displaystyle p_ {i} not | y}$. Посредством переливать свойство, это означает наличие нестандартной Икс в M для которого существует (обязательно нестандартный) у в M так что для каждого ${ displaystyle m in M}$ с ${ displaystyle m <_ {M} x}$, у нас есть

${ Displaystyle M vDash (m in A к p_ {m} | y) land (m in B to p_ {m} not | y)}$

Позволять ${ displaystyle S = N cap S_ {y}}$ - соответствующее множество в стандартной системе M. Потому что А и B r.e., можно показать, что ${ displaystyle A substeq S}$ и ${ Displaystyle B cap S = emptyset}$. Следовательно S является разделяющим множеством для А и B, и выбором А и B это означает S нерекурсивно.

Теперь, чтобы доказать теорему Тенненбаума, начнем с нестандартной счетной модели M и элемент а в M так что ${ displaystyle S = N cap S_ {a}}$ нерекурсивно. Метод доказательства показывает, что из-за способа определения стандартной системы можно вычислить характеристическую функцию множества S с помощью функции сложения ${ displaystyle oplus}$ из M как оракул. В частности, если ${ displaystyle n_ {0}}$ это элемент M соответствующий 0, и ${ displaystyle n_ {1}}$ это элемент M соответствует 1, то для каждого ${ displaystyle i in N}$ мы можем вычислить ${ Displaystyle п_ {я} = п_ {1} oplus cdots oplus n_ {1}}$ (я раз). Чтобы решить, если номер п в S, сначала вычислить п, то пй прайм в N. Затем найдите элемент у из M так что

${ displaystyle a = underbrace {y oplus y oplus cdots oplus y} _ {p { text {times}}} oplus n_ {i}}$

для некоторых ${ Displaystyle я <р}$. Этот поиск будет остановлен, потому что Евклидов алгоритм может применяться к любой модели PA. Наконец, у нас есть ${ displaystyle n in S}$ если и только если я в поиске нашел был 0. Т.к. S не рекурсивно, это означает, что операция сложения M нерекурсивно.

Аналогичное рассуждение показывает, что можно вычислить характеристическую функцию S используя умножение M как оракул, поэтому операция умножения на M также нерекурсивен (Kaye 1991: 154).

Рекомендации

• Джордж Булос, Джон П. Берджесс, и Ричард Джеффри (2002) Вычислимость и логика, 4-е изд. Издательство Кембриджского университета. ISBN  0-521-00758-5
• Ричард Кэй (1991) Модели арифметики Пеано. Издательство Оксфордского университета. ISBN  0-19-853213-X.
• Ричард Кэй (сентябрь 2011 г.). «Теорема Тенненбаума для моделей арифметики». В Джульетта Кеннеди и Роман Коссак (ред.). Теория множеств, арифметика и основы математики - теоремы, философии (PDF). Конспект лекций по логике. 36. ISBN  9781107008045.
• Стэнли Тенненбаум (1959) Неархимедовы модели для арифметики, В: Уведомления Американского математического общества 6, стр. 270