3. ЭЛЕМЕНТАРНАЯ АРИФМЕТИКА

3.1. От аксиом Пеано до аксиом элементарной арифметики

Попытаемся получить независимую формализацию средств математического рассуждения, использующих только понятие натурального числа (не упоминая ни действительных чисел, ни - тем более - произвольных множеств Кантора). Это самая надежная часть арсенала математики, не скомпрометировавшая себя парадоксами. Естественно назвать ее элементарной арифметикой (по аналогии с термином "элементарная теория чисел" - в отличие от аналитической теории чисел). Именно эти средства Д.Гильберт хотел использовать для доказательства непротиворечивости всей математики.

Итак, мы будем строить формальную теорию EA, областью изменения переменных которой будет множество {0,1,2,3,...}.

В 1880-х гг. Р.Дедекинд и Дж.Пеано сформулировали аксиомы арифметики, используя единственную константу 0 (нуль) и функциональный символ S (функция следования: S(x)=x+1):

P1) (Ax)~(0=Sx) (нуль не следует ни за каким числом),

P2) (AxAy)(x<>y -> Sx<>Sy) (однозначность функции следования),

P3) если F - любое "свойство" натуральных чисел, то

F(0) & (Ax)(F(x)->F(Sx)) -> (Ax)F(x)

(принцип математической индукции).

Если бы мы занимались построением арифметики натуральных чисел в теории множеств ZF (см. раздел 2.3), то могли бы определить 0 как пустое множество, Sx - как xU{x} и, взяв за основу множество w, могли бы доказать аксиомы Пеано как теоремы ZF. Вместо свойства F фигурировало бы тогда произвольное подмножество w:

(Az)(z<=w & 0 in z & (Ax)(x in z -> xU{x} in z) -> z=w).

Но как быть, если мы не хотим вводить в рассуждения понятие произвольного множества натуральных чисел (произвольного подмножества w), что связано с выходом в теорию множеств Кантора? По-видимому, мы должны при формулировке принципа математической индукции ограничиться свойствами натуральных чисел, которые можно записать формулами нашей теории EA. Но оказывается, что в таком случае "способности" теории зависят от выбора языка (точнее - от выбранного набора функциональных символов).

Если взять по минимуму (как Дж.Пеано) только константу 0 и функциональный символ S, то понятие терма теории EA (для большей точности будем писать EA₀) определяется очень просто:

а) константа 0 и любая переменная - терм EA₀,

б) если t - терм, то St - также терм EA₀.

Таким образом, имеется только два типа термов: SS... S0 (обозначения конкретных натуральных чисел) и SS... Sx (обозначения функций типа x+n, где n - конкретное натуральное число). Элементарными формулами EA₀ будем считать только равенства (t₁ =t₂ ), где t₁, t₂ - термы EA (таким образом, EA₀ не имеет собственных предикатных символов). Из элементарных формул с помощью логических связок ~, &,V,-> и кванторов A, E строятся более сложные формулы EA₀. В качестве аксиом EA₀ принимаются аксиомы P1,P2, а вместо P3 - схема аксиом:

B(0) & (Ax)(B(x) -> B(Sx)) -> (Ax)B(x),

где B(x) - формула на языке EA₀ с одной выделенной свободной переменной x. Кроме x формула B может содержать и другие свободные переменные (параметры).

Теория EA₀ оказывается очень слабой.

Упражнение 3.1. (курсовая работа). Покажите, что в теории EA₀ невозможно определить операцию сложения натуральных чисел - невозможна формула, означающая x+y=z, т.е.формула PLUS(x,y,z) такая, что

EA₀ |- PLUS(x,0,x), (x+0=x),

EA₀ |- (Au)(PLUS(x,y,u)->PLUS(x,Sy,Su)). (x+Sy=S(x+y))

Найдите также алгоритм, позволяющий по замкнутой формуле языка EA определить, доказуема ли она на основе аксиом EA₀ (и убедитесь, что всякая такая формула либо доказуема, либо опровержима) (см. Д.Гильберт, П.Бернайс [1934]). Возможна ли аналогичная формула, выражающая отношение x<y?

