Проблема алгебры средней школы Тарскиса - Tarskis high school algebra problem - Wikipedia

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

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

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

Икс + у = у + Икс
(Икс + у) + z = Икс + (у + z)
Икс · 1 = Икс
Икс · у = у · Икс
(Икс · у) · z = Икс · (у · z)
Икс · (у + z) = Икс · у + Икс ·z
1^Икс = 1
Икс¹ = Икс
Икс^у + z = Икс^у · Икс^z
(Икс · у)^z = Икс^z · у^z
(Икс^у)^z = Икс^у · z.

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

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

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

${ displaystyle { begin {align} (x + 1) ^ {2} & = (x + 1) ^ {1 + 1} & = (x + 1) ^ {1} cdot (x + 1 ) ^ {1} && { text {by 9.}} & = (x + 1) cdot (x + 1) && { text {by 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. и 3.}} & = x ^ {1} cdot x ^ {1} + x cdot (1 + 1) +1 && { text {на 8. и 6.}} & = x ^ {1 + 1} + x cdot 2 + 1 && { text {by 9.}} & = x ^ {2} +2 cdot x + 1 && { text {на 4.}} end {выровнено}}}$

Здесь скобки опущены, когда аксиома 2 говорит нам, что нет никакой путаницы в отношении группирования.

Длина доказательств не является проблемой; доказательства идентичности, аналогичной приведенной выше, для таких вещей, как (Икс + у)¹⁰⁰ потребует много строк, но на самом деле потребует немного большего, чем приведенное выше доказательство.

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

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

Решение

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

{ displaystyle { begin {align} & 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 {align}}}

Это тождество обычно обозначают W(Икс,у) и верно для всех натуральных чисел Икс и у, как видно из факторинга ${ Displaystyle (1-х + х ^ {2}) ^ {ху}}$ вне вторых сроков; все же это нельзя доказать с помощью одиннадцати аксиом средней школы.

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

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

Обобщения

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

Еще одна проблема, вытекающая из результата Уилки, который остается открытым, заключается в том, что спрашивает, какой наименьший алгебра для чего W(Икс, у) неверно, но приведенные выше одиннадцать аксиом верны. В 1985 г. была найдена алгебра из 59 элементов, удовлетворяющая аксиомам, но для которой W(Икс, у) было ложным.^[4] С тех пор были найдены более мелкие такие алгебры, и теперь известно, что наименьшая такая алгебра должна иметь 11 или 12 элементов.^[9]

Примечания

^ ^а ^б Стэнли Беррис, Саймон Ли, Личность Тарского в средней школе, Американский математический ежемесячный журнал, 100, (1993), № 3, стр. 231–236.
^ Строго говоря, экспоненциальное кольцо имеет экспоненциальную функцию E который принимает каждый элемент Икс к чему-то, что действует как а^Икс на фиксированный номер а. Но небольшое обобщение дает аксиомы бинарной операции возведения в степень. Отсутствие аксиом об аддитивных инверсиях означает, что эти аксиомы описывали экспоненциальную коммутативное полукольцо, за исключением того, что в аксиомах Тарского также нет аксиом об аддитивных тождествах.
^ Ричард Дедекинд, Was sind und was sollen die Zahlen?, 8te unveränderte Aufl. Фридр. Vieweg & Sohn, Брауншвейг (1960). Английский перевод: Что такое числа и какими они должны быть? Переработано, отредактировано и переведено с немецкого Г. А. Погожельский, У. Райан и У. Снайдер, Монографии RIM по математике, Научно-исследовательский институт математики, (1995).
^ ^а ^б Р. Гуревич, Уравнительная теория положительных чисел с возведением в степень, Proc. Амер. Математика. Soc. 94 № 1, (1985), pp.135–141.
^ А.Дж. Уилки, О возведении в степень - решение школьной задачи Тарского по алгебре, Связь между теорией моделей и алгебраической и аналитической геометрией, Quad. Мат., 6, Кафедра математики, Seconda Univ. Неаполь, Казерта, (2000), стр.107–129.
^ Р. Гуревич, Уравнительная теория положительных чисел с возведением в степень не является конечно аксиоматизируемой, Анналы чистой и прикладной логики, 49: 1–30, 1990.
^ Фиоре, Космо и Балат. Замечания об изоморфизмах типизированных лямбда-исчислений с пустым типом и типом суммы [1]
^ К. Уорд Хенсон, Ли А. Рубель, Некоторые приложения теории Неванлинны к математической логике: тождества экспоненциальных функций, Труды Американского математического общества, т.282 1, (1984), стр.1–32.
^ Цзянь Чжан, Компьютерный поиск контрпримеров личности Уилки, Автоматическое удержание - CADE-20, Springer (2005), стр. 441–451, Дои:10.1007/11532231_32.