§ 4. Разбиение множества на подмножества. Отношение эквивалентности

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

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

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

Множество спортивных команд данного города состоит, вообще говоря, из пересекающихся множеств, так как одно и то же лицо может входить в несколько спортивных команд (например, в команду пловцов и в команду волейболистов или лыжников).

Замечание. Для облегчения речи иногда вместо выражения «множество множеств» употребляются как совершенно равнозначащие выражения «система множеств» или «совокупность множеств».

2. Разбиение на классы. Очень важный класс систем множеств получаем, если рассматриваем всевозможные разбиения какого-нибудь множества на попарно не пересекающиеся множества. Дано множество X, представленное в виде суммы попарно не пересекающихся подмножеств; множества, слагаемые нашей суммы, и являются элементами данного разбиения множества X.

Пример 1. М есть множество всех учащихся в средних школах Москвы. Множество М можно разбить на попарно не пересекающиеся подмножества, например, следующими двумя способами:

1) мы объединяем в одно слагаемое всех учащихся одной и той же школы (т. е. разбиваем множество всех учащихся по школам);

2) мы объединяем в одно слагаемое всех учащихся одного и того же класса (хотя бы и разных школ).

Пример 2. Пусть X есть множество всех точек плоскости; возьмем на этой плоскости какую-нибудь прямую g и разобьем всю плоскость на прямые, параллельные прямой g. Множества точек каждой такой прямой и являются теми подмножествами, на которые мы разбиваем множество X.

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

Теорема 3. Пусть дано отображение f множества А на множество В. Полные прообразы всевозможных точек b множества В образуют разбиение множества А на классы. Множество этих классов находится во взаимно однозначном соответствии с множеством В.

Эта теорема, в сущности, очевидна: каждому элементу а множества А соответствует, в силу отображения, один и только один элемент множества В, так что а входит в один полный прообраз . А это и значит, что полные прообразы точек во-первых, дают в сумме все множество А, во-вторых, попарно пересекаются.

Множество классов находится во взаимно однозначном соответствии с множеством В: каждому элементу b множества В соответствует класс и каждому классу соответствует элемент b множества В.

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

Доказательство теоремы уже заключено в самой ее формулировке.

Пример. Тем самым, что учащиеся Москвы распределены но школам, уже установлено отображение множества А всех учащихся на множество В всех школ: каждому учащемуся соответствует та школа, в которой он учится.

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

3. Отношение эквивалентности. Пусть дано разбиение множества X на классы. Введем следующее определение: назовем два элемента множества X эквивалентными по отношению к данному разбиению множества X на классы, если они принадлежат к одному и тому же классу.

Таким образом, если мы разобьем учащихся Москвы по школам, то двое учащихся будут «эквивалентны», если они учатся в одной и той же школе (хотя бы и в разных классах). Если же мы разобьем учащихся по классам, то двое учащихся будут «эквивалентны», если они учатся в одном и том же классе (хотя бы и различных школ).

Отношение эквивалентности, только что определенное нами, очевидно, обладает следующими свойствами.

Свойство симметрии (или взаимности). Если а и b эквивалентны, то эквивалентны также и а.

Свойство транзитивности (или переходности). Если эквивалентны элементы а и а также b и с, то а и с эквивалентны («два элемента а и с, эквивалентные третьему эквивалентны между собою»).

Наконец, мы считаем каждый элемент эквивалентным самому себе; это свойство отношения эквивалентности называется свойством рефлексивности.

Три условия; рефлексивности, симметрии и транзитивности, которым подчинено отношение эквивалентности, называются условиями или аксиомами эквивалентности (а также аксиомами равенства).

Итак, всякое разбиение данного множества на классы определяет между элементами этого множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности.

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

Докажем, что это отношение эквивалентности определяет разбиение множества X на классы.

В самом деле, обозначим классом данного элемента а множестиа X множество всех элементов, эквивалентных элементу а.

В силу того, что наше отношение эквивалентности по предположению обладает свойством рефлексивности, каждый элемент а содержится в своем классе.

Докажем: если два класса пересекаются (т. а. имеют хоть один общий элемент), то они непременно совпадают (т. е. каждый элемент одного класса является в то же время элементом другого).

В самом деле, пусть классы имеют общий элемент с. Записывая эквивалентность двух каких-нибудь элементов х и у так: имеем по определению классов:

Следовательно, в силу симметрии с силу транзитивности

Пусть у — какой-нибудь элемент класса Имеем;

Значит, в силу транзитивности и (1)

т. е. у есть элемент класса .

Пусть теперь какой-нибудь элемент класса Имеем:

и по симметрии

а в силу (1) и по транзитивности

Вследствие симметрии

т.е. х принадлежит к классу .

Таким образом, два класса имеющие общий элемент с, действительно совпадают между собой.

Мы доказали, что различные классы образуют систему попарно не пересекающихся подмножеств множества X. Далее, классы в сумме дают все множество X, так как каждый элемент множества X принадлежит к своему классу.

Повторим еще раз доказанные выше результаты, объединив их в следующее предложение.

Теорема 5. Каждое разбиение на классы какого-нибудь множества X определяет между элементами множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности. Обратно: каждое отношение эквивалентности, установленное между элементами множества X и обладающее свойствами симметрии, транзитивности и рефлексивности, определяет разбиение множества X на классы попарно эквивалентных между собой элементов.