Таким образом, теория EA₀ не может представлять серьезного интереса - в ней невозможно обсуждать даже операцию сложения натуральных чисел. Простейший шаг вперед - добавить к языку EA₀ "недостающий" функциональный символ "+" для операции сложения. В этом случае определение терма (новой теории, которую будем обозначать через EA₁) выглядит так:

а) константы 0,1 и любая переменная - термы EA₁ (вместо символа S вводим константу 1, поскольку операция сложения позволяет получить Sx в виде x+1),

б) если t₁ , t₂ - термы EA , то (t₁+t₂) - также терм EA₁. Соответственно мы должны изменить и дополнить аксиомы:

P1) ~(0=x+1),

P2) ~(x=y) -> ~(x+1=y+1),

P3) x+0=x,

P4) x+(y+1)=(x+y)+1,

P5) B(0) & (Ax)(B(x)->B(x+1)) -> (Ax)B(x).

Здесь B(z) - формула уже на языке EA₁, т.е. схема аксиом индукции в теории EA₁ должна быть "сильнее" схемы индукции в EA₁.

Это действительно так. Теория EA₁ уже достаточно сложна. Так, например, в ней легко определить формулой отношение x<y:

x<y <-> (Ez)x+z+1=y.

К 1929 г. теория EA была подробно исследована М.Пресбургером, поэтому ее принято называть арифметикой Пресбургера. Прежде всего М.Пресбургер построил алгоритм, который позволяет для каждой замкнутой формулы на языке EA₁ определить, "истинна" ли она при нашем естественном понимании формул EA₁. Имея этот алгоритм, можно показать, что всякая замкнутая формула на языке EA₁ либо доказуема, либо опровержима на основе аксиом EA₁. Одновременно была доказана непротиворечивость EA₁, причем в этом доказательстве были использованы только средства, разрешенные в программе Гильберта. Это были уже весьма нетривиальные результаты. Полученные в 1929 г., они еще больше укрепили веру Д.Гильберта в реализуемость его программы (веру в возможность доказательства непротиворечивости всей математики с помощью надежных средств рассуждения). Казалось, остался еще один чисто математический, хотя и технически сложный шаг, - и цель будет достигнута. Однако уже в 1930 г. последовала совсем неожиданная развязка...

Упражнение 3.2. (курсовая работа). Изучите алгоритм Пресбургера (см. Д.Гильберт, П.Бернайс [1934]) и покажите, что невозможна формула, означающая x*y=z, т.е. формула MULT(x,y,z) такая, что

EA₁ |- MULT(x,0,0) (x*0=0),

EA₁ |- (AuAv)(MULT(x,y+1,u)&MULT(x,y,v)->u=v+x) (x*(y+1)=(x*y)+x).

В 1974 г. М.Фишер и М.Рабин показали, что проблема разрешения для формул EA₁ очень сложна: решение вопроса об истинности формулы длины n требует 2**2**cn единиц времени (см. М.Рабин [1977], "**" обозначает операцию возведения в степень).

Итак, теория EA₁ также не может нас удовлетворить: в ней невозможно обсуждать операцию умножения натуральных чисел и тем самым - понятие простого числа и другие важные понятия теории чисел. По-видимому, мы должны сделать еще один шаг: введем функциональный символ "*" для операции умножения, дополнив определение терма (в новой теории, которую будем обозначать просто через EA):

а) константы 0,1 и любая переменная - терм EA,

б) если t₁, t₂ - термы, то (t₁+t₂) и (t₁*t₂) - также термы EA.

Очевидно, термы EA - это обозначения полиномов (от нескольких, вообще говоря, переменных) с натуральными коэффициентами. Например, терм (((x*x)+(((1+1)*x)*y))+(y*y))

представляет полином x²+2xy+y² .

