markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 5

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

Главы состоят из параграфов. Параграфы делятся на пункты, которые иногда имеют подпункты. Нумерация параграфов в книге сквозная. В книге принята система ссылок, аналогичная той, которая использовалась в монографии [21. В каждом пункте (подпункте) отдельно нумеруются предложения н отдельно — формулы. Номера формул выписываются слева от них в круглых скобках. При номере утверждения повторяется отделяемый точкой номер пункта (подпункта). Полная ссылка на утверждение состоит из указания параграфа, номера пункта (а также подпункта, если он имеется) *) Классики теории миочкеств отчетливее, чем в наше время, понимали, чтп развиваемая ими система взглядов ие есть простая совокупность апре.

делений, лемм, теорем и т. д., а что пиа представляет забой определеиипе мирпппиимаиие, учение. Знаменитая книга Ф. Хаусдпрфа, переведенная иа русский язык под названием «Теория миогкествь в подлиннике называется именно «Мепееп!еьге». Этим же термином пользовался и сам Г. Кантор. 'е) 08 етом см., например, Н. уи Ш а и и и ! !1, $7, ПРЕДИСЛОВИЕ и номера утверждения, которые отделяются друг от друга точками, а вся ссылка заключается в прямые скобки. Например, [$18.9.31 означает ссылку на утверждение 3 пункта 9 параграфа 18; при ссылке на утверждение того же параграфа номер параграфа опускается. Аналогично делаются ссылки на параграфы, пункты н на формулы, с той лишь разницей, что точка перед заключенным в скобки номером формулы не ставится и что при ссылке на формулу того же пункта (подпункта) опускается его номер.

Несколько одновременно делаемых ссылок отделяются друг от друга запятыми н заключаются в общие прямые скобки. Литературные источники нумеруются для каждого автора (нлн группы авторов) отдельно. Н. А. Шанин и Б. А. Кушнер внимательно прочли рукопись книги и сделали большое количество критических замечаний, в основном мною учтенных и способствовавших устранению многих недочетов изложения. Я имел с ними продолжительные беседы, в результате которых у меня устоялось окончательное мнение по ряду важных для книги вопросов.

Я сердечно благодарю Николая Александровича и Бориса Абрамовича за их дружескую помощь. Мне хотелось бы особо подчеркнуть, что фактическое воздействие Н. А. Шанина на окончательную редакцию книги носит гораздо более значительный характер, чем это следует из сказанного выше. В свое время Н. А. Шанин принимал непосредственное участие в формировании многих представлений, нашедших отражение в кинге. Что же касается меня как одного из ее авторов, то, начиная еще с тех пор, когда я был студентом, я многое узнал от Николая Александровича и многому у него научился. В том или ином виде это нашло отражение в части текста, написанной мною.

Отдельные части рукописи прочли и сделали существенные замечания В. И. Хомич и И. Д. Заславский. Я дружески благодарю нх за это. Ряд деталей общего плана книги я обсуждал с С. И. Адяном, В. К. Детловсом, А. Г. Драгалиным и Б. А. Кушнером. Всем им я выражаю глубокую признательность за ик советы, которые оказались для меня в высшей степени полезными. Особого упоминания и благодарности заслуживает деятельная инициатива Сергея Ивановича Адяна, которая немало ПРЕДИСЛОВИЕ :пособствовала тому, что книга была дописана до конца и опубликована.

