<< Пред. стр.

стр. 3
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>

(P ) ?X n ?x1 . . . ?xn ?y1 . . . ?yn ((x1 = y1 ? x2 = y2 ? . . . ? xn = yn ) >
(X n (x1 , . . . , xn ) = X n (y1 , . . . , yn )).
21


Заметим, что в (P ) используется символ n-арной предикатной переменной X n ,
а в (F ) используется символ n-арной функциональной переменной f n . Строго
говоря, согласно данному нами определению, в алфавите языков логики второго
порядка нет специально зарезервированных символов для функциональных пе-
ременных. Однако это никак не ограничивает выразительной силы языка второго
порядка: на самом деле функциональные переменные можно заменить предикат-
ными переменными.
Действительно, функцию можно отождествить с ее графиком, а графики
функций это частный случай отношений. Например, “формулу” ?f (P (f (x))) (где
f – символ унарной функциональной переменной) можно считать просто сокра-
щенным написанием формулы ?X (f unc(X)?(?y(X(x, y) > P (y)))), где формула

f unc(X) := ?x?!y X(x, y)

выражает то факт, что X – график функции. Здесь использовано весьма распро-
страненное сокращение ?! (“существует и единственно”):

?!xP(x) := ?xP(x) ? ?x?y(P(x) ? P(y) > x = y).

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


5 Арифметика Пеано
Рассмотрим в качестве первого содержательного примера языков логики преди-
катов языки для описания арифметических действий с натуральными числами.
Для этой цели зададим сигнатуру

?ar := (0, s, +, ·, =),
22 Арифметика Пеано


где 0 – символ константы “нуль”, s – символ унарной функции выделения следую-
щего по порядку числа, + и · – символы бинарных функций суммы и произведе-
ния, и, наконец, = – предикатный символ равенства. Как и в случае с символом
равенства, для символов + и · будем в дальнейшем писать (x + y) и (x · y) вместо
+(x, y) и ·(x, y), соответственно, а так же не писать “лишние” скобки, приписы-
вая символу · более высокий приоритет по сравнению с +, как это и принято
в математике. Эта сигнатура задает два языка логики предикатов с равенством
– первого L?ar и второго порядка L?ar соответственно, которые мы будем назы-
I II
вать языками арифметики Пеано (по имени итальянского математика Giuseppe
Peano, впервые рассмотревшего формальные языки для описания арифметики).
Эти языки описывают только самые простые действия с натуральными числа-
ми “в пределах начальной школы”, в число которых, например, даже не входит
возведение в степень. И все же даже такие простые на первый взгляд языки
обладают, как мы в дальнейшем покажем, весьма неожиданными свойствами.
Возникает вопрос: какие формулы языка арифметики Пеано имеют смысл?
Очевидно, лишь те из них, которые верны для натуральных чисел (ведь именно
для действий с ними предназначен этот язык). Выражаясь точнее, осмыслен-
ными разумно считать только формулы, выполнимые в алгебраической системе
N , универсум которой есть множество натуральных чисел (с нулем), символ 0
соответствует нулю (т.е. 0N := 0), символ s соответствует функции прибавле-
ния единицы (т.е. sN (n) := n + 1), а символы + и · соответствуют функциям
сложения и умножения двух чисел (т.е. +N (m, n) := m + n, ·N (m, n) := mn). Ал-
гебраическую систему N будем в дальнейшем называть стандартной моделью
арифметики.
Например, формулы x = s(0) или ?x?y(¬y = 0 > ¬x = x + y) языка арифме-
тики Пеано (заметим, что это формулы первого порядка, поэтому они принадле-
жат как L?ar , так и L?ar ), являются осмысленными утверждениями о натураль-
I II
ных числах, иначе говоря, выполнимы в N , а формула ?x(x = 0), невыполнима
в N , т.к. будучи “прочитанной” как утверждение о натуральных числах, она оче-
видно неверна.
Назовем множество формул языка арифметики Пеано первого или второго по-
рядка, соответственно, истинных в N , теорией элементарной арифметики T hi (N )
(соответствующего порядка, указываемого индексом i = I или i = II). В даль-
нейшем, если из контекста ясно, о каком языке арифметики – первого или вто-
рого порядка – идет речь, либо это не имеет значения, мы будем говорить просто
о языке арифметики Пеано и о теории элементарной арифметики, не указывая
порядок. Таким образом, теория элементарной арифметики

T hi (N ) := {P ? L?ar : N |= P}, i = I, II
i

является набором формул соответствующего порядка, выражающего истинные
23


факты для натуральных чисел. Легко заметить, что введенные понятия весьма
неконструктивны. А именно, они не заключают в себе никакого способа проверки,
принадлежит ли данная формула языка арифметики Пеано теории элементарной
арифметики (т.е. действительно ли она описывает некоторое свойство натураль-
ных чисел). Конечно, такой алгоритм, пусть и очень сложный, найти было бы
весьма заманчиво. Ведь тогда творческую работу математиков, доказывающих
все новые теоремы теории чисел, можно было бы заменить на программу, ра-
ботающую по такому алгоритму. Кстати, то же самое можно сказать и о любой
другой математической (или даже шире – любой вообще научной) теории.
Попытаемся найти такой алгоритм. Для этого проанализируем, как на са-
мом деле математики проверяют истинность утверждений, например, из теории
чисел. Конечно, не путем “прямого перебора” всех возможных наборов чисел,
поскольку такая проверка в силу бесконечности множества натуральных чисел
никогда бы не завершилась! Для проверки истинности данного утверждения ма-
тематик ищет его доказательство, исходя из некоторого набора аксиом. Иначе
говоря, математик имеет в виду некоторый набор утверждений (называемых ак-
сиомами) ?, не просто истинных в данной модели M, но и в каком-то смысле
вполне ее характеризующих, иначе говоря, таких, что можно надеяться, что лю-
бое истинное утверждение о данной модели является логическим следствием
этих аксиом. Часто говорят при этом, что ? – система аксиом для модели M.
Далее он пытается проверить, является ли данная формула P логическим след-
ствием аксиом ? (в этом и состоит процесс доказывания). Если ? |= P, то P
истинно в данной модели, поскольку любая модель всех одновременно формул
?, в частности и M, является и моделью P.
О том, как устроен процесс доказывания, речь еще впереди. Сейчас же от-
метим, что успешность подобного рода действий во всяком случае должна за-
висеть от того, насколько удачно подобрана система аксиом ?. Действительно,
обозначим ?|= множество всех логических следствий ?, а T h(M) – множество
всех утверждений, истинных в модели M. Если ? выбрано корректно, то есть
так, что все формулы из ? истинны в M, то ?|= ? T h(M). Но нам бы, есте-
ственно, хотелось, чтобы все формулы, истинные в M, были бы логическими
следствиями ?. Но как это обеспечить? Иначе говоря, как выбрать множество ?,
чтобы ?|= = T h(M)? Вопрос об удачном подборе такой системы аксиом ? для
алгебраической системы M часто называют вопросом аксиоматизации M).
На поставленный вопрос есть, конечно, и тривиальный ответ: ? := T h(M),
очевидно, удовлетворяет этому требованию. Но этот ответ совершенно не инте-
ресен: ведь вся затея с аксиомами нужна была как раз для того чтобы, “кон-
структивно” (т.е. алгоритмически) описывать множество T h(M), например, най-
ти алгоритм проверки того, является ли данная формула истинной в модели M.
Для этого множество ? должно быть в определенном смысле “обозримым” (же-
24 Арифметика Пеано


лательно вообще конечным или уж во всяком случае таким, которое может быть
построено при помощи некоторого алгоритма), и конечно, не может совпадать с
T h(M).
Вернемся к рассмотрению элементарной арифметики. Попытка предложить
для нее разумную систему аксиом была осуществлена Пеано. Он показал, что
практически все основные теоремы теории чисел (т.е. истинные утверждения о
натуральных числах), записываемые в языке арифметики первого порядка, яв-
ляются логическими следствиями аксиом

