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

Одним из известных «ничейных правил» является следующее. Любой цикл выборов (т. е. «ходов»), повторенный трижды, приводит к ничьей. Это правило не является вполне эффективным, так как оно исключает большинство бесконечных последовательностей, но не все.

Другое «ничейное правило» состоит в следующем. Если в течение 40 ходов ни одна пешка не была сдвинута с места и ни одна фигура не была взята (эти операции являются необратимыми в том смысле, что после их осуществления первоначальная позиция уже не может быть восстановлена), то партия считается закончившейся вничью. Легко видеть, что это правило эффективно, хотя соответствующее v* оказывается чудовищно большим.

Замечание 2. С чисто математической точки зрения можно поставить следующий вопрос. Пусть правило остановки эффективно только в том смысле, что невозможно расположить последовательные выборы о*1? о*2> °"з» • • • таким образом, чтобы остановка никогда не наступила. Иначе говоря, пусть всегда существует конечное v, зависящее от а4, сг2, о*3, . . . Гарантирует ли это само по себе существование некоторого фиксированного конечного v*, ограничивающего правило остановки, т. е. такого, что v <С V*?

Этот вопрос является весьма академическим, так как все практические правила игры имеют в виду непосредственное установление v*. (См., однако, предыдущее замечание.) Тем не менее с математической точки зрения он весьма интересен г).

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

Это делается попросту путем такого расширения схемы игры, при котором всегда будут иметься v* ходов оМ, . . ., oSv*. Для любой последовательности о и сг2, о3, ... ничего не меняется вплоть до хода o£v, а все ходы, следующие за qMv, считаются фиктивными. Иначе говоря, если рассматривается ход к = 1, . . ., v*, для последовательности

ai, а2, аз> • • • » где v << то мы делаем оЖк случайным ходом только с одной альтернативой 2), т. е. ходом, на котором ничего не происходит.

Таким образом, предположения, сделанные в начале п. 6.2.1, особенно предположение о том, что v задано с самого начала, оказываются в конечном счете оправданными.

§ 8. МНОЖЕСТВА И РАЗБИЕНИЯ 8.1. Желательность теоретико-множественного описания игры

8.1. Мы получили удовлетворительное и достаточно общее описание понятия игры, которое можно теперь переформулировать с аксиоматической точностью и строгостью и сделать его тем самым основой для последующего математического изучения. Однако прежде чем к этому перейти, представляется заслуживающим внимания дать некоторую другую формулировку. Эта формулировка строго эквивалентна той, к которой мы пришли в предыдущих пунктах, но, будучи высказана в общей форме, является более единообразной и простой; кроме того, она приводит к более изящным и простым обозначениям.

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

х) Ответ на него является утвердительным, т. е. такое v* всегда существует. См., например, D. К б n i g, Uber eine Schlussweise aus dem Endlichen ins Unend-liche, Acta Litt. ac. Sclent, Univ. Szeged, Sect. Mat. 11 I/I I (1927), 121-130, особенно Приложение, стр. 129-130.

2) Это, разумеется, означает, что ах = 1, к% = 0 и рК (1) = 1.

8.2, Множества, их свойства и их графическое представление

8.2.1. Множеством называется произвольная совокупность объектов (на природу и количество которых не накладывается абсолютно никаких ограничений), называемых элементами рассматриваемого множества. Элементы образуют и определяют множество как таковое; никакого упорядочения или отношений иного рода между ними не предполагается. Иначе говоря, если два множества А и В таковы, что любой элемент А является также элементом В и наоборот, то эти множества тождественны во всех отношениях, т. е. А = В. Тот факт, что а является элементом множества А у мы выражаем также, говоря, что а принадлежит А г).

Нас будут интересовать главным образом (хотя и не всегда) только конечные множества, т. е. множества, состоящие из конечного числа элементов.

Пусть даны произвольные объекты а, 3, у, . . .; множество, элементами которого они являются, будет обозначаться через (а, (3, 7, . . .). Будет также удобно ввести множество, которое вовсе не содержит элементов,- пустое множество 2). Мы будем обозначать пустое множество через 0. В частности, мы можем образовывать множества, состоящие в точности из одного элемента,- одноэлементные множества. Одноэлементное множество (а) и его единственный элемент а представляют собой вовсе не одно и то же и поэтому никогда не должны смешиваться 3).

