Буклет на тему «Разбиение множеств на классы»

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

• Такие подмножества называют классами разбиения. Каждый элемент множества входит ровно в один класс.

• Разбиение можно задать не только списком подмножеств, но и отношением эквивалентности: элементы считаются эквивалентными, если они принадлежат одному классу.

Разбиение тесно связано с отношением эквивалентности: оно должно быть рефлексивным, симметричным и транзитивным.

• Класс эквивалентности элемента a — это все элементы множества, которые эквивалентны a. Обозначают его [a].

• Если множество разбито на классы, то любые два разных класса не имеют общих элементов.

• Примером служат числа по остатку от деления на 3: получаются классы 0, 1 и 2.

Одно и то же множество можно разбить по-разному. Например, все целые числа можно разделить на чётные и нечётные, а можно — по остатку от деления на 3; это уже другая система классов.

Разбиение возникает из отношения эквивалентности: для каждого элемента берут все элементы, равные ему по выбранному признаку.

• В множестве натуральных чисел можно выделить класс чётных и класс нечётных чисел; вместе они дают всё множество и не пересекаются.

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

• Для строк можно задать классы по одинаковой длине: все строки одной длины образуют один класс.

Число классов разбиения может быть конечным или бесконечным.

• Каждый элемент принадлежит только одному классу, поэтому разбиение однозначно распределяет элементы по группам.

• Если отношение эквивалентности задано на множестве, то все его классы вместе покрывают всё множество.

• Разбиение удобно записывать перечислением классов: {A1, A2, A3}, где A1∪A2∪A3 равно исходному множеству.