Текст книги "Жар холодных числ и пафос бесстрастной логики"
Автор книги: Борис Бирюков
Соавторы: В. Тростников
Жанры:
Математика
,сообщить о нарушении
Текущая страница: 13 (всего у книги 14 страниц)
20
3. В трактате «О достоинстве и преумножении наук» (1623) Ф. Бэкон сравнивал «искусство Луллия» с лавкой старьевщика, «где можно , найти множество тряпья, но нельзя найти ничего, что имело бы хоть какую-нибудь ценность» (Ф. Бэкон. Сочинения. В 2-х т.. т. 1. М., 1971, с. 349.
21
4. Предупреждаем, впрочем, что «искусство» Луллия было гораздо сложнее, чем может показаться из приведенного выше его краткого описания. Например, в его комбинаторике нашли свое место даже вопросительные предложения (заметим в этой связи, что логика вопросительных форм и по сей день остается мало разработанной). Читателя, желающего подробнее ознакомиться с логикой Луллия и его школы, мы отсылаем к книгам: В. Владиславлев. Логика. Обозрение индуктивных и дедуктивных приемов мышления и исторические очерки: логики Аристотеля, схоластической диалектики, логики формальной и индуктивной. Спб, 1881; Н. И. Стяжкин. Формирование математической логики. М.. 1967; М. Gardner. Logic Machines and Diagrams. New York – Toronto – London, 1958.
22
5. Большинство лейбницевых текстов логического содержания было впервые издано в 1901 и 1903 гг. Луи Кутюра. Впрочем, научное наследство Лейбница еще полностью не опубликовано; как отмечает И. С. Нарский в книге «Западноевропейская философия XVII века» (М., 1974, с. 281), в ганноверском архиве Лейбница хранится около 75 тысяч отдельных его работ.
23
6. По словам Б. Рассела, «есть две системы философии, каждую из которых можно рассматривать как представляющую взгляды Лейбница: одна, которую он открыто провозглашал, была оптимистической, ортодоксальной, фантастической и мелкой; другая, которую постепенно извлекали из его рукописей относительно недавние издатели, была глубокой, ясной, ... удивительно логичной» (Б. Рассел. История западной философии. М., 1959, с. 600).
24
7. О жизни и научном творчестве Лейбница в интересующей нас области см. книгу Н. И. Стяжкина, указанную в примечании 4. Философские взгляды Лейбница подробно освещены в книге И. С. Нарского, упомянутой в примечании 5. Облик Лейбница как ученого и человека обрисован в книге: И. Б. Погребысский. Готфрид Вильгельм Лейбниц. 1646—1716. М., 1971.
25
8. G.W. Leibniz. Fragmente zur Logik. Berlin. 1960, S. 16.
26
9. Там же.
27
10. Н. Винер. Кибернетика, или Управление и связь в животном и машине. Второе издание. М., 1968, с. 57.
28
11. Н. Винер. Кибернетика и общество. М., 1958, с. 32—33.
28
12. И.Слешинский. Логическая машина.– «Вестник опытной физики и элементарной математики». Одесса, 1893, № 175 (7).
29
13. Цитируется по статье: А. И. Берг. Кибернетика и общественные науки.– В кн.: Методологические проблемы науки. Материалы заседания Президиума Академии наук СССР. М., 1964, с. 260. О машине Джевонса в России, усовершенствованной известными физико-химиками П. Д. Хрущевым и А. Н. Щукаревым, см.: В. А. Велигжанин, Г.Н. Поваров. К истории создания логических машин в России.-«Вопросы философии», 1971, № 3.
30
14. Ст. Джевонс. Основы науки. Трактат о логике и научном методе. Спб, 1881, с. 2. В этой книге читатель найдет подробное и очень доступное изложение алгебры логики Джевонса – теории, в которой впервые в логике фактически присутствовало то, что ныне называется булевой алгеброй (см. следующую главу). В нашем изложении мы несколько изменили символику Джевонса, приблизив ее к современной. Примеры, которыми мы оперируем, принадлежат Джевонсу.
31
15. Операция пересечения двух произвольных классов (множеств) – это операция, порождающая такой класс – его обычно обозначают А ∩ В или просто AВ, как в нашей записи, который состоит из элементов, входящих как в класс A, так и в класс В. В дальнейшем будут использоваться также понятия объединения двух классов и дополнения к классу. Операцией объединения произвольных классов A и В называется операция, порождающая такой класс (он обозначается через A ∪ В), который состоит из элементов, входящих хотя бы в один из классов: в A или в В.
Операция взятия дополнения к произвольному классу A (до некоторого объемлющего универсального класса, или универсума, V) есть операция, порождающая класс, состоящий из всех тех и только тех) элементов универсума, которые не входят в класс А; дополнение к А обозначается через A' или -A. Заметим, что операции пересечения и объединения классов обладают свойством коммутативности (перестановочности, симметричности), то есть А ∩ В = В ∪ А, А ∪ В = В ∩ А (это свойство используется ниже в примере 3).
32
16. Действительно, по закону исключенного третьего:
A = AB ∪ AB' = ABC ∪ ABC' ∪ AB'C ∪ AB'C', A' = A'B ∪ A'B' = А'ВС ∪ А'ВС' ∪ AВ'С ∪ А'В'С' но, как очевидно, A ∪ A' = V.
33
1. G. Вооlе. The Mathematical Analysis of Logic. Cambridge and London, 1847; G. Вооlе. An Investigation of the Laws of Thought. London, 1854.
34
2. Е. Т. Веll. Men of Mathematics. New York. 1962, p. 433. О своеобразии английской математики того времени, объясняющем тот факт, что математическая логика возникла в Англии, см.: Б. В. Бирюков, А. А. Коноплянки н. Развитие логико-математических идей как элемент исторической подготовки кибернетики (на примере развития английской науки в 19 и начале 20 вв.).– «Вестник истории мировой культуры», 1961, № 6 (30).
35
3. Формулы вида (а & β) и (а V β) мы будем называть соответственно конъюнктивной и дизъюнктивной формулами (или формами, когда появится понятие формы), иногда же просто «конъюнкциями» и «дизъюнкциями».
36
4. Метазнак (греч. «мета» – за, после) – знак, обозначающий знак или конструкцию из знаков данного алфавита и не принадлежащий к этому алфавиту. В данном случае метазнаки обозначают произвольные формулы.
37
5. Строгое определение цепочки равенств выглядит следующим образом: а) каждое равенство есть (одночленная) цепочка равенств;
б) если Х – цепочка равенств, в которой последней формулой справа является формула φ и φ=χ;, то Х=χ – тоже цепочка равенств:
в) Других цепочек равенств, кроме устанавливаемых на основе пп. а) и б), не имеется.
38
6. Этот список постулатов основан на перечне равносильностей алгебры высказываний, приведенных в кн.: П. С. Новиков. Элементы математической логики. М.» 1973. с. 42.
39
7. Название связано с тем, что в математической логике законы 9 и 10 впервые сформулировал Де Морган. Однако соответствующие правила были известны уже средневековым логикам.
40
8. Вместо этого «общего» правила замены равным в число постулатов можно было бы ввести более «конкретное» правило: если а = β то (γ & а) = (γ & β). (а & γ) = (β & γ); (γ V а) = (γ V β), (а V γ)-(β V γ)» ~а= ~β. «Общее» правило замены равным оказывается в этом случае производным правилом: его можно обосновать с помощью «конкретного» правила замены равным.
41
9. Обращаем внимание на то, что мы не стремимся к независимости постулатов нашего аппарата. Например, свойство рефлексивности отношения равенства оказывается в данном построении производным от свойств симметричности и транзитивности этого отношения и каждой из схем аксиом 7, 8, 11—15. Со свойствами отношения равенства можно подробнее ознакомиться по кн.: А. Тарский. Введение в логику и методологию дедуктивных наук. М., 1948, с. 90 и далее. О философских вопросах, связанных в равенством и отождествлением, см: Д. П. Горский. Вопросы абстракции и образование понятий. М., 1961.
42
10. То есть (а → β) ≝ (~а V β), где ≝ есть знак «равенства выражений по определению» («графического» их совпадения). Мы будем считать, что к равенствам по определению тоже применимы правила [b] (ср. ниже с. 64—65 и 69—70).
43
11. Различного рода исчисления равенств оказываются весьма полезным инструментом во многих разделах логики и оснований математики (ср. кн.: Р. Л. Гудстеин. Рекурсивный математический анализ. М., 1970, в которой исчисление равенств используется для построения и исследования фрагментов конструктивной математики; о конструктивном направлении в математике см. ниже, гл. 5 и далее). Систематическое представление различных логических систем в виде соответствующих исчислений равенств было осуществлено Г. И. Сыркиным в его курсах лекций «Алгебраические методы в логике», читанных на философском факультете МГУ в 1974—1975 гг. 1
44
12. Столбцы для аргументов от остальной части таблицы мы отделяем двойной вертикальной чертой. Обращаем внимание на то, что фигурирующие в таблицах 0 и 1 не следует смешивать с константами 0 и 1.
45
13. С учетом интерпретации констант 0 и 1, которая будет дана ниже.
46
14. Мы не останавливаемся на некоторых деталях определения;
понятия «верные равенства формул», отсылая читателя к книге П. С. Новикова, указанной в примечании 6.
В этой книге говорится, правда, об отношении «равносильности» формул, но это по существу то же, что мы имеем в виду под совпадением функций (точнее, впрочем, то же, что в следующей интерпретации окажется равенством или равносильностью форм высказываний).
47
15. Вместо слов «формула а при данных значениях своих переменных переходит в истинное (или ложное) высказывание» мы будем употреблять и такое выражение: «формула а принимает такое-то (истинностное) значение», а также говорить: «формула а истинна (ложна)».
48
16. В связи с данной интерпретацией заметим, что со знаками → и ≡ можно было с самого начала поступить иначе: не вводить их определениями (как сокращения), а включить в сам язык формальной системы – в ее алфавит (расширив соответствующим образом пункт I в)). Это приведет к расширению понятия формулы и добавлению к системе постулатов схем аксиом для → и ≡. А именно, в пункт II (в) добавляется– «если а и β – формулы, то (а → β) и (а ≡ β) – тоже формулы», а к системе постулатов IV[a] присоединяются: 18. (а → β) = (~а V β) и 19. (а ≡ β) = (~а V β) & (а V ~β)). Пункт V при этом должен быть удален.
49
17. Ср. формулировку этих законов у Джевонса (с. 43). Очевидно, что способ «формульного» представления этих законов зависит от характера рассматриваемого логического аппарата.
рис. 7. Круговые схемы, изображающие пять возможных отношений между двумя произвольными классами а и β.
50
18. Аналогично, в школьной математике не пишут, скажем, ((а+b)+с)+d или (а+b)+(с+d) а записывают просто а+b+с+d.
51
19. Эрнет Шредер (E. Schroder, 1841—1902) является автором трехтомных «Лекций по алгебре логики» (Vorlesungen uber die Logik. Bd. 1-3, Leipzig, 1890—1905), знаменующих собой – вместе с трудами русского логика и астронома П. С. Порецкого (1846—1907) – вершину развития алгебры логики в прошлом столетии. Задача, которая приводится ниже, заимствована из первого тома «Лекций». Эту задачу приводила в своих лекциях по математической логике в Московском университете С. А. Яновская; мы приводим задачу в ее формулировке.
52
20. Впрочем, операции булевой алгебры можно задавать указанием и других наборов их свойств. О булевых алгебрах см., например:
И. М. Яглом. Алгебра Буля.– В сб.: «О некоторых вопросах современной математики и кибернетики». М., 1965.
53
21. Напоминаем, что здесь высказывание понимается «классически», то есть как выражение либо истинное, либо ложное, но не то и другое вместе.
54
22. При другом подходе булевой алгеброй для логической интерпретации нашего аппарата можно считать множество форм высказываний (рассматриваемых с точностью до отождествления равносильных форм) вместе с заданными на них операциями ~, &. V – такая булева алгебра высказываний оказывается алгеброй Линденбаума – Тарского, о которой см.: Е. Расёва, Р. Сикорскии. Математика метаматематики. М., 1972, с. 282 и далее.
55
23. Заметим, что булеву алгебру можно сформулировать и на основе отношения ≤ (или ≥). См: X. Б. Карри. Основания математической логики. М., 1969.
56
24. Для этого имеются и другие причины. Дело в том, что в алгебре логики Буля можно определить операцию дизъюнкции, и тогда все равенства, верные в логике высказываний как булевой алгебре, будут верными и в теории Буля; с другой стороны, в рассмотренной нами теории можно определить строгую дизъюнкцию (например, так:
(А V B)≝((A & ~В) V (~А & В)), и тогда теория Буля может быть пред. ставлена как теория булевой алгебры (в узком смысле).
57
25. Понятие формы класса (классовой формы) следует понимать по аналогии с понятием «форма высказывания».
57
26. Ср. примечание 14.
58
27. Заметим, что при проверке схем аксиом, в каждой из которых фигурирует по две формы классов, следует учитывать возможные отношения между двумя произвольными классами а и β. Таких отношений может быть пять: классы а и β совпадают; класс а полностью входит в класс β, причем в β имеются элементы, не принадлежащие а; то же отношение, но с заменой а на β и наоборот; классы а и β имеют общие элементы, причем в а есть элементы, не принадлежащие классу β, и в β есть элементы, не принадлежащие а; классы а и β не имеют общих элементов. Эти отношения можно передать следующими схемами (рис. 7). Проверяя равенство, нужно убедиться в его справедливости при каждом из этих отношений.
59
28. Абстрактное понятие булевой алгебры есть достижение середины нашего века, в то время как его спецификации – на классах и высказываниях – восходят к логикам прошлого века. Применению аппарата булевой алгебры к исследованию релейно-контактных схем начало положили в 1935—1938 гг. В. И. Шестаков, А. Никасима и К. Шеннон, один из создателей кибернетики (см. его статью «Символический анализ релейных и переключательных схем», в русском переводе опубликованную в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963). «Приоритет в применении аппарата математической логики к вопросам электротехники (связанным с построением релейно-контактных схем), – отмечает С. А. Яновская, принадлежит... В. И. Шестакову, работа которого «Алгебра релейно-контактных схем»... написанная еще в январе 1935г., к сожалению, не была своевременно опубликована, хотя и легла в основу его кандидатской диссертации» (Послесловие редакции в кн: А. Тарекии. Введение в логику и методологию дедуктивных наук. М., 1948. с. 320).
60
1. Эти – и другие – высказывания выдающихся мыслителей о математике см. в кн.: Е. Т. Веll. Men of Mathematics. N. Y. 1962, XV—XVII.
61
2. См. об этом в кн.: В. Н. Молодший. Очерки по философским вопросам математики. М., 1969, ч. II, гл. 2.
62
3. Конечную дробь, то есть (периодическую) дробь с «хвостом» из одних нулей (например, 3,14000...) при этом заменяют бесконечной периодической дробью с девяткой в периоде (в нашем примере– дробью 3,13999...).
63
4. Если действительное число есть рациональное число, то есть если десятичная дробь является периодической, то с бесконечностью можно «справиться» тривиальным способом, рассматривая число как дробь p/q, где p и q – целые числа, а q отлично от нуля.
64
5. E. Т. Веll. Men of Mathematics. N. Y., 1962. p. 431.
65
6. С теорией Дедекинда можно подробнее познакомиться по изложению автора. См.: Р. Дедекинд. Что такое числа и для чего они служат. Казань, 1905.
7. См. Г.М. Фихтенгольц. Основы математического анализа. Т. 1. М., 1960, с. 17.
66
8. Априори возможен еще случай, когда в левом классе есть наибольшее число, а в правом – наименьшее. Однако нетрудно показать, что такой случай противоречит свойствам сечения.
67
9. См. об этом подробнее в кн. В. Н. Молодшего, указанной в примечании 2.
68
10. Б. Рассел. История западной философии. М., 1959, с. 56.
69
11. Цитируется по кн.: Н. Бурбаки. Очерки по истории математики. М., 1963. с. 29.
70
12. См. об этом в кн.: История математики. Т. 1. М., 1970, с. 292 и далее.
71
13. См. статью Л. Кальмара, указанную в примечании 13 к гл.1, е.188,
72
14. С основными идеями Г. Кантора можно ознакомиться по трем его работам, имеющимся в русском переводе (опубликованы в издании:
Новые идеи в математике. Вып. 6. Спб, 1914).
73
15. С. К. Клини. Введение в метаматематику. М., 1957, с. 14.
74
16. Этот результат был в определенном смысле обобщением следующего свойства конечных множеств. Пусть дано, скажем, множество из трех элементов М = {а, b, с}. Помимо пустого множества, по определению входящего во всякое множество, и самого множества M, входящего в самое себя, в нем содержатся следующие подмножества: {а}, {b}, {с} {а, b}, {а, с}, {b, с}; таким образом, множество всех подмножеств множества из трех элементов содержит 8, или 23 элементов. Легко доказать, что если исходное множество содержит n элементов, то множество всех его подмножеств будет содержать 2n элементов. Поэтому в случае конечных множеств количественное превосходство производного множества над исходным очевидно. Но когда речь идет о бесконечных множествах, вопрос становится не таким просты»: Кантор доказал, что и в этом случае производное множество превзойдет исходное; правда, здесь уже нельзя будет сказать, что в нем окажется больше элементов – и там и там их бесконечно много, а следует говорить, что оно обладает большей мощностью. Термин «мощность» Кантор определил математически строго. См. гл. I книги С. К. Клини, указанной в примечании 15.
75
17. G. Frege. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle, 1879; G. Frege. Grundgesetze der Arithmetik, begriffsschrift lich abgeleitet. Bd. I, Jena, 1893; Bd. II, Jena, 1902:
Общую характеристику вклада Фреге в логику и основания математики см. в статье Б. В. Бирюкова «О работах Фреге по философским вопросам математики», помещенной в сборнике «Философские вопросы естествознания», вып. 2, [М], 1959.
76
18. В рассмотренном нами в гл. 3 исчислении равенств это были знаки → и ≡.
77
19. При этом в интерпретациях этого исчисления – если не иметь в виду интуиционистскую и подобные ей «неклассические» логики, о которых пойдет речь ниже, присутствуют булевы алгебры.
78
20. В построении самого Фреге фигурировали не схемы аксиом, а конкретные аксиомы, в связи с чем в числе постулатов имелось еще одно правило вывода – так называемое правило подстановки. Однако мы следуем его системе лишь в самых общих– чертах. Заметим, что символика Фреге резко отличалась от обычной линейной логической и математической символики. Она носила «рисунчатый» характер и не привилась.
79
21. Используя «родство» эквиваленции (которую без труда можно ввести в исчисление Фреге) с отношением равенства и согласовав выразительные средства этого исчисления со-средствами описанного в гл. 3 исчисления равенств (равносилъноетей) формул, можно показать, что эти исчисления в определенном смысле переводимы друг в друга – имеют одинаковую дедуктивную силу.
80
22. Ниже излагается лишь общая идея фрегевского определения натуральных чисел. Полностью изложить его подход здесь, разумеется, не представляется возможным.
81
23. Об определении натуральных чисел как конечных кардинальных чисел (по Кантору) см., например: Н. Бурбаки. Теория множеств. М., 1965, с. 197 и далее.
81
24. J. van Heienoort. From Frege to Godel. A Source Book in Mathematical Logic. Cambridge (Mass.), 1967, p. 124—125.
82
25. Под идеографией Рассел имеет в виду логическую символику.
83
26. В теории Фреге предикаты рассматривались как частный случай функций, а именно, как функции, принимающие в качестве своих значений значения «истинно» и «ложно». Эта точка зрения на предикаты общепринята и в настоящее время при содержательном исследовании закономерностей «мира свойств и отношений».
84
27. Имеется в виду книга Б; Рассела «Принципы математики», которая вышла два года спустя(В. Russell. The Principles of Mathematics. Cambridge (Engl.), 1993).
85
28. Этими словами начинается послесловие Фреге ко второму тому «Основных законов арифметики» (с. 253).
86
29. X. Б. Карри. Основания математической логики. М., 1969, с. 32.
87
30. См. L. Kreiser. Geschichte und logisch-semantische Probleme des wissenschaftlichen Werkes Fregess. In: G. Frege. Schriften zur Logik. Aus dem Nachlaβ. Berlin. 1973.
88
31. Это стало известно после опубликования первого тома научного наследства Фреге: G. Frege. Nachgelassene Schriften. Bd. I. Hamburg, 1969. В рецензии на эту книгу, написанной Б. В. Бирюковым и Н. Н. Нуцубидзе и помещенной в издании «Новые книги за рубежом по общественным наукам», 1974, 6, читатель найдет рассказ об эволюции взглядов Фреге под конец жизни и о судьбе его научного наследия, в известном смысле разделившего научную трагедию Фреге.
89
32. Это была известная «теория тинов», разработанная Расселом еще до публикации «Principia Mathematica». О теории типов см. книгу С. К. Клини, указанную в примечании 15.
90
33. Следует вместе с тем заметить, что труд А. Н. Уайтхеда и Б. Рассела (A. N. Whitehead, B. Russell. Principia Mathematica. Vol. I, 1910; vol. II, 1912; vol, III, 1913, Cambridge, Engl.) явился важной: вехой в развитии математической логики и оснований математики. От него в знаяительной мере отправляются последующие работы в этой области, в частности исследования К. Гёделя (см. ниже).
91
1. Развертывание своей философско-матемагической платформы Брауэр начал со статьи «Недостоверность логических принципов», опубликованной в 1908 г. на голландском языке. Хорошее представление о взглядах Браузра дает кн.: Г. Веиль. О философии математики. М.-Л. 1934.
92
2. «Всякая наука. – считал Р. Декарт, заключается в достоверном и очевидном познании, которое есть деятельность интеллекта. Возможны только два действия интеллекта, «посредством которых мы можем придти к познанию вещей, не боясь никаких ошибок, это интуиция и дедукция, «поэтому из всех наук только математика чиста «от всего ложного и недостоверного»,; опытное же познание «часто вводит вас в заблуждение» (Р. Декарт. Набранные произведения. [М.]» 1950, с. 81—86). О параллелях между взглядами Декарта и философскими установками Брауэра см. ниже.
93
3. Что обе они не могут -выполняться– это гарантируется законом противоречия. Этот закон Брауэр не ставил под сомнение.
94
4. Но позиция Брауэра позволяет заключать от отвержения альтернативы α, например, путем приведения ее к абсурду, к верности высказывания ~α (этот способ рассуждения признает и конструктивизм, генетически связанный с брауэровской критикой классической математики и логики).
95
5. Цитируется по кн.: E.W. Beth. The Foundations of Mathematics. A Study in the Philosophy of Science. Amsterdam, 1965. p. 618—619.
96
6. Р. Декарт. Избранные произведения, с. 86.
97
7. См., например: Ж. Пиаже. Избранные психологические труды. [М.], 1959.
98
8. А. А. Марков. Комментарии.—В кн.: А. Рейтинг. Интуиционизм. Введение. М., 1965, с. 162.
98
9. При интуиционистской – не связанной с понятием алгоритма – трактовке конструктивности.
99
10. Мы набросали лишь идею доказательства. Точную формулировку теоремы и полное ее доказательство можно найти, скажем, в кн.:
Г.М. Фихтенгольц. Основы математического анализа. Т. I. М.. 1960, с. 105—106.
100
11. См. Д. Гильберт. Основания геометрии. М.– Л., 1948.
101
12. И вступил по этому поводу в полемику с Гильбертом (переписка Фреге и Гильберта по данному вопросу опубликована в «Sitzungsberichte der Heidelberger Akademie der Wissenschaften.». Jahrgang 1940, 6. Abhandlung, Heidelberg, 1940; 1941, 2. Abhandlung, Heidelberg, 1941).
102
13. Гильберт говорит: «с применением метода идеальных элементов связано одно условие, одно единственное, но необходимое, это доказательство непротиворечивости. Именно, расширение посредством пуюбщения идеальных элементов дозволено только в том случае, когда при этом в старой, более узкой области не-возникает никаких противоречий, то есть если соотношения, которые выявляются для старых образов при исключении идеальных образов, всегда остаются справедливыми в этой старой области» (Д. Гильберт. Обоснования математики. Добавление IX в его книге «Основания геометрии», с. 376).
103
14. Д. Гильберт. О бесконечном. Добавление VIII в его книге «Основания геометрии», с. 350.
104
15. См.: Проблемы Гильберта. М., 1969, с. 22.
105
16. Д. Гильберт. О бесконечном. Добавление VIII в его книге «Основания геометрии», с. 351.
106
17. Д. Гильберт. Обоснования математики. Добавление IX в его книге «Основания геометрии», с. 381—382. Под «реальными высказываниями» Гильберт имеет в виду высказывания, не содержащие «идеальных элементов».
107
18. Обращаем внимание на различие между доказательством теорем в формальной системе и доказательством теорем о самой формальной системе. Доказательства последнего рода называются метадоказательствами, а теоремы, в них доказываемые, метатеоремами. Что доказательства в формальной системе финитны – это очевидно, так как они представляют собой знаковые конструкции, то есть материальные объекты. Задача Гильберта состояла в том, чтобы придать финитный характер метадоказательствам.
108
19. Оно, правда, представляет собой сведение к абсурду, но в такой его форме, которая приемлема даже для Брауэра: ни закон исключенного третьего, ни закон снятия двойного отрицания (также отвергаемый интуиционистами) здесь не используется.
109
20. Этот доклад составляет добавление IX в книге «Основания геометрии».
110
21. П. С. Новиков. Элементы математической логики. М.» 1959, с. 36.
111
1. О содержании этой работы Гёделя можно подробнее прочесть в кн.: Э. М. Чудинов. Теория относительности и философия. М.. 1974, с. 232 и далее.
112
2. K. Godel. Uber formal unentscheidbare Satze der Principia Mathematica und vervandter Systeme. – «Monatchefter fur Mathematik und Physik» Bd 38, 1931.
113
3. Понятие тождественной истинности, которое в гл. 3 было нами разъяснено в применении к формам высказываний, трактуемым на уровне логики высказываний (алгебры логики), естественным образом распространяется на классическую логику предикатов и строящиеся на ее основе логико-математические системы. Поскольку, однако, мы не можем здесь рассказать, как происходит такое распространение, мы будем вместо «тождественной истинности» употреблять более общее (хотя и менее определенное) понятие «содержательной истинности» (истинности по смыслу).
114
4. Заметим, что если из доказуемости (или истинности) некоторой формулы (высказывания) следует ее недоказуемость, то это не означает еще формально-логического противоречия. Таковое будет иметь место, если, кроме этого, из недоказуемости будет следовать доказуемость.
115
5. Отметим, что в своей теореме Гёдель использовал более сильное условие, чем «обычная» непротиворечивость, смысл которой был кратко пояснен в главе 5, с. 120—121. Однако впоследствии было показано, что для его теоремы достаточно и «обычной» непротиворечивости.
116
6. П. С. Новиков. Элементы математической логики. М., 1989, с. 36.
117
7. А. Н. Нагель. Дж. Р. Ньюмен. Теорема Гёделя. М., 1970. с. 58—60.
118
8. Краткий, но достаточно ясный обзор проблематики исследований формальных систем читатель найдет в гл. I кн.: С. Клини. Математическая логика. М., 1973.
9. Одно из таких доказательств приводится в кн.: Э. Мендельсон. Введение в математическую логику. М., 1971, с. 282—295.
119
1. Совокупность этих допущений составляет то, что обычно называют абстракцией потенциальной осуществимости. Представление об этой абстракции в явной форме было введено в логику и основания математики выдающимся советским ученым Андреем Андреевичем Марковым (род. в 1903 г.). См.: А. А. Марков. Теория алгорифмов. Труды Математического института АН СССР. т. ХШ. М.—Л.. 1954. с. 15; А. А. Марков. О логике конструктивной математики. М., 1972.
120
2. Более строго операцию подстановки можно задать следующим образом. По n-местным функциям q1..., gm и m-местной функции h строится n-местная функция f такая, что для любых x1, x2,..., Хn
f(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)).
121
3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого условного равенства (≃). Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,-понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают.
122
4. Отметим в этой связи, что приведенное там же определение функции δ подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 – 138). Роль f играет функция δ, в качестве r берется 0, а в качестве h – проектирующая функция I12.
122
5. См. А. И. Мальцев. Алгоритмы и рекурсивные функции. М., 1965, с. 12 и далее.
123
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.
124
7. Имеется в виду работа : А. Church. An Unsolvable Problem of Elementary Number Theory. «American Journal of Mathematics», vol. LVIII, № 2, 1936.
125
8. Характеристической (представляющей) функцией арифметического предиката P (х1, ..., Хn)называется такая арифметическая функция f, что для любого набора аргументов x1, ..., Хn
f(х1, ..., Хn) = (1, если предикат P выполняется на данном наборе) или (0, если P не выполняется на данном наборе.)
Предикат называется примитивно-, обще– или частично-рекурсивным в соответствии с типом характеристической функции.
126
9. В основополагающей статье А. Тьюринга (А. М. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. «Proceedings of the London Mathematical Society», Ser. 2, vol. 42, 1936) была не только изложена его «машина», но и дана попытка проанализировать вычислительный процесс вообще. Обширный фрагмент из этой статьи Тьюринга можно в русском переводе найти в кн.: М. Минскии. Вычисления и автоматы. М., 1971, с. 138—142. Там же читатель найдет подробное описание Тьюринговых машин. Обращаем внимание на то, что наше изложение машины Тьюринга в соответствии с традицией, принятой в современных работах, в ряде непринципиальных пунктов отличается от тьюрингова.
127
10. Отметим, что приведенные нами машины Тьюринга, работающие над целыми положительными числами, служат лишь иллюстрацией тьюринговой формализации вычислительного процесса
128
11. Об упомянутых—и других—видах автоматов можно прочесть в интересной книге М. Г. Гаазе-Рапопорта «Автоматы и живые организмы» (М., 1961)