Работа над книгой совпала для меня с завершеннем работы над переводом «Оснований математики» вЂ” великого труда Гильберта н Бернайса. Два эти дела, переплетаясь во времени и по существу, взаимодействовали между собой н оказали друг на друга благотворное влияние. В целом это составило большой период моей жизни. Семье, близким друзьям, коллегам по работе и всем остальным, кто в это время оказывал мне поддержку, я выражаю мою горячую и глубокую благодарность. Н. М. Нагорный ВАЖНЕЙШИ Е ОБОЗНАЧЕНИЯ Р ль() Р22Е [Р, Е) 7' 3 (Р-Е) (Р ()) [РА [Рд [Р« [р" [Р [х [)их Р*Е*)7 2(Р, 1),)7) Асв (АОБ) (А'~Б) А» А» А» 'Л: Р)-4« 71:Р [- 0 25 29 29 66 31 84 84 88 86 291 69 200 111 111 97 105 73 73 73 282 З05 Зоз 119, 139 119, 139 й;Р ) й: Р[=() 2(:Р=.0 а:Р~=д-) П:Р~с) Й (Р) 1й(Р) (П: Р) 2( (К ь 2)) (Й 2)) (21'('ю [(1) (»(О Б) ««н й» й~ %;Р[ (7 2(:Р!! д Р[-Е Р'="(7 РИ(7 й п !19, 139 126, 139 128, !39 128, 139 128, 139 140 !29, !39 131, 139 197 217 224 230 244 281 297 334 345 346 353 353 353 З72 372 ГЛАВА 1 ВВЕДЕНИЕ.

ОСНОВНЫЕ ПРИНЦИПЫ КОНСТРУКТИВНОЙ СЕМАНТИКИ й !. Конструктивные нроцессы и конструктивные объекты 1. Простым примером конструктивного процесса является построение ряда вертикальных черточек [[![[! путем писания одной такой черточки, приписывания к ней справа ее копии — другой черточки, приписывания к полученным черточкам еще одной черточки, затем еще одной черточки, затем еще одной и еще одной.

Результатом этого конструктивного процесса является конструктивный объект, изображенный шестью строками выше, Сам этот конструктивный объект представляет собой материальное тело, состоящее из бумаги и засохших чернил, а приведенный выше рисунок есть состоящая из бумаги и засохшей типографской краски копия этого конструктивного объекта. Она тоже есть конструктивный объект, поскольку изготовление копии можно считать конструктивным актом. Ряды вертикальных черточек вроде нашего рисунка, включая и „пустой" ряд, в состав которого не входит ни одна черточка (его можно представить себе в виде чистого листа бумаги), мы будем называть натуральными числами.

Введенные таким образом натуральные числа суть конструктивные объекты. Натуральное число, представленное нашим рисунком, называется «шесть» и иногда изображается арабской цифрой «6». Натуральное число, представленное пустым рядом черточек, называется «нулем» и изображается цифрой «О». 2. Натуральные числа строятся из одинаковых элементарных знаков — вертикальных черточек.

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

Результирующий конструктивный объект будет в этом случае рядом элементарных знаков. Как и в предыдущем случае, будет удобно включить в 4 М КОНСТРУКТИВНЫЕ ПРОПЕССЫ И ОБЪЕКТЫ 25 24 !Тл. ВВЕДЕНИЕ рассмотрение „пустой" ряд знаков, т. е. ряд, не содержащий в своем составе ни одного знака. Элементарные знаки, участвующие в такого рода построениях, мы будем называть буквами. Такое определение буквы, конечно, не может претендовать на точность.

Но своеобразие нашей ситуации как раз и будет заключаться в том, что мы не станем определять это понятие каким-либо традиционным способом, например ачерез ближайший род и видовое отличие». Просто всякий раз, начиная то или иное конкретное рассмотрение, мы будем договариваться считать такие-то и такие-то знаки элементарными, имея в виду, что остальные требующиеся нам выражения будут строиться из них как из составных частей. Соответствующие соглашения обычно досгнгаются без труда. Что же касается вопроса «что такое буква вообще1», то ответа на него, пригод.

ного на все могущие представиться воображению случаи, мы за ненадобностью не предлагаем. Ситуация несколько смягчается тем обстоятельством, что на самом деле можно обойтись использованием всего лишь двух различных букв, кодируя остальные с их помощью. Впоследствии читатель убедится в этом, ознакомившись с материалом, изложенным в пп. 1 — 4 2 41. Однако по чисто техническим соображениям удобства мы бы не хотели заниматься этим с самого начала.

Для осуществления конкретного конструктивного процесса может потребоваться заранее не оцениваемое количество экземпляров одной и той же буквы. Ввиду этого обстоятельства мы уславливаемся считать, что в начале всякого рассмотрения у нас будут фиксироваться некоторые „эталоны" участвующих в нем букв и что с этих эталонов по мере надобности будут сниматься копии. Снятие копии мы всякий раз будем считать конструктивным актом. Обыкновенно в качестве букв используются буквы каких- нибудь распространенных алфавитов (латинского, греческого, русского и т. и.), а также знаки научной символики.

По-видимому, не встретило бы возражений предложение считать буквами знаки (,а, Ь,«С),(),+ ° Ф щ (здесь запятая отделяет буквы одну от другой и сама буквой не считается; круглые скобки, напротив, выступают в роли букв). При выборе букв мы всегда будем следить за тем, чтобы, рассматривая любые две из ннх, можно было с уверенностью констатировать, что они одинаковы или различиы.

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

Можно, например, условиться писать буквы алфавита „в строку", отделяя их друг от друга запятой и заключая всю запись в целом в какие-нибудь специально для этого выделенные скобки— например, фигурные. Примером алфавита мог бы служить следующий, уже рассматривавшийся нами список букв; (), а, Ь, «, Д, (,), +, 4Ь, щ). 4. Буквы, входящие в состав какого-либо алфавита, мы будем называть буквами этого алфавита.

Ряды букв данного алфавита мы будем называть словами в эпюм алфавите. В частности, пустой ряд букв мы будем называть пустым словом и будем обозначать его заглавной буквой Л греческого алфавита. Пустое слово есть слово в любом алфавите. Мы специально подчеркиваем, что слова в алфавитах, вводимые нами как конструктивные объекты, т. е. как результаты некоторых построений, только так и будут трактоваться в дальнейшем. Мы не будем позволять себе — считая их слишком сильными — таких актов воображения, когда процесс построения всех слов в данном алфавите (принципиально незавершаемый!) считается, тем не менее, протекшим „до конца", завершившимся, в результате чего возникает новый объект рассмотрения — множество всех слов в данном алфавите, так что слова в данном алфавите суть элементы этого множества.