1.3. Разбиение множеств

Понятие разбиения множества. Пусть А - множество учеников некой школы. Обозначим А₁ множество учеников первого класса, А₂ -множество учеников второго класса и т. д., А₁₀-множество учеников десятого класса этой школы. Ясно, что А₁А_2А₁₀- подмножество множества А, причем каждое из них не пусто ( в каждом классе, конечно, есть ученики), они попарно не имеют общих элементов (не может же один и тот же человек учиться одновременно в двух разных классах) и объединение всех равно А.

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

Таким образом, в примере рассмотренном выше, совокупность подмножеств А₁,А₂А₁₀ образует разбиение множества А.

Если, например, А=1, 2, 3, 4, 5, 6, то совокупность подмножеств 1, 3, 2, 4, 6, 5 множества А образует его разбиение, а его совокупность таких подмножеств 1,2,3,4,5,3,6 разбиения не образует, ибо два из них имеют общий элемент.

Итак, выражаясь образно , под разбиением множества мы будем понимать "разбиение" его на части , подмножества. Ясно ,что одно и тоже множество "разбить" на части можно по-разному. Так, например, если В=a, b, c, d, e, f,то совокупности его подмножеств a, b, c,d, e, f, g,иa, b,c, d,e, f, gобразуют его разбиения, но различные т.е. В " разбито" на подмножества по-разному.

Разбиения будем обозначать строчными буквами греческого алфавита:,, и т.д.

Классы разбиения. Пусть М-множество и -некоторое его разбиение. Каждое из подмножеств совокупности, образующей разбиение, называется классом разбиения.

Так, например, если В=a, b, c, d, e, f, g и -разбиение множества В, образованное совокупностью его подмножеств a, b, e, d, f, c, g,то каждое из этих подмножеств является классом данного разбиения .

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

В одном и том же классе разбиения  множества М может содержаться несколько (и даже бесконечно много) элементов из М. Если элементы x, yМ принадлежат одному и тому же классу данного разбиения  , то этот факт мы будем обозначать следующим образом: xy(). Например, для рассмотренного выше разбиения  множества В можно записать ab(), de(),, а запись cd() неверна , ибо c и dпринадлежат различным классам разбиения . Так как, элементы a и а, конечно , лежат в одном и том же классе разбиения, ибо это один и тот же элемент, то можно записать aa(). Аналогично bb(),cc() и т. д.

Пусть далее для разбиения  множества М и некоторых x, y, zМ

имеет место xy() и yz() . Запись xy() означает, что элементы x и y принадлежат одному и тому же классу нашего разбиения. Аналогично y и z содержаться в одном и том же классе. Если теперь предположить, что x и z лежат в различных классах разбиения , то получим , что эти классы имеют общий элемент y, а это невозможно. Значит, xz().

Таким образом, мы доказали, что если xy()и yz(), то xz().

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

Например, для разбиения и  множества В, рассмотренных выше, класс разбиения a, b можно обозначить a, ибо он содержит элемент a. Но этот же класс содержит и элемент b, значит, его можно обозначить b. Таким образом , a, b=a=b. Аналогично e, d, f=e=d=f.

У нас получилось, что один и тот же класс разбиения обозначается по-разному. Это не должно вас удивить. И в математике, и в жизни вы не раз встречались с такой ситуацией. Например, дроби 1/2, 2/4, 3/6,-это одно и то же число, обозначаемое по-разному.

Вернемся теперь к общему случаю разбиения  множества М. Если некоторый класс разбиения содержит элементы x и y множества М, то, с одной стороны, он обозначается x, а с другой- y, т. е. x=y. Таким образом, мы доказали, что из xy() следует x=y.

Пусть теперь, наоборот, x =y. Но x - это класс, содержащий элемент y, и эти классы равны, т. е. это один и тот же класс. Значит, x и y содержатся в одном и том же классе разбиения, т. е. xy().

Из приведенных выше рассуждений мы можем сделать следующий вывод:x =y тогда и только тогда, когда xy().

Фактор множества. Рассмотрим построенное выше разбиение  множества В. Подмножества a,b,e,d,f,c,g являются классами этого разбиения. Согласно нашей договоренности, их можно обозначить, например, a,e,c, g соответственно. Таким образом, с разбиением  связана совокупность его классов разбиения, т. е. множество a,e, c,g.

И в общем случае, если -некоторое разбиение произвольного множества М, то с этим разбиением связана совокупность его классов.

Совокупность всех классов данного разбиения  множества М называется фактор- множеством множества М по разбиению  и обозначается М/.

Таким образом, элементами множества М/ являются классы данного разбиения и других элементов в нем нет.

Если мы вернемся к разбиению  множества М, изображенному на рис. 10, то множество М/ состоит из кусков (рис. 1.8), на которые мы разрезали круг, изображающий множество М. Далее, для нашего разбиения  множество В имеем В/ = a, e, c, g. Конечно же, элементы множества В/ можно обозначить и по-другому, и тогда, например, В/=b, f, c, g.

М/ = , , , ,

Пусть теперь  - разбиение множества В, классами которого являются подмножества a, b, c, d, e, f, g.Тогда В/=a, e.Обращаем ваше внимание на то, что a в В/ и a в В/ - это разные элементы, Например, кинотеатр "Мир" в Минске и кинотеатр "Мир" в Москве - это разные кинотеатры, и хотя они называются одинаково, это не вызывает недоразумений. Не будет их и в нашем случае с разбиениями, так как всегда ясно о каком разбиении идет речь.

Заметим. Что М/ - это совокупность лишь некоторых (не всех) подмножеств множества М, а 2^М-совокупность всех их. Значит, М/2^М, более того, М/ - собственное подмножество множества 2^М.

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