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

Пусть X – множество фамилий учащихся некоторого класса, обозначим через J множество всех букв, с которых начинаются эти фамилии. Если АÎХ, т.е. в классе есть ученик, фамилия которого начинается с "А”, то обозначим через K_A множество всех фамилий из X, начинающихся с "А". Аналогично вводим K_Б,…К_Я. Рассмотрим семейство множеств . Очевидно, что множества семейства обладают следующими свойствами.

1. Каждое есть подмножество X.

2. Каждое не пусто.

3. Объединение всех совпадает с X.

4. Любые два различных множества и не пересекаются.

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

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

1. для всех (любое множество из семейства является подмножеством множества Х)

2. для всех

3. (объединение всех множеств, входящих в разбиение, дает множество Х)

4. Если , то для всех . (любые два множества из семейства являются непересекающимися)

Множество принято называть множеством индексов.

Пример 1.12. Рассмотрим множество вещественных чисел R. Пусть . Семейство есть разбиение. Множество {-,0,+} есть множество индексов.

Пример 1.13. Пусть Т - множество всех треугольников. Положим: То - множество остроугольных треугольников, Тп - множество прямоугольных треугольников, Тт - множество тупоугольных треугольников, семейство {То, Тп, Тт } есть разбиение множества Т, {о, п, т} – множество индексов.

Понятие разбиения множества на классы лежит в основе понятия классификации. Классификация проводится следующим образом. Выделяются некоторые признаки предметов данного рода, опираясь на которые производится разбиение исходного множества на классы. Каждый из приведенных выше примеров, являясь примером разбиения, является и примером классификации. В примере 1 классификация проведена по начальной букве фамилии, в примере 2 - по знаку числа, в примере 3 - по величине максимального угла треугольника. Примерами классификаций из других областей являются: библиотечно-библиографические классификации, связанные с разбиением множества книг в библиотеке на классы по признакам содержания, менделеевская классификационная таблица химических элементов.

К понятию разбиения мы вернемся при рассмотрении отношения эквивалентности, с которым оно очень тесно связано.

Тождества алгебры множеств

С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения. Обозначим через (x, У, Z) некоторое алгебраическое выражение, составленное из множеств X, У и Z. Оно само представляет собой некоторое множество. Пусть (X, У, Z) — другое алгебраическое выражение, составленное из тех же множеств. Если оба алгебраических выражения представляют собой одно и то же множество, то их можно приравнять друг к другу, получая алгебраическое тождество вида

(x, У, Z) = (X, У, Z).

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

Операция пересечения связана с объединением законами дистрибутивности:

1. ХÇ(YÈZ)=(ХÇY)È(ХÇZ).

2. ХÈ(YÇZ)=(ХÈY)Ç(ХÇZ).

Они аналогичны дистрибутивному (распределительному) закону, связывающему операции сложения и умножения чисел: x(y+z)=xy+xz.

1) На рис. 1.7 приведены диаграммы Эйлера—Венна для выражений и .

Из этих диаграмм видно, что оба выражения определяют одно и то же множество, так что в алгебре множеств имеет место тождество

= ,

аналогичное дистрибутивному закону (a+b)c=ac+bc в обычной алгебре.

2) В обычной алгебре мы не можем заменить в дистрибутивном законе действие сложения умножением, а действие умножения сложением, так как это приводит к абсурдному выражению (ab)+c=(a+c) (b+с). Иначе обстоит дело в алгебре множеств.

На рис. 1.8 приведены диаграммы Эйлера—Венна для алгебраических выражений ( и . Оба эти выражения дают одно и то же множество, так что имеет место тождество

= .

3) Легко убедиться, что если У Х, то

.

Действительно, все элементы множества У являются в то же время и элементами множества X. Значит, пересечение этих множеств, т. е. общая часть множеств X и У, совпадает с У. В объединение множеств X и У множество У не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества X. Следовательно, X У совпадает с X.