Теория EA использует только предикатный символ равенства "=" (понимаемый как равенство натуральных чисел). Если t₁, t₂ - термы EA, то (t₁=t₂) - элементарная формула EA. Из элементарных формул с помощью логических связок и кванторов строятся более сложные формулы EA, причем Ex мы понимаем как "существует натуральное число", а Ax - как "для всех натуральных чисел".

Средствами языка EA легко записываются простейшие утверждения о свойствах натуральных чисел, например

"x - четное число" <-> (Ey)x=y+y,

"x - простое число" <-> 1<x & ~(EyEz)(y<x & z<x & x=y*z),

"существует бесконечно много простых чисел" <->

<->(Ax)(Ey)(x<y & "y - простое число").

Упражнение 3.3. Перепишите средствами языка EA следующие утверждения: "существует бесконечно много простых чисел- близнецов", "при делении x на y получается остаток z", "x и y не имеют общих делителей".

Все, что мы до сих пор говорили о нашем "понимании" языка элементарной арифметики, является нашим личным делом и к определению теории EA не относится. В этой теории о свойствах введенных нами символов известно только то, что сформулировано в аксиомах. Часть этих свойств уже содержится в логических аксиомах и правилах вывода, которые безоговорочно принимаются в EA. Для определения наиболее существенных свойств мы вводим собственные аксиомы EA:

E1) ~(0=x+1),

E2) ~(x=y) -> ~(x+1=y+1),

E3) x+0=x,

E4) x+(y+1)=(x+y)+1,

E5) x*0=0,

E6) x*(y+1)=(x*y)+x,

E7) B(0) & (Ax)(B(x)->B(x+1)) -> (Ax)B(x).

Здесь дополнительно к аксиомам EA введено рекурсивное определение умножения (аксиомы E5,E6), а в схеме аксиом индукции (E7) в качестве формулы B может выступать любая формула B(x) языка EA с выделенной свободной переменной x (при этом кроме x формула может содержать и другие свободные переменные - параметры).

Ясно, что теория EA еще "сильнее" EA₁. В свете результата Фишера-Рабина о сложности разрешающего алгоритма для EA₁ (см. выше), у нас мало шансов построить такой алгоритм для EA (а в разделе 6.4 будет доказано, что он вообще невозможен). Но стоит ли заниматься всем этим, если может оказаться, что в EA невозможно определить операцию возведения в степень:

x⁰ =1, y+1 y

x^y+1 =(x^y)*x ?

В разделе 3.3 будет доказана теорема о представимости, согласно которой в EA можно определить (с помощью подходящей формулы) любую вычислимую функцию, т.е. дополнение языка EA новыми функциональными символами ничего к "мощности" теории EA прибавить не может. Это свидетельствует о неслучайном характере того объема средств рассуждения, который заключен в аксиомах EA.

С точки зрения этого результата теория EA представляет собой одну из возможных формализаций дискретной математики - как раз тех "надежных средств", которые Д.Гильберт предполагал использовать для доказательства непротиворечивости всей математики. Поэтому теория EA заслуживает серьезного изучения.

С интуитивным пониманием формул языка EA связан укоренившийся платонистский предрассудок, согласно которому всякая замкнутая формула на языке EA либо "истинна", либо "ложна". Разберемся в этом. Интуиция руководила нами при отборе аксиом. Мы руководствуемся ею также в случаях, когда требуется установить формальный аналог какой-либо теоремы из обычной (интуитивной) теории чисел (вспомним упражнение 3.3). Всякая попытка идти еще дальше и придать нашей интуиции натурального ряда какой-то более глубокий смысл приводит к платонизму. Однако многие идут этим путем и серьезно рассматривают следующее определение "истинности" формул языка EA:

а) Элементарные формулы EA имеют вид (t₁=t₂), т.е. это утверждения о равенстве значений полиномов. При любых конкретных значениях переменных, входящих в термы t₁, t₂, их значения могут быть вычислены и тем самым может быть решен вопрос об истинности равенства t₁=t₂.

