%LOGIC1
%\input amstex
\documentstyle{amsppt}
\usepackage[cp866]{inputenc}
\define\sm{\operatorname{sum}}
\define\id{\operatorname{id}}
\define\pr{\operatorname{pr}}
\define\prd{\operatorname{prod}}
\define\sg{\operatorname{sgn}}
\define\rst{\operatorname{rest}}
\topmatter
\title Математическая логика\endtitle
\author А.~В.~Яковлев \endauthor
\endtopmatter
%\magnification=1200
\document
\head 1. Исчисление высказываний
\endhead
\subhead 1.1.Арифметика высказываний
\endsubhead
В этом пункте мы не заботимся о строгости изложения. Основным
понятием является понятие {\it высказывания}. Высказыванием мы
называем любое утверждение, про которое можно сказать, истинно оно
или ложно. Конечно, эту фразу нельзя принять за строгое
определение понятия высказывания; мы просто свели его к другому
термину {\it утверждение}. Впрочем, вряд ли возможно дать ни на
что не опирающееся строгое определение какого-либо первоначального
понятия. Подобную же ситуацию мы имели для множеств: никакого
точного определения множества мы дать не могли, и было возможно
привести лишь несколько синонимов этого понятия (совокупность,
коллекция и т.п.), позволяющих составить о нем представление.

Приведем несколько примеров высказываний.
\roster
\item $2\times 2=4$.
\item Волга впадает в Каспийское море.
\item Наполеон умер 5 мая 1821 года.
\item Третье тысячелетие начнется 1 января 2000 года.
\item Медианы невырожденного треугольника делятся их точкой пересечения
пополам.
\item Среди первых $10^{100}$ цифр десятичного разложения числа $e+\pi $
встретятся подряд $10^{89}$ нулей.
\endroster\noindent
Высказывания (1)-(3) истинны, высказывания (4) и (5) ложны. Что
касается высказывания (6), то мы не знаем, и вряд ли когда сможем
узнать, истинно оно или ложно; однако, это тем не менее является
высказыванием, потому что оно или выполняется, или нет, независимо
от того, знаем ли мы правильный ответ.

Будем обозначать высказывания большими латинскими буквами,
воз\-мож\-но, с индексами: $A$, $B$, $C$, $D_i$, $\bar A'$ и т.д.
Пусть нам дан некоторый набор высказываний, которые мы будем
называть {\it простыми} высказываниями. Из них можно составлять
новые высказывания при помощи нескольких элементарных конструкций.
Например, если $A$ и $B$ --- простые высказывания, то мы можем
составить высказывания "$A$ {\bf и} $B$",  "$A$ {\bf или} $B$",
"{\bf или} $A$, {\bf или} $B$",  "{\bf из} $A$ {\bf следует} $B$",
"$A,B$ {\bf эквивалентны}", "{\bf не} $B$". Хотя смысл этих новых
высказываний представляется ясным, необходимо внести некоторые
уточнения и разъяснения: ведь наш разговорный язык зачастую
допускает неоднозначное толкование, а в математике такое положение
недопустимо.

Высказывание "$A$ {\bf и} $B$" называется {\it конъюнкцией}
высказываний $A$ и $B$; оно означает, что одновременно выполняются
и $A$, и $B$. Для конъюнкции высказываний $A$ и $B$ используется
обозначение $A\&B$. Высказывание $A\&B$ истинно тогда и только
тогда, когда истинны оба высказывания $A$ и $B$; если хотя бы одно
из высказываний $A$, $B$ ложно, то и их конъюнкция $A\&B$ ложна.

Высказывание "$A$ {\bf или} $B$" означает, что выполняется хотя бы
одно из высказываний $A$, $B$. Подчеркнем, что могут выполняться и
оба высказывания; в разговорном русском языке слово "или" иногда
понимается в том смысле, что должно выполняться в точности одно из
высказываний. Обозначается высказывание "$A$ {\bf или} $B$" через
$A\lor B$ и называется {\it дизъюнкцией} $A$ и $B$. Дизъюнкция
$A\lor B$ истинна, если истинно хотя бы одно из высказываний $A$,
$B$; она является ложной только в том случае, когда ложны оба
высказывания $A$, $B$. Еще раз подчеркнем разницу между
дизъюнкцией и так называемой {\it разделительной дизъюнкцией}
"{\bf или} $A$, {\bf или} $B$", которая является истинной тогда,
когда истинно в точности одно из высказываний $A$, $B$.

Точный смысл высказывания "{\it не} A" совпадает с общепринятым:
оно истинно, если $A$ ложно, и оно ложно, если $A$ истинно. Это
высказывание называется отрицанием высказывания $A$ и обозначается
$\lnot A$.

Высказывание "$A,B$ {\bf эквивалентны}" тоже имеет общепринятый
смысл: оно истинно, если оба высказывания $A$, $B$ одновременно
истинны или одновременно ложны, и оно ложно, если одно из
высказываний $A$, $B$ истинно, а другое ложно. Это высказывание
называется эквивалентностью и обозначается $A\leftrightarrow B$.

Наконец, высказывание "{\bf из} $A$ {\bf следует} $B$", называемое
{\it импликацией} и записываемое в виде $A\rightarrow B$,
считается ложным только если $A$ истинно, а $B$ ложно. Таким
образом, из ложной посылки следует все, что угодно, а из истинной
посылки следуют только истинные высказывания. В обыденной речи мы
не всегда понимаем следование именно в таком смысле, поэтому
приведенное выше уточнение понятия импликации было необходимым.
Отметим классический пример истинной импликации, приведенный
Хаусдорфом в его "Теории множеств": если $1=0$, то все ведьмы
зеленые.

Применяя несколько раз эти операции, мы можем составить новые,
более сложные высказывания. Укажем несколько примеров таких
составных высказываний: $\lnot((A\&B)\rightarrow C)\leftrightarrow
(B\&C)$, $((A\rightarrow B) \rightarrow C)\leftrightarrow
(A\rightarrow (B\rightarrow C))$, $(\lnot(A\lor B))\rightarrow
(\lnot A\&\lnot B)$. Если нам известно, истинны или ложны простые
высказывания $A$, $B$, $C$, то мы легко можем вычислить значение
истинности для любого составного высказывания. В качестве примера
проделаем это для высказывания $\lnot((A\&B)\rightarrow C)
\leftrightarrow (B\&C)$, предположив, что $A$ ложно, а $B$ и $C$
истинны. Высказывание $A\&B$ ложно, так как ложной является одна
из компонент конъюнкции; поэтому импликация $(A\&B)\rightarrow C$
истинна, Значит, отрицание этой импликации
$\lnot((A\&B)\rightarrow C)$ ложно. Далее, конъюнкция двух
истинных высказываний $B\&C$ истинна, и потому эквивалентность
$\lnot((A\&B)\rightarrow C) \leftrightarrow (B\&C)$ истинного и
ложного высказываний ложна.

Тот факт, что высказывание истинно, будем обозначать буквой $"и"$,
а ложным высказываниям будем сопоставлять букву $"л"$. Значение
истинности высказывания $A$ будем обозначать $|A|$.



\subhead 1.2. Алгебра высказываний
\endsubhead
Так же, как при переходе от арифметики к алгебре мы вместо
конкретных натуральных чисел начинаем рассматривать произвольные
числа, обозначаемые буквами $x$, $y$ и т.д., будем обозначать
буквами $X_1$, $X_2$, \dots произвольные высказывания. Из них
можно составлять новые высказывания. Точнее говоря, высказывания
определяются следующим образом.

\proclaim{Определение}
\roster \item $"и"$ и $"л"$ --- высказывания;
\item $X_n$ --- высказывание для всякого натурального числа
$n\ge 1$;
\item если $A$, $B$ --- высказывания, то $(A\& B)$, $(A
\lor B)$, $(A\rightarrow B)$, $(A\leftrightarrow B)$, $(\neg A)$
--- тоже высказывания.
\endroster\noindent
Никакое выражение, которое не может быть получено по указанным
правилам, не является высказыванием.
\endproclaim

Таким образом, всякое высказывание --- это слово в алфавите,
состоящем из букв $"("$, $")"$, $"\&"$, $"\lor"$, $"\rightarrow
"$, $"\leftrightarrow"$, $"и"$, $"л"$, $"X_n"$ (но не все слова
являются высказываниями). Обычно бывает неудобно использовать
бесконечный алфавит; этого можно избежать, если вместо
бесконечного числа букв $X_n$ оставить всего две буквы --- $X$ и
$'$, и ввести обозначения: $X_1=X$, $X_2=X'$, $X_3=X''$ и т.д.

В определении высказывания важную роль играют скобки; они дают
возможность  однозначно восстановить построение высказывания из
простейших высказываний $"и"$, $"л"$, $"X_n"$. Однако, в
дальнейшем мы будем опускать для сокращения записи часть скобок,
считая, что операция $\neg$ предшествует операциям $\&$, $\lor$, а
эти две операции предшествуют операциям $\rightarrow$,
$\leftrightarrow$, так же, как в алгебре возведение в степень
предшествует умножению и делению, а они предшествуют сложению и
вычитанию. Любое высказывание, кроме $"и"$, $"л"$, $"X_n"$,
заключено в скобки; эти наружные скобки мы будем, как правило,
опускать. Наконец, мы будем опускать скобки в конъюнкциях и
дизъюнкциях более чем двух высказываний, считая, что сначала
действие производится над первыми двумя высказываниями, затем над
полученным высказыванием и третьим высказыванием и т.д. Например,
полной записью высказывания $X_1\&X_2\&X_3\&X_4$ будет
$(((X_1\&X_2)\&X_3)\&X_4)$.

 Высказывания $X_i$ называются
элементарными высказываниями. Всякое от\-ображение множества
элементарных высказываний $\{X_i\,|\,i=1,2,\dots\}$ в множество из
двух элементов $\{и,л\}$ естественным образом продолжается по
описанным выше правилам до отображения в $\{и,л\}$ всего множества
высказываний. Таким образом, каждому высказыванию $A$ отвечает его
функция истинности, сопоставляющая каждому набору значений
истинности элементарных высказываний значение истинности
высказывания $A$. Например, функция истинности рассмотренного выше
высказывания $A=\lnot((X_1\&X_2)\rightarrow X_3) \leftrightarrow
(X_2\&X_3)$ описывается следующей таблицей значений:
$$\left.\matrix X_1\\X_2\\X_3\\\text{---}\\A
\endmatrix \right|\matrix \text{ и}&\text{ и}&\text
{ и}&\text{ и}&\text{ л}&\text{ л}&\text{ л}&\text{ л}\\\text{ и}
&\text{ и}&\text{ л}&\text{ л}&\text{ и}&\text{ и}& \text{
л}&\text{ л}\\ \text{ и}&\text{ л}&\text{ и}&\text{ л}&\text{
и}&\text{ л} &\text{ и}&\text{
л}\\\text{---}&\text{---}&\text{---}&\text{---} &\text{---}&
\text{---}&\text{---}&\text{---}\\\text{ л}&\text{ л} &\text{
и}&\text{ и}&\text{ л}&\text{ и}&\text{ и}&\text{ и}
\endmatrix $$

Пусть $I$ --- некоторое конечное множество индексов; мы будем
обозначать через $\bigvee\limits_{i\in I}A_i$ и
$\bigwedge\limits_{i\in I}A_i$  дизъюнкцию и конъюнкцию
высказываний $A_i$, $i\in I$, взятых в произвольном порядке (все
утверждения, в формулировке которых будут участвовать эти
обозначения, выполняются при любом порядке высказываний).
Конъюнкция пустого множества высказываний считается равной
высказыванию "и", а дизъюнкция пустого множества высказываний ---
высказыванию "л".
\proclaim{Теорема}Пусть $\{и,л\}^n$ --- $n$-я декартова степень
множества $\{и,л\}$, т.е. множество всех наборов
$(\varepsilon_1,\dots,\varepsilon_n)$, таких что $\varepsilon_i=и$
или $\varepsilon_i=л$ для любого $i$, $1\le i\le n$. Далее, пусть
$I$ --- подмножество $\{и,л\}^n$. Суждение
$$X_I=\bigvee_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}((\bigwedge_{i,\varepsilon_i=и}X_i)\&(\bigwedge_{j,\varepsilon_j=л
} \neg X_j))$$ истинно тогда и только тогда, когда
$(|X_1|,\dots,|X_n|)\in I$.
\endproclaim

\demo{Доказательство}Конъюнкция
$(\bigwedge\limits_{i,\varepsilon_i =и} X_i)\&(
\bigwedge\limits_{j,\varepsilon_j=л } \neg X_j)$ истинна тогда и
только тогда, когда элементарное высказывание $X_i$ истинно при
условии, что $\varepsilon_i\!\!=\!\!и$ и ложно при условии
$\varepsilon_i\!\!=\!\!л$; иными словами, эта конъюнкция истинна,
если и только если $(|X_1|,\dots,|X_n|)=(\varepsilon_1,\dots,
\varepsilon_n)$. Высказывание $X_I$ является дизъюнкцией тех из
этих конъюнкций, которые отвечают наборам $(\varepsilon_1,\dots,
\varepsilon_n)$, принадлежащим $I$; она истинна тогда и только
тогда, когда истинна одна из этих конъюнкций, т.е. когда
$(|X_1|,\dots,|X_n|)\in I$.
\enddemo
\proclaim{Следствие 1}Если подмножества $I$, $J$ множества
$\{и,л\}^n$ не совпадают, то и функции истинности, отвечающие
высказываниям $X_I$, $X_J$ не совпадают.\endproclaim
\proclaim{Следствие 2}Пусть $f(\xi_1,\dots,\xi_n):\{и,л\}^n\to
\{и,л\} $ ---  функция, сопоставляющая каждому набору значений
истинности элементарных высказываний один из символов $"и"$,
$"л"$. Существует высказывание $X$, функция истинности для
которого совпадает с $f(\xi_1,\dots,\xi_n)$, т.е. такое
высказывание, что $|X|=f(|X_1|,\dots,|X_n|)$.
\endproclaim
\demo{Доказательство}Пусть $I\subseteq \{и,л\}^n$ --- множество
всех тех наборов $(\varepsilon_1,\dots, \varepsilon_n)$, для
которых $f(\varepsilon_1,\dots, \varepsilon_n)=и$. Тогда
высказывание $X_I$ истинно тогда и только тогда, когда
$(\varepsilon_1,\dots, \varepsilon_n)\in I$, т.е. когда
$f(\varepsilon_1,\dots, \varepsilon_n)=и$.
\enddemo

 Бывают такие высказывания, которые являются
истинными при любых значениях истинности основных высказываний
$X_1,X_2,\dots $; такие высказывания называются {\it тождественно
истинными} или {\it тавтологиями}. Приведем не\-ско\-лько примеров
тавтологий: $$X_1\&X_2\rightarrow X_1,\quad X_1\rightarrow(\lnot
X_1\lor X_1), \quad ((X_2\&\neg X_1)\rightarrow(л))\rightarrow
(X_2\rightarrow X_1).$$



\subhead 1.3. Булевы алгебры\endsubhead Рассмотрим один тип
алгебраических структур, который очень хорошо приспособлен для
описания алгебры высказываний.
\proclaim{Определение}Булевой алгеброй называется множество $B$, на
котором заданы две бинарных операции --- сложение "+" и умножение
"$\cdot$", одна унарная операция --- дополнение $x\to x'$ и в
котором выделены две константы --- 0 и 1, причем для любых
элементов $x,y,z\in B$ выполняются следующие соотношения: \roster
\item (законы поглощения) \  $x+x=x$, $x\cdot x=x$;
\item (коммутативность) \ $x+y=y+x$, $x\cdot y=y\cdot x$;
\item (ассоциативность) \ $x+(y+z)=(x+y)+z$, $x\cdot(y\cdot z)=(x
\cdot y)\cdot z$;
\item (дистрибутивность) \ $x\cdot (y+z)=(x\cdot y)+ (x\cdot z)$,
$(x\cdot y)+z=(x+z)\cdot(y+z)$;
\item (свойства 0 и 1) \ $x\cdot 0=0$, $x\cdot 1=x$, $x+0=x$,
$x+1=1$;
\item (свойства дополнения) \ $x\cdot x'=0$, $x+x'=1$, $(x+y)'=
x'\cdot y'$, $(x\cdot y)'=x'+y'$, $(x')'=x$.
\endroster
\endproclaim
Важнейшим примером булевой алгебры является множество $P(A)$ всех
подмножеств некоторого множества $A$; действия над подмножествами
определены следующим образом: для любых $X,Y\subseteq A$
$$X+Y=X\cup Y,\,\,X\cdot Y=X\cap Y,\,\,X'=A\setminus X=\{a\in
X\,|\,a\notin X\}. $$ Единицей булевой алгебры $P(A)$ является все
множество $A$, а нулем --- пустое подмножество.

В дальнейшем мы часто будем опускать знак умножения $\cdot$ и
часть скобок, пользуясь привычными соглашениями о том, что
умножение предшествует сложению. Например, выражение $xy+ztu$ в
развернутом виде выглядит так: $(x\cdot y)+(z\cdot(t\cdot u))$.

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

В последующих рассуждениях нам будет удобно применять следующее
обозначение. Пусть $b$ --- элемент некоторой булевой алгебры, и
пусть $\varepsilon$ равно 1 или -1; через $b^\varepsilon$ мы будем
обозначать элемент $b$, если $\varepsilon=1$, и элемент $b'$, если
$\varepsilon=-1$.

Пусть $B$ --- произвольная булева алгебра, и пусть
$b_1$,\dots,$b_n$ --- какие-то элементы из $B$.  Если $I$ ---
подмножество $n$-й декартовой степени $\{1,-1\}^n$ множества
$\{1,-1\}$, то обозначим
$b_I=\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}(\prod\limits_{i=1}^nb_i^{\varepsilon_i})$. В частности,
$b_{\emptyset}=0$, \ \
$b_{\{1,-1\}^n}=\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)}
(\prod\limits_{i=1}^nb_i^{\varepsilon_i})=\prod\limits_{i=1}^n(b_i+b_i')=1$.
\proclaim{Лемма}Для любых подмножеств $I,J\subseteq \{1,-1\}^n$
$$b_I+b_J=b_{I\cup J},\quad b_I\cdot b_J=b_{I\cap J},\quad
b_I'=b_{P(n)\setminus I}. $$ Кроме того, для любого $s$, $1\le s
\le n$, элемент $b_s$ совпадает с $b_{I(s)}$, где $I(s)$ ---
множество всех тех наборов $(\varepsilon_1,\dots,\varepsilon_n)$,
в которых $\varepsilon_s=1$. Таким образом, множество
$S(b_1,\dots,b_n)$ всех элементов $b_I$ является подалгеброй
булевой алгебры $B$; она содержит элементы $b_1,\dots,b_n$ и
содержится в любой подалгебре булевой алгебры $B$, обладающей этим
свойством.
\endproclaim
\demo{Доказательство}Утверждение $b_I+b_J=b_{I\cup J}$ сразу
следует из закона поглощения для суммы. Заметим теперь, что если
$(\varepsilon_1,\dots,\varepsilon_n)\ne (\delta_1,\dots,\delta_n)$
существует номер $s$, такой что $\varepsilon_s\ne\delta_s$;
поэтому произведение
$(\prod\limits_{i=1}^nb_i^{\varepsilon_i})\cdot
(\prod\limits_{i=1}^nb_i^{\delta_i})$ содержит сомножители $b_s$,
$b_s'$ и потому равно 0. Из дистрибутивности и законов поглощения
для умножения и сложения следует, что произведение $$b_I\cdot
b_J=(\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}(\prod\limits_{i=1}^nb_i^{\varepsilon_i}))\cdot(\sum
\limits_{(\delta_1,\dots,\delta_n)\in
J}(\prod\limits_{i=1}^nb_i^{\varepsilon_i}))$$ состоит только из
таких слагаемых $\prod\limits_{i=1}^nb_i^{\varepsilon_i}$, которые
входят и в $b_I$, и в $b_J$, и потому $b_I\cdot b_J=b_{I\cap J}$.

Пусть теперь $J=\{1,-1\}^n\setminus I$; из уже доказанного
следует, что $b_I+b_J=b_{I\cup J}=1$, $b_I\cdot
b_J=b_{\emptyset}=0$. Поэтому
$b_I'=b_I'(b_I+b_J)=b_I'b_i+b_I'b_J=0+b_I'b_J=b_Ib_J+b_I'b_J=
(b_I+b_I')b_J=1\cdot b_J=b_J$.

Наконец, $b_s=b_s\prod\limits_{i\ne
s}(b_i+b_i')=\sum\limits\Sb(\varepsilon_1,\dots,\varepsilon_n)
\\\varepsilon_s=1 \endSb \prod\limits_{i=1}^nb_i^{\varepsilon_i}=b_{I_s}$.
\enddemo

Будем говорить, что построенная в только что доказанной лемме
подалгебра $S(b_1,\dots,b_n)$ порождена элементами
$b_1,\dots,b_n$. Если $S(b_1,\dots,b_n)=B$, то говорим, что
$b_1,\dots,b_n$ --- порождающая система булевой алгебры $B$; если
к тому же все элементы $b_I$, $I\subseteq \{1,-1\}^n$, различны,
то говорим, что $B$ --- свободная булева алгебра со свободными
образующими $b_1,\dots,b_n$. Из этого определения следует, что
свободная булева алгебра с $n$ свободными образующими состоит из
$2^{2^n}$ элементов.

Пусть теперь $\{b_i\,|\,i\in I \}$ --- какое-то, вообще говоря,
бесконечное семейство элементов из $B$. Будем говорить, что булева
алгебра $B$ порождена этим семейством, если для любого элемента
$x\in B$ существует его конечное подсемейство
$\{b_{i_1},\dots,b_{i_n}\}$, такое что $x\in S(b_{i_1},\dots,
b_{i_n})$. Далее, если булева алгебра $B$  порождена семейством
$\{b_i\,|\,i\in I \}$ и если для каждого конечного подсемейства
$\{b_{i_1},\dots,b_{i_n}\}$ множество $S(b_{i_1},\dots,b_{i_n})$
является свободной булевой алгеброй со свободными образующими
$b_{i_1},\dots,b_{i_n}$, то мы говорим, что $B$ --- свободная
булева алгебра со свободными образующими $\{b_i\,|\,i\in I \}$.



\subhead 1.4. Булева алгебра высказываний\endsubhead
 Будем говорить, что два высказывания $A$, $B$ эквивалентны, если
высказывание $A\leftrightarrow B$ является тавтологией. Поскольку
эквивалентность истинна тогда и только тогда, когда обе её части
имеют одинаковое значение истинности, приходим к выводу: два
высказывания $A$, $B$ эквивалентны тогда и только тогда, когда при
любых значениях истинности элементарных высказываний $X_i$ оба
высказывания $A$, $B$ одновременно истинны или ложны. Отсюда и из
того факта, что значение истинности высказываний $A\&B$, $A\lor
B$, $\neg A$, $A\rightarrow B$, $A\leftrightarrow B$ вполне
определяется значениями истинности высказываний $A$, $B$, сразу
вытекает следующее важное утверждение.
\proclaim{Лемма}\roster
\runinitem Всякое высказывание эквивалентно самому себе.
\item Если высказывание $A$ эквивалентно высказыванию $B$, то
высказывание $B$ эквивалентно высказыванию $A$.
\item Если высказывание $A$ эквивалентно высказыванию $B$, а
высказывание $B$ эквивалентно высказыванию $C$, то высказывание
$A$ эквивалентно высказыванию $C$.
\item Если высказывание $A_1$ эквивалентно высказыванию $A$, а
высказывание $B_1$ эквивалентно высказыванию $B$, то высказывания
$A_1\&B_1$, $A_1\lor B_1$, $\neg A_1$, $A_1\rightarrow B_1$,
$A_1\leftrightarrow B_1$ эквивалентны соответственно высказываниям
$A\&B$, $A\lor B$, $\neg A$, $A\rightarrow B$, $A\leftrightarrow
B$.
\endroster
\endproclaim

Первые три утверждения леммы показывают, что эквивалентность
высказываний действительно является отношением эквивалентности на
множестве всех высказываний. Поэтому множество высказываний
разбивается в объединение классов эквивалентности. Пусть $\frak X$
--- множество классов эквивалентности высказываний. Класс
эквивалентности, содержащий высказывание $A$, будем обозначать
через $[A]$. Определим на $\frak X$ действия сложения, умножения и
дополнения, положив $$[A]+[B]=[(A\lor B)],\quad [A]\cdot [B]=[(A\&
B)],\quad [A]'=[(\neg A)];$$ последнее утверждение леммы
показывает, что эти определения не зависят от выбора высказываний,
представляющих классы эквивалентности. Обозначим также через 0 и 1
классы $[л]$ и $[и]$, а через $x_i$ --- классы $[X_i]$.
\proclaim{Теорема}Множество $\frak X$ с введенными выше операциями
является свободной булевой алгеброй со свободными образующими
$x_i$, $i=1,2,\dots $. Для любых высказываний $A$, $B$ выполняются
 соотношения $[A\rightarrow
B]=[A]'+[A]\cdot[B]$, $[A\leftrightarrow B]=[A]\cdot [B]+[A]'\cdot
[B]'$. Высказывания $A$, $B$ эквивалентны тогда и только тогда,
когда $[A]=[B]$. Высказывание $A$ является тавтологией тогда и
только тогда, когда $[A]=[и]=1$.
\endproclaim
\demo{Доказательство}Последние два утверждения приведены для
полноты и фактически содержатся в самом определении множества
$\frak X$. Далее, непосредственная проверка показывает, что
следующие пары высказываний эквивалентны, т.е. имеют одинаковые
функции истинности: \roster
\item   $A\lor A$ \ и \ $A$,\phantom{cc} $A\& A$ \ и \ $A$;
\item  $A\lor B$ \ и \ $B\lor A$,\phantom{cc} $A\& B$ \ и \ $B\& A$;
\item  $A\lor (B\lor C)$ \ и \ $(A\lor B)\lor C$,\phantom{cc} $A\&(B\& C)$ \ и \ $(A
\& B)\& C$;
\item  $A\& (B\lor C)$ \ и \ $(A\& B)\lor  (A\& C)$,\phantom{cc}
$(A\& B)\lor C$ \ и \ $(A\lor C)\&(B\lor C)$;
\item  $A\& (л)$ \ и \ $(л)$,\phantom{cc} $A\& (и)$ \ и \ $A$,
\phantom{cc} $A\lor (л)$ \ и \ $A$,\phantom{cc} $A\lor (и)$ \ и \
$(и)$;
\item $A\& (\neg A)$ \ и \ $(л)$,\phantom{cc} $A\lor (\neg A)$
 \ и \ $(и)$,\phantom{cc} $\neg(A\lor B)$ \ и \ $
(\neg A)\& (\neg B)$,\phantom{cccccccccccccc}\linebreak $\neg(A\&
B)$ \ и \ $(\neg A)\lor (\neg B)$,\phantom{cc} $\neg(\neg A)$ \ и
\ $A$;
\item $A\rightarrow B$ \ и \  $(\neg A)\lor (A\&B)$,\phantom{cc}
$A\leftrightarrow B$, $(A\&B)\lor((\neg A)\&(\neg B))$.\endroster
Все утверждения теоремы, кроме того, что элементы $x_i$ являются
свободными образующими $\frak X$, следуют отсюда; в частности,
эквивалентность пар высказываний, собранных в
\therosteritem1-\therosteritem6, показывает, что выполняются все
аксиомы булевой алгебры.

Ясно, что элементы $x_i$ порождают алгебру $\frak X$; для того,
чтобы показать, что они являются свободными образующими $\frak X$,
достаточно проверить, что для любого $n$ элементы
$x_1$,\dots,$x_n$ свободно порождают алгебру $S(x_1,\dots,x_n)$,
т.е. что для любых различных подмножеств $I$, $J$ множества
$\{0,1\}^n$ элементы
$$x_I=\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}(\prod\limits_{i=1}^nb_i^{\varepsilon_i}),\quad
x_J=\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)\in
J}(\prod\limits_{i=1}^nb_i^{\varepsilon_i})$$ различны. Но эти
элементы являются классами эквивалентности высказываний $$\gather
X_I\!=\!\bigvee_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}((\bigwedge_{i,\varepsilon_i=1}X_i)\&(\bigwedge_{j,\varepsilon_j=-1}
\neg X_j)),\\
X_J\!=\!\bigvee_{(\varepsilon_1,\dots,\varepsilon_n)\in
J}((\bigwedge_{i,\varepsilon_i=1}X_i)\&(\bigwedge_{j,\varepsilon_j=-1}
\neg X_j)),\endgather$$ которые не эквивалентны, ибо по следствию
1 из \S 1.2 они имеют различные функции истинности.
\enddemo
\subhead 1.5 Каноническая дизъюнктивно-конъюнктивная форма
высказывания \endsubhead
\proclaim{Теорема}Всякое высказывание, зависящее только от
элементарных высказываний $X_1$,\dots,$X_n$, эквивалентно
единственному высказыванию вида
$$X_I=\bigvee_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}((\bigwedge_{i,\varepsilon_i=и}X_i)\&(\bigwedge_{j,\varepsilon_j=л
} \neg X_j)),$$ где $I$ --- некоторое подмножество множества
$\{и,л\}^n$.
\endproclaim
Эта теорема немедленно следует из теоремы предыдущего пункта и из
того, что всякий элемент свободной булевой алгебры, порожденной
элементами $x_1,\dots,x_n$, однозначно представим в виде
$x_I=\sum\limits_{(\varepsilon_1,\dots,\varepsilon_n)\in
I}(\prod\limits_{i=1}^nx_i^{\varepsilon_i})$ для некоторого
подмножества $I\subseteq\{1,-1\}^n$. Такой представитель класса
эквивалентных высказываний называется канонической
дизъюнктивно-конъюнктивной формой высказывания.