(P A1 ) ?x ¬(s(x) = 0),

(P A2 ) ?x ?y (s(x) = s(y) > x = y),

(P A3 ) ?x (x + 0 = x),

(P A4 ) ?x (x · 0 = 0),

(P A5 ) ?x ?y (x + s(y) = s(x + y)),

(P A6 ) ?x ?y (x · s(y) = x + x · y),

(P A7 ) P(0) ? ?x (P(x) > P(s(x))) > ?y P(y), где
P – любая формула языка L?ar с одной свободной переменной.
I

|=
Мы будем называть формальной арифметикой Пеано первого порядка P AI мно-
жество всех логических следствий аксиом (P A5 )–(P A7 ). Формальной арифмети-
|=
кой Пеано второго порядка P AII будем называть множество всех логических
следствий аксиом (P A1 )–(P A6 ) и аксиомы

?X (X(0) ? ?x (X(x) > X(s(x))) > ?x X(x)) (IN D).

Сами эти аксиомы мы также будем называть аксиомами Пеано. Аксиома (P A1 )
утверждает, что нуль – первый по порядку элемент натурального ряда. Аксиома
(P A2 ) утверждает, что функция выбора следующего по порядку элемента инъ-
ективна, иначе говоря, что за каждым числом непосредственно следует только
одно число. (P A3 ) и (P A4 ) задают правила прибавления нуля и умножения на
нуль, а (P A5 ) и (P A6 ) связывают между собой функции сложения и умножения
с функцией выбора следующего по порядку элемента. Наконец, (P A7 ) представ-
ляет собой схему аксиом (т.е. “шаблон” бесконечного числа аксиом) и выражает
принцип математической индукции. Тот же самый принцип выражает и аксиома
второго порядка (IN D). Стоит еще раз подчеркнуть, что отличие формальной
арифметики Пеано первого и второго порядка состоит только в написании прин-
ципа математической индукции. В первом случае он записывается при помощи
25


