Дискретка

2. Теорема Л¼венгейма-Скулема. Пусть M некоторая интерпретации множества символов констант C и множества символов предикатов P, и пусть S множество суждений из A(C; P), истинных в интерпретации M. Теорема Геделя о полноте утверждает существование модели малой мощности для множества суждений S; однако, она ничего не говорит о связи этой модели с исходной моделью M. Более точный результат дает следующая теорема.

Теорема 1 (теорема Л¼венгейма-Скулема). Для любой интерпретации множества символов констант C и множества симво-

лов предикатов P существует е¼ элементарная подинтерпретация малой мощности.

Доказательство. Рассуждения, приводящие к теореме Л¼венгеймаСкулема, напоминают доказательства теорем 3 и 1 из x 6, но несколь-

ко проще их (следует отметить, что и исторически эта теорема была получена ранее теоремы Геделя о полноте). Пусть M = fM; cM ; PM g

интерпретация множества символов констант C и множества сим-

волов предикатов P. Обозначим через N0 M множество всех элементов cM , отвечающих символам констант c 2 C. Ясно, что N0

множество малой мощности.

Определим возрастающую цепочку подмножеств малой мощности N0 N1 : : : множества M, удовлетворяющих следующему усло-

âèþ:

( ) для каждой формулы A(x; x1; : : : ; xk) и каждых элементов m 2 M, n1; : : : ; nk 2 Ni 1 â Ni есть такой элемент n, что значения истинности формул A(m; n1; : : : ; nk) è A(n; n1; : : : ; nk) в интерпретации M совпадают.

Пусть множество Ni уже построено; если A(x; x1; : : : ; xk) формула, n1; : : : ; nk 2 Ni и " 2 fи,лg таковы, что множество элементов m0 2 M, для которых значение истинности формулы A(m0; n1; : : : ; nk) â èí-

