Школьная задача Тарского по алгебре

В математической логике школьная алгебраическая задача Тарского была вопросом, заданным Альфредом Тарским . Он спрашивает, существуют ли тождества, включающие сложение , умножение и возведение в степень положительных целых чисел , которые нельзя доказать с помощью одиннадцати аксиом на уровне средней школы об этих операциях, которые преподаются в математике . Вопрос был решен в 1980 году Алексом Уилки , показавшим, что такие недоказуемые тождества действительно существуют.

Постановка задачи

Тарский считал следующие одиннадцать аксиом о сложении ('+'), умножении ('·') и возведении в степень стандартными аксиомами, преподаваемыми в средней школе:

1. х + у = у + х
2. ( Икс + у ) + z знак равно Икс + ( у + z )
3. х · 1 = х
4. х · у = у · х
5. ( Икс · y ) · z знак равно Икс · ( y · z )
6. Икс · ( у + z ) знак равно Икс · у + Икс · z
7. 1 ^х  = 1
8. х ¹ = х
9. х ^{y + z} = х ^и · х ^С
10. ( х · у ) ^С = х ^С · и ^С
11. ( х ^и ) ^С = х ^{y · z}

Эти одиннадцать аксиом, иногда называемые школьными идентичностями , связаны с аксиомами бикартовой замкнутой категории или кольца экспонент . Тогда проблема Тарского звучит так: существуют ли тождества, включающие только сложение, умножение и возведение в степень, которые верны для всех положительных целых чисел, но которые нельзя доказать, используя только аксиомы 1–11?

Пример доказуемой личности

Поскольку аксиомы, кажется, перечисляют все основные факты о рассматриваемых операциях, не сразу очевидно, что должно быть что-то доказуемо истинное, что можно утверждать, используя только три операции, но нельзя доказать с помощью аксиом. Однако доказательство, казалось бы, безобидных утверждений может потребовать длинных доказательств с использованием только приведенных выше одиннадцати аксиом. Рассмотрим следующее доказательство того, что $(x+1)^{2}=x^{2}+2\cdot x+1:$

$${\begin{aligned}(x+1)^{2}&=(x+1)^{1+1}\\&=(x+1)^{1}\cdot (x+1)^{1}&&{\text{by 9.}}\\&=(x+1)\cdot (x+1)&&{\text{by two applications of 8.}}\\&=(x+1)\cdot x+(x+1)\cdot 1&&{\text{by 6.}}\\&=x\cdot (x+1)+(x+1)&&{\text{by 4. and 3.}}\\&=(x\cdot x+x\cdot 1)+(x\cdot 1+1)&&{\text{by 6. and 3.}}\\&=x\cdot x+(x\cdot 1+x\cdot 1)+1&&{\text{by two applications of 2.}}\\&=x^{1}\cdot x^{1}+x\cdot (1+1)+1&&{\text{by 6. and two applications of 8.}}\\&=x^{1+1}+x\cdot 2+1&&{\text{by 9.}}\\&=x^{2}+2\cdot x+1&&{\text{by 4.}}\end{aligned}}$$

Строго говоря, мы не должны писать суммы, состоящие более чем из двух слагаемых, без скобок, и поэтому вполне формальное доказательство доказывает тождество $(x+1)^{2}=\left(x^{2}+2\cdot x\right)+1$ (или $(x+1)^{2}=x^{2}+(2\cdot x+1)$) и будет иметь дополнительный набор скобок в каждой строке, начиная с $x\cdot x+(x\cdot 1+x\cdot 1)+1$ далее.

Длина доказательств не является проблемой; доказательства идентичности, аналогичные приведенным выше, для таких вещей, как $(x+y)^{100}$ заняло бы много строк, но на самом деле потребовало бы немного больше, чем приведенное выше доказательство.

История проблемы