бесконечного числа аксиом, объединенных в одну схему аксиом, а во втором – в
одну аксиому второго порядка.
Очевидно, что стандартная модель N является моделью для арифметики Пе-
ано (как первого, так и второго порядка). А есть ли у арифметики Пеано другие
модели? Стоит отметить, что заданный вопрос весьма глубокий, и по сути де-
ла является вопросом о том, что вообще следует понимать под натуральными
числами. В самом деле, действия с натуральными числами являются для нас
настолько привычными, что мы и не задумываемся об их смысле, а именно, о
том, что такое число, что следует понимать под суммой и произведением чи-
сел и т.п. В окружающем нас мире натуральные числа отсутствуют – это лишь
абстракция, “идея”, присутствующая только в нашем сознании (хотя, конечно,
при построении этой, как и всякой другой, абстрактной конструкции, человече-
ство использует идеализацию свойств реальных объектов окружающего мира).
Значит, ответить на вопрос о том, что такое число, просто указав на какой-то
объект или явление природы, невозможно. Поэтому математики, в особенности
те из них, которые с особым трепетом относятся к строгости рассуждений, как
правило, дают другой, весьма естественный и вместе с тем достаточно строгий
(хотя и не вполне очевидный) ответ на этот вопрос. А именно, натуральные чис-
ла и действия с ними можно определить просто как элементы алгебраической
системы, являющейся моделью всех “осмысленных утверждений о числах”. Сло-
ва “осмысленные утверждения о числах” взяты в кавычки, так как под этим на
самом деле понимается некоторый набор утверждений языка арифметики Пеано
первого или второго порядка, которые мы условимся считать таковыми. Раньше
мы говорили об осмысленности формул языка арифметики, если они были вы-
полнимы в стандартной модели N . Но если мы хотим строго определить сами
понятия натуральных чисел и действий с ними, то на такое понимание “осмыслен-
ности” опираться уже нельзя, так как, строго говоря, пока не определено даже
само множество натуральных чисел N, являющееся универсумом алгебраиче-
ской системы N . Поэтому осмысленными в данном случае естественно считать
лишь все логические следствия выбранной “разумной” системы аксиом, напри-
мер, в нашем случае формальную арифметику Пеано первого или второго по-
рядка. Тогда определение натуральных чисел и действий с ними как элементов
соответствующей модели формальной арифметики становится уже достаточно
строгим, поскольку оно не ссылается на интуитивное понятие числа как коли-
чества объектов любого сорта. Кстати, именно таким способом обычно строго
определяют все другие базовые математические понятия, которые мы привыкли
считать интуитивно ясными и неопределимыми. Например, в геометрии такими
базовыми и неопределимыми понятиями принято считать точки, прямые и плос-
кости. “В природе” геометрических точек, прямых и плоскостей не существует.
Эти понятия получены в результате систематизации многотысячелетнего опыта
26 Арифметика Пеано


