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

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

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

А структура на языке ПА это рекурсивный если есть рекурсивный функции + и × из к , рекурсивное двухместное отношение <на , и выделенные константы такой, что

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

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

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

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

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

С помощью методов, используемых для кодирования упорядоченных кортежей, каждый элемент можно рассматривать как код для набора элементов M. В частности, если мы положим быть яй прайм в M, тогда . Каждый набор будет ограничен M, но если Икс нестандартно, то множество может содержать бесконечно много стандартных натуральных чисел. В стандартная система модели это коллекция . Можно показать, что стандартная система любой нестандартной модели ПА содержит нерекурсивное множество, либо обращаясь к теорема о неполноте или непосредственно рассматривая пару рекурсивно неразделимый r.e. наборы (Kaye 1991: 154). Это непересекающиеся т. П. наборы так что нет рекурсивного набора с и .

Для последней конструкции начнем с пары рекурсивно неразделимых r.e. наборы А и B. Для натурального числа Икс Существует у такое, что для всех я <х, если тогда и если тогда . Посредством переливать свойство, это означает наличие нестандартной Икс в M для которого существует (обязательно нестандартный) у в M так что для каждого с , у нас есть

Позволять - соответствующее множество в стандартной системе M. Потому что А и B r.e., можно показать, что и . Следовательно S является разделяющим множеством для А и B, и выбором А и B это означает S нерекурсивно.

Теперь, чтобы доказать теорему Тенненбаума, начнем с нестандартной счетной модели M и элемент а в M так что нерекурсивно. Метод доказательства показывает, что из-за способа определения стандартной системы можно вычислить характеристическую функцию множества S с помощью функции сложения из M как оракул. В частности, если это элемент M соответствующий 0, и это элемент M соответствует 1, то для каждого мы можем вычислить (я раз). Чтобы решить, если номер п в S, сначала вычислить п, то пй прайм в N. Затем найдите элемент у из M так что

для некоторых . Этот поиск будет остановлен, потому что Евклидов алгоритм может применяться к любой модели PA. Наконец, у нас есть если и только если я в поиске нашел был 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