Подчеркнем еще раз, что элементами множества могут быть любые объекты. Разумеется, мы ограничимся математическими объектами. Эти элементы вполне могут быть, например, множествами, что приведет к рассмотрению множеств множеств и т. д. Последние нередко называются, например, системами или классами множеств, хотя это и не обязательно.

8.2.2. Перечислим основные понятия и операции, связанные с множествами.

(8:А:а) А является подмножеством В (В является надмножеством А), если любой элемент А является также элементом В. Символически это записывается в виде А В или В з А. А является собственным подмножеством В, а В - собственным надмножеством Ау если сказанное выше верно, но В содержит элементы, не являющиеся элементами А. В символах: А а В или В zd А. Мы видим, что если А является подмножеством В ж В является подмножеством А, то А =В. (Это представляет собой переформулировку принципа, высказанного в начален. 8.2.1.) Отметим еще, что А является

х) Математическая литература по теории множеств весьма обширна. Мы не будем пользоваться ею в пределах, выходящих за рамки изложенного в тексте. Заинтересованный читатель найдет больше сведений по теории множеств в хорошем вводном курсе: A. Fraenkel, Einleitung in die Mengenlehre, Berlin, 1928, а также в сжатой и технически превосходной книге F. Hausdorff, Mengenlehre, 2nd Edit, Leipzig, 1927 (рус. пер. Ф. Хаусдорф, Теория множеств, ОНТИ, 1937).

2) Если два множества А и В оба не содержат элементов, то мы можем сказать, что они содержат одни и те же элементы. Следовательно, в силу сказанного выше А = = В. Иначе говоря, существует только одно пустое множество. Это рассуждение может показаться странным, но тем не менее оно безупречно.

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

собственным подмножеством В в том и только в том случае, когда А является подмножеством В и не имеет места равенство А = В.

(8:А:Ь) Суммой или объединением двух множеств А и В называется множество всех элементов А вместе со всеми элементами В. Объединение А и В будет обозначаться через A (J В. Аналогично образуются объединения более чем двух множеств 1).

(8:А:с) Произведением или пересечением двух множеств А и В называется множество всех общих элементов А и В. Пересечение А и В будет обозначаться через A f В. Аналогично образуются пересечения более чем двух множеств 1).

(8:A:d) Разностью двух множеств А и В называется множество всех тех элементов А, которые не принадлежат В. Разность А и В будет обозначаться через А - В *).

(8:А:е) Если В является подмножеством А, то мы будем называть разность А - В дополнением В в А. Иногда будет настолько очевидным, какое множество А имеется в виду, что мы будем писать просто -В и говорить просто о дополнении множества В без всяких дальнейших уточнений.

(8:A:f) Два множества А и В называются непересекающимися (дизъюнктными), если они не имеют общих элементов, т. е. если А (\В = 0.

(8: A:g) Система (множество) А множеств называется системой попарно непересекающихся множеств, если все пары различных элементов системы Л представляют собой дизъюнктные множества, т. е. для А, В £<Л из А ф В следует А [\ В = 0.

8.2.3. Здесь могут оказаться полезными некоторые графические иллюстрации.

Мы будем обозначать объекты, являющиеся в этих рассмотрениях элементами множеств, точками (рис. 1). Множество будет обозначаться путем обведения принадлежащих ему точек (элементов), причем обозначающий множество символ будет писаться в разрыве обводящей линии в одном или в Рис. 1. нескольких местах. Изображенные на

рис. 1 множества А и С являются непересекающимися, а множества А и В таковыми не являются.

С помощью этого приема можно проиллюстрировать также понятия объединений, пересечений и разности множеств (рис. 2). На этом рисунке

х) Эта терминология (суммы, произведения, разности) является традиционной. Она основана на некоторых алгебраических аналогиях, которые мы здесь использовать не будем. В действительности алгебра этих операций \J, f» известная под названием булевой алгебры, имеет большой самостоятельный интерес. См., например, А. Т а г s k i, Introduction to logic, New York, 1941, а также G. В i r kh о f f, Lattice theory, New York, 1940 (русский перевод: Г. Б и p к г о ф, Теория структур, М., ИЛ, 1952). Последняя книга представляет большой интерес для понимания современного абстрактного метода. Гл. VI посвящена булевым алгебрам; там же указана дальнейшая литература.