19. Appel K., Haken W. Every planar map is four colorable. Part II: Reducibility // Illinois Journal of Mathematics. 1977. Vol. 21. № 3. Pp. 491–567.
20. Appel K., Haken W. The solution of the Four-Color-Map problem // Scientific American. 1977. Vol. 237. № 4. Pp. 108–121.
21. Успенский В. А. Теорема Гёделя о неполноте. – М.: Физмат-лит, 1982. – 111 с.
22. Плиско В. Е. Теорема // Математическая энциклопедия. Т. 5. – М.: Сов. энциклопедия, 1985. Стлб. 334–335.
23. Толстиков А. В. Ферма теорема // Математическая энциклопедия. Т. 5. – М.: Сов. энциклопедия, 1985. – Стлб. 605–608.
24. Козырев В. П., Юшманов С. В. Теория графов (Алгоритмические, алгебраические и метрические проблемы) // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. 1985. Т. 23. С. 68–117.
25. Кусраев А. Г., Кутателадзе С. С. Субдифференциалы и их применения: Учеб. пособие. – Новосибирск: Новосиб. гос. ун-т, 1985. – 86 с.
26. Уроки открывает беседа с математиком Л. Понтрягиным: Интервью академика Л. С. Понтрягина «Учительской газете» // Учительская газета. 1985. 23 мая.
27. Cantor G. Ein Beitrag zur Mannigfaltigkeitslehre // Journal für die reine und angewandte Mathematik. 1878. Bd. 84. S. 242–258. (Русский перевод см. в работе [30, с. 22–35].)
28. Cantor G. Über unendliche, lineare Punktmannigfaltigkeiten. Nr. 6 // Mathematische Annalen. 1884. Bd. 23. H. 4. S. 453–488. (Русский перевод см. в работе [30, с. 106–139].)
29. Cantor G. Gesammelte Abhandlungen. Berlin: Springer, 1932. 486 S.
30. Кантор Г. Труды по теории множеств / Пер. с нем. Ф. А. Медведева, П. С. Юшкевича; Отв. редакторы А. Н. Колмогоров, А. П. Юшкевич. – М.: Наука, 1985. – 430 с.
31. Cox D. A. Introduction to Fermat's Last Theorem // American Mathematical Monthly. 1994. Jan. Pp. 3–14.
32. Сингх С. Великая теорема Ферма / Пер. с англ. – М.: МЦНМО, 2000. – 288 с. (Оригинальное издание: Singh S. Fermat's Last Theorem. L.: Fourth Estate, 1997.)
33. Thomas R. An update on the Four-Color Theorem // Notices of the American Mathematical Society. 1998. Vol. 45. № 7. Pp. 848–859.
34. Самохин А. В. Проблема четырёх красок: неоконченная история доказательства // Соросовский образовательный журнал. 2000. Т. 6. № 7 (56). С. 91–96.
Приложение
Проблема континуума и языки второго порядка
На языке второго порядка можно написать такую систему аксиом, что наличие или отсутствие у неё модели будет равносильно соответственно подтверждению или опровержению континуум-гипотезы. А если соединить все эти аксиомы знаком конъюнкции, то возникнет формула второго порядка, которая тогда и только тогда имеет модель, когда континуум-гипотеза справедлива; такая формула и была обещана в главе 4, в конце четвёртого размышления. Указанную систему аксиом мы и намерены выписать в настоящем приложении.
Пусть множество M обладает следующими свойствами: 1) его мощность континуальна; 2) в нём выделено некоторое такое подмножество Q счётно-бесконечной мощности, что всякое подмножество множества, содержащее, в свою очередь, Q в качестве подмножества, имеет мощность либо счётно-бесконечную, либо континуальную. Легко проверить, что возможность такого множества равносильна подтверждению континуум-гипотезы. Поэтому всякое такое M временно условимся называть подтверждающим. Наша цель – выписать систему аксиом, задающую подтверждающее множество. Для этого мы воспользуемся следующей теоремой из теории упорядоченных множеств: всякое линейно упорядоченное множество, обладающее плотным в нём счётно-бесконечным подмножеством и такое, что любое его сечение дедекиндово, имеет мощность континуума. (Напомним, что сечением линейно упорядоченного множества называется такое его разбиение на два класса, нижний и верхний, что любой элемент нижнего класса предшествует любому элементу верхнего класса. Сечение называется дедекиндовым, если либо в нижнем классе есть наибольший элемент, либо в верхнем классе есть наименьший элемент, но не то и другое вместе.) Система аксиом, которую мы собираемся выписать, как раз и задаст нам в качестве подтверждающего такое линейно упорядоченное множество, причём в роли Q выступит подмножество, плотное в M. (Подмножество A упорядоченного множества B называется плотным в B, коль скоро для любых двух различных элементов из B найдётся элемент из A, расположенный между ними.)
Но прежде чем выписывать аксиомы, необходимо указать сигнатуру. Наша сигнатура имеет четыре члена. Она состоит из константы «0Q», имени «Q» одноместного отношения (т. е. свойства), имени двуместного отношения и имени «'» одноместной операции. Об этих членах сигнатуры не требуется знать ничего, кроме того, что будет записано в аксиомах.
Как известно, носителем модели называется множество её элементов. Все операции и отношения модели считаются заданными на её носителе.
Начнём выписывать аксиомы, попутно их комментируя.
Аксиомы H1–H3 утверждают, что отношение представляет собою строгий линейный порядок, определённый на носителе модели. Таким образом, этот носитель оказывается линейно упорядоченным множеством.
Аксиома H4 утверждает, что линейный порядок на носителе является дедекиндовым. (Сечение образуется областями истинности свойств P и ¬P.)
Аксиома H5 утверждает, что между любыми двумя элементами носителя найдётся элемент из области истинности свойства Q (т. е. из множества тех элементов носителя модели, которые обладают этим свойством). Иначе говоря, аксиома утверждает, что эта область плотна в носителе.
Аксиомы H6–H10 гарантируют счётную бесконечность области истинности свойства Q. В самом деле, аксиомы H6 и H7 означают, что элемент 0Q принадлежит области истинности свойства Q, а операция «'» не выводит за пределы этой области. Аксиомы H8 – H10 напоминают аксиомы Пеано I–III; их можно было бы назвать «аксиомами Пеано» для области истинности свойства Q. Эта область истинности, следовательно, представляет собою один из натуральных рядов (со строчной буквы, разумеется). Поэтому она, эта область, счётно-бесконечна.
Аксиома Н11 (последняя) утверждает нечто о произвольном надмножестве области истинности свойства Q; в аксиоме это надмножество фигурирует в качестве области истинности свойства W. А именно: H11 утверждает, что всякое такое надмножество находится во взаимно однозначном соответствии либо с носителем модели, либо с областью истинности свойства Q. В первом случае оно континуально, во втором – счётно-бесконечно. Соответствие, о котором идёт речь, представлено функцией φ, которая взаимно однозначно отображает область истинности свойства W либо на весь носитель, либо на область истинности свойства Q.
Математика языка
[170]
Правильно говорить на каком-либо языке, в частности на русском, можно, конечно, и не зная математики. Но вот для того, чтобы дать языку научное описание, математика оказывается полезной, а в XXI в., пожалуй, что и необходимой. Посмотрите на эту книгу[171]. Она называется «Математические методы в лингвистике». Даже вкратце обозреть её содержание, конечно, невозможно. Но можно обратить внимание на её толщину. Издана она известным издательством Kluwer и является наглядным свидетельством того, сколь серьёзно сейчас в мире понимается связь математики с лингвистикой.
Попробуем уловить эту связь на конкретных примерах.
Все знают, что в русском языке шесть падежей: именительный, родительный, дательный, винительный, творительный, предложный. Такова традиция. Этому учат в школе. Поэтому эти шесть падежей будем именовать школьными или традиционными.
Когда слово меняет свой падеж, происходит изменение его формы; изменение, в частности, может состоять и в том, что форма слова остаётся прежней: у слова кровать, например, совпадают формы именительного и винительного, а у слова кофе – вообще все формы. Изменение форм данного слова по всем падежам называется его склонением; обычно термином «склонение» обозначают изменение слова не только по падежам, но и по числам, но мы для простоты «забудем» на некоторое время о существовании множественного числа и будем рассматривать слова лишь в единственном числе. Вот, например, склонение слова сахар: им. п. сахар, род. п. сахара, вин. п. сахар, дат. п. сахару, тв. п. сахаром, предл. п. о сахаре. Все эти формы: сахар, сахара, сахару, сахаром, сахаре – называются словоформами слова сахар; словоформы часто называют просто словами.
Спросим себя, какой падеж у словоформы сахару. В только что приведённом списке словоформ указано, что это дательный падеж. Теперь посмотрим на фразу
(1) Положить тебе ещё сахару?
Согласится ли любезный читатель, что у слова сахару здесь дательный падеж? Ведь дательный падеж, как известно, отвечает на вопрос Кому?/Чему?. Здесь же слово сахару отвечает на вопрос Чего?. Но на вопрос Чего? отвечает родительный падеж. Но формой родительного падежа для слова сахар служит слово (форма) сахара. Как же быть?
Отложим ответ на заданный вопрос и рассмотрим похожую ситуацию. Самая знаменитая детская песенка начинается со слов
(2) В лесу родилась ёлочка…
В каком падеже здесь слово лесу? Судя по окончанию – в дательном. Однако сразу возникают две трудности, препятствующие тому, чтобы радостно принять этот ответ. Первая трудность аналогична той, которую мы видели в примере (1) со словом сахару. Дательный падеж у слова лес должен отвечать на вопрос Кому?/Чему?, как, например, во фразе