\subhead 1.6 Идеалы и дуальные идеалы булевой алгебры \endsubhead
Пусть $\frak B$ --- булева алгебра; её непустое подмножество
$\frak I$ называется идеалом алгебры $\frak B$, если для любых
$x,y\in\frak I$, $b\in\frak B$ элементы $x+y$, $bx$ принадлежат
$\frak I$.

Во всякой булевой алгебре есть два тривиальных идеала --- 0 и вся
алгебра. Пусть теперь $S\subseteq\frak B$; очевидно, пересечение
всех идеалов булевой алгебры $\frak B$, содержащих $S$, снова
является идеалом алгебры $\frak B$, содержащим $S$. Этот идеал
называется идеалом, порожденным множеством $S$, и является
наименьшим идеалом, содержащим это множество элементов.
\proclaim{Теорема}Пусть $\frak B$ --- булева алгебра, и пусть $S
\subseteq\frak B$. Идеал алгебры $\frak B$, порожденный множеством
$S$, является объединением идеалов, порожденных всеми конечными
подмножествами $S$. Идеал, порожденный конечным множеством
$\{b_1,\dots,b_n\}$, порождается одним элементом $b=b_1+\dots
+b_n$ и состоит из всех элементов вида $ab$, $a\in \frak B$.
\endproclaim
\demo{Доказательство}Обозначим через $\frak J$ объединение всех
идеалов, порожденных конечными подмножествами $S$; каждый из этих
идеалов содержится в идеале $\frak I$, порожденном множеством $S$,
и потому $\frak J\subseteq\frak I$. Обратно, ясно, что $\frak J$
является идеалом алгебры $\frak B$, содержащим множество $S$ и,
поскольку $\frak I$ --- наименьший идеал, содержащий $S$, находим,
что $\frak I \subseteq\frak J$.

Пусть теперь $\frak I$ --- идеал, порожденный конечным множеством
$b_1,\dots,b_n$; тогда $b=b_1+\dots+b_n\in \frak I$. Обратно,
элемент $b_1=b_1\cdot 1=b_1(1+b_2+\dots+b_n)=b_1+
b_1(b_2+\dots+b_n)=b_1b_1+b_1(b_2+\dots+b_n)=
b_1(b_1+b_2+\dots+b_n)=b_1b$ принадлежит идеалу, порожденному
одним элементом $b$, и точно так же элементы $b_2=b_2b$, \dots,
$b_n=b_nb$ принадлежат идеалу, порожденному $b$. Итак, эти два
идеала совпадают. Остается заметить, что идеал, порожденный
единственным элементом $b$, состоит из всех элементов вида $ab$,
$a\in \frak B$.
\enddemo

В отличие от колец, где операции сложения и умножения отнюдь не
равноправны, в булевой алгебре сложение и умножение обладают
одними и теми же свойствами. В частности, если мы поменяем местами
0 и 1 и будем записывать сложение как умножение, а умножение ---
как сложение, мы снова получим булеву алгебру. Из этой дуальности
следует, что в теории булевых алгебр понятие, дуальное понятию
идеала, должно играть столь же важную роль, как и понятие идеала
(что совсем не так для колец). Итак, мы приходим к следующему
определению.

Пусть $\frak B$ --- булева алгебра; её непустое подмножество
$\frak I$ называется дуальным идеалом алгебры $\frak B$, если для
любых $x,y\in\frak I$, $b\in\frak B$ элементы $xy$, $b+x$
принадлежат $\frak I$.

Во всякой булевой алгебре есть два тривиальных дуальных идеала ---
1 и вся алгебра. Пусть теперь $S\subseteq\frak B$; очевидно,
пересечение всех дуальных идеалов булевой алгебры $\frak B$,
содержащих $S$, снова является дуальным идеалом алгебры $\frak B$,
содержащим $S$. Этот дуальный идеал называется дуальным идеалом,
порожденным множеством $S$, и является наименьшим дуальным
идеалом, содержащим это множество элементов.
\proclaim{Теорема}Пусть $\frak B$ --- булева алгебра, и пусть $S
\subseteq\frak B$. Дуальный идеал алгебры $\frak B$, порожденный
множеством $S$, является объединением дуальных идеалов,
порожденных всеми конечными подмножествами $S$. Дуальный идеал,
порожденный конечным множеством $\{b_1,\dots,b_n\}$, порождается
одним элементом $b=b_1\cdot\dots\cdot b_n$ и состоит из всех
элементов вида $a+b$, $a\in \frak B$.
\endproclaim