обращения людей с реальными предметами очень маленьких размеров (в случае
точек), очень тонкими и длинными предметами (в случае прямых) и очень плос-
кими предметами больших размеров (в случае плоскостей), а именно, в результа-
те абстрактизации (идеализации) свойств такого рода предметов. Полученная в
результате умственная конструкция – мир геометрических точек, прямых и плос-
костей – далее описывается при помощи подходящего набора аксиом, т.е. такого,
который бы адекватно нашему интуитивному представлению описывал свойства
объектов этого мира и, по возможности, был бы достаточно полным в том смыс-
ле, что все (или, по крайней мере, значительная часть) истинные (опять-таки в
соответствии с нашим интуитивным представлением) утверждения о таких объ-
ектах были бы логическими следствиями этих аксиом. Выбор системы аксиом,
естественно, при этом соответствует только нашим интуитивным представлени-
ям об “адекватности” и “полноте” и поэтому никак не может быть формализован.
Единственное формальное и к тому же естественное требование к набору аксиом
– непротиворечивость. Так, большинство людей, ограничивающих свое представ-
ление о физическом мире современной физикой, могут вполне удовлетвориться
аксиомами Эвклида (с аксиомой или без аксиомы параллельных). Когда система
аксиом выбрана, можно дать и строгое определение точкам, прямым и плоско-
стям как элементам алгебраической системы, являющейся моделью выбранных
аксиом (а значит, и всех их логических следствий). Таким образом, эти понятия,
строго говоря, становятся зависимыми от выбранной системы аксиом.
Итак, натуральные числа и действия с ними будут пониматься как элементы
алгебраической системы, являющейся моделью формальной арифметики Пеано
первого или второго порядка, в зависимости от того, какую систему аксиом –
первого или второго порядка – мы будем выбирать. В связи с этим возникают
два связанных между собой вопроса. Во-первых, насколько выбор набора аксиом
влияет на получаемое понятие натуральных чисел (a priori это понятие зависит
от выбранных аксиом)? Во-вторых, сколько вообще различных “версий” нату-
ральных чисел определяются выбранной системой аксиом (т.е. сколько разных
моделей у выбранных аксиом). Простой ответ на второй вопрос очевиден: ни
аксиомы Пеано первого, ни второго порядка не определяют натуральные чис-
ла и действия с ними однозначно. Действительно, предположим, что формаль-
ная арифметика Пеано (безразлично какого порядка) имеет модель. Элементы
универсума этой модели мы считаем “настоящими” натуральными числами, т.е.
таким образом эта модель становится стандартной моделью арифметики. Но то-
гда очевидно, что моделью формальной арифметики Пеано будет являться и
любая алгебраическая система M, универсум которой – произвольно выбран-
ная последовательность {xi }? , 0M := x0 , sM (xn ) := xn+1 , +M (xm , xn ) := xm+n ,
i=0
M
· (xm , xn ) := xmn ). Однако более пристальное рассмотрение всех таких моделей
убеждает, что все они между собой весьма схожи, а именно, они изоморфны в
27


смысле следующего определения.

Определение 5.1 Пусть A и B алгебраические системы для языка L? . A на-
зывается изоморфной B (пишут A B), если существует биекция ?: A > B,
удовлетворяющая условиям

(i) ?(cA ) = cB для всех c ? Const,

(ii) ?(f A (t1 , t2 , . . . , tn )) = f B (?(t1 ), ?(t2 ), . . . , ?(tn )) для всех f ? Funcn ,

(iii) P A (t1 , t2 , . . . , tn ) = P B (?(t1 ), ?(t2 ), . . . , ?(tn )) для всех P ? Predn .

Очевидно, что отношение изоморфности моделей является отношением экви-
валентности, т.е. оно симметрично, рефлексивно и транзитивно (проверьте это!).
Не менее тривиально проверяется и следующее свойство.

Упражнение 5.1 Пусть A и B алгебраические системы для языка L? , и пусть
A B. Докажите, что для любого P ? ? верно A |= P, если и только если
B |= P.

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

Теорема 5.1 (Дедекинд) Любые две модели формальной арифметики Пеано
второго порядка изоморфны между собой.
|=
Доказательство: Пусть A |= P AII . Докажем, что A N . Определим функ-
цию ?: N > A следующим образом:

(i) ?(0) := 0A ,

(ii) ?(n + 1) := sA (?(n)).

В силу принципа математической индукции функция ?, таким образом, коррект-
но задана на всем множестве N . Заметим, что в силу аксиомы (IND) принцип
|=
математической индукции действует во всех моделях P AII .
28 Арифметика Пеано


Выполнение условий (i)–(iii) определения изоморфизма алгебраических си-
стем при таком определении очевидно (проверьте это!). Осталось только прове-
рить, что таким образом определенная функция действительно является биекци-
ей.
Шаг 1. Докажем, что ? – инъекция, то есть из m = n следует ?(m) = ?(n).
Поведем доказательство по методу математической индукции в N .

• База индукции. Пусть n = 0, m = 0. Тогда m = k + 1 для некоторого k.
Этот факт верен, вообще говоря, только для стандартной модели. Тогда
?(m) = ?(k + 1) = sA (?(k)) = 0A = ?(0N ) в силу (P A1 ). База индукции
доказана.

• Шаг индукции. Пусть m = n + 1. Докажем, что при этом ? (m) = ? (n + 1).
Рассмотрим два случая.
Случай 1. m = 0. Тогда ?(n + 1) = sA (?(n)) = 0A = ?(0N ) = ?(m).
Случай 2. m = k + 1. Из предположения m = n + 1 следует k = n. Но тогда
?(k) = ?(n) в силу предположения индукции, а значит, sA (?(k)) = sA (?(n))
в силу (P A2 ). Поэтому ?(m) = ?(k + 1) = sA (?(k)) = ?(n + 1) = sA (?(n)).

