Главная > Математика > Введение в теорию игр
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Геометрическое обоснование

Евклидовым -мерным пространством (обозначим его ) мы будем называть множество всех упорядоченных систем n чисел , где — действительные числа. Если — две точки множества , то мы определяем расстояние между формулой

Подмножество множества называется ограниченным, если существует такое число М, что для всех точек и из

Легко доказать, что необходимым и достаточным условием ограниченности множества является нахождение его в некоторой гиперсфере, т. е. существование точки а множества и числа R таких, что для всякого

Назовем точку пространства предельной тонкой подмножества А из если для всякого положительного существует точка отличная от и такая, что .

Так, если А есть множество точек пространства для которых

то любая точка для которой выполняется равенство

есть предельная точка множества А. Следует обратить внимание, что конечное множество точек не имеет предельных точек: С другой стороны, всякое ограниченное бесконечное множество точек имеет по меньшей мере одну предельную точку.

Замыканием множества называется множество, полученное путем добавления к данному множеству всех его предельных точек. Так, замыкание множества А упомянутых выше точек есть множество точек пространства таких, что

Конечное множество совпадает со своим замыканием. Множество называется замкнутым, если оно совпадает со своим замыканием. Таким образом, всякое конечное множество замкнуто, так же как, например, множество, состоящее из всех точек пространства для которых

Множество открытым, если его дополнение замкнуто. Так, множество А, упомянутое выше, открыто.

Некоторые множества не являются ни открытыми, ни замкнутыми. Множество точек х пространства , для которых

не открыто и не замкнуто.

Внутренняя часть множества есть дополнение замы кания его дополнения. Следовательно, внутренней частью множества точек х пространства , для которых , является множество точек х пространства таких, что . Внутренней частью любого конечного множества является пустое множество. Легко видеть, что замыкание любого множества замкнуто и внутренняя часть любого множества открыта. Дополнение любого замкнутого множества открыто, а дополнение любого открытого множества замкнуто.

Множество для любого n открыто и замкнуто, и то же справедливо для пустого множества; это единственные множества, которые и открыты, и замкнуты.

Границей множества мы называем пересечение его замыкания с замыканием его дополнения. Так, границей упомянутого выше множества А является множество всех точек пространства таких, что

Если В естй множество всех точек пространства таких, что х и у суть рациональные числа, то граница множества есть все пространство .

Множество называется связным, если его нельзя представить в виде суммы двух непересекающихся множеств, ни одно из которых не содержит предельной точки другого. Так, упомянутое выше множество А — связное; то же справедливо, например, для множества всех точек пространства , для которых

Если С есть множество всех точек пространства , для которых х, то множество С не связное; действительно, если есть множество всех точек для которых есть множество всех точек , для которых х < 0, то С есть сумма множеств и , и ни одно из множеств не содержит предельной точки другого.

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

Пусть

и

суть точки пространства ; — элемент множества (т.е для и ); предположим еще, что

Тогда мы будем говорить, что есть выпуклая линейная комбинация точек с весами и, записывать это так:

Так, например, точка пространства есть выпуклая линейная комбинация точек и с весами и

Аналогично точка пространства есть выпуклая линейная комбинация точек и с весами и

Мы называем подмножество X пространства выпуклым, если всякая выпуклая линейная комбинация точек множества X есть точка множества X.

Так, множество А, состоящее из всех точек , таких, что

и множество В, состоящее из всех точек , таких, что

оба выпуклые. Множество С, состоящее из всех точек , таких, что

и множество D, состоящее из всех точек , таких, что

оба не выпуклые; действительно, точка есть выпуклая линейная комбинация (с весами ) точек и которые принадлежат и множеству С и множеству D; сама же точка ||0 0|| не принадлежит ни к С, ни к D.

Мы определили выпуклое множество как множество X, такое, что когда — элементы множества X и принадлежит , то и

принадлежит X. Однако легко показать, что для того, чтобы множество было выпуклым, необходимо и достаточно, чтобы вышеуказанное условие выполнялось для ; таким образом, множество X выпуклое, если всегда, когда и принадлежат X и принадлежит ,

тоже принадлежит X.

Выпуклой оболочкой множества X называется пересечение всех выпуклых множеств, подмножеством которых является X. Так, выпуклой оболочкой множества D всех точек , таких, что

является множество всех точек , таких, что

Выпуклой оболочкой множества всех точек , таких, что

является вся плоскость .

Поскольку пространство выпуклое, очевидно, любое множество содержится по меньшей мере в одном выпуклом множестве, и, следовательно, любое множество имеет выпуклую оболочку. Нетрудно показать, что выпуклая оболочка множества X состоит как раз из тех точек, которые являются выпуклыми линейными комбинациями точек множества X. В этом разделе мы не будем приводить ни одного доказательства, так как теория выпуклых множеств представляет лишь математический подготовительный аппарат к теории игр. Теорема Френкеля, которую мы здесь приводим, не будет использована в этой главе, на она нам будет необходима позднее при доказательстве теоремы

Теорема 2.1. Если X есть некоторое подмножество пространства то любая точка выпуклой оболочки подмножества X может быть представлена как выпуклая линейная комбинация n + 1 точек из X. Если, кроме того, подмножество X связно, то любая точка выпуклой оболочки подмножества X может быть представлена как выпуклая линейная комбинация n точек X.

Замечание 2.2. Для пояснения теоремы допустим, что X состоит из четырех точек и пространства то есть X состоит из четырех вершин квадрата (рис. 1). Тогда выпуклой оболочкой X, очевидно, является весь квадрат, включая его границу. Каждую точку треугольника можно представить как выпуклую линейную комбинацию трех точек а, b и d, и аналогично любую точку треугольника можно представить как выпуклую линейную комбинацию трех точек b, с и d. Точка , не находящаяся ни на границе квадрата, ни на одной из диагоналей ас и bd, не может быть представлена как выпуклая линейная комбинация двух точек подмножества X.

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

Пусть суть n действительных чисел, не все равные нулю, и пусть b — какое-нибудь действительное число; тогда множество точек пространства таких, что

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

есть гиперплоскость пространства . Гиперплоскость пространства есть обычная плоскость, гиперплоскость пространства прямая, а гиперплоскость пространства есть точка.

Если

— уравнение гиперплоскости, то под двумя полупространствами, соответствующими данной гиперплоскости, будем подразумевать множество точек , удовлетворяющих условию

и множество точек удовлетворяющих условию

Очевидно, гиперплоскость и два полупространства не пересекаются, и их сумма есть . Сформулируем теперь теорему, которая будет использована позднее в этой главе.

Рис. 1.

Теорема 2.3. Пусть X — любое замкнутое выпуклое подмножество пространства , и пусть — точка пространства не принадлежащая множеству X; тогда существует гиперплоскость содержащая такая, что X есть подмножество одного из полупространств, определенных гиперплоскостью .

В заключение этого параграфа мы введем еще одно понятие и сформулируем теорему, которая будет использована в главе III.

Если X есть подмножество пространства , то экстремальным множеством называется множество точек х, принадлежащих X, которые не могут быть представлены в виде

где и — различные точки множества X.

Таким образом, экстремальным множеством замкнутого круга ( т. е. круга вместе с его границей) является граница круга. Экстремальное множество замкнутого треугольника есть множество, состоящее из трех вершин треугольника.

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

Теорема 2.4. Пусть X — непустое ограниченное замкнутое выпуклое подмножество пространства . Тогда К(X) — непустое множество, а X есть выпуклая оболочка множества К(X).

<< Предыдущий параграф Следующий параграф >>
Оглавление