2. Изображение высказываний равенствами вида t=0; суммы и произведения с переменным числом членов; изображение высказываний с ограниченными кванторами; изображение максимума и минимума.

После этих предварительных замечаний мы перейдем к доказательству следующей теоремы:

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

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

1. Каждое равенство

переводимо в некоторое равенство

2. Если формула переводима в равенство вида

то также переводима в равенство такого вида.

3. Если формулы обе переводимы в равенства вида

то формула также переводима в такое равенство.

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

1. Как упоминалось выше, выводима эквивалентность

подставив в эту эквивалентность вместо a и b вместо мы получим, что равенство

переводимо в равенство

2. С помощью рекурсивных равенств

введем функцию Из этих равенств с помощью формулы

мы выведем эквивалентность

Пусть теперь формула переводима в равенство

т. е. пусть выводима эквивалентность

Тогда из нее может быть получена формула

с другой стороны, из только что выведенной эквивалентности для функции мы при помощи подстановки получаем

тем самым получается формула

3. Предположим, что у нас имеются эквивалентности

Из них мы получим

Теперь воспользуемся выводимой эквивалентностью

Если мы подставим в нее вместо вместо то в сочетании с предыдущей эквивалентностью получим

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

и

с помощью выводимой формулы

может быть выведена эквивалентность

Таким образом, при переводе формул в равенства вида

конъюнкции соответствует сумма, а дизъюнкции — произведение приравниваемых нулю термов.

Поэтому, если формула переводима в формулу

то для любой цифры -членная конъюнкция

переводима в равенство

а -членная дизъюнкция

переводима в равенство

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

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

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

формула

соответствует содержательному высказыванию о том, что предикат имеет место для всех чисел а от до (включительно), и в точности так же формула

соответствует высказыванию о том, что предикат имеет место по крайней мере для одного числа а среди чисел от до Это соответствие имеет место еще и в том смысле, что в нашем формализме равенства

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

и

Действительно, применение основных формул (а) и (Ь) к обеим этим формулам дает нам

и

а схемы (а) и в применении к этим формулам выглядят следующим образом:

(здесь обозначает формулу, которая не содержит переменной а, но может содержать переменную ). Если теперь мы заменим формулу

равенством

а формулу

равенством

то обе получающиеся из (a) и (b) в результате такой подстановки формулы перейдут в формулы

и

которые обе выводимы индукцией по с помощью эквивалентности

а вместо применений схем (а) и мы получим переход от формулы

к формуле

и от формулы

к формуле

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

из формулы

можно индукцией по вывести формулу

Если в эту формулу вместо подставить то можно будет опустить посылку являющуюся выводимой формулой, и мы получим

Совершенно аналогично, из формулы

при помощи

индукцией по мы получим формулу

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

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

Если бы мы захотели вместо условия а взять условие а следовательно, выразить то обстоятельство, что некоторое высказывание имеет место для всех чисел, меньших или соответственно для некоторого числа, меньшего то вместо функций нам пришлось бы взять функции

определяемые рекурсивными равенствами вида

С другой стороны, если мы захотим брать эти суммы и произведения не от до , а от 1 до , то мы должны будем положить

Рекурсивно же можно определить и максимум термов Сначала равенством

можно явно определить максимум чисел Из этого равенства можно будет получить формулы

из которых затем, на основании альтернативы

мы получим формулы

и

так что в делом у нас для получается следующая формальная характеризация:

Максимум и с определяется равенством

Аналогичным образом мы получим представление и для максимума нескольких чисел.

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

С помощью этих равенств индукцией по могут быть выведены формулы

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

Аналогично максимуму мы можем рекурсивно определить и минимум этих термов. Исходная функция

задается посредством явного определения

из которого получается формула

Кроме того, на основании ранее выведенной формулы

(после перестановки мы получаем

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

Определяющие эту функцию рекурсивные равенства записываются в виде

Следует обратить внимание на то, что функция

наряду с выделенной в этой рекурсии переменной может дополнительно содержать какие-нибудь параметры.

Характеристическое свойство этой функции формально представляется посредством следующих двух, выводимых с помощью схемы индукции формул:

Терм

в том случае, если среди чисел, меньших к, имеются числа со свойством представляет собой наибольшее из таких чисел, а в противном случае он равен числу k. Затем, используя рекурсивно определенную функцию мы получим функцию

которая в том случае, когда среди чисел от до к имеются числа со свойством равна наименьшему из этих чисел, а в противном случае равна О.