В силу принципа математической индукции, таким образом, доказана инъек-
тивность функции ?.
Шаг 2. Докажем, что ? сюръективна, то есть, что для всех a ? A выполнено
a ? Im(?). Для этого воспользуемся принципом математической индукции, но
|=
на этот раз в A. Напомним, что этот принцип действует во всех моделях P AII
в силу (IN D). База индукции в этом случае тривиальна: 0A ? Im(?) по опре-
делению ?. Пусть теперь b ? Im(?), то есть b = ?(n) для некоторого n ? N.
Тогда и sA (b) = ?(n + 1) ? Im(?) в силу определения ?, т.е. доказан и шаг индук-
ции. В силу произвольности b по принципу математической индукции все a ? A
принадлежат образу ?, иначе говоря, функция ? сюрьективна.
В дальнейшем мы покажем, что утверждение, аналогичное теореме Дедекин-
да, неверно для формальной арифметики Пеано первого порядка, а именно, по-
следняя имеет бесконечно много разных с точностью до изоморфизма моделей.
Более того, среди этих моделей можно найти и такие, которые обладают универ-
сумом сколь угодно большой наперед заданной мощности. Иначе говоря, фор-
мальная арифметика Пеано первого порядка допускает бесконечно много прин-
ципиально разных “версий” натуральных чисел и действий над ними, в том числе
и таких, в которых “множество натуральных чисел” несчетно (т.е. неизоморфно
“стандартному” множеству натуральных чисел N)! Почему же доказательство
теоремы Дедекинда не работает для формальной арифметики Пеано первого по-
рядка? Анализируя доказательство, мы видим, что в первом шаге нет никаких
29


рассуждений, которых нельзя было бы провести для арифметики первого поряд-
ка (на этом шаге мы пользовались лишь аксиомами (P A1 ), (P A2 ) и принципом
математической индукции в N ). Проблема, таким образом, во втором шаге, где
мы воспользовались уже принципом математической индукции в A, а именно,
тем, что для любого свойства X элементов универсума A верно следующее: если
0A обладает свойством X (база индукции), а также для любого b ? A из облада-
ния b свойством X следует обладание sA (b) тем же свойством, то свойством X
обладают все элементы A. Для арифметики второго порядка выполнимость этого
принципа в любой модели гарантирована аксиомой (IN D). Однако в арифмети-
ке первого порядка вместо этой аксиомы имеется гораздо более слабый набор
(схема) аксиом (P A7 ). Он гарантирует выполнение вышеприведенного принципа
не для всех свойств X, а лишь для тех из них, которые можно записать при
помощи формул P языка арифметики Пеано первого порядка с одной свободной
переменной. Заметим, что множество таких свойств очевидно счетно, так как
алфавит языка конечен. В то же время всех вообще свойств элементов множе-
ства A гораздо больше. Действительно, такие свойства можно тривиально отож-
дествить с подмножествами универсума A (каждому свойству X соответствует
подмножество элементов A, обладающих этим свойством, а каждому подмноже-
ству A соответствует свойство принадлежности этому подмножеству). Так как
A не может быть конечным множеством (в силу (P A1 ) и (P A2 )), то множество
всех свойств элементов A более чем счетно! Таким образом, обязательно найдут-
ся свойства, невыразимые формулами первого порядка с одной свободной пере-
менной, и таким вполне может оказаться свойство принадлежности множеству
Im(?), а значит, второй шаг доказательства становится необоснованным.




Еще одно важное замечание: в доказательстве теоремы Дедекинда мы вос-
пользовались тем, что в стандартной модели арифметики из m = 0 следует
m = k+1 для некоторого натурального k. Никакая аксиома Пеано не гарантирует
выполнение этого свойства во всех моделях формальной арифметики Пеано. Тот
же факт, что это свойство верно для стандартной модели арифметики, следует
из наших знаний именно об этой модели, а не из аксиом арифметики. Кстати,
и само существование такой стандартной модели арифметики тоже не обеспечи-
вается аксиомами Пеано. Строго обосновать существование стандартной модели
арифметики, обладающей привычными для нас свойствами, можно только при
помощи введения специальных “более сильных” аксиом, например, аксиом теории
множеств, речь о которой впереди.
30 Элементы теории доказательств


6 Элементы теории доказательств
6.1 Формальные cистемы

<< Пред. стр.

стр. 3
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>