терпретации M совпадает с ", непусто, то выберем в этом непустом множестве какой-то один элемент m0("; A; n1; : : : ; nk) 2 M. Отметим, что, осуществляя этот выбор одновременно для всех возможных наборов ("; A; n1; : : : ; nk), мы пользуемся аксиомой выбора. В качестве

Ni+1 возьмем множество, полученное присоединением к множеству Ni всех выбранных элементов m0("; A; n1; : : : ; nk). ßñíî, ÷òî Ni+1

множество малой мощности, удовлетворяющее условию ( ). Объединение N всех множеств Ni, i = 0; 1; 2; : : : òîæå ìíî-

жество малой мощности. Покажем, что N элементарная подинтерпретация интерпретации M. Для этого надо доказать, что для каждой формулы A(x1; : : : ; xk) и каждых элементов n1; : : : ; nk 2 N значения истинности формулы A(n1; : : : ; nk) в интерпретациях N и M N совпадают. Мы сделаем это индукцией по построению форму-

ëû A(x1; : : : ; xk). Базу индукции составляет случай, когда формула A имеет один из видов c = d, c = x1, x1 = x2, P (t1; : : : ; tk), ãäå c; d 2 C,

31

P символ n-местного предиката: для этого случая утверждение

очевидно.

Если формула A представляется в виде B&C, B _ C, B ! C, B $ C или :B, то е¼ значение истинности определяется по правилам исчисления высказываний значениями истинности формул B, C,

которые, по предположению индукции, одинаковы для обеих интерпретаций. Остается рассмотреть случай, когда формула A(x1; : : : ; xk)

имеет вид 8xB(x; x1; : : : ; xk) èëè 9xB(x; x1; : : : ; xk).

Пусть n1; : : : ; nk 2 N M; тогда n1; : : : ; nk 2 Ni äëÿ какого-то номера i. Если формула 8xB(x; n1; : : : ; nk) истинна в интерпретации M, то формула B(m; n1; : : : ; nk) истинна в M для всех m 2 M и тем более для всех m 2 N; таким образом, формула 8xB(x; n1; : : : ; nk) истинна в подинтерпретации N. Если же формула 8xB(x; n1; : : : ; nk) не истинна в интерпретации M, то существует элемент m 2 M, та-

кой что формула B(m; n1; : : : ; nk) не истинна в интерпретации M; по построению множества Ni+1, существует элемент n 2 Ni+1 N, такой что формула B(n; n1; : : : ; nk) не истинна в интерпретации M, а потому, по предположению индукции, и в интерпретации N. Таким

образом, формула 8xB(x; n1; : : : ; nk) не истинна в интерпретации N. Дуальным образом рассматривается формула 9xB(x; n1; : : : ; nk), n1; : : : ; nk 2 Ni. Если она не истинна в интерпретации M, то формула B(m; n1; : : : ; nk) не истинна в M для всех m 2 M и тем более для всех m 2 N; таким образом, формула 9xB(x; n1; : : : ; nk) не истинна в подинтерпретации N. Если же формула 9xB(x; n1; : : : ; nk) истинна в интерпретации M, то существует элемент m 2 M, такой

что формула B(m; n1; : : : ; nk) истинна в интерпретации M; по построению множества Ni+1, существует элемент n 2 Ni+1 N, такой что формула B(n; n1; : : : ; nk) истинна в интерпретации M, а потому, по предположению индукции, и в интерпретации N. Таким образом, формула 9xB(x; n1; : : : ; nk) истинна в интерпретации N.

x 8. Аксиоматика Z1 полукольца натуральных чисел

Натуральные числа обычно определяются при помощи аксиом Пеано. В этой системе аксиом натуральные числа образуют множество N0 с единственной заданной на нем унарной операцией следования:

для каждого натурального числа x определено единственное натуральное число x0, следующее за x. При этом должны выполняться следующие условия (аксиомы Пеано):

(1)Åñëè x0 = y0, òî x = y.

(2)Существует натуральное число 0 2 N0, такое что x0 6= 0 ни для какого x 2 N0.

(3)Если M подмножество множества N0, содержащее 0 и такое, что для любого элемента x 2 M следующий за ним элемент

x0 также принадлежит M, то M = N0.

32

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

В формальной арифметике Z1 два символа тернарных предикатов S(x; y; z), P (x; y; z) и два символа констант 0, 1. Неформально говоря, предикат S соответствует сумме, а предикат P произведению, и обычно вместо S(x; y; z), P (x; y; z) пишут x + y = z и xy = z. Следу-

ющие суждения считаются истинными в Z1 (то есть принимаются за аксиомы).

(1)8x8y9z(S(x; y; z));

(2)8x8y8z8t((S(x; y; z)&S(x; y; t)) ! (z = t));

(3)8x8y9z(P (x; y; z));

(4)8x8y8z8t((P (x; y; z)&P (x; y; t)) ! (z = t));

(5)8x(S(x; 0; x)&P (x; 1; x));

(6)8x8y8z((S(x; 1; z)&S(y; 1; z)) ! (x = y));

(7)8x8y8z8t8u8v8w((S(x; y; t)&S(t; z; u)&S(y; z; v)&S(x; v; w)) !

(u=w));

(8)8x8y8z8t8u8v8w((P (x; y; t)&P (t; z; u)&P (y; z; v)&P (x; v; w)) !

(u=w));

(9)8x8y8z8t8u8v8w8p((S(x; y; t)&P (t; z; u)&P (x; z; v)&P (y; z; w)& &S(v; w; p)) ! (u=p));

(10)8x8y8z8t((S(x; y; z)&S(y; x; t)) ! (z =t));

(11)8x8y8z8t((P (x; y; z)&P (y; x; t)) ! (z =t));

(12)8x(:S(x; 1; 0)).

Первая аксиома неформально означает, что для всяких двух натуральных чисел существует их сумма, а вторая что эта сумма единственна. Точно так же, аксиомы (3) и (4) утверждают существование и единственность произведения. Аксиома (5) выражает обыч- ные свойства 0 и 1, в аксиомах (7)-(11) постулируются ассоциативность и коммутативность суммы и произведения и дистрибутивный закон. Аксиома (6) по существу совпадает с первой аксиомой Пеано: если совпадают элементы, следующие за двумя натуральными числами, то совпадают и сами эти числа, а аксиома (12) со второй аксиомой Пеано: не существует числа, предшествующего 0. В этом списке отсутствует аксиома индукции; в полной общности она не может быть сформулирована на нашем формальном языке. Однако, можно надеяться, что в полной общности она нам и не нужна, а использовать ее придется только для тех подмножеств множества натуральных чисел, которые могут быть сконструированы. Но что

33

означает "сконструированы"? Это значит, что они заданы при помощи формул; поэтому достаточно сформулировать аксиому индукции для каждой формулы в нашем алфавите, и мы получаем не одну, а бесконечно много аксиом индукции, занумерованных формулами. Пусть Q(x1; : : : ; xn; y) формула, в которое входят свободно только

символы переменных x1; : : : ; xn; y; аксиома индукции для не¼ имеет следующий вид:

(13Q) 8x18x2 : : : 8xn bQ(x1; : : : ; xn; 0)&

&h8y8zf[S(y; 1; z)&Q(x1; : : : ; xn; y)] ! Q(x1; : : : ; xn; z)gic !

! [8xQ(x1; : : : ; xn; x)]

(для удобства мы обозначили скобки разного уровня разными знаками и при переносе с одной строки на другую повторили последний логический знак).

Насколько адекватно отражает эта система аксиом свойства натуральных чисел? Является ли она непротиворечивой? Если да, то являются ли все ее модели элементарно эквивалентными? Эти и другие вопросы должны были, естественно, с самого начала заинтересовать математиков. На часть из них ответа нет до сих пор. Не доказано, что система Z1 непротиворечива; наличие обычных натуральных чи-

сел, которые, казалось бы, должны составлять модель Z1, ничего не

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

Для того, чтобы описать ситуацию с другими вопросами, дадим одно определение. Множество суждений S A(C; P) называется пол-

ным, если для любого суждения X 2 A(C; P) одно из суждений X, :X выводимо из S. Гедель доказал, что если система аксиом теории

Z1 непротиворечива, то она не полна, то есть можно сформулировать

в терминах этой теории такую теорему, что ни она сама, ни ее отрицание не могут быть доказаны в этой теории. Мы объясним ниже некоторые идеи, объясняющие, почему это так; для этого нам понадобится изучить функции на множестве натуральных чисел, все зна- чения которых можно в принципе сосчитать. Теории таких функций, называемых рекурсивными, посвящена большая часть последующих параграфов, а в конце мы дадим набросок доказательства упомянутой теоремы Геделя о неполноте системы аксиом Z1.

Тот факт, что существуют неполные системы аксиом, не должен удивлять; например, аксиомы теории групп, формальную запись которой после формулировок аксиом системы Z1 будет теперь легко осуществить читателю, заведомо не полна: суждение "группа состоит

34

из 7 элементов"не может быть ни доказано, ни опровергнуто в рамках формальной теории групп, поскольку существует модель этой теории, в которой это суждение верно (циклическая группа порядка 7), и существует модель, в которой оно не верно (аддитивная группа целых чисел). Тем удивительнее тот факт, что существуют достаточ- но богатые теории, описываемые сравнительно простыми полными системами аксиом. Примером является теория вещественно упорядо- ченных полей, которую мы сейчас и опишем. В этой теории два символа констант 0 и 1, два трехместных предиката S(x; y; z) P (x; y; z)

и двухместный предикат O(x; y), содержательно соответствующий

неравенству x < y. Читатель по аналогии с аксиомами Z1 без труда

перепишет в формальном виде аксиомы поля. Кроме них, в систему аксиом вещественно упорядоченного поля входят три аксиомы неравенства

(1)8x8y((x = y) _ (O(x; y)) _ O(y; x));

(2)8x8y(:(O(x; y)&O(y; x));

(3)8x8y8z8t((O(0; x)&O(0; y)&S(x; y; z)&P (x; y; t)) !

!(O(0; z)&O(0; t)))

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

(4n) 8a08a1 : : : 8an8x8y

(O(0; a0 +a1x+ +anxn)&O(a0 +a1y+ +anyn; 0)&O(x; y)) ! ! (9z(O(x; z)&O(z; y)&(a0 + a1z + + anzn = 0))).

Упрощение, которое мы сделали в последней аксиоме, состоит в том, что мы не сводили вычисление значения многочлена к предикатам S

и P ; это можно было бы легко сделать, значительно увеличив число

переменных в формуле (количество новых переменных зависит только от n). Смысл последней аксиомы очевиден: если многочлен в двух

точках принимает значения разных знаков, то у него в промежутке между этими точками есть корень.

x 9. Примитивно рекурсивные функции

1. Элементарные функции. Как обычно, мы обозначаем через N0

множество, состоящее из 0 и всех натуральных чисел. Все функции, рассматриваемые в этой главе, являются функциями нескольких переменных x1; x2; : : : èç N0 со значениями в N0. Следующие функции мы будем называть элементарными:

o(x1) = 0; s(x1) = x1 + 1;

35

id(x1) = x1;

pr1(x1; x2) = x1; pr2(x1; x2) = x2:

2. Подстановка. Пусть f(x1; : : : ; xn); g1(x1; : : : ; xm); : : : ; gn(x1; : : : ; xm)

некоторые функции; мы будем говорить, что функция

h(x1; : : : ; xm) = f(g1(x1; : : : ; xm); : : : ; gn(x1; : : : ; xm))

получена из функций f; g1; : : : ; gn подстановкой.

3. Примитивная рекурсия. Опишем еще один способ построения

новых функций из уже имеющихся. Этот способ называется примитивной рекурсией и по существу представляет собой построение зна- чений функции по индукции. Точнее, пусть

h(x1; : : : ; xn 1); g(x1; : : : ; xn 1; xn; xn+1)

две функции; мы говорим, что функция f(x1; : : : ; xn 1; xn) полу- чена из них примитивной рекурсией, если

f(x1; : : : ; xn 1; 0) = h(x1; : : : ; xn 1);

f(x1; : : : ; xn 1; xn + 1) = g(x1; : : : ; xn 1; xn; f(x1; : : : ; xn 1; xn)):

Ясно, что каждое значение функции f может быть найдено по этим формулам, и притом однозначно, так что функция f однозначно определена функциями h; g.

4. Примитивно рекурсивные функции. Все функции, которые

могут быть получены при помощи операций подстановки и примитивной рекурсии из элементарных функций o; s; id; pr1; pr2, называ- ются примитивно рекурсивными. Точнее говоря,

(1)функции o; s; id; pr1; pr2 примитивно рекурсивны;

(2)åñëè f(x1; : : : ; xn); g1(x1; : : : ; xm); : : : ; gn(x1; : : : ; xm) примитивно рекурсивные функции, то и функция

h(x1; : : : ; xm) = f(g1(x1; : : : ; xm); : : : ; gn(x1; : : : ; xm));

полученная из них подстановкой функция, примитивно рекурсивна;

(3)если h; g примитивно рекурсивные функции, то функция,

полученная из них при помощи примитивной рекурсии, примитивно рекурсивна;

(4)функции, которые не могут быть получены из элементарных функций многократным применением операций подстановки и примитивной рекурсии, не являются примитивно рекурсив-

íûìè.

36

5. Простейшие примитивно рекурсивные функции. Проекции

pr(in)(x1; : : : ; xi; : : : ; xn) = xi (1 i n)

являются примитивно рекурсивными функциями, поскольку при n > 2 они получаются из элементарных функций pr1, pr2 подстановками

pr(in)(x1; : : : ; xn) = prs1 (x1; prs2 (x2; : : : ; prsn 1 (xn 1; xn) : : : ));

ãäå sj = 2 ïðè j < i, sj = 1 при j i, а функция pr(1)1 тождественной функцией id.

Для любого c 2 N0 функция c(x1; : : : ; xn), принимающая при всех значениях аргументов одно и то же значение c, тоже получается подстановками и потому примитивно рекурсивна:

0(x1; : : : ; xn) = o(pr(1n)(x1; : : : ; xn)); 1(x1; : : : ; xn) = s(0(x1; : : : ; xn)); 2(x1; : : : ; xn) = s(1(x1; : : : ; xn)); : : :

(для получения функции c надо проделать c + 2 подстановок).

Сумма sum(x1; x2) = x1 + x2 может быть определена при помощи примитивной рекурсии

а произведение prod(x1; x2) = x1x2 при помощи примитивной рекурсии

В дальнейшем мы не будем проявлять столь щепетильный формализм, как в рассмотренных примерах, и будем обычно употреблять для вводимых функций более естественные обозначения; читатель легко сможет восстановить пропущенные детали. В частности, аргументы функций мы не всегда будем обозначать x1; x2; : : : , а для суммы и произведения будем обычно использовать привычные знаки x + y; xy.

Нам будут полезны три простые функции s (x), sgn(x) (знак) и sgn(x) (антизнак), определенные следующими примитивными рекурсиями:

Функция s сопоставляет каждому числу, кроме 0, предшествующее ему число, а число 0 не двигает; функции sgn и sgn положительные

37

натуральные числа отображает соответственно в 1 и 0, а число 0, наоборот, отображают соответственно в 0 и 1.

Разность и частное натуральных чисел из N0 не всегда принадле- æàò N0, поэтому приходится использовать их некоторые видоизменения. Усеченной разностью x y называется функция двух аргументов x; y 2 N0, определенная следующим образом:

x y =

x y; åñëè x y;

0; åñëè x < y.

Вместо частного x=y используется неполное частное [x=y]. При y > 0 это такое целое число, что [x=y]y x; ([x=y] + 1)y > x; для того,

чтобы сделать неполное частное определенными всегда, условимся считать, что [x=0] = 0. Усеченная разность и неполное частное полу-

чаются следующими примитивными рекурсиями: x 0 = x; x (y + 1) = s (x y);

[0=y] = 0; [(x + 1)=y] = [x=y] + sgn(x + 2 ([x=y] + 1)y) sgn(y):

Вместе с усеченной разностью и неполным частным примитивнорекурсивными функциями являются также модуль разности

jx yj = (x y) + (y x)

и остаток rest(x; y) = x [x=y]y от деления числа x на число y. Отметим, что rest(x; 0) = x.

6. Суммы и произведения с переменными пределами. Для примитивно рекурсивной функции f(x1; : : : ; xn 1; xn) положим

xn

X

F (x1; : : : ; xn 1; xn) = f(x1; : : : ; xn 1; i):

i=0

Эта функция примитивно рекурсивна, так как она может быть определена примитивной рекурсией

F (x1; : : : ; xn 1; 0) = f(x1; : : : ; xn 1; 0);

F (x1; : : : ; xn 1; xn + 1) = F (x1; : : : ; xn 1; xn) + f(x1; : : : ; xn 1; xn + 1):

Отсюда следует, что примитивно рекурсивна и функция

f(x1; : : : ; xn 1; i) = ( f(x1; : : : ; xn 1; i) f(x1; : : : ; xn 1; i))+

i=xn i=0 i=0

+ sgn((xn+1 + 1) xn)f(x1; : : : ; xn 1; xn):

Подставляя вместо xn; xn+1 произвольные примитивно рекурсивные функции g(x1; : : : ; xn 1; xn); h(x1; : : : ; xn 1; xn), получаем, что функция

h(x1;:::;xn)

X

f(x1; : : : ; xn 1; i)

i=g(x1;:::;xn)

38

тоже примитивно рекурсивна. Таким же образом показывается, что произведение значений примитивно рекурсивной функции с переменными верхним и нижним пределами, выражаемыми примитивно рекурсивными функциями, само является примитивно рекурсивной функцией.

7. Кусочное задание примитивно рекурсивной функции. Для

функций g1(x1; : : : ; xn); : : : ; gm(x1; : : : ; xn), никакие две из которых ни при каких значениях переменных не обращаются одновременно в 0, и для любых функций h1(x1; : : : ; xn); : : : ; hm(x1; : : : ; xn); h(x1; : : : ; xn)

следующим образом определим функцию f(x1; : : : ; xn):

Тогда, очевидно,

f= h1sgn(g1) + + hmsgn(gm) + h sgn(g1 gm);

èесли все функции g1; : : : ; gm; h1; : : : ; hm; h примитивно рекурсивны, то и функция f(x1; : : : ; xn) примитивно рекурсивна.

8. Ограниченная минимизация. Пусть функция f(x1; : : : ; xn; t)

такова, что для любых x1; : : : ; xn уравнение f(x1; : : : ; xn; t) = 0 имеет решение (напомним, что значения функции и все аргументы предполагаются принадлежащими множеству натуральных чисел N0, òàê что и решение предполагается натуральным). Обозначим наименьшее решение этого уравнения через ( tf)(x1; : : : ; xn). Мы получили функцию tf от первых n аргументов x1; : : : ; xn функции f; она называется минимизацией по t функции f(x1; : : : ; xn; t).

Вообще говоря, минимизация tf не примитивно рекурсивна, даже если f примитивно рекурсивна. Однако, если f примитивно рекур-

сивна и при этом существует такая примитивно рекурсивная функция g(x1; : : : ; xn), что для любых x1; : : : ; xn найдется решение t уравнения f(x1; : : : ; xn; t) = 0, не превосходящее g(x1; : : : ; xn), òî tf примитивно рекурсивная функция. Действительно,

g(x1;:::;xn) i

В самом деле, фигурирующее в этой формуле произведение отлично от 0 лишь до тех пор, пока мы не дойдем до решения t0 уравнения (а мы до него дойдем по условию), и в сумме слагаемые, отвечающие индексам i < t0, равны 1, а все остальные слагаемые равны 0.

39

9. Теоретико-числовые функции. Количество всех делителей чис-

ëà x

x

X

div(x) = sgn(rest(x; i))

i=0

и количество простых чисел, не превосходящих x,

x

X

(x) = sgn(jdiv(i) 2j)

i=0

являются примитивно рекурсивными, как композиции примитивно рекурсивных функций (мы считаем, что div(0) = 0, а во второй фор-

муле используем, что число является простым тогда и только тогда, когда число его делителей равно 2).

Перенумеруем все простые числа в порядке возрастания: p0 = 2; p1 = 3; p2 = 5; : : :

Тогда x-е простое число это наименьшее число y, такое что (y) = x + 1, то есть px = ( yg)(x), где g(x; y) = j (y) (x + 1)j. Таким образом, функция px получается минимизацией из примитивно рекурсивной функции j (y) (x + 1)j, и для доказательства е¼ прими-

тивной рекурсивности достаточно доказать, что решение уравнения j (y) (x+1)j = 0 ограничено сверху примитивно рекурсивной функ- цией от x. Но это действительно так: px 22x ; в самом деле, это верно для x = 0, и, если это доказано для всех меньших x значений аргу-

мента, то

px p0p1 px 1 + 1 220 221 22x 1 + 1 < 2 21+2+ +2x 1 = 22x ;

ибо число N = p0p1 px 1 + 1 не делится ни на одно из чисел p0; p1; : : : ; px 1 и потому все его простые делители (а хотя бы один простой делитель существует) больше px 1 и не больше N, а, значит, px N. Обозначим через exp(x; y) показатель степени, с которым простое число px входит в разложение y в произведение простых чи-

i=1

так что exp(x; y) тоже примитивно рекурсивная функция.

10. Координатные функции. Пусть n 1 натуральное чис-

ло; построим примитивно рекурсивные функции c(1n)(x),. . . , c(nn)(x), d(n)(x1; : : : ; xn), такие что

d(n)(c(1n)(x); : : : ; c(nn)(x)) = x; c(in)(d(n)(x1; : : : ; xn)) = xi (1 i n)

äëÿ âñåõ x; x1; : : : ; xn 2 N0. Эти равенства в точности означают, что наши функции осуществляют взаимно обратные биективные отобра-

40