б) В теории EA имеется четыре логические связки: ~,&,V,->. Если решен вопрос об истинности формул A, B, то по обычным правилам алгебры логики решается вопрос об истинности ~B, A&B, AVB, A->B.

в) В теории EA имеется два квантора: E,A. Формула (Ex)C(x) считается истинной, если формула C(x) истинна при хотя бы одном значении переменной x. Формула (Ax)C(x) считается истинной, если C(x) истинна при любом значении переменной x.

Итак, вроде получается, что всякая замкнутая формула языка EA (формула, не имеющая свободных переменных) должна оказаться либо "истинной", либо "ложной". Это хорошо согласуется с нашей привычной интуицией: замкнутая формула языка EA выражает вполне определенное свойство системы натуральных чисел (вроде бесконечности множества простых чисел), которым эта система либо обладает, либо не обладает.

Заметим, однако, что в своем определении "истинности" формул мы воспользовались оборотами типа "C(x) истинна при любом значении x". Согласно нашему интуитивному пониманию природы натуральных чисел, всевозможных значений x существует бесконечно много, т.е. мы не можем установить "истинность" (Ax)C(x) простой проверкой "истинности" C(x) для конкретных значений x. Истинность (Ax)C(x) мы в состоянии установить (если это вообще удается) только теоретическим путем - доказывая это утверждение на основе каких-либо аксиом, т.е. в определенной теории (например, EA или ZF). Можем ли мы утверждать, что всякую замкнутую формулу EA можно либо "теоретически доказать", либо "теоретически опровергнуть"? Нам хотелось бы так утверждать..., но какую конкретную теорию мы имеем в виду при этом - EA, ZF или другую? Чтобы придать нашему определению "истинности" точный смысл, мы должны сделать выбор, иначе определение будет висеть в воздухе.

По-видимому, одним из источников упрямой веры в осмысленность приведенного определения "истинности" является закон исключенного третьего, принятый в классической логике. Согласно этому закону, в частности,

EA |- AV~A

для любой формулы A. Однако следует ли отсюда, что если A - замкнутая формула, то либо EA |- A, либо EA |- ~A? Из теоремы Геделя о неполноте вытекает, что ни EA, ни ZF, ни какая-либо другая серьезная математическая теория этим идеальным свойством обладать не могут - несмотря на постулирование закона исключенного третьего в их аксиомах! (Подробнее см. раздел 5.)

Основным средством вывода теорем в теории EA является, как и следовало ожидать, схема индукции. Рассмотрим в качестве примера вывод формулы 0+x=x (она отличается от аксиомы x+0=x!). Обозначим 0+x=x через A(x). Сначала мы должны доказать A(0), т.е. 0+0=0, но это частный случай упомянутой только что аксиомы. Теперь можем доказать A(x)->A(x+1). Предполагая воспользоваться теоремой дедукции, возьмем A(x) в качестве гипотезы:

A(x) или 0+x=x (гипотеза),

0+(x+1)=(0+x)+1 (частный случай аксиомы),

0+x=x -> (0+x)+1=x+1 (свойство равенства),

(0+x)+1=x+1 (MODUS PONENS),

0+(x+1)=x+1 или A(x+1) (транзитивность равенства).

По теореме дедукции отсюда следует EA |- A(x)->A(x+1), а затем EA |- (Ax)(A(x)->A(x+1)). Так как A(0) уже доказано, то по схеме индукции получаем EA |- (Ax)A(x) или EA |- 0+x=x.

Аналогично доказываются другие простые теоремы EA. Следует помнить, однако, что перед тем как доказывать какую-либо теорему (например, коммутативность умножения: х*у=у*х), полезно уже знать некоторые теоремы. Таким образом, даже доказательство простых теорем EA содержит в себе творческий момент - он состоит в наиболее рациональном выборе порядка, в котором эти теоремы следует доказывать.

Упражнение 3.4. Докажите коммутативность умножения, пройдя следующую цепь теорем (заимствованную из книги Э.Мендельсона [1976]):