Список одиннадцати аксиом можно найти в явном виде записанным в работах Ричарда Дедекинда : хотя они, очевидно, были известны и использовались математиками задолго до этого. Однако Дедекинд был первым, кто, похоже, задавался вопросом, достаточны ли эти аксиомы, чтобы рассказать нам все, что мы хотим знать о целых числах. Этот вопрос был поставлен на прочную основу как проблема логики и теории моделей где-то в 1960-х годах Альфредом Тарским: и к 1980-м годам она стала известна как школьная алгебраическая задача Тарского.

Решение

В 1980 году Алекс Уилки доказал, что не каждое рассматриваемое тождество можно доказать с помощью приведенных выше аксиом. Он сделал это, явно обнаружив такую ​​идентичность. Введя новые функциональные символы, соответствующие многочленам , которые отображают положительные числа в положительные числа, он доказал это тождество и показал, что этих функций вместе с одиннадцатью приведенными выше аксиомами было достаточно и необходимо для его доказательства. Личность, о которой идет речь, $${\begin{aligned}&\left((1+x)^{y}+(1+x+x^{2})^{y}\right)^{x}\cdot \left((1+x^{3})^{x}+(1+x^{2}+x^{4})^{x}\right)^{y}\\={}&\left((1+x)^{x}+(1+x+x^{2})^{x}\right)^{y}\cdot \left((1+x^{3})^{y}+(1+x^{2}+x^{4})^{y}\right)^{x}.\end{aligned}}$$ Это тождество обычно обозначается $W(x,y)$ и верно для всех положительных целых чисел $x$ и $y,$ как можно увидеть с помощью факторинга $(1-x+x^{2})^{xy}$ выход второго фактора с каждой стороны; однако это невозможно доказать с помощью одиннадцати школьных аксиом.

Интуитивно, тождество невозможно доказать, поскольку аксиомы средней школы нельзя использовать для обсуждения многочлена. $1-x+x^{2}.$ Рассуждения об этом многочлене и подчлене $-x$ требует концепции отрицания или вычитания , а их нет в аксиомах средней школы. Без этого невозможно использовать аксиомы для манипулирования полиномом и доказательства его истинных свойств. Результаты, полученные Уилки из его статьи, выражаясь более формальным языком, показывают, что «единственным пробелом» в аксиомах средней школы является неспособность манипулировать полиномами с отрицательными коэффициентами .

В 1988 году Р. Гуревич показал, что не существует конечной аксиоматизации действительных уравнений для положительных натуральных чисел с 1, сложения, умножения и возведения в степень.

Обобщения

Уилки доказал, что существуют утверждения о натуральных числах, которые невозможно доказать с помощью одиннадцати аксиом, приведенных выше, и показал, какая дополнительная информация необходима, прежде чем такие утверждения можно будет доказать. С помощью теории Неванлинны также было доказано, что если ограничить типы принимаемых экспонент, то приведенных выше одиннадцати аксиом будет достаточно для доказательства каждого истинного утверждения.

Другая проблема, вытекающая из результата Уилки и остающаяся открытой, — это вопрос о том, какова наименьшая алгебра , для которой $W(x,y)$ неверно, но одиннадцать аксиом, приведенных выше, верны. В 1985 году была найдена алгебра из 59 элементов, удовлетворяющая аксиомам, но для которой $W(x,y)$ что за ложь. С тех пор были найдены такие алгебры меньшего размера, и теперь известно, что самая маленькая из них должна иметь либо 11, либо 12 элементов.

См. также

• Элементарная функция – Математическая функция
• Арифметика элементарных функций - Система арифметики в теории доказательств
• Теорема Лиувилля (дифференциальная алгебра) - говорит, когда первообразные элементарных функций могут быть выражены как элементарные функции.
• Неэлементарный интеграл - интегралы, не выражаемые в замкнутой форме из элементарных функций.
• Теорема Ричардсона - Неразрешимость равенства действительных чисел

Ссылки

• Стэнли Н. Беррис, Карен А. Йейтс , Сага о школьных идентичностях , Algebra Universalis 52, № 2–3, (2004), стр. 325–342, MR 2161657 .