Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

19. Оно, правда, представляет собой сведение к абсурду, но в такой его форме, которая приемлема даже для Брауэра: ни закон исключенного третьего, ни закон снятия двойного отрицания (также отвергаемый интуиционистами) здесь не используется.

20. Этот доклад составляет добавление IX в книге «Основания геометрии».

21. П. С. Новиков. Элементы математической логики. М.» 1959, с. 36.

1. О содержании этой работы Гёделя можно подробнее прочесть в кн.: Э. М. Чудинов. Теория относительности и философия. М.. 1974, с. 232 и далее.

2. K. Godel. Uber formal unentscheidbare Satze der Principia Mathematica und vervandter Systeme. -— «Monatchefter fur Mathematik und Physik» Bd 38, 1931.

3. Понятие тождественной истинности, которое в гл. 3 было нами разъяснено в применении к формам высказываний, трактуемым на уровне логики высказываний (алгебры логики), естественным образом распространяется на классическую логику предикатов и строящиеся на ее основе логико-математические системы. Поскольку, однако, мы не можем здесь рассказать, как происходит такое распространение, мы будем вместо «тождественной истинности» употреблять более общее (хотя и менее определенное) понятие «содержательной истинности» (истинности по смыслу).

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

5. Отметим, что в своей теореме Гёдель использовал более сильное условие, чем «обычная» непротиворечивость, смысл которой был кратко пояснен в главе 5, с. 120—121. Однако впоследствии было показано, что для его теоремы достаточно и «обычной» непротиворечивости.

6. П. С. Новиков. Элементы математической логики. М., 1989, с. 36.

7. А. Н. Нагель. Дж. Р. Ньюмен. Теорема Гёделя. М., 1970. с. 58—60.

8. Краткий, но достаточно ясный обзор проблематики исследований формальных систем читатель найдет в гл. I кн.: С. Клини. Математическая логика. М., 1973.

9. Одно из таких доказательств приводится в кн.: Э. Мендельсон. Введение в математическую логику. М., 1971, с. 282—295.

1. Совокупность этих допущений составляет то, что обычно называют абстракцией потенциальной осуществимости. Представление об этой абстракции в явной форме было введено в логику и основания математики выдающимся советским ученым Андреем Андреевичем Марковым (род. в 1903 г.). См.: А. А. Марков. Теория алгорифмов. Труды Математического института АН СССР. т. ХШ. М.—Л.. 1954. с. 15; А. А. Марков. О логике конструктивной математики. М., 1972.

2. Более строго операцию подстановки можно задать следующим образом. По n-местным функциям q1..., gm и m-местной функции h строится n-местная функция f такая, что для любых x1, x2,..., Хn

f(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)).

3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого условного равенства (≃). Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,-понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают.

4. Отметим в этой связи, что приведенное там же определение функции δ подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 — 138). Роль f играет функция δ, в качестве r берется 0, а в качестве h — проектирующая функция I 1 2.

5. См. А. И. Мальцев. Алгоритмы и рекурсивные функции. М., 1965, с. 12 и далее.

6. Имеется в виду статья: L. Kalmar. An Argument against the Plausibiolitu of Church's Thesis. «Constructivity in Mathematics. Proceedings of the Colloquium held at Amsterdam». Amsteerdam, 1959, p. 72—73.

7. Имеется в виду работа : А. Church. An Unsolvable Problem of Elementary Number Theory. «American Journal of Mathematics», vol. LVIII, № 2, 1936.

8. Характеристической (представляющей) функцией арифметического предиката P (х1, ..., Хn)называется такая арифметическая функция f, что для любого набора аргументов x1, ..., Хn

f(х1, ..., Хn) = (1, если предикат P выполняется на данном наборе) или (0, если P не выполняется на данном наборе.)

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