x=y -> x+z=y+z, x+z=y+z -> x=y,

0+x=x, (x+1)+y=(x+y)+1, x+y=y+x, (x+y)+z=x+(y+z),

x=y -> x*z=y*z, 0*x=0, (x+1)*y=(x*y)+y, x*y=y*x.

В теории EA можно доказать все обычные свойства отношения x<y, определенного формулой (Ez)(x+z+1=y). В частности, можно доказать схему теорем, равносильную схеме индукции, - так называемый принцип наименьшего числа:

EA |- ~(Ax)C(x) -> (Ey)(~C(y)&(Az<y)C(z)).

В теории EA можно свободно трактовать делимость чисел. Если через R(x,y,z) обозначить формулу (Eu)(x=y*u+z & z<y), т.е. "при делении x на y получается остаток z", то можно доказать, что

EA |- 0<y -> (Ez)R(x,y,z),

EA |- R(x,y,z₁) & R(x,y,z₂) -> z₁ = z₂,

т.е. теоремы о существовании и единственности остатка.

Все недостающие здесь доказательства можно найти в книге Э.Мендельсона [1976], в которой изложены формальные выводы из аксиом EA основных свойств натуральных чисел. После того, как средствами EA воспроизведены основы теории, можно приступить к формальному доказательству уже более серъезных теорем, например о бесконечности количества простых чисел. Потратив определенные усилия, мы могли бы "передоказать" средствами EA все теоремы, содержащиеся в элементарных учебниках теории чисел. Эту техническую работу мы здесь проводить не будем. Поверим на слово тем, кто уже проделал ее - для себя и для нас. Итак, следующее утверждение является эмпирически установленным фактом: все рассуждения обычной (интуитивной) теории чисел, которые не апеллируют к произвольным действительным числам и функциям, могут быть формально воспроизведены в EA.

Введем особые обозначения для некоторых специальных термов EA: 2 - для (1+1), 3 - для ((1+1)+1) и т.д. Термы такого рода принято называть нумералами - стандартными обозначениями конкретных натуральных чисел. Нумералы, используемые в схемах формул EA, будем обозначать через k, l, m, n, p, q, r.

Отметим теперь ряд простых свойств отношения "<", которые понадобятся нам в дальнейшем. Если k>0, то

EA |- x<k <-> (x=0)V(x=1)V... V(x=k-1),

EA |- (Ex<k)C(x) <-> C(0)VC(1)V... VC(k-1),

EA |- (Ax<k)C(x) <-> C(0)&C(1)&... &C(k-1).

Разумеется, это схемы теорем.

Упражнение 3.5. Если в элементарной формуле t₁=t₂, содержащей переменные ("неизвестные"), все слагаемые правой части перенести в левую, то получим диофантово уравнение (см. раздел 4.1). Нас интересует решение таких уравнений в натуральных числах. Покажите, что если найдено конкретное решение (b₁, b₂,..., b_n) уравнения t₁ = t₂ , то

EA |- (Ex₁Ex₂... Ex_n)t₁ = t₂.

(Указание: сначала индукцией по структуре термов покажите, что в EA доказуема любая истинная формула t₁ = t₂, не содержащая переменных.)

3.2. Натуральные числа в других теориях

Формальная арифметика EA представляет простейший уровень математических рассуждений - в которых участвуют только целые числа (и не участвуют произвольные действительные числа, не говоря уже о произвольных множествах Кантора). Более сложные рассуждения формализуются и более сложными (по сравнению с EA) формальными теориями. "Силу" этих более сложных теорий составляет прежде всего их способность обсуждать более сложные объекты (действительные числа, функции действительных и комплексных переменных и т.д.), которые недоступны в EA. Однако не может ли оказаться, что более сложная теория в состоянии доказать некоторые утверждения, трактующие исключительно о свойствах натуральных чисел, которые не в состоянии доказать EA? Не может ли оказаться, например, что EA не в состоянии доказать бесконечность количества простых чисел-близнецов, однако с привлечением действительных чисел это доказательство удается? На первый взгляд такое невозможно - ведь натуральные числа определяются независимо от действительных чисел (и "до них"). На самом деле ситуация сложнее...