\subhead 1.7. Выводимость \endsubhead Пусть $S$ --- некоторое
множество высказываний; мы говорим, что высказывание $A$ выводимо
из множества высказываний $S$ и записываем это в виде $S\vdash A$,
если существует конечное (быть может, пустое) множество
высказываний $Y_1,\dots,Y_m\in S$, такое что высказывание
$(Y_1\&\dots\&Y_m)\rightarrow A$ является тождественно истинным
высказыванием (тавтологией). Пусть $A$ --- тавтология; поскольку
высказывание $(и)\rightarrow A$ тоже является тавтологией, а
тождественно истинное высказывание "и"
--- это конъюнкция пустого множества высказываний, то высказывание
$A$ выводимо из $S$.
\proclaim{Теорема}Высказывание $A$ выводимо из множества
высказываний $S$ тогда и только тогда, когда его класс $[A]$ в
булевой алгебре высказываний $\frak X$ принадлежит дуальному
идеалу, порожденному классами $[Y]$ всех высказываний $Y\in S$.
\endproclaim
\demo{Доказательство}Пусть $S\vdash A$; тогда существуют
высказывания $Y_1,\dots,Y_m\in S$, такие что высказывание
$(Y_1\&\dots\&Y_m)\rightarrow A$ тождественно истинно. Обозначим
через $Z$ высказывание $Y_1\&\dots\&Y_m$. По теореме из \S 1.4
тождественная истинность высказывания $Z\rightarrow A$ означает,
что $[Z]'+[Z][A] = 1$. Домножив обе части этого равенства на
$[Z]$, получаем: $[Z]=[Z]([Z]'+[Z][A])=[Z][A]$, откуда следует,
что элемент $$[A]=[A]([Z]+[Z]')=[A][Z] +[A][Z]'=[Z]+[A][Z]'=[Y_1]
\dots[Y_n]+A[Z]'$$ принадлежит дуальному идеалу булевой алгебры
$\frak X$, порожденному элементами $[Y_1]$,\dots,$[Y_m]$.

Обратно, пусть класс эквивалентности $[A]$ высказывания $A$
принадлежит дуальному идеалу, порожденному классами высказываний,
принадлежащих $S$. По теореме из предыдущего пункта, существуют
высказывания $Y_1,\dots,Y_n\in S$ и высказывание $X$, такие что
$[A]=[Y_1]\dots[Y_n]+[X]$. Обозначим, как и выше, через $Z$
высказывание $Y_1\&\dots\&Y_n$; тогда $[A]=[Z]+[X]$. Находим
теперь, что $[Z]'+[Z][A]=[Z]'+[Z]([Z]+[X])=[Z]'+[Z]+[Z][X]=1$, а
это означает, что высказывание $Z\rightarrow A$ тождественно
истинно, т.е. что высказывание $A$ выводимо из высказывания
$Z=Y_1\&\dots\&Y_n$.
\enddemo
%Обычное логическое рассуждение состоит в следующем. Пусть у нас
%есть некоторое множество высказываний $\frak X=\{X_i\}_{i\in I}$
%(возможно, пустое); вообще говоря, эти высказывания могут быть
%сложными высказываниями, составленными из каких-то простых
%высказываний, которые для нас не интересны и поэтому специально не
%указываются. По каким-то причинам мы знаем, что эти высказывания
%истинны, или же мы принимаем эти высказывания за истинные,
%рассматривая их как аксиомы некоторой теории. Конечно, это
%накладывает ограничения на истинность или ложность основных
%простых высказываний. Мы хотим теперь научиться выводить новые
%истинные высказывания (при тех же ограничениях на основные простые
%высказывания).
\subhead 1.8.Правила подстановки и силлогизма\endsubhead
Покажем, что если высказывание выводимо из множества
высказываний $\frak S$, то оно может быть получено многократным
применением нескольких простых правил.
\proclaim {Теорема}Пусть $S$ --- некоторое множество
высказываний.\roster \item Если $X\in S$, то $X$ выводимо из $S$.
\item Если высказывание $X$ --- тавтология, то $X$ выводимо из
$S$.
\item Если высказывания $X$, $X\rightarrow Y$ выводимы из
$S$, то и высказывание $Y$ выводимо из $S$.
\item Любое высказывание, выводимое из $S$, может
быть получено многократным применением правил (1)-(3).
\endroster\noindent\endproclaim
\demo{Доказательство}Утверждение (2) уже было отмечено выше, а
утверждение (1) тривиально: высказывание $X\rightarrow X$ является
тавтологией. Докажем теперь (3). Пусть $\frak I$ --- дуальный
идеал алгебры высказываний $\frak X$, порожденный классами всех
высказываний из $S$. Если высказывания $X$, $X\rightarrow Y$
выводимы из $S$, то, по теореме из \S 1.7, их классы $[X]$,
$[X\rightarrow Y]=[X]'+[X][Y]$ принадлежат $\frak I$, а потому и
$[Y]=[Y]+[X]([X]'+[X][Y])\in \frak I$, а это и значит, по той же
теореме, что высказывание $Y$ выводимо из $S$.

Несколько сложнее доказывается обратное утверждение (4). Сначала
индукцией по $m$ покажем, что если высказывания $Y_1$,\dots,$Y_m$
принадлежат $S$, то высказывание $Y_1\&\dots\&Y_m$ получается
применением правил (1)-(3). База индукции доставляется правилом
(1). Пусть $m>1$ и уже доказано, что высказывание
$Y_1\&\dots\&Y_{m-1}$ получается применением правил (1)-(3).
Высказывание $$(Y_1\&\dots\&Y_{m-1})\rightarrow
(Y_m\rightarrow(Y_1\&\dots\&Y_m))$$ является тавтологией, т.е. оно
получается при помощи правила (2). Применяя к последним двум
высказываниям правило (3), видим, что высказывание
$Y_m\rightarrow(Y_1\&\dots\&Y_m)$ получается применением правил
(1)-(3). Опять применяя правило (3), на сей раз к высказываниям
$Y_m\in S$, $Y_m\rightarrow(Y_1\&\dots\&Y_m)$, найдем, что
высказывание $Y_1\&\dots\&Y_m$ получается применением правил
(1)-(3).

Пусть высказывание $A$ выводимо из $S$; тогда найдутся такие
высказывания $Y_1,\dots,Y_m\in S$, что высказывание
$(Y_1\&\dots\&Y_m)\rightarrow A$ --- тавтология, т.е. оно
получается при помощи правила (2). Но мы только что доказали, что
высказывание $Y_1\&\dots\&Y_m$ получается применением правил
(1)-(3). Высказывание $A$ получается из предыдущих двух
высказываний по правилу (3).

Теорема полностью доказана.\enddemo



Правило (3) называется правилом силлогизма, или $modus\,\,
\,ponens$. Обычно его иллюстрируют следующим рассуждением:

$$\left.\aligned &\text{Все люди смертны. }\\  &\text{Сократ ---
человек. }\endaligned\,\,\right\} \quad \text{Следовательно,
Сократ смертен.}$$

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

Обратимся теперь к правилу (2). Строго говоря, это не одно
правило, а бесконечно много правил, потому что имеется бесконечно
много тавтологий. Однако,  используя $modus\,\, ponens$ и еще одно
правило --- правило подстановки --- мы можем вывести все
тавтологии из некоторого конечного множества тавтологий. Этот
основной конечный набор тавтологий можно выбрать многими
способами; мы приведем здесь один такой набор; хотя некоторые
входящие в него тавтологии могут быть выведены из других (так что
набор не минимален), нам он кажется наиболее естественным:
тавтологии (6)-(18) по существу совпадают с аксиомами булевой
алгебры, тавтологии (4) и (5) выражают характеристические свойства
дизъюнкции и конъюнкции, а остальные тавтологии из этого набора
сводят импликацию и эквивалентность к булевым операциям. \roster
\item $(A\leftrightarrow B)\rightarrow((A\rightarrow B)\&(B\rightarrow A))$;
\item $((A\rightarrow B)\&(B\rightarrow A))\rightarrow(A\leftrightarrow B)$;
\item $(A\rightarrow B)\leftrightarrow(\lnot A\lor B)$;
\item $A\rightarrow (A\lor B)$;
\item $(A\&B)\rightarrow A$;
\item $(A\&B)\leftrightarrow (B\&A)$;
\item $((A\&B)\&C)\leftrightarrow (A\&(B\&C))$;
\item $(A\&A)\leftrightarrow A$;
\item $(A\lor B)\leftrightarrow (B\lor A)$;
\item $((A\lor B)\lor C)\leftrightarrow (A\lor(B\lor C))$;
\item $(A\lor A)\leftrightarrow A$;
\item $(A\&(B\lor C))\leftrightarrow ((A\lor C)\&(B\lor C))$;
\item $(A\lor(B\& C))\leftrightarrow ((A\& C)\lor(B\& C))$;
\item $(\lnot(A\&B))\leftrightarrow (\lnot A\lor\lnot B)$;
\item $(\lnot(A\lor B))\leftrightarrow (\lnot A\&\lnot B)$;
\item $(\lnot(\lnot A))\leftrightarrow A$;
\item $(A\&(B\lor\lnot B))\leftrightarrow A$;
\item $(A\lor(B\&\lnot B))\leftrightarrow A$.
\endroster\noindent
\proclaim{Правило подстановки}Пусть $F(A_1,A_2,\dots ,A_m)$
--- тавтология, и пусть $Y_1$, $Y_2$, \dots ,$Y_m$ ---
произвольные высказывания; тогда высказывание, полученное из
$F(A_1,A_2,\dots ,A_m)$ подстановкой вместо каждого вхождения букв
$A_1$, $A_2$, \dots , $A_m$ соответствующих высказываний $Y_1$,
$Y_2$, \dots ,$Y_m$, является тавтологией.\endproclaim
\proclaim {Теорема}Любая тавтология может быть получена из
тавтологий (1)-(18) при помощи правил подстановки и силлогизма.
\endproclaim
Мы опускаем доказательство этой теоремы: она нам не понадобится.
\proclaim {Следствие}Пусть $S$ --- некоторое множество
высказываний. Любое высказывание, выводимое из $S$, может быть
получено  из тавтологий (1)-(18) и из суждений, принадлежащих $S$,
многократным применением правил подстановки и силлогизма.
\endproclaim

 \subhead 1.9. Непротиворечивость\endsubhead Будем
говорить, что множество $S$ высказываний противоречиво, если
тождественно ложное высказывание $"л"$ выводимо из $S$, т.е.
$S\vdash л$. Если же тождественно ложное высказывание не выводимо
из $S$, то множество высказываний $S$ называется непротиворечивым.
Из теоремы \S 1.7 следует, что множество высказываний $S$
противоречиво тогда и только тогда, когда дуальный идеал,
порожденный классами всех высказываний из $S$, содержит 0. Но
тогда этот дуальный идеал содержит также любой элемент $x=0\cdot
y+x$ булевой алгебры высказываний $\frak X$, т.е. он совпадает с
$\frak X$. Таким образом, из противоречивого множества
высказываний выводимо любое высказывание.


 \head 2. Исчисление предикатов
\endhead \subhead 2.1. Предикаты на множестве \endsubhead
Как и в \S 1.1, в этом пункте мы не стремимся к полной строгости;
наша цель --- дать интуитивное представление о тех понятиях,
которые будут формализованы ниже.  Пусть $M$
--- некоторое множество, и пусть для каждого набора
$c_1,\dots,c_n\in M$ задано высказывание $P(c_1,\dots,c_n)$. Мы
говорим тогда, что $P$ --- $n$-местный предикат на множестве $M$.
Для любых $c_1,\dots,c_n\in M$ высказывание $P(c_1,\dots,c_n)$
истинно или ложно; предикат $P$ полностью определяется заданием
множества $P_M\subseteq M^n$ всех тех наборов $(c_1,\dots,c_n)\in
M^n$, для которых высказывание $P(c_1,\dots,c_n)$ истинно.

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

\subsubhead{Предикат сложения}\endsubsubhead Высказывание
$P(a,b,c)$ истинно тогда и только тогда, когда $a+b=c$.

\subsubhead{Предикат строгого неравенства}
\endsubsubhead Высказывание $P(a,b)$ истинно тогда и то\-лько тогда,
когда $a<b$. \subsubhead{Предикат равенства}
\endsubsubhead Высказывание $P(a,b)$ истинно тогда и только тогда,
когда $a=b$. Поскольку предикат равенства играет особую роль, мы
будем обозначать его привычным образом, т.е. записывать
высказывание не в виде $P(a,b)$, а в виде $"a=b"$.

Из высказываний, связанных с предикатами, можно по правилам
исчисления высказываний строить новые высказывания. Например, если
$P(c_1,c_2,c_3)$, $Q(c)$, $R(c_1,c_2)$ --- предикаты на множестве
$M$, и $a,b,c\in M$, то можно составить высказывания
$(P(a,b,b)\&\neg Q(a))\lor R(b,a)$, $((a=c)\&Q(b))\rightarrow
P(a,b,c)$ и др.

Как и выше, наряду с самими высказываниями можно рассматривать
связанную с ними алгебру высказываний. Пусть, например, на
множестве $M$ заданы предикаты равенства и предикаты $P$, $Q$, $R$
из предыдущего абзаца; рассмотрим алгебру высказываний $\frak A$,
свободно порожденную всеми высказываниями видов $(a=b)$,
$P(a,b,c)$, $Q(a)$, $R(a,b)$, где элементы $a$, $b$, $c$
независимо пробегают множество $M$. Точнее говоря, \roster \item
$и,л\in \frak A$;
\item выражения $(a=b)$, $P(a,b,c)$, $Q(a)$, $R(a,b)$ принадлежат
$\frak A$ для любых $a,b,c\in M$;
\item если $A,B\in \frak A$, то $(A\& B)$, $(A
\lor B)$, $(A\rightarrow B)$, $(A\leftrightarrow B)$, $(\neg A)$
принадлежат $\frak A$.
\endroster\noindent
Никакое выражение, которое не может быть получено по указанным
правилам, не входит в $\frak A$.

Отметим, однако, существенную разницу с алгеброй высказываний из
\S 1.2: там элементарные высказывания $X_i$ могли иметь любые
значения истинности, в то время как высказывание $(a=a)$
обязательно истинно. Кроме того, истинными являются и составные
высказывания вида $(a=a_1)\rightarrow (R(a,b)\rightarrow
R(a_1,b))$ и другие подобные им высказывания. Это, конечно,
связано с тем, что в число предикатов мы включили предикат
равенства, обладающий специфическими свойствами, в том числе,
свойством: $a=a$ для любого $a\in M$.

Тот факт, что наши высказывания зависят от параметров, пробегающих
множество $M$, позволяет формулировать суждения другого типа.
Пусть некоторое высказывание $A(c_1,\dots,c_n)$ зависит от
параметров $c_1,\dots,c_n$; пусть, далее, это высказывание истинно
не только в случае, когда первый параметр равен $c_1$, но и при
любом его значении $c\in M$ (и тех же значениях остальных
параметров). В этой ситуации мы будем переменный первый параметр
обозначать $x$, а утверждение о том, что высказывание справедливо
при любом значении $x$ записывать так: $\forall
x(A(x,c_2,\dots,c_n))$. Аналогично, если среди высказываний
$A(c,c_2,\dots,c_n)$, $c\in M$, есть хоть одно верное, будем
писать: $\exists x(A(x,c_2,\dots,c_n))$.

Введенные только что символы $\forall$ и $\exists$ называются
квантором всеобщности и квантором существования. Отметим, что в
случае конечного множества $M$ в них нет необходимости:
утверждение $\forall x(A(x,c_2,\dots,c_n))$ равносильно
высказыванию $\bigwedge\limits_{c\in M}A(c,c_2,\dots,c_n)$, а
утверждение $\exists x(A(x,c_2,\dots,c_n))$ --- высказыванию
$\bigvee\limits_{c\in M}A(c,c_2,\dots,c_n)$. Однако, для
бесконечных множеств, и тем более в ситуации, когда множество $M$
не зафиксировано, не удается свести кванторы к операциям
исчисления высказываний.

\subhead 2.2. Исчисление предикатов \endsubhead В этом пункте мы
строим формальную систему, в которую вкладываются содержательные
рассмотрения предыдущего пункта. Как и в \S 1.2, предметом нашего
рассмотрения являются слова в некотором конечном алфавите. На сей
раз алфавит состоит из букв $$,
\,\,\,(\,\,\,)\,\,\,=\,\,\,\&\,\,\,\lor\,\,\,\neg\,\,\,
\rightarrow\,\,\,\leftrightarrow\,\,\,
\forall\,\,\,\exists\,\,\,c_n \,\,\,x_n\,\,\,P_n\,\,\,и\,\,\,л $$
$(n=1,2,\dots)$. Этот алфавит бесконечен, но при желании его можно
свести к конечному алфавиту, введя вместо трех бесконечных серий
букв три буквы $c$, $x$, $P$ и еще одну букву $'$ и обозначив
$c_1=c$, $x_1=x$, $P_1=P$, $c_2=c'$, $x_3=x''$ и т.д.  Буквы $c_i$
будем называть символами констант, буквы $x_i$ --- символами
переменных, буквы $P_i$ --- символами предикатов. В дальнейшем мы
обычно не будем строго следовать этой системе обозначений и будем
использовать буквы $c,d,\dots$ (возможно, с индексами) для записи
символов констант, буквы $x,y,z,\dots$ --- для записи символов
переменных, буквы $P,Q,R\dots$ --- для записи символов предикатов.
Каждому символу предиката соотнесем натуральное число; если
символу $P$ соответствует число $n$, то говорим, что $P$ ---
символ $n$-местного предиката.

Не все слова представляют для нас интерес: некоторые из них ---
просто бессмысленные наборы букв. Следующее определение вводит
сразу два понятия: осмысленное выражение и свободное или связанное
вхождение символа переменной в осмысленное выражение.
\proclaim{Определение}
\roster \item $"и"$ и $"л"$ --- осмысленные выражения;
\item $(x=y)$, $(x=c)$, $(c=d)$ --- осмысленные выражения, и все
вхождения символов переменных в них свободные;
\item если $P$ --- символ $n$-местного предиката, и каждая из букв
$t_1,\dots,t_n$ обозначает символ переменной или символ константы,
то $P(t_1,\dots,t_n)$ --- осмысленное выражение, и все вхождения
символов переменных в него свободны;
\item если $A$, $B$ --- осмысленные выражения, то $(A\& B)$, $(A
\lor B)$, $(A\rightarrow B)$, $(A\leftrightarrow B)$, $(\neg A)$
--- тоже осмысленные выражения; при этом каждое свободное
(связанное) вхождение символа переменной в $A$ или $B$ остается
свободным (связанным) и в $(A\& B)$, $(A \lor B)$, $(A\rightarrow
B)$, $(A\leftrightarrow B)$, $(\neg A)$;
\item если $A$ --- осмысленное выражение, все вхождения символа
переменной $x$ в которое свободны, то $(\forall x A)$ и $(\exists
x A)$ --- осмысленные выражения, все вхождения символа переменной
$x$ в которые связанные, а вхождения остальных переменных ---
такие же, как в $A$.
\endroster\noindent Никакое выражение, которое не может быть
получено по указанным правилам, не является осмысленным.
\endproclaim

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

Прежде, чем сформулировать следующее определение, рассмотрим
ситуацию, несколько напоминающую нашу. Пусть $f(x)$ --- некоторая
функция натурального аргумента. Тогда выражения
$\sum\limits_{s=1}^nf(s)$, $\sum\limits_{t=1}^nf(t)$ являются
функциями только от верхнего предела суммирования $n$ и не зависят
от "связанных переменных" $s$, $t$. Поэтому обычно эти два
выражения отождествляются, хотя и являются графически различными.
Аналогичное отождествление произведем и для осмысленных выражений.

\proclaim{Определение}Пусть $A$, $A_1$ --- осмысленные выражения;
будем считать, что  $A\equiv A_1$, если $A$ можно преобразовать в
$A_1$, применив несколько раз следующие правила
\therosteritem1-\therosteritem3. \roster \item Если $A$ ---
осмысленное выражение, то $A\equiv A$.
\item если $A$, $B$, $A_1$, $B_1$ --- осмысленные выражения, и
$A\equiv A_1$, $B\equiv B_1$, то $(A\& B)\equiv(A_1\& B_1)$, $(A
\lor B)\equiv(A_1 \lor B_1)$, $(A\rightarrow
B)\equiv(A_1\rightarrow B_1)$, $(A\leftrightarrow
B)\equiv(A_1\leftrightarrow B_1)$, $(\neg A)\equiv(\neg A_1)$.
\item если $A(x)$ --- осмысленное выражение, $y$ --- символ
переменной, не входящей свободно в $A(x)$ и $A(y)$ --- выражение,
получающееся из слова $A(x)$ заменой всех свободных вхождений
символа переменной $x$ на символ переменной $y$, то $(\forall x
A(x))\equiv(\forall y A(y))$, $(\exists x A(x))\equiv(\exists y
A(y))$.
\endroster
\endproclaim
Иначе говоря, $A\equiv A_1$, если слово $A_1$ получается из слова
$A$ заменой связанных вхождений символов переменных на другие
символы переменных, причем должны соблюдаться некоторые правила
предосторожности. В частности, все вхождения символа переменной,
связанных одним квантором, должны заменяться на одну и ту же
букву.

Если $A$, $A_1$ --- осмысленные выражения, и $A\equiv A_1$, то мы
отождествляем выражения $A$, $A_1$, полагая, что это --- две
записи одного и того же осмысленного выражения.

 Осмысленное выражение, в которое ни один символ переменной не
входит свободно, называется суждением.
 \subhead 2.3. Интерпретации символов констант и предикатов.
 Модели
\endsubhead
Соде\-ржательное описание исчисления предикатов из \S 2.1
получается из формальной схемы предыдущего пункта при
интерпретировании символов констант и предикатов в некотором
множестве. Пусть $\frak C$ --- множество символов констант, а
$\frak P$ --- множество символов предикатов. Для самого исчисления
предикатов $\frak C=\{c_1,c_2,\dots\}$, $\frak P
=\{P_1,P_2,\dots\}$; однако в дальнейшем мы будем допускать в
качестве $\frak C$ и $\frak P$ любые множества, поскольку основные
содержательные результаты не зависят от конкретного вида множеств
символов констант и предикатов. Пусть $M$
--- множество, и пусть каждому символу константы $c\in \frak C$
сопоставлен элемент $c_M\in M$, а каждому символу $n$-местного
предиката $P\in\frak P$ сопоставлено подмножество $P_M$ $n$-й
декартовой степени $M^n$ множества $M$. Набор, состоящий из
множества $M$, элементов $c_M$ ($c\in \frak C$) и подмножеств
$P_M$ ($P\in\frak P$) называется интерпретацией множеств символов
констант $\frak C$ и символов предикатов $\frak P$.

Пусть $A=A(x_1,\dots,x_N)$ --- осмысленное выражение со свободными
символами переменных $x_1,\dots,x_N$, в записи которого
использованы только символы констант из $\frak C$ и символы
предикатов из $\frak P$; для любых элементов $m_1,\dots,m_N$
присвоим выражению $A(m_1,\dots,m_N)$ значение истинности в
интерпретации $\{M;c_M,P_M\}$. Присвоение значения истинности
проведем индукцией по построению выражения $A$. Выражения $c=d$,
$c=m$, $m=m'$, где $c,d\in \frak C$, $m,m'\in M$, истинны в
интерпретации $M$ тогда и только тогда, когда, соответственно,
$c_M=d_M$ или $c_M=m$ или $m=m'$. Выражение $P(t_1,\dots,t_n)$, в
котором каждый символ $t_i$ означает или элемент из $M$, или
символ константы из $\frak C$, истинно в интерпретации $M$ тогда и
только тогда, когда $(m_1,\dots,m_n)\in P_M$, где $m_i=t_i$, если
$t_i$ --- элемент из $M$, и $m_i=(t_i)_M$, если $t_i\in \frak C$
--- символ константы. Значения истинности выражений $A\&B$, $A
\lor B$, $A\rightarrow B$, $A\leftrightarrow B$, $\neg A$
определяются по правилам исчисления высказываний. Если выражение
$A(x_1,\dots,x_N)$ имеет вид $\forall x B(x,x_1,\dots,x_N)$, то
выражение $A(m_1,\dots,m_N)$ считается истинным тогда и только
тогда, когда выражение $B(m,m_1,\dots,m_N)$ истинно для любого
$m\in M$. Наконец, если выражение $A(x_1,\dots,x_N)$ имеет вид
$\exists x B(x,x_1,\dots,x_N)$, то выражение $A(m_1,\dots,m_N)$
считается истинным тогда и только тогда, когда найдется такой
элемент $m\in M$, что выражение $B(m,m_1,\dots,m_N)$ истинно.

Начи\-ная отсюда, для множества символов предикатов $\frak P$ и
множества символов констант $\frak C$ будем обозначать через
$\frak A(\frak P,\frak C)$ множество всех суждений, в записи
которых участвуют лишь символы предикатов, принадлежащие $\frak
P$, и символы констант, принадлежащие $\frak C$. Иногда мы будем
опускать упоминание о множестве символов предикатов и писать
$\frak A(\frak C)$ вместо $\frak A(\frak P,\frak C)$. Пусть $\frak
S\in \frak A(\frak P,\frak C)$ --- некоторое множество суждений.
Интерпретация $\{M;c_M,P_M\}$ множеств символов констант $\frak C$
и символов предикатов $\frak P$ называется моделью $\frak S$, если
все суждения из $\frak S$ истинны в этой интерпретации.

Обычная формальная аксиоматическая теория строится следующим
образом: задаются множества символов констант $\frak C$ и символов
предикатов $\frak P$ и некоторое множество суждений $\frak S\in
\frak A(\frak P,\frak C)$, называемых аксиомами, и изучаются
всевозможные утверждения, которые можно вывести из аксиом при
помощи правил вывода, изложенных выше, а также всевозможные модели
системы аксиом. В качестве примера рассмотрим аксиоматическую
теорию с одним символом констант $e$ и одним 3-местным символом
предиката $P$ со следующей системой аксиом: \roster
\item $\forall x\forall y\exists z P(x,y,z)$;
\item $\forall x\forall y\forall z\forall t((P(x,y,z)\&P(x,y,t))
\rightarrow(z=t))$;
\item $\forall x\forall y\forall z\forall t\forall u\forall v
\forall w((P(x,y,t)\&P(t,z,u)\&P(y,z,v)\&P(x,v,w))
\rightarrow(u\!=\!w))$;
\item $\forall x(P(x,e,x)\&P(e,x,x))$;
\item $\forall x\exists y(P(x,y,e)\&P(y,x,e))$.\endroster
Пусть $G$ --- любая модель этой системы аксиом. Соотношение
$P(x,y,z)$ запишем в виде $xy=z$; первая аксиома означает, что для
любых двух элементов $x,y\in G$ существует их произведение $z=xy$,
а вторая аксиома показывает, что это произведение определено
однозначно. Таким образом, $G$ является множеством с одной
бинарной операцией умножения. Остальные аксиомы утверждают, что
это умножение ассоциативно, что $e$ является единицей для него и
что всякий элемент из $G$ обратим. Таким образом, моделями
множества аксиом (1)-(5) являются группы.

\subhead 2.4. Универсально верные суждения\endsubhead
 В исчислении высказываний мы выделили класс тавтологий ---
суждений, истинных при любых значениях истинности элементарных
высказываний. Точно так же, универсально верными суждениями в
исчислении предикатов назовем такие суждения, которые истинны при
любой интерпретации символов констант и предикатов, входящих в
запись этих суждений. В этом пункте мы опишем несколько способов
построения универсально верных суждений. {\it A priori} не ясно,
достаточно ли этих правил для построения всех универсально верных
суждений, и поэтому мы пока будем называть суждения, полученные по
этим правилам, выводимыми (точнее, выводимыми из пустого множества
суждений).

 \roster
\item {\it Правило подстановки.} Пусть $F(X_1,X_2,\dots ,X_m)$
--- тавтология исчисления высказываний, и пусть $Y_1$, $Y_2$,
\dots ,$Y_m$ --- произвольные суждения; тогда суждение, полученное
из $F(X_1,X_2,\dots ,X_m)$ подстановкой вместо каждого вхождения
букв $X_1$, $X_2$, \dots , $X_m$ соответствующих суждений $Y_1$,
$Y_2$, \dots ,$Y_m$, выводимо.
\item {\it Modus ponens.} Если суждения $X$, $X\rightarrow Y$
выводимы, то и суждение $Y$ выводимо.
 \endroster

Перед тем, как сформулировать другие правила построения
универсально верных суждений, введем одно полезное обозначение.
Пусть $A(t)$ --- осмысленное выражение, а $t$ --- символ константы
или переменной, и пусть $c$ -- символ константы; через $A(c)$ мы
будем обозначать слово, получающееся из слова $A(t)$ заменой всех
свободных вхождений $t$, если $t$ --- символ переменной, или всех
вхождений $t$, если $t$ --- символ константы, на символ $c$.

  \roster
\item[3] Суждения $(c=c)$, $(c=d)\rightarrow(d=c)$, $((c=d)\&(d=e))
\rightarrow(c=e)$ выводимы.
\item Если $A(c)$ --- любое суждение, то $(c=d)\rightarrow (A(c)
\rightarrow A(d))$ --- выводимое суждение.
\item Пусть $A(x)$ --- осмысленное выражение, в которое свободно
входит только символ переменной $x$, $B$ --- любое суждение; тогда
$$\align&(\forall x A(x))\rightarrow A(c),\\ &(\neg(\forall x
A(x)))\leftrightarrow (\exists x(\neg A(x))),\\ &((\forall x
A(x))\&B)\leftrightarrow (\forall x(A(x)\&B)),\\ &((\exists x
A(x))\&B)\leftrightarrow (\exists x(A(x)\&B))\endalign$$ ---
выводимые суждения.
 \endroster
Наконец, отметим еще один, принципиально отличный от предыдущих,
способ построения выводимых суждений. Для того, чтобы обосновать
его, дадим сначала его интуитивный смысл. Ясно, что если суждение
$\forall x A(x)$ верно, то для любого символа константы должно
быть верно и суждение $A(c)$; нам хотелось бы, чтобы и обратно,
если суждение $A(c)$ верно для всех символов констант, то было бы
верно и суждение $\forall x A(x)$. Но верно для всех символов
констант --- это то же самое, что верно для произвольного символа
константы. Мы приходим к следующему правилу построения выводимых
суждений.
 \roster
\item[6] Пусть $A(x)$ --- осмысленное выражение с единственным
символом переменной $x$, входящим в него свободно. Если $c$
--- символ константы, не входящий в $A(x)$, и суждение $A(c)$
выводимо, то и суждение $\forall x A(x)$ выводимо.
 \endroster

 Еще раз отметим, что в последнем правиле  $c$ --- символ
константы, не связанный никакими дополнительными ограничениями;
вообще говоря, суждение $((A(c))\rightarrow(\forall x A(x)))$ не
обязано быть верным.
\proclaim{Теорема}Всякое выводимое суждение является универсально
верным (т.е. истинным при любой интерпретации символов констант и
предикатов). Обратно, всякое универсально верное суждение
выводимо.
\endproclaim
\demo{Доказательство} Докажем, что суждения, построенные по
правилам (1)-(6), универсально верны. Напомним, что суждения
являются высказываниями; правила (1) и (2) как раз и являются
переформулировками соответствующих правил исчисления высказываний.
Совершенно очевидно, что по правилам (3)-(5) получаются суждения,
истинные при любой интерпретации символов констант и предикатов.
Осталось показать, что и по правилу (6) получаются универсально
верные суждения. Пусть $\{M;c_M,P_M\}$
--- любая интерпретация множеств констант и предикатов, и пусть
$m\in M$. Предположим, что мы уже убедились в универсальной
верности выводимого суждения $A(c)$. Значение истинности выражения
$A(m)$ в интерпретации $M$ совпадает совпадает со значением
истинности суждения $A(c)$ в интерпретации, отличающейся от
интерпретации $M$ только тем, что символу константы $c$ ставится в
соответствие не элемент $c_M$, а элемент $m$. Но суждение $A(c)$
истинно в любой интерпретации; поэтому выражение $A(m)$ истинно в
интерпретации $M$ для любого $m\in M$, т.е. суждение $\forall x
A(x)$ истинно в интерпретации $M$.

Обратное утверждение значительно глубже и будет доказано ниже как
след\-с\-т\-вие теоремы Геделя о полноте.
\enddemo

\subhead 2.5. Непротиворечивость. Теорема Геделя о полноте
\endsubhead
Пусть теперь $\frak S$ --- некоторое множество суждений; мы
говорим, что суждение $A$ выводимо из $\frak S$, если существуют
суждения $X_1,\dots, X_m\in \frak S$, такие что суждение
$(X_1\&\dots\&X_m)\rightarrow A$ выводимо (т.е. выводимо из
пустого множества суждений). Система суждений $\frak S$ называется
непротиворечивой, если тождественно ложное суждение $"л"$ не
выводимо из $\frak S$.

 Ясно, что если для множества суждений существует модель, то это
множество суждений непротиворечиво. Оказывается, верно и обратное.
\proclaim{Теорема Геделя о полноте}Пусть $\frak S\subseteq
\frak A(\frak P,\frak C)$ --- некоторое непротиворечивое множество
суждений. Тогда существует модель этого множества суждений. Более
того, если множества $\frak P$, $\frak C$ конечны, то существует
не более чем счетная модель $\frak S$, а если хотя бы одно из них
бесконечно, существует модель множества $\frak C$, мощность
которой не превосходит максимума мощностей множеств $\frak P$,
$\frak C$.
\endproclaim
Доказательство этой теоремы будет дано в следующем параграфе.

То же самое ограничение на мощность, что и в теореме Геделя, будет
встречаться у нас еще несколько раз. Для сокращения речи будем
называть множества, мощность которых удовлетворяет этому условию,
множествами малой мощности (по отношению к множествам символов
констант и предикатов $\frak C$, $\frak P$). В этих терминах
теорема Геделя гарантирует существование модели малой мощности.

В следующих пунктах мы укажем несколько важных следствий теоремы
Геделя.

\subhead 2.6. Выводимость и существование модели\endsubhead
\proclaim{Теорема}Пусть $\frak X\subseteq \frak A(\frak C,
\frak P)$ --- непротиворечивое множество суждений. Если суждение
$A\in \frak A(\frak C, \frak P)$ не выводимо из $\frak X$, то
существует модель множества суждений $\frak X$, в которой суждение
$A$ ложно. Иначе говоря, суждение $A\in \frak A(\frak C, \frak P)$
выводимо из $\frak X$ тогда и только тогда, когда оно истинно во
всех моделях множества суждений $\frak X$. В частности, суждение
выводимо (т.е. выводимо из пустого множества) тогда и только
тогда, когда оно универсально верно.
\endproclaim
\demo{Доказательство}Заметим сначала, что высказывание
$$((X_2\&\neg X_1)\rightarrow(л))\rightarrow (X_2\rightarrow
X_1)$$  тождественно истинно. Пусть суждение $A\in \frak A(\frak
C, \frak P)$ не выводимо из $\frak X$. Если бы множество суждений
$\frak X\cup\{\neg A\}$  было противоречивым, то существовало бы
конечное множество суждений $Y_1,\dots,Y_n\in \frak X$, такое что
суждение $(Y_1\&\dots\&Y_n\&\neg A)\rightarrow (л)$ было бы
выводимым. Подставляя в указанное выше тождественно истинное
высказывание суждение $Y_1\&\dots\&Y_n$ вместо $X_2$ и $A$ вместо
$X_1$ и пользуясь {\it modus ponens}, мы увидели бы, что
$(Y_1\&\dots\&Y_n)\rightarrow A$  --- выводимое суждение , т.е.
что суждение $A$ выводимо из $\frak X$ вопреки предположению.
Итак, множество суждений $\frak X\cup\{\neg A\}$ непротиворечиво,
и по теореме Гёделя о полноте существует его модель. Эта модель
является моделью множества суждений $\frak X$, но суждение $A$ в
этой модели ложно, поскольку в ней выполняется суждение $\neg A$.
\enddemo
Последнее утверждение только что доказанной теоремы показывает,
что для построения всех универсально верных суждений достаточно
пользоваться лишь  правилами (1)-(6). Иначе говоря, эти правила
составляют полную систему правил вывода универсально верных
суждений; этим объясняется название теоремы Геделя: это по
существу теорема о полноте системы правил вывода (1)-(6).

 \subhead 2.7. Теорема компактности
\endsubhead
\proclaim{Теорема}Если для всякого конечного подмножества
множества суждений $\frak X\subseteq \frak A(\frak C,\frak P)$
существует модель, то существуют и модель всего множества суждений
$\frak X$.
\endproclaim
\demo{Доказательство}Если бы множество суждений $\frak X$ было
противоречивым, то существовали бы суждения $X_1,\dots,X_n\in
\frak X$, такие что суждение $$(X_1\&\dots\&X_n)\rightarrow(л)$$
было бы выводимым. Но тогда было бы противоречивым уже конечное
множество суждений $\{X_1,\dots,X_n\}\subseteq \frak X$, и для
него не существовало бы модели, что противоречит предположению
теоремы. Следовательно, множество суждений $\frak X$
непротиворечиво, и по теореме Гёделя о полноте существует модель
этого множества суждений.
\enddemo
 \subhead 2.8. Существование сколь угодно больших
моделей
\endsubhead
\proclaim{Теорема}Если для множества суждений $\frak X\subseteq
\frak A(\frak C,\frak P)$ существует бесконечная модель или даже
сколь угодно большие конечные  модели, то существуют и модели
множества суждений $\frak X$ сколь угодно большой мощности.
\endproclaim
\demo{Доказательство}Расширим множество символов констант $\frak
C$, добавив к нему произвольное множество $\frak D$. Обозначим
через $\frak X'\subseteq\frak A(\frak C\cup\frak D,\frak P)$
множество суждений, полученное из $\frak X$ добавлением суждений
$\neg(d=d')$ для всех пар $d,d'\in \frak D$, $d\ne d'$.

Каждое конечное подмножество $\frak Y$ множества $\frak X'$
допускает модель. Действительно, в $\frak Y$ участвует лишь
конечное число элементов $d_1,\dots,d_m\in \frak D$. По условию,
существует модель $M$ множества суждений $\frak X$, состоящая не
менее чем из $m$ элементов; сопоставляя символам констант
$d_1,\dots,d_m$ различные элементы из множества $M$, мы превратим
$M$ в интерпретацию множества символов констант $\frak
C\cup\{d_1,\dots,d_m\}$ и символов предикатов $\frak P$, в которой
истинны все суждения из $\frak X$ и суждения $\neg(d_i=d_j)$,
$1\le i,j\le m$, $i\ne j$. В частности, в $M$ выполнены все
суждения из $\frak Y$, так что $M$ --- модель множества суждений
$\frak Y$.

По теореме компактности существует и модель $M'$ всего множества
суждений $\frak X'$; очевидно, она является моделью множества
суждений $\frak X$, а её мощность не меньше мощности множества
$\frak D$, так как всем символам констант из $\frak D$ должны
соответствовать различные элементы из $M'$.
\enddemo

 \head 3. Доказательство теоремы Гёделя о полноте\endhead

\subhead 3.1. Максимальные непротиворечивые и экзистенциально
полные множества суждений
\endsubhead
Определим два важных класса множеств суждений.
Под\-мно\-же\-ст\-во $\frak S$ множества суждений $\frak A(\frak
P,\frak C)$ называется экзистенциально полным, если для любого
суждения вида $\exists x(A(x))$, принадлежащего $\frak S$,
найдется символ константы $c\in \frak C$, такой что суждение
$A(c)$ тоже принадлежит множеству $\frak S$ (здесь, как обычно,
$A(x)$ --- осмысленное выражение, в которое свободно входит только
символ переменной $x$).

Множество суждений $\frak S\subseteq \frak A(\frak P, \frak C)$
называется максимальным непротиворечивым подмножеством $\frak
A(\frak P,\frak C)$, если множество суждений $\frak S$
непротиворечиво, но любое его собственное расширение уже не
является непротиворечивым.

\proclaim{Предложение}Пусть $\frak S$ --- максимальное
непротиворечивое подмножество $\frak A(\frak P,\frak C)$, и пусть
$A$ --- любое суждение из $\frak A(\frak P,\frak C)$. Тогда одно,
и только одно, из суждений $A$, $\neg A$ содержится в $\frak S$.
Если суждение $A$ выводимо из $\frak S$, то $A\in \frak S$. В
частности, все выводимые суждения (т.е. суждения, выводимые из
пустого множества суждений) принадлежат $\frak S$.
\endproclaim
\demo{Доказательство}Оба суждения $A$, $\neg A$ не могут
содержаться в непротиворечивом множестве $\frak S$, так как в
противном случае  тождественно ложное суждение $A\&\neg A$ было бы
выводимо из $\frak S$, что несовместимо с непротиворечивостью
$\frak S$. Пусть $A,\neg A\notin \frak S$; поскольку $\frak S$ ---
максимальное непротиворечивое множество, оба множества суждений
$\frak S\cup\{A\}$, $\frak S\cup\{\neg A\}$ не являются
непротиворечивыми. Поэтому существуют суждения
$B_1,\dots,B_m,B_{m+1},\dots,B_n\in \frak B$, такие что суждения
$$(A\&B_1\&\dots\&B_m)\rightarrow (л),\quad (\neg A\&
B_{m+1}\&\dots\&B_n)\rightarrow (л)$$ выводимы. Далее,
высказывание $$(((X\&Y)\rightarrow (л))\&((\neg X\&Z)\rightarrow
(л)))\rightarrow ((Y\&Z)\rightarrow (л))$$ является, как нетрудно
выяснить, вычисляя функцию истинности, тавтологией. Подставляя
сюда $A$, $B_1\&\dots\&B_m$ и $B_{m+1}\&\dots\&B_n$ вместо $X$,
$Y$, $Z$ и пользуясь $modus\,\,ponens$, находим, что и суждение
$$(B_1\&\dots\&B_m\& B_{m+1}\&\dots\&B_n)\rightarrow (л)$$
выводимо, а это означает, что $\frak S$ --- противоречивое
множество суждений. Следовательно, предположение о том, что ни
суждение $A$, ни суждение $\neg A$ не принадлежат $\frak S$, было
неверно.

Если суждение $A$ выводимо из $\frak S$ и $A\notin \frak S$, то,
как мы только что доказали, суждение $\neg A$ принадлежит $\frak
S$; таким образом, оба суждения $A$, $\neg A$ выводимы из $\frak
S$, а потому и тождественно ложное суждение $A\&\neg A$ выводимо
из $\frak S$ вопреки непротиворечивости множества суждений $\frak
S$.
\enddemo

\subhead 3.2. Интерпретации максимальных непротиворечивых
экзистенци\-а\-ль\-но полных множеств суждений
\endsubhead
\proclaim{Теорема}Пусть $M=\{M;c_M,P_M\}$ --- интерпретация
множеств символов констант $\frak C$ и символов предикатов $\frak
P$, такая что для любого элемента $m\in M$ существует символ
константы $c\in \frak C$, для которого $m=c_M$. Множество $\frak
S$ всех суждений из $\frak A(\frak P, \frak C)$, истинных в
интерпретации $M$, является максимальным непротиворечивым и
экзистенциально полным. Обратно, пусть $\frak S\subseteq \frak
A(\frak P, \frak C)$ --- максимальное непротиворечивое и
экзистенциально полное множество суждений; тогда существует такая
интерпретация $M=\{M;c_M,P_M\}$ множеств $\frak C$, $\frak P$, что
для любого элемента $m\in M$ существует символ константы $c\in
\frak C$, для которого $m=c_M$, и суждение из $\frak A(\frak P,
\frak C)$ истинно в $M$ тогда и только тогда, когда оно содержится
в множестве $\frak S$.
\endproclaim
\demo{Доказательство}Пусть сначала $\frak S$ --- множество всех
суждений из $\frak A(\frak P, \frak C)$, истинных в интерпретации
$M$. Ясно, что оно непротиворечиво. Если суждение $A\in \frak
A(\frak P, \frak C)$ не принадлежит $\frak S$, то оно не истинно в
интерпретации $M$; это значит, что его отрицание $\neg A$ истинно
в $M$ и потому принадлежит $\frak S$. Таким образом, множество
суждений $\frak S\cup\{A\}$ содержит одновременно суждения $A$,
$\neg A$, и потому противоречиво. Следовательно, $\frak S$ ---
{\it максимальное} непротиворечивое множество суждений. Далее,
если суждение $\exists x(A(x))$ принадлежит $\frak S$, то оно
истинно в $M$, т.е. найдется символ константы $c\in \frak C$,
такой что суждение $A(c)$ (точнее, суждение $A(c_M)$) истинно в
$M$ и потому принадлежит множеству $\frak S$. Итак, множество
суждений $\frak S$ экзистенциально полно.

Сложнее доказывается обратное утверждение. Пусть $\frak S\subseteq
\frak A(\frak P, \frak C)$ --- максимальное непротиворечивое и
экзистенциально полное множество суждений. Две константы $c,d\in
\frak C$ будем считать эквивалентными и писать $c\sim d$, если
суждение $c=d$ содержится в $\frak S$.
\proclaim{Лемма 1}Отношение $c\sim d$ является отношением
эквивалентности на множестве $\frak C$. Если $P$ --- символ
$n$-местного предиката, $c_1,\dots,c_n,d_1,\dots,d_n\in \frak C$,
$c_1\sim d_1$, \dots, $c_n\sim d_n$ и суждение $P(c_1,\dots,c_n)$
содержится в $\frak S$, то и суждение $P(d_1,\dots,d_n)$
содержится в $\frak S$.
\endproclaim
\demo{Доказательство}Суждение $c=c$ выводимо и потому принадлежит
$\frak S$; значит, $c\sim c$. Если $c\sim d$, то суждение $c=d$
принадлежит $\frak S$, и из него и выводимого суждения
$(c=d)\rightarrow (d=c)$, тоже принадлежащего $\frak S$, по
$modus\,\,ponens$ выводится суждение суждение $d=c$. По
предложению из предыдущего пункта  суждение $d=c$ тоже принадлежит
$\frak S$, т.е. $d\sim c$. Точно так же, если $c\sim d$, $d\sim
e$, то суждения $c=d$, $d=e$ вместе с выводимым суждением
$((c=d)\&(d=e)) \rightarrow(c=e)$ принадлежат $\frak S$; по
предложению из предыдущего пункта выводимое из них суждение $c=e$
тоже принадлежат $\frak S$, т.е. $c\sim e$. Итак, отношение $\sim$
является эквивалентностью.

Аналогично доказывается и второе утверждение леммы. Если $c_1\sim
d_1$, \dots, $c_n\sim d_n$, то суждения $c_1=d_1$, \dots,
$c_n=d_n$ принадлежат $\frak S$. Из них, суждения
$P(c_1,c_2,\dots,c_n)$ и выводимых суждений
$$\align(c_1=d_1)&\rightarrow (P(c_1,c_2,\dots,c_n) \rightarrow
P(d_1,c_2,\dots,c_n)),\\ (c_2=d_2)&\rightarrow
(P(d_1,c_2,\dots,c_n) \rightarrow P(d_1,d_2,\dots,c_n)), \dots,\\
(c_n=d_n)&\rightarrow (P(d_1,d_2,\dots,c_n) \rightarrow
P(d_1,d_2,\dots,d_n))\endalign$$ последовательно выводятся
суждения $P(d_1,c_2,\dots,c_n)$, $P(d_1,d_2,\dots,c_n)$, \dots,
$P(d_1,d_2,\dots,d_n)$. По предложению из предыдущего пункта
последнее суждение $P(d_1,d_2,\dots,d_n)$ принадлежит $\frak S$.
\enddemo

Обозначим через $M$ множество классов эквивалентности множества
$\frak C$ по отношению $\sim$. Для каждого символа константы $c\in
C$ обозначим через $c_M$ класс эквивалентности элемента $c$, а для
каждого символа $n$-местного предиката $P\in\frak P$ обозначим
через $P_M$ подмножество декартовой степени $M^n$, состоящее из
всех таких наборов $(m_1,\dots,m_n)$, что суждение
$P(c_1,\dots,c_n)$ принадлежит $\frak S$ для любых элементов
$c_1,\dots,c_n\in\frak C$, классы эквивалентности которых равны
соответственно $m_1,\dots,m_n\in M$. Таким образом, элементы $c_M$
и множества $P_M$ составляют интерпретацию множества суждений
$\frak S\subseteq\frak A(\frak P,\frak C)$.

Для доказательства теоремы осталось показать, что значения
истинности суждения $A\in \frak A(\frak P,\frak C)$ в
интерпретации $M=\{M;c_M, P_M\}$ и высказывания $(A\in \frak S)$
совпадают. Пусть это не так, и пусть $A\in \frak A(\frak P,\frak
C)$ --- суждение наименьшей длины (как слово в алфавите из
символов констант, предикатов, переменных и других логических
знаков), такое что его значение истинности в интерпретации $M$ не
совпадает со значением истинности высказывания $(A\in \frak S)$.
Рассмотрим все возможные варианты \therosteritem1-\therosteritem5
для суждения $A$ и покажем, что в каждом из них мы приходим к
противоречию.

(1). Суждение "и", истинно в любой интерпретации и принадлежит
$\frak S$, а суждение "л" не истинно в любой интерпретации и не
принадлежит непротиворечивому множеству суждений $\frak S$.
Поэтому суждение $A$ не совпадает ни с "и", ни с "л".

(2), (3).  Интерпретация $M$ построена так, что суждения видов
$c=d$, $P(c_1,\dots,c_n)$ истинны в $M$ тогда и только тогда,
когда они принадлежат $\frak S$. Поэтому суждение $A$ не может
совпадать с суждением одного из видов $c=d$, $P(c_1,\dots,c_n)$.

(4). Пусть $B,C\in \frak A(\frak P,\frak C)$. Суждение $B\& C$
выводимо из суждений $B$ и $C$, и наоборот, суждения $B$ и $C$
выводимы из суждения $B\& C$; поэтому $(B\& C)\in \frak S$ тогда и
только тогда, когда $B\in \frak S$ и $C\in \frak S$. Поэтому
значения истинности высказываний $(B\in \frak S)\&(C\in \frak S)$
и $(B\& C)\in \frak S$ совпадают. Далее, очевидно, что совпадают
значения истинности высказываний $\neg(B\in \frak S)$ и $(\neg
B)\in \frak S$. Отсюда, пользуясь тем, что значения истинности для
$B\lor C$, $B\rightarrow C$, $B\leftrightarrow C$ совпадают со
значениями истинности для $\neg((\neg B)\&(\neg C))$,
$\neg(B\&(\neg C))$, $\neg((\neg(B\& C))\&(\neg B)\&(\neg C))$,
находим, что значения истинности высказываний $(B\in \frak
S)\lor(C\in \frak S)$, $(B\in \frak S)\rightarrow(C\in \frak S)$,
$(B\in \frak S)\leftrightarrow(C\in \frak S)$ совпадают со
значениями истинности высказываний  $(B\lor C)\in \frak S$,
$(B\rightarrow C)\in \frak S$, $(B\leftrightarrow C)\in \frak S$.


Если суждение $A$ имеет один из видов $B\& C$, $\neg B$, $B\lor
C$, $B\rightarrow C$, $B\leftrightarrow C$, то суждения $B$, $C$
короче суждения $A$, и потому их значения истинности в
интерпретации $M$ совпадают со значениями истинности высказываний
$(B\in \frak S)$, $(C\in \frak S)$. Из рассуждений предыдущего
абзаца мы видим теперь, что и значения истинности суждения $A$ и
высказывания $(A\in \frak S)$ совпадают, вопреки выбору суждения
$A$.

(5). Пусть суждение $A$ имеет вид $\forall x B(x)$. Если
$A\in\frak S$, то для всех символов констант $c\in \frak C$
суждения $B(c)$, выводимые из суждения $\forall x B(x)$,
принадлежат $\frak S$, и, поскольку слово $B(c)$ короче слова
$\forall x B(x)$, все суждения $B(c)$ истинны в интерпретации $M$.
Следовательно, суждение $\forall x B(x)$ истинно в интерпретации
$M$. Если же высказывание $(A\in\frak S)$ ложно, то суждение
$\exists x(\neg B(x))$, равносильное суждению $\neg A$,
принадлежит множеству суждений $\frak S$, и, поскольку это
множество суждений экзистенциально полно, найдется символ
константы $c\in \frak C$, такой что суждение $\neg B(c)$
принадлежит $\frak S$. Но суждение $\neg B(c)$ короче суждения
$A$; поэтому оно истинно в интерпретации $M$, и, значит, суждение
$B(c)$ не истинно в интерпретации $M$. Следовательно, суждение
$A$, имеющее вид $\forall x B(x)$, не истинно в $M$. Итак, в обоих
случаях значение истинности суждения $A$ в интерпретации $M$
совпадает со значением истинности высказывания $(A\in\frak S)$,
что противоречит нашему предположению.

Двойственным образом разбирается случай суждения $A$ вида $\exists
x B(x)$. Если оно принадлежит $\frak S$, то из экзистенциальной
полноты $\frak S$ следует, что найдется символ константы $c\in
\frak C$, такой что суждение $B(c)$ принадлежит $\frak S$; оно
короче суждения $A$ и потому истинно в интерпретации $M$.
Следовательно, суждение $\exists x B(x)$ истинно в интерпретации
$M$. Если же суждение $A$ не принадлежит $\frak S$, то суждение
$\forall x(\neg B(x))$, равносильное суждению $\neg A$,
принадлежит множеству суждений $\frak S$, и вместе с ним множеству
$\frak S$ принадлежат все суждения $\neg B(c)$, $c\in \frak C$.
Отсюда следует, что ни одно из суждений $B(c)$ не принадлежит
$\frak S$ и, поскольку эти суждения короче суждения $A$, ни одно
из них не истинно в интерпретации $M$. Поэтому суждение $A$,
имеющее вид $\exists x B(x)$, не истинно в $M$. Снова мы получили,
что значение истинности суждения $A$ в интерпретации $M$ совпадает
со значением истинности высказывания $(A\in\frak S)$.

Этим и завершается доказательство теоремы.
\enddemo
\subhead 3.3. Существование максимальных непротиворечивых множеств
су\-ждений
\endsubhead
\proclaim{Теорема}Для всякого непротиворечивого множества суждений
$\frak S\in \frak A(\frak C)$ существует содержащее его
максимальное непротиворечивое множество суждений $\frak B\in \frak
A(\frak C)$.
\endproclaim
\demo{Доказательство}Конечно, наиболее естественным при
доказательстве подобных утверждений является использование леммы
Цорна. Пусть $\Cal M$ --- множество всех непротиворечивых множеств
суждений $\frak B\subseteq \frak A(\frak C)$, содержащих множество
$\frak S$. Множество $\Cal M$ естественным образом упорядочено
отношением включения; покажем, что оно индуктивно, т.е. что любое
линейно упорядоченное подмножество множества $\Cal M$ имеет
верхнюю грань, тоже принадлежащую $\Cal{M}$

Пусть $\{\frak B_i\,|\,i\in I\}$ --- линейно упорядоченное
подмножество $\Cal M$. Обозначим через $\frak B$ объединение всех
подмножеств $\frak B_i$ множества $\frak A(\frak C)$ $(i\in I)$.
Множество $\frak B$ содержит все множества $\frak B_i$, и для
того, чтобы показать, что $\frak B$ --- верхняя грань для
семейства $\{\frak B_i\,|\,i\in I\}$, достаточно установить, что
$\frak B\in \Cal M$, т.е. что множество суждений $\frak B$
непротиворечиво. Но это действительно так: в противном случае
нашлись бы суждения $A_1,\dots,A_n\in \frak B$, такие что суждение
$(A_1\&\dots\&A_n)\rightarrow (л)$ выводимо; но конечное множество
суждений $A_1,\dots,A_n$ содержится уже в каком-то из множеств
$\frak B_i$, $i\in I$, и, значит, это множество $\frak B_i$ не
является непротиворечивым, т.е. $\frak B_i\notin \Cal M$ вопреки
предположению.

Итак, частично упорядоченное отношением включения множество $\Cal
M$ индуктивно, и по лемме Цорна в нем есть максимальный элемент
$\frak B$. Множество $\frak B$ и будет максимальным
непротиворечивым множеством суждений, содержащим $\frak S$.
\enddemo
 \subhead 3.4. Существование экзистенциально полных расширений
множества суждений
\endsubhead

\proclaim{Теорема}Для любого непротиворечивого множества суждений
$\frak S\subseteq \frak A(\frak P, \frak C)$ существуют множество
символов констант $\frak C'\supseteq \frak C$ малой мощности и
экзистенциально полное максимальное непротиворечивое множество
суждений $\frak S'\subseteq \frak A(\frak P, \frak C')$,
содержащее $\frak S$.
\endproclaim
\demo{Доказательство}Пусть $\frak C_0=\frak C$,  и пусть $\frak
S_0\subseteq \frak A(\frak C_0)$ --- максимальное непротиворечивое
множество суждений, содержащее $\frak S$. Пусть уже построены
множество символов констант $\frak C_i$ и максимальное
непротиворечивое множество суждений $\frak S_i\subseteq \frak
A(\frak C_i)$. Обозначим через $\frak M$ множество всех
осмысленных выражений $A=A(x)$ с единственной свободной переменной
$x$, таких что суждение $\exists x(A(x))$ содержится в $\frak
S_i$. Для каждого $A\in \frak M$ введем новый символ константы
$c_A$ и обозначим через $\frak C_{i+1}$ множество, полученное из
$\frak C_i$ добавлением всех новых символов констант $c_A$, а
через $\frak S_{i+1}'\subseteq \frak A(\frak C_{i+1})$ ---
множество суждений, полученное из $\frak S_i$ добавлением всех
суждений $A(c_A)$, $A\in\frak M$.

Покажем, что множество суждений $\frak S_{i+1}'$ непротиворечиво.
Если бы оно было противоречиво, то для некоторых суждений
$B_1,\dots,B_m\in\frak S_i$ и выражений $A_1,\dots,A_n\in \frak M$
суждение
$(B_1\&\dots\&B_m\&A_1(c_{A_1})\&\dots\&A_n(c_{A_n}))\rightarrow
(л)$ было бы выводимо.  Из правил исчисления высказываний отсюда
бы следовало, что выводимо и эквивалентное предыдущему суждение
$$\neg(B_1\&\dots\&B_m\&A_1(c_{A_1})\&\dots\&A_n(c_{A_n})),$$
которое в свою очередь эквивалентно суждению $$\neg
B_1\lor\dots\lor\neg B_n\lor\neg A_1(c_{A_1})\lor\dots\lor\neg
A_n(c_{A_n})).$$ По правилу \therosteritem6 отсюда следует
выводимость суждения $$\forall x_1\dots\forall x_n(\neg
B_1\lor\dots\lor\neg B_m\lor\neg A_1(x_1)\lor\dots\lor\neg
A_n(x_n)),$$ которое по другим правилам вывода эквивалентно
суждению $$\neg B_1\lor\dots\lor\neg B_m\lor\neg (\exists
x_1(A_1(x_1)))\lor\dots\lor\neg (\exists( A_n(x_n))).$$ Из него и
из принадлежащих множеству $\frak S_i$ суждений $B_1$,\dots,$B_m$,
$\exists x_1(A_1(x_1))$,\dots,$\exists( A_n(x_n))$ по правилам
исчисления высказываний выводится тождественно ложное суждение
$$\gather (B_1\&\neg B_1)\lor\dots\lor (B_m\&\neg B_m)\lor\\ \lor
(\exists x_1(A_1(x_1))\&\neg(\exists
x_1(A_1(x_1))))\dots\lor(\exists( A_n(x_n))\&\neg(\exists(
A_n(x_n))) ),\endgather$$
 а это несовместимо с непротиворечивостью  $\frak S_i$.

Итак, множество суждений $\frak S_{i+1}'\subseteq \frak A(\frak
C_{i+1})$ непротиворечиво, и его можно дополнить до максимального
непротиворечивого множества суждений $\frak S_{i+1}\subseteq \frak
A(\frak C_{i+1})$.

