Разбиение множества на подмножества

Разбиение множества на подмножества

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Программа nero для чего нужна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Unins000 exe что это

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые задачи, связанные с операциями над конечными множествами.

Основная литература 7, 10, 11, 16, 23, 33, 34;

Дополнительная литература 17, 18, 50, 82, 86, 87

1. Понятие разбиения множества на классы

Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.

Классификация – это действие распределения объектов по классам на основании сходств объектов внутри класса и их отличия от объектов других классов.

Как правило, целью классификации является систематизация наших знаний. Например, в биологии имеется классификация животных, охватывающая до 1,5 млн. различных видов животных, в ботанике – классификация растений, включающая 500 тыс. видов растений. Классификация дает возможность рассмотреть это многообразие в определенной системе, выделить интересующие нас виды растений и животных.

Широко применяется классификация в математике. Например, натуральные числа делятся на четные и нечетные; углы (меньше развернутого) бывают острые, прямые и тупые.

Выясним условия, которым должны удовлетворять правильно выполненная классификация.

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

Если не выполнено хотя бы одно из этих условий, классификацию считают не правильной.

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

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

Читайте также:  Как запустить скаченную игру на xbox 360

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

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

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

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

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

Проанализируем получившуюся картину. Круг, изображающий множество N натуральных чисел, разбился на 4 непересекающиеся области – они пронумерованы римскими цифрами. Каждая область изображает некоторое подмножество множества N. Определим, какие числа оказались в каждом из этих непересекающихся подмножеств. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II – из чисел, кратных 3 и не кратным 5; подмножество III – из чисел, кратных 5 и не кратных 3; подмножество IY – из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.

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

А — класс прямоугольных треугольников;

В — класс тупоугольных треугольников;

С — класс треугольников, не являющихся ни прямоугольными, ни тупоугольными треугольниками.

Встретилось задание из раздела о динамическом программировании, которое вызывает у меня трудности. Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на три части, в которых суммы всех элементов будут равны. Например:
[1, 2, 3, 4, 4, 5, 8] -> <1,8>, <4,5>,

Очевидно, что если сумма всех элементов не делится на 3, то множество не содержит такого разбиения (самая простая часть:) ). Но как действовать дальше? Вроде как мы должны проверять, к какому подмножеству у нас относится a_i элемент.
Но все это формализовать и прикрутить динамику не получается.
Буду признателен, если сможете направить на истинный путь.

Ссылка на основную публикацию
Adblock detector