Каким образом выделить в некоторой формальной теории T ту ее часть, которая относится к компетенции EA? Этот вопрос решается очень естественно с помощью так называемых относительных интерпретаций. Чтобы воспроизвести в теории T арифметику, прежде всего какие-то объекты из области значений переменных T должны быть объявлены натуральными числами. Это связано с выделением в языке T некоторой формулы N(x) (с единственной свободной переменной x), которая "утверждает", что x является натуральным числом. Далее, необходимо отобразить в теории T элементарные формулы EA, т.е. формулы вида t₁ = t₂, трактующие о значениях полиномов t₁, t₂ с натуральными коэффициентами. В самом общем виде это будет некоторое вычислимое отображение pi, переводящее всякую элементарную формулу F из языка EA в формулу pi(F) из языка T. При этом естественно требовать, чтобы формула pi(F) всегда имела в точности те свободные переменные, которые имеет F. Такое отображение можно доопределить для произвольных формул EA:

pi(~A)=~pi(A), pi(A&B)=pi(A)&pi(B),

pi(AVB)=pi(A)Vpi(B), pi(A->B)=pi(A)->pi(B),

pi((Ex)C(x))=(Ex)N(x)&pi(C(x)),

pi((Ax)C(x))=(Ax)(N(x)->pi(C(x))).

Пару (N, pi) будем называть относительной интерпретацией EA в теории T, если для каждой аксиомы A теории EA

T|- N(x₁)&... &N(x_k) -> pi(A),

где x₁,..., x_k - свободные переменные аксиомы A. Например, для аксиомы x+1=y+1 -> x=y требуется

T|- N(x)&N(y) -> (pi(x+1=y+1)->pi(x=y)).

Так как теория T содержит полный набор логических средств рассуждения, то отсюда следует, что для любой замкнутой формулы C из языка EA: если EA|- C, то T|- pi(C). Это означает, что, имея относительную интерпретацию EA в T, в теории T можно доказать любое свойство натуральных чисел, которое доказуемо в EA. И если нас интересует только "арифметическое содержание" теории T, мы можем, допуская вольность, даже писать T|- C вместо T|- pi(C). Учитывая роль системы натуральных чисел в математике, формальную теорию, в которой относительно интерпретируема теория EA (и которая содержит в этом смысле полноценное понятие натурального числа), будем называть фундаментальной теорией. Простейшей из фундаментальных теорий является, конечно, сама теория EA.

Теория множеств ZF, разумеется, также оказывается фундаментальной. Формула N(x), определяющая относительную интерпретацию EA в ZF, означает здесь просто "x in w", где w - множество всех натуральных чисел. Однако если написать "x in w" в развернутом виде средствами языка ZF, то получится довольно сложная формула (см.раздел 2.3). Таким же сложным оказывается и отображение pi. Ограничимся простейшими примерами. Во-первых, pi(х=у)=(х=у). Поскольку нуль определяется как пустое множество 0, единица - как {0}, 2 - как {0, {0}} и т.д., то pi(x=0)=(Ay)~(y in x), pi(x=1)=(Ay)(y in x<->pi(y=0)) и т.д. Формула pi(x=2) получится, если развернуть формулу

(Ay)(y in x <-> pi(y=0)Vpi(y=1)).

Вопрос, с которого мы начали этот раздел, можно теперь переформулировать следующим образом: возможно ли, что для некоторой фундаментальной теории T (которая "сильнее" теории EA) найдется в языке EA формула C такая, что T|- C, но не EA|- C? Ответ на этот вопрос будет получен в разделе 6.5 (см. также приложение 2).

Упражнение 3.6. Обобщая результат упражнения 1.4, покажите, что множество pi^-1(T) "арифметических теорем" всякой фундаментальной теории T является эффективно перечислимым. (Воспользуйтесь вычислимостью отображения pi. )