Обозначим теперь через $\frak C'$ объединение всех множеств $\frak
C_i$, а через $\frak S'\subseteq \frak A(\frak C')$ ---
объединение всех множеств суждений $\frak S_i$, $i=0,1,\dots$.
Покажем, что $\frak S'$ --- экзистенциально полное и максимальное
непротиворечивое множество суждений. Действительно, если суждение
$\exists x(A(x))$ содержится в $\frak S'$, то это суждение
содержится уже в некотором $\frak S_i$, а тогда в множестве $\frak
S_{i+1}'\subseteq\frak S_{i+1}\subseteq\frak S'$ есть суждение
$A(c_A)$, где $c_A\in \frak C_{i+1}\subseteq\frak C'$. Таким
образом, множество суждений $\frak S'$ экзистенциально полно. Если
бы это множество не было бы максимальным непротиворечивым, то
существовало бы суждение $A\in \frak A(\frak C')$, такое что ни
суждение $A$, ни суждение $\neg A$ не принадлежали бы $\frak S'$.
Но для записи суждения $A$ используется лишь конечное число
символов констант из $\frak C'$, и потому существует номер $i$,
для которого $A\in \frak A(\frak C_i)$; по лемме 1, одно из
суждений $A$, $\neg A$ принадлежит максимальному непротиворечивому
множеству суждений $\frak S_i\subseteq\frak S'$, что противоречит
выбору суждения $A$.

Из наших построений ясно, что $\frak C'$ --- множество малой
мощности. Теорема полностью доказана.
\enddemo
 \subhead 3.5. Доказательство теоремы Геделя\endsubhead
Теперь мы можем завершить доказательство теоремы Геделя о полноте.
Пусть $\frak C\subseteq\frak A(\frak P,\frak C)$ ---
непротиворечивое множество суждений. По теореме из \S 3.4
существует множество символов констант $\frak C'\supseteq\frak C$
малой мощности и максимальное непротиворечивое экзистенциально
полное множество суждений $\frak S'\subseteq\frak A(\frak P,\frak
C')$, содержащее $\frak S$. Далее, по теореме из \S 3.2 существует
такая интерпретация $M=\{M;c_M,P_M\}$ множеств $\frak C'$, $\frak
P$, что для любого элемента $m\in M$ существует символ константы
$c\in \frak C'$, для которого $m=c_M$ (и потому мощность $M$ не
больше мощности $\frak C'$), и суждение из $\frak A(\frak P, \frak
C')$ истинно в $M$ тогда и только тогда, когда оно содержится в
множестве $\frak S'$. Таким образом, интерпретация $M$ является
моделью множества суждений $\frak S'$ и тем более моделью
содержащегося в нем множества суждений $\frak S$.

 \head 4. Теорема Лёвенгейма-Скулема \endhead

\subhead 4.1. Элементарная эквивалентность
\endsubhead Пусть опять $\frak
P$, $\frak C$ --- какие-то множества символов предикатов и
констант. Две интерпретации $M$, $N$ этих множеств называются
элементарно эквивалентными, если множество суждений из $\frak
A(\frak P, \frak C)$, истинных в интерпретации $M$, совпадает с
множеством суждений из $\frak A(\frak P, \frak C)$, истинных в
интерпретации $N$.

Пусть $M=\{M;c_M,P_M\}$ --- интерпретация множества символов
констант $\frak C$ и множества символов предикатов $\frak P$, и
пусть $N$ --- подмножество множества $M$, содержащее элементы
$c_M$ для всех символов констант $c\in \frak C$. Если $P\in \frak
P$ --- символ  $n$-местного предиката, то обозначим через $P_N$
пересечение множества $P_M\subseteq M^n$ с $n$-й декартовой
степенью $N^n$ множества $N$; если $c\in C$, то положим
$c_N=c_M\in N\subseteq M$. Набор $N=\{N;c_N,P_N\}$ представляет
собой интерпретацию множества символов констант $\frak C$ и
множества символов предикатов $\frak P$; мы будем говорить, что
$N$ --- подинтерпретация интерпретации $M$ (согласно правилам
русской орфографии, следовало бы писать {\it подынтерпретация}, но
мы все же предпочтём вариант с "и"). Отметим, что подинтерпретация
полностью определяется подмножеством $N\subseteq M$, от которого
требуется лишь, чтобы оно содержало все элементы $c_M$.

Подинтерпретация $N$ интерпретации $M$ называется элементарной
подинтерпретацией, если она не только элементарно эквивалентна
$M$, но еще и удовлетворяет более сильному условию: если
$A(x_1,\dots,x_s)$ --- любое осмысленное выражение (не обязательно
суждение), в записи которого участвуют только символы предикатов,
принадлежащие $\frak P$, и символы констант, принадлежащие $\frak
C$, и $n_1,\dots,n_s$ --- любые элементы из $N\subseteq M$, то
значения истинности выражения $A(n_1,\dots,n_s)$ в интерпретациях
$M$ и $N$ совпадают.

 \subhead 4.2. Теорема Лёвенгейма-Скулема \endsubhead
Пусть $M$ --- некоторая интерпретации множества символов констант
$\frak C$ и множества символов предикатов $\frak P$, и пусть
$\frak X$ --- множество суждений из $\frak A(\frak P, \frak C)$,
истинных в интерпретации $M$. Теорема Геделя о полноте утверждает
существование модели малой мощности для множества суждений $\frak
X$; однако, она ничего не говорит о связи этой модели с исходной
моделью $M$. Более точный результат дает следующая теорема.
\proclaim{Теорема Лёвенгейма-Скулема}Для любой интерпретации
множества символов констант $\frak C$ и множества символов
предикатов $\frak P$ существует её элементарная подинтерпретация
малой мощности.
\endproclaim
\demo{Доказательство} Рассуждения, приводящие к теореме
Лёвенгейма-Скулема, напоминают рассуждения из \S 3.2-3.4, но
намного проще (следует отметить, что и исторически эта теорема
была получена ранее теоремы Геделя о полноте). Пусть
$M=\{M;c_M,P_M\}$
--- интерпретация множества символов констант $\frak C$ и
множества символов предикатов $\frak P$. Обозначим через
$M_0\subseteq M$ множество всех элементов $c_M$, отвечающих
символам констант $c\in \frak C$. Ясно, что $M_0$ --- множество
малой мощности.

Определим возрастающую цепочку подмножеств малой мощности
$M_0\subseteq M_1\subseteq\dots$ множества $M$, удовлетворяющих
следующему условию: \roster \item"($\ast$)" для каждого
осмысленного выражения $A(x,x_1,\dots,x_n)$ и каждых элементов
$m\in M$, $m_1,\dots,m_n\in M_i$ найдется элемент $m'\in M$, такой
что значения истинности выражений $A(m,m_1,\dots,m_n)$ и
$A(m',m_1,\dots,m_n)$ в интерпретации $M$ совпадают.\endroster
Пусть множество $M_i$ уже построено; если $A(x,x_1,\dots,x_n)$ ---
осмысленное выражение, $m_1,\dots,m_n\in M_i$ и $\varepsilon\in
\{и,л\}$ таковы, что множество элементов $m'\in M$, для которых
значение истинности выражения $A(m',m_1,\dots,m_n)$  в
интерпретации $M$ совпадает с $\varepsilon$, непусто, то выберем в
этом непустом множестве какой-то один элемент
$m'(\varepsilon,A,m_1,\dots,m_n)\in M$. Отметим, что, осуществляя
этот выбор одновременно для всех возможных наборов
$(\varepsilon,A,m_1,\dots,m_n)$, мы пользуемся аксиомой выбора. В
качестве $M_{i+1}$ возьмем множество, полученное присоединением к
множеству $M_i$ всех выбранных элементов
$m'(\varepsilon,A,m_1,\dots,m_n)$. Ясно, что $M_{i+1}$ ---
множество малой мощности, удовлетворяющее условию ($\ast$).

Объединение $N$ всех множеств $M_i$, $i=0,1,2,\dots$ --- тоже
множество малой мощности. Покажем, что $N$ --- элементарная
подинтерпретация интерпретации $M$. Для этого надо доказать, что
для каждого осмысленного выражения $A(x_1,\dots,x_n)$ и каждых
элементов $m_1,\dots,m_n\in N$ значения истинности выражения
$A(m_1,\dots,m_n)$ в интерпретациях $N$ и $M\supseteq N$
совпадают, что мы и сделаем индукцией по построению выражения
$A(x_1,\dots,x_n)$.

Если выражение $A$ имеет один из видов $c=d$, $c=m$, $m=m'$,
$P(t_1,\dots,t_n)$, где $c,d\in \frak C$, $m,m'\in N$, $P$ ---
символ $n$-местного предиката, то, очевидно, истинность этого
выражения в интерпретациях $N$ и $M$ одна и та же.  Если $A$
представляется в форме $B\&C$, $B \lor C$, $B\rightarrow C$,
$B\leftrightarrow C$ или $\neg B$, то его значение истинности
определяется по правилам исчисления высказываний значениями
истинности выражений $B$, $C$, которые, по предположению индукции,
одинаковы для обеих интерпретаций. Остается рассмотреть случай,
когда выражение $A(x_1,\dots,x_n)$ имеет вид $\forall x
B(x,x_1,\dots,x_n)$ или $\exists x B(x,x_1,\dots,x_n)$.

Пусть $m_1,\dots,m_n\in N\subseteq M$; тогда $m_1,\dots,m_n\in
M_i$ для какого-то номера $i$. Если значение истинности выражения
$\forall x B(x,m_1,\dots,m_n)$ в интерпретации $M$ истинно, то
$B(m,m_1,\dots,m_n)$ истинно в $M$ для всех $m\in M$ и тем более
для всех $m\in N$; таким образом, выражение $\forall x
B(x,m_1,\dots,m_n)$ истинно в подинтерпретации $N$. Если же
выражение  $\forall x B(x,m_1,\dots,m_n)$ не истинно в
интерпретации $M$, то существует элемент $m\in M$, такой что
выражение $B(m,m_1,\dots,m_n)$ не истинно в интерпретации $M$; по
построению множества $M_{i+1}$, существует элемент $m'\in
M_{i+1}\subseteq N$,  такой что выражение $B(m',m_1,\dots,m_n)$ не
истинно в интерпретации $M$, а потому, по предположению индукции,
и в интерпретации $N$. Таким образом, выражение  $\forall x
B(x,m_1,\dots,m_n)$ не истинно в интерпретации $N$.

Дуальным образом рассматривается выражение $\exists x
B(x,m_1,\dots,m_n)$. Если оно не истинно в интерпретации $M$, то
$B(m,m_1,\dots,m_n)$ не истинно в $M$ для всех $m\in M$ и тем
более для всех $m\in N$; таким образом, выражение $\exists x
B(x,m_1,\dots,m_n)$ не истинно в подинтерпретации $N$. Если же
выражение  $\exists x B(x,m_1,\dots,m_n)$ истинно в интерпретации
$M$, то существует элемент $m\in M$, такой что выражение
$B(m,m_1,\dots,m_n)$ истинно в интерпретации $M$; по построению
множества $M_{i+1}$, существует элемент $m'\in M_{i+1}\subseteq
N$,  такой что выражение $B(m',m_1,\dots,m_n)$ истинно в
интерпретации $M$, а потому, по предположению индукции, и в
интерпретации $N$. Таким образом, выражение  $\exists x
B(x,m_1,\dots,m_n)$ истинно в интерпретации $N$.
\enddemo

\head 5. Аксиоматика $Z_1$ полукольца натуральных чисел
\endhead
Натуральные числа обычно определяются при помощи аксиом Пеано. В
этой системе аксиом натуральные числа образуют множество $\Bbb
N_0$ с единственной заданной на нем унарной операцией следования:
для каждого натурального числа $x$ определено единственное
натуральное число $x'$, следующее за $x$. При этом должны
выполняться следующие условия (аксиомы Пеано): \roster\item Если
$x'=y'$, то $x=y$.
\item Существует натуральное число $0\in \Bbb N_0$, такое что $x'
\ne 0$ ни для какого $x\in \Bbb N_0$.
\item Если $M$ --- подмножество множества $\Bbb N_0$, содержащее 0
и такое, что для любого элемента $x\in M$ следующий за ним элемент
$x'$ также принадлежит $M$, то $M=\Bbb N_0$.
\endroster

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

В формальной арифметике $Z_1$ два символа тернарных предикатов
$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$. Следующие суждения считаются истинными в $Z_1$ (т.е.
принимаются за аксиомы). \roster
\item $\forall x\forall y\exists z(S(x,y,z))$;
\item $\forall x\forall y\forall z\forall t ((S(x,y,z)\&S(x,y,t))
\rightarrow(z=t))$;
\item $\forall x\forall y\exists z(P(x,y,z))$;
\item $\forall x\forall y\forall z\forall t ((P(x,y,z)\&P(x,y,t))
\rightarrow(z=t))$;
\item $\forall x(S(x,0,x)\&P(x,1,x))$;
\item $\forall x\forall y\forall z((S(x,1,z)\&S(y,1,z))
\rightarrow(x=y))$;
\item $\forall x\forall y\forall z\forall t\forall u\forall v
\forall w((S(x,y,t)\&S(t,z,u)\&S(y,z,v)\&S(x,v,w))
\rightarrow(u\!=\!w))$;
\item $\forall x\forall y\forall z\forall t\forall u\forall v
\forall w((P(x,y,t)\&P(t,z,u)\&P(y,z,v)\&P(x,v,w))
\rightarrow(u\!=\!w))$;
\item $\forall x\forall y\forall z\forall t\forall u\forall v
\forall w\forall p ((S(x,y,t)\&P(t,z,u)\&P(x,z,v)\&P(y,z,w)\&$

$\&S(v,w,p)) \rightarrow(u\!=\!p))$;
\item $\forall x\forall y\forall z\forall t((S(x,y,z)\&S(y,x,t))
\rightarrow(z\!=\!t))$;
\item $\forall x\forall y\forall z\forall t((P(x,y,z)\&P(y,x,t))
\rightarrow(z\!=\!t))$;
\item $\forall x(\neg S(x,1,0))$.\endroster

Первая аксиома неформально означает, что для всяких двух
натуральных чисел существует их сумма, а вторая --- что эта сумма
единственна. Точно так же, аксиомы \therosteritem3 и
\therosteritem4 утверждают существование и единственность
произведения. Аксиома \therosteritem5 выражает обычные свойства 0
и 1, в аксиомах \therosteritem7-\therosteritem{11} постулируются
ассоциативность и коммутативность суммы и произведения и
дистрибутивный закон. Аксиома \therosteritem6 по существу
совпадает с первой аксиомой Пеано: если совпадают элементы,
следующие за двумя натуральными числами, то совпадают и сами эти
числа, а аксиома \therosteritem{12} --- со второй аксиомой Пеано:
не существует числа, предшествующего 0. В этом списке отсутствует
аксиома индукции; в полной общности она не может быть
сформулирована на нашем формальном языке. Однако, можно надеяться,
что в полной общности она нам и не нужна, а использовать ее
придется только для тех подмножеств множества натуральных чисел,
которые могут быть сконструированы. Но что означает
"сконструированы?" Это значит, что они заданы при помощи
осмысленных выражений; поэтому достаточно сформулировать аксиому
индукции для каждого осмысленного выражения в нашем алфавите, и мы
получаем не одну, а бесконечно много аксиом индукции,
занумерованных осмысленными выражениями. Пусть
$Q(x_1,\dots,x_n,y)$ --- осмысленное выражение, в которое входят
свободно только символы переменных $x_1,\dots,x_n,y$; аксиома
индукции для этого выражения имеет следующий вид:

\roster\item"(13$_Q$)"$\forall x_1\forall x_2\dots\forall
x_n\Big(\lfloor Q(x_1,\dots,x_n,0)\&$\newline $\&\langle\forall
y\forall z\{[S(y,1,z)\&Q(x_1,\dots,x_n,y)]\rightarrow
Q(x_1,\dots,x_n,y)\}\rangle\rfloor
\rightarrow$\newline$\rightarrow[\forall x
Q(x_1,\dots,x_n,y)]\Big) $\endroster (для удобства мы обозначили
скобки разного уровня разными знаками и при переносе в формуле с
одной строки на другую повторили последний логический знак).

Насколько адекватно отражает эта система аксиом свойства
натуральных чисел? Является ли она непротиворечивой? Если да, то
являются ли все ее модели элементарно эквивалентными? Эти и другие
вопросы должны были, естественно, с самого начала заинтересовать
математиков. На часть из них ответа нет до сих пор. Не доказано,
что система $Z_1$ непротиворечива; наличие обычных натуральных
чисел, которые, казалось бы, должны составлять модель $Z_1$,
ничего не доказывает, так как единственное, что мы можем сказать,
это то, что многовековая история использования человечеством
натуральных чисел до сих пор не привела ни к какому противоречию,
и мы {\it верим}, что противоречие и не возникнет. Такое {\it
экспериментальное} доказательство вполне удовлетворило бы физиков,
но совершенно не приемлемо для математика.

Для того, чтобы описать ситуацию с другими вопросами, дадим одно
определение. Множество суждений $ S\subseteq\frak A(\frak P,\frak
C)$ называется полным, если для любого суждения $X\in \frak
A(\frak P,\frak C)$ одно из суждений $X$, $\neg X$ выводимо из
$S$. Гедель доказал, что если система аксиом теории $Z_1$
непротиворечива, то она не полна, т.е. можно сформулировать в
терминах этой теории такую теорему, что ни она сама, ни ее
отрицание не могут быть доказаны в этой теории. Мы объясним ниже
некоторые идеи, объясняющие, почему это так; для этого нам
понадобится изучить функции на множестве натуральных чисел, все
значения которых можно в принципе сосчитать. Теории таких функций,
называемых рекурсивными, посвящена большая часть последующих
параграфов, а в конце мы дадим набросок доказательства упомянутой
теоремы Геделя о неполноте системы аксиом $Z_1$.

Тот факт, что существуют неполные системы аксиом, не должен
удивлять; например, аксиомы теории групп, формальную запись
которой после формулировок аксиом системы $Z_1$ будет теперь легко
осуществить читателю, заведомо не полна: суждение "группа состоит
из 7 элементов" не может быть ни доказано, ни опровергнуто в
рамках формальной теории групп, поскольку существует модель этой
теории, в которой это суждение верно (циклическая группа порядка
7), и существует модель, в которой оно не верно (аддитивная группа
целых чисел). Тем удивительнее тот факт, что существуют достаточно
богатые теории, описываемые сравнительно простыми полными
системами аксиом. Примером является теория вещественно
упорядоченных полей, которую мы сейчас и опишем. В этой теории два
символа констант --- 0 и 1, два трехместных предиката $S(x,y,z)$
$P(x,y,z)$ и двухместный предикат $O(x,y)$, содержательно
соответсвующий неравенству $x<y$. Читатель по аналогии с аксиомами
$Z_1$ без труда перепишет в формальном виде аксиомы поля. Кроме
них, в систему аксиом вещественно упорядоченного поля входят три
аксиомы неравенства \roster\item $\forall x\forall
y((x=y)\lor(O(x,y))\lor O(y,x))$;
\item $\forall x\forall y(\neg (O(x,y)\& O(y,x))$;
\item$\forall x\forall y\forall z\forall t((O(0,x)\& O(0,y)\&S(x,y,z)\&
P(x,y,t))\rightarrow(O(0,z)\&O(t,0)))$\endroster (содержательно
они означают, что  для любых двух элементов или эти элементы
равны, или первый меньше второго, или второй меньше первого; не
может быть, чтобы каждый из двух элементов был меньше второго;
если два элемента больше 0, то их сумма и их произведение тоже
больше 0), а также бесконечная серия аксиом, занумерованных
натуральными числами, которые мы не будем записывать в формальном
виде, а дадим их упрощенную форму: \roster\item"(4$_n$)"$\forall
a_0\forall a_1\dots\forall a_n\forall x\forall y$\newline $(
O(0,a_0+a_1x+\dots+a_nx^n)\& O(a_0+a_1y+\dots+a_ny^n,0)\&
O(x,y))\rightarrow$\newline $\rightarrow(\exists z(O(x,z)\&
O(z,y)\&(a_0+a_1z+\dots+a_nz^n=0) ))$.\endroster

Упрощение, которое мы сделали в последней аксиоме, состоит  в том,
что мы не сводили вычисление значения многочлена к предикатам $S$
и $P$; это можно было бы легко сделать, значительно увеличив число
переменных в формуле (количество новых переменных зависит только
от $n$). Смысл последней аксиомы очевиден: если многочлен в двух
точках принимает значения разных знаков, то у него в промежутке
между этими точками есть корень.

\head 6. Примитивно рекурсивные функции
\endhead
\subhead 6.1. Элементарные функции
\endsubhead
Как обычно, мы обозначаем через $\Bbb N_0$ множество, состоящее из
0 и всех натуральных чисел. Все функции, рассматриваемые в этой
главе, являются функциями нескольких переменных $x_1,\,x_2,...$ из
$\Bbb N_0$ со значениями в $\Bbb N_0$. Следующие функции мы будем
называть элементарными: $$\align  &o(x_1)=0,\\
&s(x_1)=x_1+1,\\&\id(x_1)=x_1,\\&\pr_1(x_1,x_2)=x_1,\,\,
\pr_2(x_1,x_2)=x_2.
\endalign $$
%В дальнейшем нам будет иногда удобнее не употреблять в обозначениях функций
%верхние и нижние индексы, а так же натуральные числа. Поэтому для функции
%$p_n^i$ мы будем иногда применять обозначение $pp...k...p$, где общее число
%букв равно $n$, а $k$ стоит на $i$-м месте; например, $ppkp=p_4^3,\,kp=p_2^1
%\,,pk=p_2^2,\,k=p_1^1$.
\subhead 6.2.  Подстановка
\endsubhead
Пусть
$f(x_1,...\,,x_n),\,g_1(x_1,...\,,x_m),...\,,g_n(x_1,...\,,x_m)$
-- некоторые функции; мы будем говорить, что функция
$$h(x_1,...\,,x_m)=
f(g_1(x_1,...\,,x_m),...\,,g_n(x_1,...\,,x_m))$$ получена из
функций $f,g_1,...\,,g_n$ подстановкой.
%Тот факт, что функция $h$
%получена из функций $f,g_1,...\,,g_n$ подстановкой, будем
%записывать так: $h=t[f,g_1,...\,,g_n]$. Конечно, выражение
%$t[f,g_1,...\,,g_n]$ не всегда осмысленно: для того, чтобы оно
%представляло некоторую функцию, необходимо (и достаточно), чтобы
%$f$ была функцией от $n$ переменных, а все функции $g_1,...\,,g_n$
%были бы функциями от одного и того же числа переменных. При
%выполнении этого условия функция $t[f,g_1,...\,,g_n]$ однозначно
%определена.
\subhead 6.3. Примитивная рекурсия
\endsubhead
Опишем еще один способ построения новых функций из уже имеющихся.
Этот способ называется примитивной рекурсией и по существу
представляет собой построение значений функции по индукции.
Точнее, пусть $h(x_1,...\,,x_{n-1}),\,\,
g(x_1,...\,,x_{n-1},x_n,x_{n+1})$ -- две функции; мы говорим, что
функция $f(x_1,...\,,x_{n-1},x_n)$ получена из них примитивной
рекурсией, если $$\align
f(x_1,...\,,x_{n-1},0)&=h(x_1,...\,,x_{n-1}),\\
f(x_1,...\,,x_{n-1},x_n+1)&=g(x_1,...\,,x_{n-1},x_n,
f(x_1,...\,,x_{n-1},x_n)).
\endalign $$
Ясно, что каждое значение функции $f$ может быть найдено по этим
формулам, и притом однозначно, так что функция $f$ однозначно
определена функциями $h,\,g$.
%Тот факт, что функция $f$ получена
%из функций $h,\,g$ примитивной рекурсией, будем записывать так:
%$f=r[h,g]$. Функция $r[h,g]$ определена тогда и только тогда,
%когда число аргументов функции $h$ на 2 меньше числа аргументов
%функции $g$.
\subhead 6.4. Примитивно рекурсивные функции
\endsubhead
Все функции, которые могут быть получены при помощи операций
подстановки и примитивной рекурсии из элементарных функций
$o,\,s,\,\id,\,\pr_1,\,\pr_2$, называются примитивно рекурсивными.
Точнее говоря, \roster
\item функции $o,\,s,\,\id,\,\pr_1,\,\pr_2$ примитивно
рекурсивны;
\item если $f(x_1,...\,,x_n),\,g_1(x_1,...\,,x_m),...\,,
g_n(x_1,...\,,x_m)$ -- примитивно рекурсивные функции, то и
функция $$h(x_1,...\,,x_m)=
f(g_1(x_1,...\,,x_m),...\,,g_n(x_1,...\,,x_m)),$$ полученная из
них подстановкой функция, примитивно рекурсивна;
\item если $h,\,g$ -- примитивно рекурсивные функции, то
функция, полученная из них при помощи примитивной рекурсии,
примитивно рекурсивна;
\item функции, которые не могут быть получены из элементарных
функций многократным применением операций подстановки и
примитивной рекурсии, не являются примитивно рекурсивными.
\endroster
%Напомним, что функции $p_n^i$ мы условились записывать в виде $p...k...p$;
%из приведенного выше определения следует, что каждая примитивно рекурсивная
%функция может быть представлена как слово в конечном алфавите
%из 9 букв $\{,\,o\,s\,p\,k\,t\,r\,]\,[\,\}$. Конечно, не всякому слову отвечает
%некоторая примитивно рекурсивная функция; однако, если для слова существует
%соответствующая примитивно рекурсивная функция, то она определена однозначно.
%Это соответствие не взаимно однозначно; нетрудно привести пример,
%показывающий, что разным словам может отвечать одна и та же функция.
\subhead 6.5. Простейшие примитивно рекурсивные функции
\endsubhead
\example{Проекции}Функции $\pr_i^{(n)}$, определенные равенствами
$\pr_i^{(n)}(x_1,\dots,x_n)=x_i$, примитивно рекурсивны для любых
$n>2$, $1\le i\le n$, так как они получаются подстановками:
$$\pr_i^{(n)}(x_1,\dots,x_n)=\pr_{s_1}(x_1,\pr_{s_2}(x_2,\dots,
\pr_{s_{n-1}}(x_{n-1},x_n)\dots)),$$ где  $s_j=2$ при $j<i$,
$s_j=1$ при $j\ge i$.
\endexample
\example{Константы}Функции $s(o(x_1)),\,s(s(o(x_1))),...$,
представляют собой функции одной переменной $x_1$, значения
которых тождественно равны 1,2,... , а функции
$o(p_1^{(n)}(x_1,\dots,x_n)),\,s(o(p_1^{(n)}(x_1,\dots,x_n))),\,
s(s(o(p_1^{(n)}(x_1,\dots,x_n)))),...$, яв\-ля\-ются функциями $n$
переменных, значения которых тождественно равны 0,1,2,... Таким
образом, постоянные функции примитивно рекурсивны.
\endexample
\example{Сумма и произведение}Сумма $\sm(x_1,x_2)=x_1+x_2$ может
быть определена при помощи примитивной рекурсии $$\alignat2
\sm(x_1,0)&=x_1&&=\id(x_1),\\\sm(x_1,x_2+1)&=\sm(x_1,x_2)+1
&&=s(\pr_3^{(3)}(x_1, x_2,\sm(x_1,x_2)))\,.
\endalignat $$
Правые части обоих равенств примитивно рекурсивны, потому и
функция $\sm$ получена примитивно рекурсивна.

Произведение $\prd(x_1,x_2)=x_1x_2$ определяется примитивной
рекурсией $$\alignat2 \prd(x_1,0)&=0&&=o(x_1), \\
\prd(x_1,x_2+1)&=\prd(x_1,x_2)+x_1&&=\sm(x_1,\prd(x_1,x_2))\,.
\endalignat $$
Следовательно, $\prd$ -- примитивно рекурсивная функция.
\endexample
В дальнейшем мы не будем проявлять столь щепетильный формализм,
как в рассмотренных примерах, и будем обычно употреблять для
вводимых функций более естественные обозначения; читатель легко
сможет восстановить пропущенные детали. В частности, аргументы
функций мы не всегда будем обозначать $x_1,x_2,...$, а для суммы и
произведения будем обычно использовать привычные знаки $x+y,\,xy$.
\example{Усеченная разность. Модуль разности} Не для любых чисел
из $\Bbb N_0$ их разность принадлежит $\Bbb N_0$; поэтому в
качестве суррогата разности приходится использовать так называемую
усеченную разность: усеченная разность $x\ominus y$ чисел $x$ и
$y$ равна $x-y$, если $x\ge y$, и равна 0, если это не так. Для
задания усеченной разности сначала зададим функцию одного
аргумента $\alpha(x)=x\ominus 1$ примитивной рекурсией $$\align
0\ominus 1&=0,\\(x+1)\ominus 1&=x\,.
\endalign $$
 Усеченная разность задается теперь такой примитивной рекурсией:
$$\align x\ominus 0&=x,\\x\ominus (y+1)&=(x\ominus y)\ominus
1=\alpha(x\ominus y)\,.
\endalign $$
Примитивно рекурсивной функцией является и модуль разности
$|x-y|=(x\ominus y)+(y\ominus x)$. Эта функция получается из суммы
подстановкой вместо слагаемых соответствующих усеченных разностей.
\endexample
\example{Знак и антизнак} Определим функцию $\sg(x)$, положив
$\sg(0)=0,\, \sg(x)=1$ при $x>0$, и функцию $\overline {\sg}(x)$,
положив $\overline{\sg}(0)=1,\, \overline{\sg}(x)=0$ при $x>0$.
Обе эти функции задаются примитивными рекурсиями $$
\left\{\aligned \sg(0)&=0,\\\sg(x+1)&=1;\endaligned\right.\qquad
\left\{\aligned \overline{\sg}(0)&=1,\\ \overline{\sg}(x+1)&=0.
\endaligned\right. $$
\endexample
\example{Неполное частное и остаток}Не всегда возможно разделить
одно натуральное число на другое; поэтому вместо деления мы вводим
деление с остатком. Пусть $x,y\in \Bbb N_0$. Если $y>0$ неполным
частным $[x/y]$ называется такое целое число, что $[x/y]y\le
x,\,\,([x/y]+1)y>x$, а остаток определяется формулой
$\rst(x,y)=x-[x/y]y$; для того, чтобы сделать неполное частное и
остаток определенными всегда, условимся считать, что $[x/0]=0,\,\,
\rst(x,0)=x$. Остаток и неполное частное могут быть заданы такими
примитивными рекурсиями: $$\align
\rst(0,y)&=0,\\\rst(x+1,y)&=(\rst(x,y)+1)\cdot
\sg|y-(\rst(x,y)+1)|\,;\\ \vspace{2\jot}
[0/y]&=0,\\[(x+1)/y]&=[x/y]+\overline{\sg}(\rst(x+1),y)\,.
\endalign $$
\endexample
\subhead 6.6. Суммы и произведения с переменными пределами
\endsubhead
Для примитивно рекурсивной функции $f(x_1,...\,,x_{n-1},x_n)$
положим
$$F(x_1,...\,,x_{n-1},x_n)=\sum_{i=0}^{x_n}f(x_1,...\,,x_{n-1},i)\,.$$
Эта функция примитивно рекурсивна, так как она может быть
определена примитивной рекурсией $$\align
F(x_1,...\,,x_{n-1},0)&=0\,,\\
F(x_1,...\,,x_{n-1},x_n+1)&=F(x_1,...\,,x_{n-1},x_n)+
f(x_1,...\,,x_{n-1},x_n+1)\,.
\endalign $$
Отсюда следует, что примитивно рекурсивна и функция
$$\gathered\sum_{i=x_n}^{x_{n+1}}f(x_1,...\,,x_{n-1},i)=\\
\sum_{i=0}^{x_{n+1}}f(x_1,...\,,x_{n-1},i) \ominus
\sum_{i=0}^{x_n}f(x_1,...\,,x_{n-1},i)\,\,+ \sg(x_{n+1}\ominus
x_n)f(x_1,...,x_{n-1},x_n)\,.\endgathered$$ Подставляя вместо
$x_n,\,x_{n+1}$ произвольные примитивно рекурсивные функции
$g(x_1,...\,,x_{n-1},x_n),\,h(x_1,...\,,x_{n-1},x_n)$, получаем,
что функция $$\sum_{i=g(x_1,...,x_n)}^{h(x_1,...,x_n)}
f(x_1,...\,,x_{n-1},i)$$ тоже примитивно рекурсивна. Таким же
образом показывается, что произведение значений примитивно
рекурсивной функции с переменными верхним и нижним пределами,
выражаемыми примитивно рекурсивными функциями, само является
примитивно рекурсивной функцией.

\subhead 6.7. Кусочное задание примитивно рекурсивной функции
\endsubhead
Пусть $$g_1(x_1,...\,,x_n),...\,,g_m(x_1,...\,,x_n),
\,\,h_1(x_1,...\,,x_n),...\,, h_m(x_1,...\,,x_n),
\,\,h(x_1,...\,,x_n)$$ -- примитивно рекурсивные функции, причем
никакие две из функций $g_1,...\,,$ $g_m$ ни при каких значениях
переменных не обращаются одновременно в 0. Тогда функция
$f(x_1,...\,,x_n)$, определенная условиями
$$f(x_1,...\,,x_n)=\left \{ \aligned h_1&(x_1,...\,,x_n),\quad
\text{если}\quad g_1(x_1,...\,,x_n)=0,\\
&\hdots\\h_m&(x_1,...\,,x_n),\quad \text{если}\quad
g_m(x_1,...\,,x_n)=0,\\ h&(x_1,...\,,x_n)\quad\,\,\, \text{в
остальных случаях,} \endaligned \right.$$ примитивно рекурсивна,
так как $$f=h_1\overline
{\sg}(g_1)+...+h_m\overline{\sg}(g_m)+h\cdot \sg(g_1\cdots g_m)
\,.$$

\subhead 6.8. Ограниченная минимизация
\endsubhead
Пусть $f(x_1,...\,,x_n,t)$ -- такая функция, что для любых
$x_1,...\,,x_n$ уравнение $f(x_1,...\,,x_n,t)=0$ имеет решение
(напомним, что значения функции и все аргументы предполагаются
принадлежащими множеству натуральных чисел $\Bbb N_0$, так что и
решение предполагается натуральным). Обозначим через $(\mu
_tf)(x_1,...\,,x_n)$ наименьшее решение этого уравнения. Вообще
говоря, функция $\mu _tf$ не примитивно рекурсивна, даже если $f$
примитивно рекурсивна. Однако, если $f$ примитивно рекурсивна и
существует такая примитивно рекурсивная функция
$g(x_1,...\,,x_n)$, что для любых $x_1,...\,,x_n$ уравнение
$f(x_1,...\,,x_n,t)=0$ имеет решение $t\leq g(x_1,...\,,x_n)$, то
$\mu _tf$ -- примитивно рекурсивная функция. Действительно, $$(\mu
_tf)(x_1,...\,,x_n)=\sum_{i=0}^{g(x_1,...,x_n)} \sg(\prod_{j=0}^i
f(x_1,...\,,x_n,j))\,.$$ Действительно, фигурирующее в этой
формуле произведение отлично от 0 лишь до тех пор, пока мы не
дойдем до решения $t_0$ уравнения (а мы до него дойдем по
условию), и в сумме слагаемые, отвечающие индексам $i<t_0$, равны
1, а все остальные слагаемые равны 0. Вместо $(\mu
_tf)(x_1,...\,,x_n)$ мы будем писать иногда $\mu
_tf(x_1,...\,,x_n,t)$; еще раз отметим, что это функция только от
$x_1,...\,,x_n$, но не от $t$.

\subhead 6.9. Теоретико-числовые функции
\endsubhead
Количество делителей числа $x$
$$div(x)=\sum_{i=0}^x\overline{\sg}(\rst(x,i))$$ и количество
простых чисел, не превосходящих $x$, $$\pi
(x)=\sum_{i=0}^x\overline{\sg}(|div(x)-2|)$$ являются примитивно
рекурсивными, как композиции примитивно рекурсивных функций (мы
считаем, что $div(0)=0$, а во второй формуле используем, что число
является простым тогда и только тогда, когда число его делителей
равно 2). Перенумеруем все простые числа в порядке возрастания:
$p_0=2,\, p_1=3,\,p_2=5,...$ Тогда $n$-е простое число -- это
наименьшее число, такое что $\pi (x)=n+1$, т.е. $p_x=\mu _y|\pi
(y)-(x+1)|$. Таким образом, функция $p_x$ получается минимизацией
из примитивно рекурсивной функции $|\pi (y)-(x+1)|$, и для
доказательства её примитивной рекурсивности достаточно доказать,
что решение уравнения $|\pi (y)-(x+1)|=0$ ограничено сверху
примитивно рекурсивной функцией от $x$. Но это действительно так:
$p_x\leq 2^{2^x}$; в самом деле, это верно для $x=0$, и, если это
доказано для всех меньших $x$ значений аргумента,  то $$p_x\leq
p_0p_1\cdots p_{x-1}+1\leq 2^{2^0}2^{2^1}\cdots 2^{2^{x-1}}+1<
2\cdot 2^{1+2+...+2^{x-1}}=2^{2^x},$$ ибо число $N=p_0p_1\cdots
p_{x-1}+1$ не делится ни на одно из чисел
$p_0,\,p_1,\,...\,,p_{x-1}$ и потому все его простые делители (а
хотя бы один простой делитель существует) больше $p_{x-1}$ и не
больше $N$, а, значит, $p_x\leq N$. Обозначим через $\exp(x,y)$
показатель степени, с которым простое число $p_x$ входит в
разложение $y$ в произведение простых чисел (для $y=0$ считаем,
что $\exp(x,y)=0$ для всех $x$). Ясно, что $$ \exp(x,y)=\left\{
\aligned &\mu _z\overline{\sg}(\rst(y,p_x^z))\ominus 1, \text{
если } \overline{\sg}(y)=0\,,\\ &0 \text{ в остальных
случаях,}\endaligned\right. $$ так что $\exp(x,y)$ -- тоже
примитивно рекурсивная функция.

\subhead 6.10. Координатные функции
\endsubhead
Пусть $n\ge 1$ -- натуральное число; построим примитивно
рекурсивные функции $c_1^{(n)}(x)$,\dots, $c_n^{(n)}(x)$,
$d^{(n)}(x_1,\dots,x_n)$, такие что
$$d^{(n)}(c^{(n)}_1(x),\dots,c^{(n)}_n(x))=x,\quad
c^{(n)}_i(d^{(n)}(x_1,\dots,x_i,\dots,x_n))=x_i\,\,(1\le i\le n)$$
для всех $x,x_1,\dots,x_n\in \Bbb N_0 $. Эти равенства в точности
означают, что наши функции осуществляют взаимно обратные
биективные отображения $\Bbb N_0 ^n\to \Bbb N_0 $, $\Bbb N_0 \to
\Bbb N_0 ^n$. Функции $c^{(n)}_i$ называются координатными
функциями.

При $n=1$ положим $c_1^{(1)}(x)=d^{(1)}(x)=x$. Рассмотрим случай
$n=2$. Поскольку этот случай наиболее важный и часто
встречающийся, мы будем использовать вместо $с_1^{(2)}$,
$с_2^{(2)}$ более простые обозначения $c_1$, $c_2$.  Функция
$d^{(2)}(x,y)=[(x+y)(x+y+1)/2]+x$ примитивно рекурсивна. Для
построения функций $c_1$, $c_2$ определим вспомогательную функцию
$h(z)=\mu _t(\overline{\sg}(t^2+t\ominus 2z))\ominus 1$. Иначе
говоря, $h(z)$ -- наибольшее число, такое что $[h(z)(h(z)+1)/2]\le
z$. Функция $h(z)$ получена минимизацией из примитивно рекурсивной
функции, и, поскольку $h(z)\le z$, эта минимизация ограниченная.
Таким образом, $h(z)$ -- примитивно рекурсивная функция. Тогда и
функции $c_1(z)\!=\!z\ominus [h(z)(h(z)+1)/2],\,\,
c_2(z)\!=\!h(z)\ominus c_1(z)$ примитивно рекурсивны. При этом
 $$\gathered
d^{(2)}(c_1(z),c_2(z))=[(c_1(z)+c_2(z))(c_1(z)+
c_2(z)+1)/2]+c_1(z)=\\[h(z)(h(z)+1)/2]+z\ominus
[h(z)(h(z)+1)/2]=z.\endgathered $$
 Далее, для любых $x,y\in\Bbb
N_0$ имеем: $(x+y)(x+y+1)/2\le d^{(2)}(x,y)$,
$(x+y+1)(x+y+2)/2>(x+y)(x+y+1)/2+(x+y)\ge
(x+y)(x+y+1)/2+x=d^{(2)}(x,y)$, и потому $h(d^{(2)}(x,y))=x+y$,
$c_1(d^{(2)}(x,y))=d^{(2)}(x,y)-[(x+y)(x+y+1)/2]=x$,
$c_2(d^{(2)}(x,y))=y$. Отметим, что функции $d^{(2)}$,
$c_1,\,c_2$, которые мы только что определили, имеют простой
смысл: они осуществляют перечисление целочисленных точек плоскости
с неотрицательными координатами по прямым $x+y=b$, т.е. в
следующем порядке: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0),
(0,3), (1,2), (2,1), (3,0)... Конечно, возможны и другие варианты
построения функций $c_2^i$, $d^{(2)}$. Если уже определены функции
$d^{(n-1)}$, $c^{(n-1)}_i$ ($n>2$), то следующим образом определим
функции $d^{(n)}$, $c^{(n)}_i$: $$\align
d^{(n)}&(x_1,\dots,x_{n-1},x_n)=d^{(2)}(d^{(n-1)}(x_1,\dots,
x_{n-1}),x_n), \\ c^{(n)}_i&(y)=c^{(n-1)}_i(c_1(y))\,\,\text{ при
}1\le i<n,\quad c_n^{(n)}(y)= c_2(y).\endalign $$
 Из последнего определения, в частности, следует, что $c_n^i(y)$
является примитивно рекурсивной функцией не только от $y$, но и от
$n$ и $i$.

\subhead 6.11. Функция Гёделя\endsubhead Наряду с координатными
функциями, нам понадобится и так называемая функция Гёделя $\Gamma
(x,y)$. Примитивно рекурсивная функция двух аргументов $\Gamma
(x,y)$ называется функцией Гёделя, если для любого $m$ и любого
набора $a_0,a_1,...\,,a_m\in \Bbb N_0$ существует число $t\in \Bbb
N_0$, такое что $\Gamma (t,0)=a_0, \Gamma (t,1)=a_1,..\,,\Gamma
(t,m)=a_m$. Примером функции Гёделя является введенная в
предыдущем пункте функция $\exp(x,y)$; точнее, функция $\Gamma
(x,y)=\exp(y,x)$ является функцией Гёделя, так как для любых
$a_0,a_1,...\,,a_m\in \Bbb N_0$ имеем для
$t=p_o^{a_0}p_1^{a_1}\cdots p_m^{a_m}$: $$\align \Gamma
(t,0)\,\,&=\exp(0,t)\,\,=a_0,\\ \Gamma
(t,1)\,\,&=\exp(1,t)\,\,=a_1,\\ &\hdots \\ \Gamma
(t,m)&=\exp(m,t)=a_m\,.
\endalign $$
Функция Гёделя, как и координатные функции, определена
неоднозначно. Зафиксируем раз и навсегда какие-то координатные
функции и функцию Гёделя.

\head 7. Рекурсивно перечислимые множества
\endhead
\subhead 7.1. Определение рекурсивно перечислимого множества чисел
\endsubhead
\proclaim{Tеорема}Пусть $M$ -- непустое подмножество множества
натуральных чисел $\Bbb N_0$. Следующие условия равносильны:
\roster
\item для некоторого $n$ существует примитивно рекурсивная функция от $n$
переменных $f(x_1,...\,,x_n)$, множество значений которой
совпадает с $M$;
\item существует примитивно рекурсивная функция $f(x)$, множество значений
которой совпадает с $M$;
\item существует примитивно рекурсивная функция $h(a,x)$, такая что уравнение
$h(a,x)=0$  (относительно неизвестной $x$) имеет решение тогда и
только тогда, когда $a\in M$;
\item для некоторого $n$ существует такая примитивно рекурсивная функция
$h(a,x_1,...\,,x_n)$ от $n+1$ переменных, что уравнение
$h(a,x_1,...\,,x_n)=0$  (относительно неизвестных $x_1,...\,,x_n$)
имеет решение тогда и только тогда, когда $a\in M$.
\endroster
\endproclaim
\demo{Доказательство}\therosteritem1$\Rightarrow$\therosteritem2.
Пусть $f(x_1,...\,,x_n)$ -- примитивно рекурсивная фун\-кция,
множество значений которой совпадает с $M$; тогда множество
значений функции $g(x)=f(c_1(x),...\,,c_n(x))$, где $c_1,..,,c_n$
-- координатные функции, тоже совпадает с $M$.
\therosteritem2$\Rightarrow$\therosteritem3. Пусть $f(x)$ --
примитивно рекурсивная функция, множество значений которой
совпадает с $M$; положим $h(a,x)=|f(x)-a|$. Разрешимость уравнения
$h(a,x)=0$ равносильна существованию $x\in \Bbb N_0$, такого что
$f(x)=a$, т.е. тому, что число $a$ принадлежит множеству значений
$M$ функции $f(x)$. \therosteritem3$\Rightarrow$\therosteritem4 --
очевидно. \therosteritem4$\Rightarrow$\therosteritem1. Пусть
$h(a,x_1,...\,,x_n)$ -- такая примитивно рекурсивная функция, что
уравнение $h(a,x_1,...\,,x_n)=0$ разрешимо относительно
$x_1,...\,,x_n$ тогда и только тогда, когда $a\in M$. Выберем
произвольный элемент $b\in M$ и положим
$$f(x,x_1,...\,,x_n)=x\cdot\overline{\sg}(h(x,x_1,...\,,x_n))+
b\cdot \sg(h(x,x_1,...\,,x_n))\,.$$ Если $x\in M$, то существуют
$x_1,...\,,x_n\in \Bbb N_0$, для которых $h(x,x_1,...\,,x_n)=0$ и
$f(x,x_1,...\,,x_n)= x\cdot 1+b\cdot 0=x$. Таким образом,
множество значений функции $f(x,x_1,...\,,x_n)$ содержит $M$.
Обратно, пусть $z=f(x,x_1,...\,,x_n)$ принадлежит множеству
значений функции $f(x,x_1,...\,,x_n)$; если
$h(x,x_1,...\,,x_n)=0$, то $z=x$ принадлежит $M$, так как
существует решение $x_1,...\,,x_n$ уравнения
$h(x,x_1,...\,,x_n)=0$, а если $h(x,x_1,...\,,x_n)\ne 0$, то
$z=b\in M$. Теорема полностью доказана.
\enddemo
Подмножество $M$ множества $\Bbb N_0$ называется рекурсивно
перечислимым, если оно либо пусто, либо удовлетворяет равносильным
требованиям только что доказанной теоремы.

\subhead 7.2. Рекурсивно перечислимые подмножества декартовых
степеней $\Bbb N_0$
\endsubhead
Подмножество $M$ декартовой степени $\Bbb N_0^n$ множества
натуральных чисел называется рекурсивно перечислимым, если
подмножество $$M_0=\{d^{(n)}(a_1,\dots,a_n)\,|\,(a_1,\dots,a_n)\in
M\}$$ множества $\Bbb N_0 $ рекурсивно перечислимо (здесь, как и
раньше, через $d^{(n)}$ обозначается примитивно рекурсивная
функция, нумерующая точки из $\Bbb N_0^n$).
%Подмножество
%$M$ декартовой степени $\Bbb N_0^n$ множества натуральных чисел
%называется рекурсивно перечислимым, если существует рекурсивно
%перечислимое подмножество $M_0\subseteq\Bbb N_0$, такое что $M$
%состоит из всех точек $$(c_1^{(n)}(x),...\,,c_n^{(n)}(x))$$ с
%$x\in M_0$ (здесь, как и прежде, $c_1^{(n)},...\,,c_n^{(n)}$ --
%координатные функции). На первый взгляд это определение не
%инвариантно: оно зависит от выбора координатных функций. Следующая
%теорема дает несколько инвариантных характеризаций рекурсивно
%перечислимых подмножеств $\Bbb N_0^n$.
\proclaim{Теорема}Пусть $M$ -- непустое подмножество $\Bbb N_0^n$;
следующие условия равносильны: \roster
\item $M$ рекурсивно перечислимо;
\item для некоторого $m$ существуют такие примитивно рекурсивные функции
$f_1(t_1,...\,,t_m),...\,,f_n(t_1,...\,,t_m)$, что $M$ состоит из
всех точек вида $(f_1(t_1,...\,,t_m),...\,,f_n(t_1,...\,,t_m))$,
где $t_1,...\,,t_m$ независимо пробегают $\Bbb N_0$;
\item существуют примитивно рекурсивные функции
$f_1(t),\dots,f_n(t)$, такие что $M$ состоит из всех точек
$(f_1(t),...\,,f_n(t))$, $t\in \Bbb N_0$;
\item существует примитивно рекурсивная функция $h(a_1,...\,,a_n,x)$, такая
что уравнение $h(a_1,...\,,a_n,x)=0$  (относительно неизвестной
$x$) имеет решение тогда и только тогда, когда $(a_1,...\,,a_n)\in
M$;
\item для некоторого $m$ существует такая примитивно рекурсивная
функция $h(a_1,...\,,a_n,x_1,...\,,x_m)$ от $n+m$ переменных, что
уравнение $$h(a_1,...\,,a_n,x_1,...\,,x_n)=0$$  (относительно
неизвестных $x_1,...\,,x_n$) имеет решение тогда и только тогда,
когда $(a_1,...\,,a_n)\in M$.
\endroster
\endproclaim
\demo{Доказательство}Повторяя доказательство теоремы 5.1, мы
получим равносильность условий \therosteritem2-\therosteritem5;
остается установить равносильность \therosteritem1 и
\therosteritem3.

\therosteritem1$\Rightarrow$\therosteritem3. Если $M\subseteq \Bbb
N_0^n$ -- рекурсивно перечислимое множество, то, по определению,
множество $M_0=\{d^{(n)}(a_1,\dots,a_n)\,|\,(a_1,\dots,a_n)\in
M\}$ является рекурсивно перечислимым подмножеством $\Bbb N_0 $ и
потому совпадает с множеством значений некоторой примитивно
рекурсивной функции $f(t)$. Координатные функции
$c_1^{(n)},...\,,c_n^{(n)}$ осуществляют отображение $\Bbb N_0 \to
\Bbb N_0 ^n$, обратное к $d^{(n)}$;  поэтому $M$ -- это множество
точек $(f_1(t),...\,,f_n(t))$, где через $f_i(t)$ обозначены
примитивно рекурсивные функции $c_i^{(n)}(f(t))$ $(1\le i\le n)$.

\therosteritem3$\Rightarrow$\therosteritem1.Пусть  $M$ --
множество точек $(f_1(t),...\,,f_n(t))$, где $t$ пробегает $\Bbb
N_0$, а $f_1(t),...\,,f_n(t)$ -- примитивно рекурсивные функции.
Тогда множество
$M_0=\{d^{(n)}(a_1,\dots,a_n)\,|\,(a_1,\dots,a_n)\in M\}$
представляет собой множество значений примитивно рекурсивной
функции $d^{(n)}(f_1(t),...\,,f_n(t))$ и потому является
рекурсивно перечислимым подмножеством $\Bbb N_0 $. Но это и
означает, что множество $M\subseteq\Bbb N_0 ^n$ рекурсивно
перечислимо.

\enddemo
\subhead 7.3. Свойства рекурсивно перечислимых множеств
\endsubhead
Покажем, что объединение и пересечение конечного числа рекурсивно
перечислимых множеств рекурсивно перечислимы. Действительно, пусть
$f_i(a_1,...\,a_n,x)$ $(1\le i\le k)$ -- такие примитивно
рекурсивные функции, что уравнение относительно $x$
$$f_i(a_1,...\,,a_n,x)=0$$ тогда и только тогда имеет решение,
когда $(a_1,...\,,a_n)\in M_i$. Функции $$\gathered
f(a_1,...\,,a_n,x_1,...\,,x_k)=\sum_{i=1}^k
f_i(a_1,...\,,a_n,x_i)\,,\\
g(a_1,...\,,a_n,x_1,...\,,x_k)=\prod_{i=1}^k
f_i(a_1,...\,,a_n,x_i)
\endgathered$$
примитивно рекурсивны, и уравнения
$$f(a_1,...\,,a_n,x_1,...\,,x_k)=0,\quad
g(a_1,...\,,a_n,x_1,...\,,x_k)=0 $$ разрешимы относительно
$x_1,...\,,x_k$ тогда и только тогда, когда $(a_1,...\,,a_n)$
принадлежит соответственно пересечению и объединению множеств
$M_1,...,$ $M_k$.
%\subhead 5.4. Примитивно рекурсивные отображения
%\endsubhead
%Пусть $\phi $ - некоторое отображение из $\Bbb N_0^n$ в $\Bbb
%N_0^m$. Для его задания достаточно указать координатные функции
%$\phi _{i}$, определяемые равенством $$\phi (x_1,...\,,x_n)=(\phi
%_1(x_1,...\,,x_n),...\,,\phi _m(x_1,...\,,x_n))\,.$$ Отображение
%$\phi $ называется примитивно рекурсивным, если все функции $\phi
%_i$ примитивно рекурсивны.
%\proclaim{Теорема}Пусть $\phi :\Bbb N_0^n\to\Bbb N_0^m$ --
%примитивно рекурсивное отображение. Тогда
%\roster
%\item если $M$ -- рекурсивно перечислимое подмножество $\Bbb N_0^n$, то
% $\phi (M)$ -- рекурсивно перечислимое подмножество $\Bbb N_0^m$;
%\item  если $M_1$ -- рекурсивно перечислимое подмножество $\Bbb N_0^m$, то
%его полный прообраз $M=\phi^{-1} (M)$ (т.е. множество всех элементов из
%$\Bbb N_0^n$, образ которых при действии $\phi $ принадлежит $M_1$) --
%рекурсивно перечислимое подмножество $\Bbb N_0^n$.
%\endroster
%\endproclaim
%\demo{Доказательство}\therosteritem1. Поскольку $M$ -- рекурсивно перечислимое
%множество, существуют примитивно рекурсивные функции $f_1(t),...\,,f_n(t)$,
%такие что $M=\{(f_1(t),...\,,f_n(t))\,|t\in \Bbb N_0\}$. Но тогда
%$$M_1=\phi (M)=\{(g_1(t),...\,,g_n(t))\,|t\in \Bbb N_0\}\,,$$
%где $g_i(t)=\phi _i(f_1(t),...\,,f_n(t))$ -- функции, получающиеся из
%примитивно рекурсивных функций $\phi _i$ подстановкой в них вместо аргументов
%примитивно рекурсивных функций $f_i$, т.е. тоже примитивно рекурсивные
%функции. По теореме 5.2 множество $M_1$ рекурсивно перечислимо.
%\therosteritem2. По теореме 5.2 существует такая примитивно рекурсивная
%функция $g(x_1,...\,,x_m,t)$, что уравнение $g(a_1,...\,,a_m,t)=0$ имеет
%решение тогда и только тогда, когда $(a_1,...\,,a_m)\in M_1$. Функция
%$$h(y_1,...\,,y_n,t)=g(\phi_1(y_1,...\,,y_n,t),...\,,\phi_m(y_1,...\,,y_n,t))$$
%примитивно рекурсивна и уравнение $h(b_1,...\,,b_n,t)=0$ имеет решение тогда
%и только тогда, когда $\phi (b_1,...\,,b_n)\in M_1$, т.е. $(b_1,...\,,b_n
%)\in M$; по теореме 5.2 это означает, что $M$ -- рекурсивно перечислимое
%множество.
%\enddemo
%\subhead 5.5. Объединение рекурсивной последовательности рекурсивно
%перечислимых множеств
%\endsubhead
%Пусть $\phi _1(x_1,...\,,x_n,i),...\,,\phi _n(x_1,...\,,x_n,i)$ -- примитивно
%рекурсивные функции; тогда для каждого $i$ отображение $\Phi _i$,
%определенное формулой
%$$\Phi _i(x_1,...\,,x_n)=(\phi _1(x_1,...\,,x_n,i),...\,,
%\phi _n(x_1,...\,,x_n,i))\,,$$
%является примитивно рекурсивным отображением $\Bbb N_0^n$ в себя.
%\proclaim{Теорема}Пусть $M_0$ -- рекурсивно перечислимое подмножество
%$\Bbb N_0^n$, и пусть $M_{i+1}=\Phi _i(M_i)$ для любого $i\in \Bbb N_0$.
%Тогда объединение всех множеств $M_i$ тоже рекурсивно перечислимо.
%\endproclaim
\head 8. Рекурсивные функции
\endhead
\subhead 8.1. Определение рекурсивных функций
\endsubhead
В свойствах примитивно рекурсивных функций, приведенных в
предыдущей главе, отсутствовало упоминание обратных функций. И это
не случайно: обратная к примитивно рекурсивной функции, даже если
она существует, не обязана быть примитивно рекурсивной.



При нашем подходе к определению рекурсивной функции мы будем
пользоваться понятием графика функции. Пусть $f(x_1,...\,,x_n)$ --
некоторая функция; её графиком называется множество точек
$(x_1,...\,,x_n,f(x_1,...\,,x_n))\in \Bbb N_0^{n+1}$, где
$x_1,...\,,x_n$ независимо пробегают множество натуральных чисел
$\Bbb N_0$. Функция $f(x_1,...\,,x_n)$ называется рекурсивной (в
другой терминологии общерекурсивной), если её график рекурсивно
перечислим. Отметим простейшие свойства рекурсивных функций.
Всякая примитивно рекурсивная функция рекурсивна. Действительно,
если $f(x_1,...\,,x_n)$ -- примитивно рекурсивная функция, то её
график -- множество всех точек $(x_1,...\,,x_n,f(x_1,...\,,x_n))$;
но все координаты $x_1,...\,,x_n,f(x_1,...\,,x_n)$ -- примитивно
рекурсивные функции от $x_1,...\,,x_n$, и по теореме 5.2 это
множество рекурсивно перечислимо. Пусть $f(x_1,\dots,x_n)$ --
рекурсивная функция; поскольку её график рекурсивно перечислим,
существуют такие примитивно рекурсивные функции $g_1(t)$,\dots,
$g_n(t)$, $g(t)$, что этот график состоит из точек
$(g_1(t),\dots,g_n(t),g(t))$. Поскольку $x_1,...\,,x_n$ независимо
друг от друга пробегают $\Bbb N_0$ и определяют значение функции
$f$, функции $g_1(t),...\,,g_n(t),g(t)$ обладают свойствами:
\roster
\item для любых чисел $x_1,...\,,x_n\in \Bbb N_0$ найдется число
$t\in\Bbb N_0$, для которого $g_1(t)=x_1,...\,,g_n(t)=x_n$;
\item если  $g_1(t)=g_1(t'),...\,,g_n(t)=g_n(t')$, то $g(t)=g(t')$;
\item $f(g_1(t),...\,,g_n(t))=g(t)$ для любого $t\in \Bbb N_0$.
\endroster
Предшествующее представление рекурсивной функции будем называть её
примитивно рекурсивной параметризацией. Из существования
параметризации сразу следует, что всякая рекурсивная функция может
быть получена из примитивно рекурсивных при помощи подстановки и
единственный раз примененной операции минимизации (см. 6.8).
Действительно, для указанной параметризации
$$f(x_1,...\,,x_n)=g(\mu _t(|g_1(t)-x_1|+...+|g_n(t)-x_n|))\,.$$
Отметим, что по свойству \therosteritem1 уравнение
$|g_1(t)-x_1|+...+|g_n(t)-x_n|=0$ всегда имеет решение $t$, так
что функция $\mu _t(|g_1(t)-x_1|+...+|g_n(t)-x_n|)$ имеет смысл.

\subhead 8.2. Подстановка для рекурсивных функций
\endsubhead
\proclaim{Теорема}Пусть $f(x_1,...\,,x_n)$, $g_1(y_1,...\,,y_m)$,
... ,\,$g_n(y_1,...\,,y_m)$ -- рекурсивные функции. Тогда функция
$h(y_1,...\,,y_m)$, получающаяся из $f$ подстановкой вместо
неизвестных функций $g_1,...\,,g_n$ (так что
$h=t[f,g_1,...\,,g_n]$), тоже рекурсивна.
\endproclaim
\demo{Доказательство}Пусть $$\gathered \Delta
=\{(p_1(t),...\,p_n(t),p(t))\,\,|t\in\Bbb N_0\}\,,\\ \Sigma
_i=\{(q_{i1}(s_i),...\,q_{im}(s_i),q_i(s_i))\,\,|s_i\in\Bbb N_0\}
\endgathered$$
-- графики функций $f$, $g_i$ $(1\le i\le n)$ c примитивно
рекурсивными компонентами $p_i,\,q_{ij},\,p,\,q_i$. Для того,
чтобы точка $(a_1,...\,,a_m,a)$ принадлежала графику $\Lambda $
функции $h$, необходимо и достаточно, чтобы существовали такие
$t,s_1,...\,,s_n$ и $x_1,...\,,x_n$, что
$$q_{i1}(s_i)=a_1,...\,,q_{im}(s_i)=a_m,\,\,q_i(s_i))=x_i\quad
(1\le i\le n)$$ (эти равенства означают, что
$g_i(a_1,...\,,a_m)=x_i$),
$$p_1(t)=x_1,...\,,p_n(t)=x_n,\,\,p(t)=b$$ (это значит, что
$f(x_1,...\,,x_n)=b$). Но эта система равенств равносильна одному
уравнению $$|p(t)-b|+\sum_{i=1}^n(|q_i(s_i)-x_i|+|p_i(t)-x_i|)+
\sum_{j=1}^m|q_{ij}(s_i)-a_j|)=0\,,$$ левая часть которого --
примитивно рекурсивная функция от $a_1,...,a_m,b, t$,
$s_1,...,s_n,x_1,...,x_n$. Таким образом, $(a_1,...\,,a_m,b)\in
\Lambda $ тогда и только тогда, когда наше уравнение разрешимо
относительно $t,s_1,...\,,s_n,x_1,...\,,x_n$. По теореме 5.2 это
означает, что график $\Lambda $ функции $h$ рекурсивно перечислим,
т.е. сама функция $h(y_1,...\,,y_m)$ рекурсивна.
\enddemo
\subhead 8.3. Минимизация для рекурсивных функций
\endsubhead
\proclaim{Теорема}Пусть $f(x_1,...\,,x_n,t)$ -- такая рекурсивная
функция, что для любых $x_1,...\,,x_n\in \Bbb N_0$ существует
решение $t$ уравнения $f(x_1,...\,,x_n,t)=0$. Тогда функция $(\mu
_tf)(x_1,...\,,x_n)$ также рекурсивна.
\endproclaim
\demo{Доказательство}Пусть $$\Delta
=\{(p_1(s),...\,p_n(s),p(s),q(s))\,\,|s\in\Bbb N_0\}$$ -- график
функции $f$ c примитивно рекурсивными компонентами $p_i,p,q$. Для
того, чтобы точка $(x_1,...\,,x_n,a)$ принадлежала графику
$\Lambda $ функции $\mu _tf$, необходимо и достаточно, чтобы
$$f(x_1,...\,,x_n,0)\ne 0,...\,,f(x_1,...\,,x_n,a\ominus 1)\ne
0,\,\, f(x_1,...\,,x_n,a)= 0\,.$$ Для этого необходимо, чтобы для
$i=0,1,...\,,a$ существовали значения параметра $s_i$, для которых
$$\gathered p_1(s_i)=x_1,...\,,p_n(s_i)=x_n,\,\,p(s_i)=i\,,\\
q(s_i)\ne 0, \text{ если }i<a,\quad q(s_a)=0\,.
\endgathered$$
К сожалению, количество неизвестных $s_i$ зависит от $a$; чтобы
устранить это неудобство, используем функцию Гёделя $\Gamma
(s,i)$. Согласно определению этой примитивно рекурсивной функции
существует число $s\in \Bbb N_0$, такое что $\Gamma (s,0)=s_0,\,\,
\Gamma (s,1)=s_1,..\,,\Gamma (s,a)=s_a$. Подставляя эти выражения
в предыдущие равенства, преобразуем их к системе уравнений
$$\gathered p_1(\Gamma (s,i))=x_1,...\,,p_n(\Gamma
(s,i))=x_n,\,\,p(\Gamma (s,i))=i\,,\\ \overline{\sg}(q(\Gamma
(s,i)))= 0, \text{ если }i<a,\quad \sg(q(\Gamma (s,a)))=0\,,
\endgathered $$
которая равносильна одному уравнению $$\sg(q(\Gamma
(s,a)))+\sum_{i=0}^{a\ominus 1}\overline{\sg}(q(\Gamma (s,i)))
+\sum_{i=0}^a (|p(\Gamma (s,i))-i|+\sum_{j=1}^n |p_j(\Gamma
(s,i))-x_j|)=0\,,$$ левая часть которого -- примитивно рекурсивная
функция от $a,s,x_1,...\,,x_n$. Таким образом, $(x_1,...\,,x_n,a)$
принадлежит графику $\Lambda $ функции $\mu _tf$ тогда и только
тогда, когда наше уравнение разрешимо относительно $s$. По теореме
5.2 это означает, что график $\Lambda $ рекурсивно перечислим,
т.е. сама функция $(\mu _tf)(x_1,...\,,x_n)$ рекурсивна.
\enddemo
\subhead 8.4. Примитивная рекурсия для рекурсивных функций
\endsubhead
\proclaim{Теорема}Пусть $h(x_1,...\,,x_{n-1})$,
$g(x_1,...\,,x_{n-1},x_n,x_{n+1})$ -- рекурсивные функции. Тогда
функция $f(x_1,...\,,x_n)$, полученная из них примитивной
рекурсией, также рекурсивна.
\endproclaim
\demo{Доказательство}Пусть $$\gathered \Delta
=\{(p_1(s),...\,p_{n-1}(s),p(s))\,\,|s\in\Bbb N_0\}\,,\\ \Sigma
=\{(q_1(t),...\,q_{n-1}(t),q_n(t),q_{n+1}(t),q(t))\,\,|t\in\Bbb
N_0\}
\endgathered$$
-- графики функций $h,\,\,g$ c примитивно рекурсивными
компонентами $p_i,\,q_j$, $p,\,q$. Точки $$\align
(x_1,...\,,&x_{n-1},0,y_0),\\ (x_1,...\,,&x_{n-1},1,y_1),\\
       &\hdots         \\
(x_1,...\,,&x_{n-1},a,y_a)
\endalign $$
принадлежат графику $\Lambda $ функции $f$ тогда и только тогда,
когда $$\align y_0&=h(x_1,...\,,x_{n-1}),\\
y_1&=g(x_1,...\,,x_{n-1},0,y_0),\\
y_2&=g(x_1,...\,,x_{n-1},1,y_1),\\ &\hdots\\
y_a&=g(x_1,...\,,x_{n-1},a\ominus 1,y_{a\ominus 1})\,,
\endalign $$
т.е. точка $(x_1,...\,,x_{n-1},,y_0)$ принадлежит $\Delta $, а
точки $(x_1,...\,,x_{n-1},i,y_i,y_{i+1})$ $(0\le i<a)$ принадлежат
$\Sigma $. Для этого необходимо и достаточно существование таких
$s_0,\,s_1,...\,,s_a$, что $$\gathered
p_1(s_0)=x_1,...\,,p_{n-1}(s_0)=x_{n-1},\,p(s_0)=y_0,\\
q_1(s_i)=x_1,...\,,q_{n-1}(s_i)=x_{n-1},\,q_n(s_i)=i\ominus 1,\,,
q_{n+1}(s_i)=y_{i\ominus 1}\,,
 q(s_i)=y_i
\endgathered$$
$(1\le i\le a)$. Исключая из этой системы равенств величины
$y_0,y_1,...\,y_{a-1}$ и обозначая $y_a$ через $b$, находим, что
для того, чтобы точка $(x_1,...\,,x_{n-1},a,b)$ принадлежала
графику $\Lambda $ функции $f$, необходимо и достаточно, чтобы
существовали $s_0,\,s_1,...\,,s_a\in \Bbb N_0$, такие что
$$\gathered
p_1(s_0)=x_1,...\,,p_{n-1}(s_0)=x_{n-1},\,p(s_0)=q_{n+1}(s_1),\\
q_1(s_i)=x_1,...\,,q_{n-1}(s_i)=x_{n-1},\,q_n(s_i)=i\ominus 1
\quad(1\le i\le a)\,,\\
 q(s_i)=q_{n+1}(s_{i+1})\quad(1\le i<a)\,,\quad q(s_a)=b\,.
\endgathered$$
Заменяя, как и выше, неизвестные $s_i$ на $\Gamma (s,i)$,
преобразуем эти равенства к системе уравнений $$\gathered
p_1(\Gamma (s,0))=x_1,...\,,p_{n-1}(\Gamma (s,0))=x_{n-1},\,
p(\Gamma (s,0))=q_{n+1}(\Gamma (s,1)),\\ q_1(\Gamma
(s,i))=x_1,...\,,q_{n-1}(\Gamma (s,i))=x_{n-1},\, q_n(\Gamma
(s,i))=i\ominus 1 \quad(1\le i\le a)\,,\\
 q(\Gamma (s,i))=q_{n+1}(\Gamma (s,i+1))\quad(1\le i<a)\,,
\quad q(\Gamma (s,a))=b\,,
\endgathered$$
которая равносильна одному уравнению $$\gathered |p(\Gamma
(s,0))-q_{n+1}(\Gamma (s,1))|+ \sum_{i=1}^{a-1}|q(\Gamma
(s,i))-q_{n+1}(\Gamma (s,i+1))|+ |q(\Gamma (s,a))-b|+\\
\sum_{j=1}^{n-1}(|p_j(\Gamma (s,0))-x_j|+ \sum_{i=1}^a |q_j(\Gamma
(s,0))-x_j|) +\sum_{i=1}^a |q_n(\Gamma (s,i))-(i\ominus 1)|=0\,,
\endgathered$$
левая часть которого представляет собой примитивно рекурсивную
функцию от $a,b,s,x_1,...\,,x_{n-1}$. Таким образом,
$(x_1,...\,,x_{n-1},a,b)$ принадлежит графику $\Lambda $ функции
$f$ тогда и только тогда, когда наше уравнение разрешимо
относительно $s$. По теореме 5.2 это означает, что график $\Lambda
$ рекурсивно перечислим, т.е. сама функция $f(x_1,...\,,x_n)$
рекурсивна.
\enddemo
\subhead 8.5. Другое описание класса рекурсивных функций
\endsubhead
Соединяя результаты предыдущих пунктов, мы получаем следующую
характеризацию рекурсивных функций. \proclaim{Теорема}Класс
рекурсивных функций совпадает с классом функций, которые могут
быть получены из элементарных функций
$o,\,s,\,\id,\,\pr_1,\,\pr_2$ при помощи применения (вообще
говоря, многократного) операций подстановки, примитивной рекурсии
и минимизации.
\endproclaim
\demo{Доказательство}В конце пункта 6.1 было отмечено, что любая
рекурсивная функция получается минимизацией из примитивно
рекурсивной функции, которая, в свою очередь, может быть получена
из элементарных функция подстановками и примитивными рекурсиями.
Таким образом, класс рекурсивных функций содержится в классе
функций, которые могут быть получены из элементарных функций при
помощи подстановок, примитивных рекурсий и минимизаций. Обратно,
элементарные функции рекурсивны, и теоремы 6.2--6.4 показывают,
что подстановки, примитивные рекурсии и минимизации не выводят за
пределы класса рекурсивных функций, который, таким образом,
содержит класс функций, которые получаются из элементарных
подстановками, примитивными рекурсиями и минимизациями.
\enddemo
До сих пор у нас не было ни одного примера рекурсивных, но не
примитивно рекурсивных функций; в следующих пунктах мы докажем
существование таких функций.

\subhead 8.6. Рекурсия второй ступени
\endsubhead
Напомним, что координатные функции $c_1,c_2:\Bbb N_0\to\Bbb N_0$,
$d^{(2)}:\Bbb N_0 ^2\to\Bbb N_0 $ примитивно рекурсивны, и
отображение $x\rightsquigarrow (c_1(x),c_2(x))$,
$(x,y)\rightsquigarrow d^{(2)}(x,y)$ являются взаимно обратными
соответствиями между множеством $\Bbb N_0 $ и его декартовым
квадратом.

При вычислении значений функции, получающейся при помощи
примитивной рекурсии, мы должны знать значения этой функции для
меньших значений аргумента. Рассмотрим теперь функцию от двух
аргументов, определяемую следующим образом: $$\align f(0,0)&=a,\\
f(x,y)&=g(x,y,f(c_1(\varphi(x,y)),c_2(\varphi(x,y)))),
\endalign $$
где $a\in \Bbb N_0$, $g(x,y,z)$, $\varphi(x,y)$ --- примитивно
рекурсивные функции, причем $\varphi(x,y)<d^{(2)}(x,y)$. Нетрудно
видеть, что функция $f(x,y)$ корректно определена и примитивно
рекурсивна. Действительно, функция $h(z)$, определенная условиями
$$\align h(0)&=a,\\
h(z)&=g(c_1(z),c_2(z),h((\varphi(c_1(z),c_2(z))))),
\endalign $$
примитивно рекурсивна, а $f(x,y)=h(d^{(2)}(x,y))$. Предыдущее
построение по существу использует полное упорядочение декартова
квадрата множества $\Bbb N_0$, причем получившееся вполне
упорядоченное множество снова изоморфно $\Bbb N_0$. Однако,
декартов квадрат множества $\Bbb N_0$ допускает и другие полные
упорядочения, например, лексикографическое. Будем обозначать
лексикографический порядок на $\Bbb N_0^2$ символом $\preceq$:
$$(x,y)\preceq (z,t),\quad \text{если }x<z\text{ или }x=z,y\leq
t.$$ Лексикографический порядок позволяет определить новый способ
построения функций, который мы будем называть рекурсией второй
ступени. Пусть $\varphi(x,y,z)$, $\psi(x,y,z)$, $\alpha(x,y)$,
$\beta(x,y)$
--- такие примитивно рекурсивные функции, что $(\alpha(x,y),
\beta(x,y))\prec (x,y)$, $(\varphi(x,y,z),\psi(x,y,z))\prec (x,y)$
для любой пары $(x,y)\in\Bbb N_0^2$, $(x,y)\ne (0,0)$, и любого
 $z\in \Bbb N_0$. Пусть, далее, $a\in \Bbb N_0$ и $g(x,y,z,t)$ ---
примитивно рекурсивная функция, и пусть $f(x,y)$ --- такая
функция, что $$\align f(0,0)&=a,\\
f(x,y)&=g(x,y,f(u,v),f(\varphi(x,y,f(u,v)),\psi(x,y,f(u,v)))),
\endalign $$
где $u=\alpha(x,y)$, $v=\beta(x,y)$. Покажем, что функция $f(x,y)$
полностью определена этими свойствами. Точнее говоря, мы докажем
более точное утверждение. Назовем набор точек
$(x,y)=(x_0,y_0)\succ(x_1,y_1)\succ\dots\succ(x_m,y_m)=(0,0)$  и
чисел $z_0$,$z_1$,\dots,$z_m$ вычисляющим значение функции $f$ в
точке $(x,y)$, если для любого $i$, $0\le i<m$, существуют номера
$j,l>i$, для которых $\alpha(x_i,y_i)=x_j$, $\beta(x_i,y_i)=y_j$,
$\varphi(x_i,y_i,z_j)=x_l$, $\psi(x_i,y_i,z_j)= y_l$,
$g(x_i,y_i,z_j,z_l)=z_i$; обратной индукцией по $i$ находим, что
из этих условий следует, что $z_i=f(x_i,y_i)$; в частности,
значение функции $f(x,y)=f(x_0,y_0)$ равно $z_0$. Мы утверждаем,
что вычисляющие наборы есть для всех точек $(x,y)\in\Bbb N_0 ^2$,
и потому все значения функции $f(x,y)$ однозначно определены
наложенными условиями. Если бы это было не так, то, поскольку
множество $\Bbb N_0 ^{2}$ вполне упорядочено относительно
лексикографического порядка, нашлась бы наименьшая пара $(x,y)$,
для которой нет вычисляющего набора; ясно, что $(x,y)\ne (0,0)$.
Но пара $(u,v)=(\alpha(x,y),\beta(x,y))$ предшествует паре
$(x,y)$, поэтому для нее есть набор $M$ с нужными свойствами. В
частности, определено значение $f(u,v)$. По нашему предположению,
$(\varphi(x,y,f(u,v)), \psi(x,y,f(u,v))\prec(x,y)$, и потому для
пары $$(\varphi(x,y,f(u,v)),\psi(x,y,f(u,v)))$$ тоже есть
вычисляющий набор $N$. Но ясно, что объединение наборов $M_1$ и
$N$ после перенумерации, располагающей все точки объединения в
порядке возрастания, и добавления точки $(x,y)$ и числа
$$g(x,y,f(u,v),f(\varphi(x,y,f(u,v)),\psi(x,y,f(u,v))))$$
становится набором, вычисляющим значение функции $f$ в точке
$(x,y)$, а это противоречит предположению о том, что таких наборов
не существует. В описанной ситуации мы говорим, что функция
$f(x,y)$ получена рекурсией второй ступени при помощи функций
$g(x,y,z,t)$, $\varphi(x,y,z)$, $\psi(x,y,z)$, $\alpha(x,y)$,
$\beta(x,y)$ при начальном условии $f(0,0)=a$.
\proclaim{Теорема}Функция, полученная из примитивно рекурсивных
функций рекурсией второй ступени, рекурсивна.
\endproclaim
\demo{Доказательство}Пусть $\Delta\subseteq\Bbb N_0^3$ --- график
функции $f(x,y)$. Из предыдущих рассуждений видно, что точка
$(x,y,z)$ принадлежит графику $\Delta$ тогда и только тогда когда
существуют такие числа $m$, $x_i$, $y_i$, $z_i$ ($0\le i\le m$),
что $x=x_0$, $y=y_0$, $z=z_0$ и для каждого $i$, $0\le i\le m$,
существуют числа $j$,  $l$, $0\le j,k,l\le m$, для которых
$\alpha(x_i,y_i)=x_j$, $\beta(x_i,y_i)=y_j$,
$\varphi(x_i,y_i,z_j)=x_l$, $\psi(x_i,y_i,z_j)= y_l$,
$g(x_i,y_i,z_j,z_l)=z_i$. Эти условия равносильны одному равенству
$$\gathered |x-x_0|+|y-y_0|+ |z-z_0|+
\sum_{i=0}^m(\prod_{j,l=0}^m(|\alpha(x_i,y_i)-x_j|+
|\beta(x_i,y_i)-y_j|+\\|\varphi(x_i,y_i,z_j)-x_l|+
|\psi(x_i,y_i,z_j)-y_l|+|g(x_i,y_i,z_j,z_l)-z_i|))=0.\endgathered
$$ Заменяя, как и выше, переменные $x_i$, $y_i$, $z_i$ на
$\Gamma(s,i)$, $\Gamma(t,i)$, $\Gamma(u,i)$, преобразуем это
соотношение в равенство $$\gathered
|x-\Gamma(s,0)|+|y-\Gamma(t,0)|+ |z-\Gamma(u,0)|+\\
\sum_{i=0}^m(\prod_{j,l=0}^m(|\alpha(\Gamma(s,i),
\Gamma(t,i))-\Gamma(s,j)|+|\beta(\Gamma(s,i),\Gamma(t,i))-
\Gamma(t,j)|+\\|\varphi(\Gamma(s,i),\Gamma(t,i),\Gamma(u,j))-
\Gamma(s,l)|+|\psi(\Gamma(s,i),\Gamma(t,i),\Gamma(u,j))-
\Gamma(t,l)|+\\|g(\Gamma(s,i),\Gamma(t,i),\Gamma(u,j),\Gamma(u,l))
-\Gamma(u,i)|))=0.\endgathered $$
 Обозначим левую часть этого равенства через $h(x,y,z,m,s,t,u)$;
 ясно, что это примитивно рекурсивная функция. Таким образом,
 $(x,y,z)\in \Delta$ тогда и только тогда, когда уравнение
 $h(x,y,z,m,s,t,u)=0$ с примитивно рекурсивной левой частью
 разрешимо относительно $m$, $s$, $t$, $u$. Следовательно, график
 $\Delta$ функции $f(x,y)$ рекурсивно перечислим, и потому сама
 функция $f(x,y)$ рекурсивна.
\enddemo
\comment \proclaim{Лемма}Пусть $f(x)$ --- примитивно рекурсивная
функция, такая что $f(x)<x$ для любого $x\in \Bbb N_0$. Тогда
существует примитивно рекурсивная функция $g:\Bbb N_0 \!\to\!\Bbb
N_0$, такая что \roster
\item функция $g(x)$ биективна;
\item для всякого $x\in \Bbb N_0$ существует $y<x$, для которого
 $f(x)=g(y)$.
\endroster  \noindent
\endproclaim
\demo{Доказательство}
\enddemo
\endcomment

\head 9. Функция, универсальная для класса примитивно рекурсивных
функций \endhead

\subhead 9.1. Нумерация примитивно рекурсивных функций
\endsubhead
Напомним, что любую примитивно рекурсивную функцию можно
построить, исходя из элементарных функций $o(x)$, $s(x)$,
$\id(x)$, $\pr_1(x_1,x_2)$, $\pr_2(x_1,x_2)$ при помощи
подстановок и примитивных рекурсий. Процесс построения примитивно
рекурсивной функции может быть закодирован в некотором алфавите,
и, используя взаимно однозначное соответствие между словами в
алфавите и натуральными числами, мы можем сопоставить нашей
функции (точнее, процессу ее построения: одна и та же функция
может быть получена из элементарных многими способами) некоторое
натуральное число. Конечно, это можно сделать многими способами;
здесь мы изложим один из вариантов такого сопоставления.
Существенную роль в нашей конструкции играют примитивно
рекурсивные функции $d^{(k)}(x_1,\dots,x_k)$,
$c_1^{(k)}(x)$,\dots, $c_k^{(k)}(x)$ из \S 6.10, осуществляющие
взаимно обратные биекции $\Bbb N_0^k\to \Bbb N_0$, $\Bbb N_0\to
\Bbb N_0 ^k$. Напомним (см. \S 6.10), что
$$c^{(k)}_i(d^{(k)}(x_1,\dots,x_k))=x_i,\quad d^{(2)}(d^{(k-1)}
(x_1,\dots,x_{k-1}),x_k)=d^{(k)}(x_1,\dots,x_k).$$
 Пусть $n\in \Bbb N_0$; построим примитивно рекурсивную функцию
 $f_n(x)$ одной переменной. Сначала определим эту функцию для
 первых значений $n$:
 $$\alignat2 f_0(x)&=o(x)&&=0,\\f_1(x)&=s(x)&&=x+1.\endalignat$$
 Пусть теперь $n>1$ и примитивно рекурсивные функции $f_m(x)$ уже
 определены для всех $m<n$. Число $n$ однозначно раскладывается в
 произведение простых множителей: $n=2^{i_0}3^{i_1}\dots
 p_r^{i_r}$. Если $k=i_0\ge 1$, то положим
 $$f_n(x)=f_{i_1}(d^{(k)}(f_{i_2}(x),\dots, f_{i_{1+k}}(x))).$$
 Если $i_0=0$, но $i_1\ge 1$, т.е. $n=3^{i+1}5^j\dots p_r^{i_r}$
 ($a\ge 0$, $j\ge 0$, $r\ge 2$), то в качестве $f_n(x)$ возьмем
 функцию, получающуюся следующей примитивной рекурсией:
 $$\align f_n(d^{(2)}(x,0))&=f_i(x),\\f_n(d^{(2)}(x,y+1))&=
 f_j(d^{(2)}(d^{(2)}(x,y),f_nd^{(2)}(x,y))).\endalign$$
 Если $i_0=i_1=0$, $i_2=1,2,3$, то в качестве функции $f_n(x)$
 возьмем соответственно функции $\id(x)$, $c_1(x)$, $c_2(x)$.
 Во всех остальных случаях (т.е. при $i_0=i_1=0$ и $i_3=0$ или
 $i_3>3$) положим $f_n(x)=o(x)=0$.
\proclaim{Теорема}Для любой примитивно рекурсивной функции $g(x)$
найдется номер $n\in \Bbb N_0 $, такой что $g(x)=f_n(x)$ для всех
$x\in \Bbb N_0$.
\endproclaim
\demo{Доказательство}Наше определение примитивно рекурсивной
функции таково, что в нем участвуют функции от разного числа
переменных, и даже при построении примитивно рекурсивных функций
от одной переменной нам не обойтись без использования функций
нескольких переменных. Поэтому нам придется несколько усилить
доказываемое утверждение. Для любых натуральных чисел $k\ge 1$,
$n$ обозначим через $f_n^k$ следующую функцию $k$ переменных:
$$f_n^k(x_1,\dots,x_k)=f_n(d^{(k)}(x_1,\dots,x_k)).$$ Мы будем
доказывать следующее утверждение: \proclaim\nofrills{}Для любой
примитивно рекурсивной функции от $k$ переменных
$g(x_1,\dots,x_k)$ найдется номер $n\in \Bbb N_0 $, такой что
$g(x_1,\dots,x_k)=f_n^k(x_1,\dots,x_k)$ для всех $x_1,\dots,x_k\in
\Bbb N_0$.
\endproclaim
По определению, примитивно рекурсивная функция $g(x_1,\dots, x_k)$
является элементарной или получается из ранее построенных функций
подстановкой или примитивной рекурсией. Мы будем доказывать наше
утверждение индукцией по построению функции $g$. Убедимся сначала,
что оно верно для элементарных функций: $$\gathered
o(x)=f_0(x)=f^1_0(x), \quad
s(x)=f_1(x)=f^1_1(x),\quad\id(x)=f_5(x)=f_5^1(x),\\
\pr_1(x,y)=x=c_1(d^{(2)}(x,y))=f_{25}(d^{(2)}(x,y))=
f_{25}^{2}(x,y)),\\\pr_2(x,y)=y=c_2(d^{(2)}(x,y))=f_{125}(d^{(2)}
(x,y))=f_{125}^{2}(x,y)).\endgathered$$


Пусть теперь $g(x_1,\dots,x_k)=h(q_1(x_1,\dots,x_k),\dots,q_l
(x_1,\dots,x_k))$ и пусть уже найдены такие номера $j$,
$i_1$,\dots, $i_l$, что $$\align
h(y_1,\dots,y_l)&=f_j^l(y_1,\dots,y_l),\\
q_s(x_1,\dots,x_k)&=f_{i_s}^k(x_1,\dots,x_k)\endalign $$ для
$s=1,\dots,l$ и любых $x_1,\dots,x_k,y_1,\dots,y_l\in \Bbb N_0 $.
Для сокращения записи введем обозначения
$\overrightarrow{x}=(x_1,\dots,x_k)$, $z=d^{(k)}(x_1,\dots,x_k)$.
Для $n= 2^l3^{i_1}\dots p_{l+1}^{i_{l+1}}$ находим, что
$$\gathered g(x_1,\dots,x_k)=h(q_1(\overrightarrow{x}),\dots,q_l
(\overrightarrow{x}))=\\f_j^l(f_{i_1}^k(\overrightarrow{x}),\dots,
f_{i_l}^k(\overrightarrow{x}))=f_j(d^{(l)}(f_{i_1}^k
(\overrightarrow{x}),\dots,f_{i_l}^k(\overrightarrow{x})))
\\=f_j(d^{(l)}(f_{i_1}(z),\dots,f_{i_l}(z)))=f_n(z)=f_n^k(x_1,
\dots,x_k).
\endgathered$$
Пусть, наконец, функция $g(x_1,\dots,x_k)$ получена примитивной
рекурсией
 $$\align g(x_1,\dots,x_{k-1},0)&=h(x_1,\dots,x_{k-1}),\\
g(x_1,\dots,x_{k-1},x_k+1)&=q(x_1,\dots,x_{k-1},x_k,g(x_1,
\dots,x_{k-1},x_k)),\endalign $$ и пусть уже найдены такие номера
$i$, $j$, что $h(x_1,\dots,x_{k-1})=f_i^{k-1}(x_1,\dots,x_{k-1})$,
$q(x_1,\dots,x_{k-1},x_k,y)=f_j^{k+1}(x_1,\dots,x_{k-1},x_k,y)$.
Положим $n=3^{i+1}5^j$; тогда $$\align
f_n^k(x_1,\dots,&x_{k-1},0)=f_n(d^{(k)}(x_1,\dots,x_{k-1},0))=
f_n(d^{(2)}(d^{(k-1)}(x_1,\dots,x_{k-1}),0))\\
&=f_i(d^{(k-1)}(x_1,\dots,x_{k-1}))=f_i^{k-1}(x_1,\dots,x_{k-1})=
h(x_1,\dots,x_{k-1}).
\endalign $$
Далее, обозначая для краткости $t=d^{(k-1)}(x_1,\dots,x_{k-1})$ и
пользуясь тем, что
$d^{(k)}(x_1,\dots,x_{k-1},y)=d^{(2)}(d^{(k-1)}(x_1,\dots,x_{k-1})
,y)=d^{(2)}(t,y)$, находим: $$\align
f_n^k(x_1,\dots,&x_k+1)=f_n(d^{(k)}(x_1,\dots,x_k+1))=
f_n(d^{(2)}(t,x_k+1))\\ &= f_j(d^{(2)}(d^{(2)}(t,x_k),f_n(d^{(2)}
(t,x_k))))\\&=
f_j(d^{(2)}(d^{(k)}(x_1,\dots,x_{k-1},x_k),f_n(d^{(k)}
(x_1,\dots,x_{k-1},x_k))))
\\ &=f_j(d^{(k+1)}(x_1,\dots,x_k,f_n^k(x_1,\dots,x_k)))\\&
=f_j^{k+1}(x_1,\dots,x_k,f_n^k(x_1,\dots,x_k))=q(x_1,\dots,x_k,
f_n^k(x_1,\dots,x_k)).
\endalign $$
Таким образом, функция $f_n^k(x_1,\dots,x_{k-1},x_k)$ получена той
же примитивной рекурсией, что и функция
$g(x_1,\dots,x_{k-1},x_k)$, и потому эти две функции совпадают.
Теорема полностью доказана.
\enddemo
\subhead 9.2. Универсальная функция для класса примитивно
рекурсивных функций
\endsubhead
Рассмотрим теперь функцию двух аргументов $U(x,y)$, определенную
равенством $U(x,y)=f_x(y)$. Как следует из предыдущей теоремы, для
каждой примитивно рекурсивной функции одной переменной $g(x)$
существует число $n\in\Bbb N_0 $, такое что $g(x)=U(n,x)$ для
любого $x\in\Bbb N_0 $. Таким образом, все примитивно рекурсивные
функции легко получаются из одной функции двух переменных
$U(x,y)$, и потому естественно называть функцию $U(x,y)$
универсальной для класса примитивно рекурсивных функций.
\proclaim{Теорема}Функция $U(x,y)$ рекурсивна.
\endproclaim
\demo{Доказательство}Из рассуждений предыдущего пункта видно, что
построение функции $U(x,y)$ очень похоже на рекурсию второй
ступени; однако, если при нашем определении рекурсии второй
ступени для вычисления значения функции в точке $(x,y)$
требовалось знать ее значение только в двух точках, то для
вычисления значения $U(x,y)=f_x(y)$ в некоторых случаях (например,
при подстановке) требуется знать значения функции $U$ в нескольких
точках, предшествующих $(x,y)$, причем количество этих точек
зависит от $(x,y)$. Мы обойдем эту трудность, заменив функцию
$U(x,y)$ тесно связанной с ней функцией
$V(x,y)=\prod\limits_{i=0}^xp_i^{U(i,y)}$. Докажем, что функция
$V(x,y)$ может быть построена рекурсией второй ступени и поэтому
она рекурсивна; утверждение теоремы немедленно следует отсюда, так
как функция $U(x,y)=\exp(x,V(x,y))$ получается подстановкой в
примитивно рекурсивную функцию $\exp(x,z)$ на место второго
аргумента рекурсивной функции $V(x,y)$. В процессе доказательства
нам будет удобно использовать две вспомогательные примитивно
рекурсивные функции. \proclaim{Лемма}{\bf 1.} Функция

$\phantom{ttttttt}w(k,x,z)=d^{(k+1)}(\exp
(\exp(2,x)),z),\dots,\exp(\exp(k+2,x),z)$

\noindent примитивно рекурсивна как функция от $k$, $x$, $z$.

{\bf 2.} Функция $q(y)=d^{(2)}(c_1(y),c_2(y)\ominus\!1)$
примитивно рекурсивна. Если $c_2(y)>0$, то $q(y)<y$.
\endproclaim
\demo{Доказательство}{\bf 1.} Эта функция получается примитивной
рекурсией
 $$\align
w(0,x,z)&=\exp(\exp(2,x),z),\\
w(k+1,x,z)&=d^{(k+2)}(\exp(\exp(2,x),z),\dots,
\exp(\exp(k+3,x),z))\\&=d^{(2)}(d^{(k+1)}(\exp(\exp(2,x),z),\dots,
\exp(\exp(k+3,x),z)))\\&=d^{(2)}(w(k,x,z),
\exp(\exp(k+3,x),z)).\endalign$$ {\bf 2.} То, что функция $q(y)$
примитивно рекурсивна, очевидно. Если $c_2(y)>0$, то
$c_1(y)+(c_2(y)\ominus \!1)<c_1(y)+ c_2(y)$. Напомним, что
определенные в \S 6.10 координатные функции нумеруют пары
натуральных чисел так, что пара с меньшей суммой координат всегда
предшествует паре с большей суммой координат; поэтому номер
$q(y)=d^{(2)}(c_1(y),c_2(y)\ominus\!1)$ пары
$(c_1(y),c_2(y)\ominus\!1)$ строго меньше номера
$y=d^{(2)}(c_1(y),c_2(y))$ пары $(c_1(y),c_2(y))$.
\enddemo
Вернемся к доказательству того, что функция $V(x,y)$ строится
рекурсией второй ступени. Для этого надо построить примитивно
рекурсивные функции $\alpha(x,y)$, $\beta(x,y)$, $\varphi(x,y,z)$,
$\psi(x,y,z)$, $g(x,y,z,t)$, связанные с функцией $V(x,y)$ как в
\S 8.6: $$(\alpha(x,y),\beta(x,y))\prec (x,y),\quad
(\varphi(x,y,z),\psi(x,y,z))\prec (x,y)$$ для любой пары
$(x,y)\in\Bbb N_0^2$, $(x,y)\ne (0,0)$, и любого
 $z\in \Bbb N_0$,
 $$V(x,y)=g(x,y,V(u,v),V(\varphi(x,y,V(u,v)),\psi(x,y,V(u,v)))),$$
где $u=\alpha(x,y)$, $v=\beta(x,y)$. Мы зададим эти функции
кусочно, разбив всю область задания на несколько областей.
\enddemo
\subsubhead Случай 1: $x=0$\endsubsubhead
 Ясно, что $V(0,y)=2^{U(0,y)}= 2^{f_0(y)}=2^0=1$, и можно
 положить $\alpha(0,y)=\beta(0,y)=\varphi(0,y,z)=\psi(0,y,z)=0$,
$ g(0,y,z,t)=1$. \demo\nofrills{}\indent Пусть теперь $x\ge 1$; во
всех оставшихся случаях $\alpha(x,y)=x\ominus\!1$, $\beta(x,y)=y$.
Заметим, что при $x\ge 1$ справедливо соотношение
$$V(x,y)=V(x\ominus\!1,y)p_x^{U(x,y)}=V(\alpha(x,y),\beta(x,y))
p_x^{f_x(y)},$$ и потому достаточно указать такие функции
$\varphi(x,y,z)$, $\psi(x,y,z)$, $h(x,y,z,t)$, что
$$f_x(y)=h(x,y,V(x\ominus\!1,y),V(\varphi(x,y,V(x\ominus\!1,y)),
\psi(x,y,V(x\ominus\!1,y)))).\tag{$\ast$}$$
\enddemo
\subsubhead Случай 2: $\exp(0,x)>0$\endsubsubhead Тогда $x=2^{k+1}
3^{i_1}5^{i_2}\dots $, где $k=\exp(0,x)-1$, $i_s=\exp(s,x)$, и
 $$\gathered f_x(y)= f_{i_1}(d^{(k+1)}
(f_{i_2}(y),\dots,f_{i_{k+2}}(y))=f_{i_1}(d^{(k+1)}(\exp(i_2,z),
\dots,\exp(i_{k+2},z))=
\\f_{i_1}(w(k,x,z))=\exp(\exp(1,x),V(x\ominus\!1,
w(\exp(0,x)\ominus\! 1,x,V(x\ominus\!1,y)))),
\endgathered$$
где через $z$ обозначено выражение $V(x\ominus\!1,y)$. Эта формула
получается из $(\ast)$, если положить $\varphi(x,y,z)=x$,
$\psi(x,y,z)=w(\exp(0,x)\ominus\!1,x,z)$,
$h(x,y,z,t)=\exp(\exp(1,x),t)$. \subsubhead Случай 3:
$\exp(0,x)=0$, $\exp(1,x)>0$, $c_2(y)=0$\endsubsubhead В этом и
следующем случаях $x=3^{i+1} 5^j\dots $, где $i=\exp(1,x)-1$,
$j=\exp(2,x)$. Мы имеем:
$$f_x(y)=f_x(d^{(2)}(c_1(y),0))=f_i(c_1(y))=\exp(\exp(1,x)\ominus\!
1,V(x\ominus\!1,c_1(y))),$$ что получается из $(\ast)$ при
$\varphi(x,y,z)=x\ominus\!1$, $\psi(x,y,z)=c_1(y)$,
$h(x,y,z,t)=\exp(\exp(1,x)\ominus\!1,t)$. \subsubhead Случай 4:
$\exp(0,x)=0$, $\exp(1,x)>0$, $c_2(y)>0$\endsubsubhead Тогда
$f_x(y)=$ $$\gathered \vspace{-5pt}
f_x(d^{(2)}(c_1(y),c_2(y)))=f_j(d^{(2)}(d^{(2)}(c_1(y),
c_2(y)\ominus 1),f_x(d^{(2)}(c_1(y),c_2(y)\ominus 1))
)=\\f_j(d^{(2)}(v(y),f_x(v(y))))=\exp(\exp(2,x),d^{(2)}(v(y),
\exp(x,V(x,v(y))))),\endgathered $$ что совпадает с формулой
$(\ast)$, если положить в ней $\varphi(x,y,z)=x$,
$\psi(x,y,z)=v(y)$,
$h(x,y,z,t)=\exp(\exp(2,x),d^{(2)}(v(y),\exp(x,t))$.

\subsubhead Случай 5: $\exp(0,x)=\exp(1,x)=0$\endsubsubhead В этом
случае функция $f_x(y)$ совпадает с одной из элементарных функций
от $y$: $$\alignat2 f_1(y)&=s(y),&&\\f_x(y)&=\id(y),\quad&&\text{
если }\exp(2,x)=1,\\f_x(y)&=с_1(y),&&\text{ если }
\exp(2,x)=2,\\f_x(y)&=с_2(y),&&\text{ если }\exp(2,x)=3,\\
f_x(y)&=o(y),&&\text{ если }\exp(2,x)\ne 1,2,3,\,\,x\ne 1.
\endalignat$$
Она на самом деле не зависит от $z$ и $t$, и потому в качестве
$\varphi(x,y,z)$, $\psi(x,y,z)$ можно взять любые функции
(например, $\varphi(x,y,z)=\psi(x,y,z)=0$), а в качестве
$h(x,y,z,t)$ --- соответственно функции $s(y)$, $\id(y)$,
$c_1(y)$, $c_2(y)$, $o(y)$.

\subhead 9.3. Пример рекурсивной, но не примитивно рекурсивной
функции
\endsubhead
Рассмотрим функцию $g(x)=U(x,x)+1$. Поскольку функция $U(x,y)$
рекурсивна, функция $U(x,x)$, получающаяся из нее подстановкой,
тоже рекурсивна, а вместе с ней рекурсивна и функция
$g(x)=U(x,x)+1$. Но эта функция не примитивно рекурсивна: если бы
это было не так, то существовал бы номер $n$, такой что
$g(x)=f_n(x)=U(n,x)$, и мы имели бы $U(n,n)=g(n)=U(n,n)+1$.

\head 10. Рекурсивные множества\endhead

\subhead 10.1. Определение рекурсивного множества\endsubhead Пусть
$A$ --- подмножество $\Bbb N_0 $; напомним, что характеристической
функцией множества $A$ называется функция, определенная следующим
образом: $$\chi_A(x)=\cases 1,\,\,&\text{ если }x\in A,\\0,&\text{
если }x\notin A.\endcases$$ Подмножество $A$ множества $\Bbb N_0 $
называется рекурсивным (примитивно рекурсивным) множеством, если
функция $\chi_A(x)$ рекурсивна (примитивно рекурсивна).

Примитивно рекурсивные множества не играют сколько-нибудь важной
роли. Напротив, рекурсивные множества имеют принципиальное
значение: поскольку все значения рекурсивных функций и только
рекурсивных функций могут быть вычислены, рекурсивные множества
являются в точности теми множествами, для которых вопрос о
принадлежности элемента множеству может быть в принципе решен.
\subhead 10.2. Рекурсивные и рекурсивно перечислимые множества
\endsubhead
\proclaim{Теорема}Всякое примитивно рекурсивное множество
рекурсивно. Всякое рекурсивное множество рекурсивно перечислимо.
\endproclaim
\demo{Доказательство}Если множество $A$ примитивно рекурсивно, то
его характеристическая функция примитивно рекурсивна, а потому и
рекурсивна; значит, множество $A$ рекурсивно. Пусть теперь
множество $A$ рекурсивно. Тогда $A$ можно охарактеризовать как
множество точек $a\in \Bbb N_0 $, таких что $\chi(a)=1$; но это
множество совпадает с множеством тех $a\in \Bbb N_0 $, для которых
уравнение $|a-1|(x+1)=0$ имеет решение. Следовательно, множество
$A$ рекурсивно перечислимо.
\enddemo
Оказывается, все три класса множеств, участвующие в этой теореме,
различны. Довольно легко построить рекурсивное, но не примитивно
рекурсивное множество. Для этого опять воспользуемся универсальной
функцией $U(x,y)$. Функция $h(x)=\overline{\sg}(U(x,x))$
рекурсивна и принимает только два значения --- 0 и 1;
следовательно, она является характеристической функцией некоторого
множества $A$ (а именно, множества тех чисел $a\in \Bbb N_0 $, для
которых $h(a)=1$). Это множество $A$ рекурсивно. В то же время,
если бы функция $h(x)$ была примитивно рекурсивна, то существовал
бы номер $i\in \Bbb N_0 $, такой что $h(x)=U(i,x)$, и тогда мы бы
имели $\overline{\sg}(U(i,i))=h(i)=U(i,i)$, что невозможно.
Следовательно, функция $\chi_A(x)=h(x)$ не примитивно рекурсивна,
и потому множество $A$ не примитивно рекурсивно.

Пример рекурсивно перечислимого, но не рекурсивного множества,
несколько сложнее и будет предъявлен в конце этого параграфа.
\subhead 10.3. Свойства рекурсивных множеств\endsubhead
\proclaim{Теорема}Объединение и пересечение конечного числа
рекурсивных (примитивно рекурсивных) множеств рекурсивно
(примитивно рекурсивно). Дополнение рекурсивного (примитивно
рекурсивного) множества рекурсивно (примитивно рекурсивно).
\endproclaim
\demo{Доказательство} Пусть множества $A_1$,\dots,$A_n$ рекурсивны
(примитивно рекурсивны). Тогда функции $\chi_{A_1}(x)$,
\dots,$\chi_{A_n}(x)$ рекурсивны (примитивно рекурсивны). Но ясно,
что характеристическими функциями объединения и пересечения
множеств $A_1$,\dots,$A_n$ и дополнения множества $A_1$ являются
функции $\sg(\sum\limits_{i=1}^n\chi_{A_i}(x))$,
$\prod\limits_{i=1}^n\chi_{A_i}(x)$,
$\overline{\sg}(\chi_{A_1}(x))$, и эти функции тоже рекурсивны
(примитивно рекурсивны). А это и означает, что объединение и
пересечение множеств $A_1$,\dots,$A_n$ и дополнение множества
$A_1$ рекурсивны (примитивно рекурсивны).
\enddemo
Заметим, что дополнение рекурсивно перечислимого множества не
обязано быть рекурсивно перечислимым. Действительно, пусть
множество $A$ и его дополнение $B$ оба рекурсивно перечислимы.
Тогда существуют примитивно рекурсивные функции $f(x)$, $g(x)$,
множествами значений которых являются соответственно множества
$A$, $B$. Поскольку любое число $a\in \Bbb N_0 $ принадлежит в
точности одному из множеств $A$, $B$, в точности одно из уравнений
$|f(x)-a|=0$, $|g(x)-a|=0$ разрешимо, а значит, уравнение
$|f(x)-a||g(x)-a|=0$ разрешимо относительно $x$ всегда, и потому
определена функция $h(y)=\mu_x(|f(x)-y||g(x)-y|)$, и эта функция
рекурсивна. Ясно, что характеристической функцией множества $A$
будет рекурсивная функция $\overline{\sg}|f(h(y))-y|$, а это
означает, что множество $A$ рекурсивно. Но мы упомянули выше, что
бывают рекурсивно перечислимые, но не рекурсивные множества;
приведенное рассуждение показывает, что дополнение таких множеств
не может быть рекурсивно перечислимым.

\subhead 10.4. Замечание о рекурсивно перечислимых множествах
\endsubhead
\proclaim{Теорема}Пусть $M$ -- непустое подмножество $\Bbb N_0^n$;
следующие условия равносильны: \roster
\item $M$ рекурсивно перечислимо;
\item для некоторого натурального числа $m$ существуют такие рекурсивные функции
$f_1(t_1,...\,,t_m),...\,,f_n(t_1,...\,,t_m)$, что $M$ состоит из
всех точек вида $(f_1(t_1,...\,,t_m),...\,,f_n(t_1,...\,,t_m))$,
где $t_1,...\,,t_m$ независимо пробегают $\Bbb N_0$;
\item существуют рекурсивные функции
$f_1(t),\dots,f_n(t)$, такие что $M$ состоит из всех точек
$(f_1(t),...\,,f_n(t))$, $t\in \Bbb N_0$;
\item существует рекурсивная функция $h(a_1,...\,,a_n,x)$, такая
что уравнение $h(a_1,...\,,a_n,x)=0$  (относительно неизвестной
$x$) имеет решение тогда и только тогда, когда $(a_1,...\,,a_n)\in
M$;
\item для некоторого натурального числа $m$ существует такая
рекурсивная функция $h(a_1,...\,,a_n,x_1,...\,,x_m)$ от $n+m$
переменных, что уравнение $$h(a_1,...\,,a_n,x_1,...\,,x_n)=0$$
(относительно неизвестных $x_1,...\,,x_n$) имеет решение тогда и
только тогда, когда $(a_1,...\,,a_n)\in M$.
\endroster
\endproclaim
\remark{Замечание}Это утверждение отличается от теоремы из \S 7.2
только тем, что здесь вместо примитивно рекурсивных функций
фигурируют функции из более широкого класса --- рекурсивные
функции; оно показывает, что такая модификация определения не
приводит к появлению более широкого класса множеств, чем класс
рекурсивно перечислимых множеств.
\endremark
\demo{Доказательство}Повторяя доказательство теоремы 5.1, мы
получим равносильность условий \therosteritem2-\therosteritem5;
То, что из \therosteritem1 следует \therosteritem3, тривиально: по
теореме из \S 7.2 для рекурсивно перечислимого множества
существуют даже примитивно рекурсивные функции
$f_1(t),\dots,f_n(t)$, такие что $M$ состоит из всех точек
$(f_1(t),...\,,f_n(t))$, $t\in\Bbb N_0$.

Заметим, что если $f(x)$ --- рекурсивная функция и $g(t)$, $h(t)$
--- такие примитивно рекурсивные функции, что график функции
$f(x)$ состоит из всех точек вида $(g(t),h(t))$, то множество
значений функции $f(x)$ совпадает с множеством значений примитивно
рекурсивной функции $h(t)$ и потому является рекурсивно
перечислимым подмножеством множества $\Bbb N_0 $. Пусть теперь
$f_1(t),\dots,f_n(t)$ --- такие  рекурсивные функции, что
множество $M$ состоит из всех точек $(f_1(t),...\,,f_n(t))$, $t\in
\Bbb N_0$. Тогда множество
$$M_0=\{d^{(n)}(a_1,\dots,a_n)\,|\,(a_1,\dots,a_n)\in M\}\subseteq
\Bbb N_0 $$ является множеством значений рекурсивной функции
$d^{(n)}(f_1(t),\dots,f_n(t))$ и потому, как мы только что
заметили, является рекурсивно перечислимым подмножеством $\Bbb N_0
$. Но это в точности означает, что множество $M\subseteq \Bbb N_0
^n$ рекурсивно перечислимо. Таким образом, из \therosteritem3
следует \therosteritem1.
\enddemo
\subhead 10.5. Существование рекурсивно перечислимого, но не
рекурсивного множества\endsubhead \proclaim{Теорема} Пусть
$U(x,y)$ --- рекурсивная функция, универсальная для класса
примитивно рекурсивных функций, и пусть $M$ --- множество всех
$x\in\Bbb N_0 $, таких что уравнение $|U(c_1(x),t)-x|+
|U(c_2(x),t)|=0$ разрешимо относительно $t$. Множество $M$
рекурсивно перечислимо, но не рекурсивно.
\endproclaim
\demo{Доказательство} Функция $|U(c_1(x),t)-x|+ |U(c_2(x),t)|=0$
рекурсивна относительно $x$ и $t$; поэтому по теореме из
предыдущего пункта множество $M$ рекурсивно перечислимо. Покажем,
что это множество не рекурсивно.

Предположим, что это не так. Тогда характеристическая функция
$\chi_M(x)$ рекурсивна. Пусть $f(t)$, $g(t)$ --- такие примитивно
рекурсивные функции, что график функции $\chi_M(x)$ состоит из
всех точек вида $(f(t),g(t))$; тогда $\chi_M(f(t))=g(t)$ для
любого $t\in \Bbb N_0 $, и, поскольку функция $\chi_M(x)$
определена на всем множестве $\Bbb N_0 $, для всякого числа $a\in
\Bbb N_0 $ найдется число $t_0\in \Bbb N_0 $, такое что
$f(t_0)=a$.

Функции $f(t)$, $g(t)$ примитивно рекурсивны; поскольку функция
$U(x,y)$ универсальна для класса примитивно рекурсивных функций,
существует такие числа $a,b\in \Bbb N_0 $, что $f(t)=U(a,t)$,
$g(t)=U(b,t)$ для любого $t\in \Bbb N_0 $. Пусть $n=d^{(2)}(a,b)$.

Если $n\in M$, то для всякого $t\in \Bbb N_0 $, такого что
$U(c_1(n),t)=U(a,t)=f(t)=n$ должно быть
$U(c_2(n),t)=U(b,t)=g(t)=\chi_M(f(t))=\chi_M(n)=1$, и потому числа
$|U(c_1(n),t)-n|$, $|U(c_2(n),t)|$ не могут одновременно
обращаться в 0, т.е. уравнение $|U(c_1(n),t)-n|+|U(c_2(n),t)|=0$
не имеет решения. Это значит, по определению множества $M$, что
$n\notin M$.

Обратно, пусть $n\notin M$; пусть число $t_0\in \Bbb N_0$ таково,
что $f(t_0)=n$. Тогда $$|U(c_1(n),t_0)-n|+
|U(c_2(t_0))|=|U(a,t_0)-n|+|U(b,t_0)|=|f(t_0)-n|+|g(t_0)|=0,$$
потому что $g(t_0)=\chi_M(f(t_0))=\chi_M(n)=0$. Следовательно,
уравнение $$|U(c_1(n),t)-n|+|U(c_2(n),t)|=0$$ имеет решение $t_0$,
а это означает, что $n\in M$.

В обоих случаях мы пришли к противоречию, которое показывает, что
предположение о рекурсивности множества $M$ было ошибочно.
\enddemo
\head 11.Теорема Гёделя\endhead Одним из наиболее знаменитых
результатов математической логики является теорема Гёделя о
неполноте системы $Z_1$. \proclaim\nofrills{}Если система $Z_1$
непротиворечива, то существует такое суждение в теории $Z_1$, что
ни это суждение, ни его отрицание не могут быть доказаны в $Z_1$.
\endproclaim
В этом пункте мы дадим набросок доказательства этой теоремы,
сформулировав основные идеи и отбросив их довольно скучное
техническое осуществление.

Напомним, что все суждения являются словами в некотором конечном
алфавите $a_0,a_1,\dots,a_{n-1}$; будем при этом полагать, что
$a_0$  --- это правая скобка ")". Слову $a_{i_1}a_{i_2}\dots
a_{i_r}$ сопоставим натуральное число
$i_r+i_{r-1}n+\dots+i_2n^{r-2}+i_1n^{r-1}$. Мы получим биективное
соответствие между положительными натуральными числами и теми
словами, которые не начинаются с символа ")". Поскольку ни одно
суждение не начинается с этого символа, все суждения получают
некоторые номера, причем номер однозначно определяет суждение;
этот номер называется гёделевым номером суждения. Отметим, что не
всем номерам отвечают именно суждения (многим из них отвечают
просто бессмысленные наборы букв), но для нас это не существенно.

Все доказательства в теории $Z_1$ тоже могут быть пронумерованы
(аналогично тому, как выше мы пронумеровали все примитивно
рекурсивные функции). При этом в результате $n$-го доказательства
получается суждение, гёделев номер которого обозначим через
$h(n)$. Нетрудно провести нумерацию доказательств так, чтобы
получившаяся функция $h(n)$ была рекурсивна.

Пусть $M$ --- рекурсивно перечислимое, но не рекурсивное множество
из предыдущего пункта. Еще один факт, доказательство которого мы
опускаем: утверждение $n\in M$ и его отрицание $n\notin M$ могут
быть выражены как суждения $B_n$, $\neg B_n$ в системе $Z_1$,
причем гёделевы номера этих суждений $g(n)$, $g'(n)$ являются
рекурсивными функциями от $n$.

\proclaim{Теорема}Существует $n\in \Bbb N_0 $, для которого ни
суждение $B_n$, ни его отрицание не могут быть доказаны в $Z_1$.
\endproclaim
\demo{Доказательство} Если существует доказательство суждения
$B_n$ , то существует $t\in\Bbb N_0 $, такое что $g(n)=h(t)$.
Точно так же, если можно доказать суждение $\neg B_n$, то
существует $t\in \Bbb N_0 $, такое что $g'(n)=h(t)$. Предположим,
что для всех $n$ можно доказать либо суждение $B_n$, либо суждение
$B_n'$ (оба суждения не могут быть одновременно доказуемы, так как
тогда существовало бы доказательство тождественно ложного суждения
$B_n\&\neg B_n$, т.е. система $Z_1$ была бы противоречива ). Тогда
уравнение $|g(n)-h(t)|\cdot|g'(n)-h(t)|=0$ разрешимо для любого
$n$; обозначим через $w(n)$ наименьшее решение этого уравнения:
$$w(n)=\mu_t(|g(n)-h(t)|\cdot|g'(n)-h(t)|).$$ Функция $w(n)$
рекурсивна; вместе с ней рекурсивна и функция $$v(n)=
\sg(|g'(n)-h(w(n))|).$$ \proclaim{Лемма}Функция $v(n)$ является
характеристической функцией множества $M$.\endproclaim
\demo{Доказательство}Если $n\in M$, то утверждение $n\notin M$ не
может быть доказано. Тогда $|g'(n)-h(t)|\ne 0$ для всех $t\in \Bbb
N_0 $, и $v(n)=\sg(|g'(n)-h(w(n))|)\ne 0$; но функция $v(x)$
принимает только значения 0, 1, и потому $v(n)=1$.

Если $n\notin M$, то утверждение $n\in M$ не может быть доказано;
поэтому $|g(n)-h(t)|\ne 0$ для всех $t\in \Bbb N_0 $.
Следовательно, число $w(n)=\mu_t(|g(n)-h(t)|\cdot|g'(n)-h(t)|)$ не
является корнем уравнения $|g(n)-h(t)|=0$ и потому
$|g'(n)-h(w(n))|=0$, т.е. $v(n)=\sg(|g'(n)-h(w(n))|)=0$.
\enddemo
Таким образом, мы получили, что рекурсивная функция $v(n)$
является характеристической функцией множества $M$, т.е. множество
$M$ рекурсивно. Это противоречие доказывает, что предположение о
том, что для всякого $n$ существует доказательство  одного из
суждений $B_n$, $\neg B_n$, неверно.
\enddemo

\enddocument