4) Полагая Y=X и учитывая, что Х Х, находим

.

Установление тождеств алгебры множеств с помощью диаграммы Эйлера—Венна в ряде случаев оказывается неудобным. Имеется более общий способ установления тождественности двух алгебраических выражений.

Пусть, как и прежде, через и обозначены два алгебраических выражения, получившихся путем применения операций объединения, пересечения и дополнения к множествам X, Y и Z. Для того, чтобы доказать, что , достаточно показать, что и что .

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

5) Докажем тождество

.

Предположим, что , т. е. что . Это значит, что и , т. е. и . Следовательно, . Предположим теперь, что , т.е. и . Это значит, что и , т. е. что . Следовательно, .

6) Тождество

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

.

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

В литературе последние два тождества называются тождествами де-Моргана.

1-3. УПОРЯДОЧЕНИЕ ЭЛЕМЕНТОВ И ПРЯМОЕ ПРОИЗВЕДЕНИЕ МНОЖЕСТВ

Упорядоченное множество

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

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

В технических задачах эта определенность часто является просто предметом договоренности. Так, только договоренностью можно объяснить, почему долготу ставят на первое место, а широту на второе. Состояние технической системы часто описывают множеством параметров, принимающих числовые значения. При этом состояние системы – просто некоторое множество чисел. Чтобы не оговаривать каждый раз, какое число что означает, устанавливают заранее, какой параметр считать первым, какой вторым и т. д., т. е. совокупность параметров представляют в виде упорядоченного множества.

Длина кортежа – это число элементов в нем. Картежи равны, если на одинаковых местах (номерах) у них находятся одинаковые элементы. Для обозначения кортежа используем круглые скобки. Так, множество

a = (a₁, a₂,…, a_n)

является кортежем длины п с элементами a₁,...,a_n. Кортежи длины 2 называются парами или упорядоченными парами, кортежи длины 3 — тройками, 4 — четверками и т. д. В общем случае кортежи длины п называются n-ками.

Частным случаем кортежа является кортеж (а) длины 1 и пустой кортеж длины 0, обозначаемый ( ) или . В отличие от обычного множества в кортеже могут быть и одинаковые элементы: два одинаковых слова в фразе, одинаковые числовые значения долготы и широты точки на местности и т. п.

Пример 1.14 Рассмотрим уравнение x² –y=1. Его решением является упорядоченная пара (x₀, y₀) такая, что x₀² –y₀=1. Упорядоченные пары (1,0), (2,3), (3,8), (-2,3), являются решениями. Пара (3, 2) не является решением, так как 3²-2≠1.

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и У называется множество, обозначаемое X×Y и состоящее из всех тех и только тех упорядоченных пар (x,y), первая компонента которых принадлежит множеству X, а вторая принадлежит множеству У. Таким образом, элементами прямого произведения являются двухэлементные кортежи вида (х, у). Формальное определение

Х×У = {(х,у)|х Х,у У}.

Число элементов декартового произведения, равно произведению мощностей данных множеств. |AxB| = |A|·|B|.

По определению полагают, что X´Ø=Ø, Ø´Y=Ø. Декартово произведение множества X на себя называют декартовым (или прямым) квадратом. При этом полагают X´X=X² . Имеем: X²={(x,y)|xÎХ, yÎX}.

Если R — множество вещественных чисел, то R²= R×R представляет собой вещественную плоскость, а R³=R×R×R представляет собой трехмерное вещественное пространство.

Пример 1.15. Пусть Х={1, 2}, У={1, 3, 4}. Тогда Х×У= = {(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4)}. Перемножим множества X и Y в обратном порядке:Y´X={(1, 1), (1,2), (3, 1), (3, 2), (4,1), (4,2)}. Замечаем, что X´Y≠Y´X. Следовательно, декартово произведение не обладает свойством коммутативности (переместительности).

Х×У ≠ У×Х.