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

Прямым (или декартовым) произведением множеств А и В называется множество , состоящее из всех упорядоченных пар(a,b) таких, что и.

Если А иВ- конечное множество, мощностии, то.

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

Множество всех двоичных наборов длины nможно рассматривать как-n-ую декартову степень двухэлементного множества. Отсюда следует, что число двоичных наборов длиныnравно2ⁿ. Считая каждый двоичный набор характеристическим вектором подмножестваn-элементного множества, получаем, что число всех подмножествn-элементного множества равно2ⁿ.Этим объясняется часто используемое обозначение2^Aдля множества всех подмножествA, которое используется как для конечных, так и для бесконечных множеств.

Если A конечное непустое множество, , то, так как2ⁿ>n при Покажем, что для бесконечных множеств данное соотношение между мощностями сохраняется. Допустим противное, пусть междуA и 2^A установлено взаимно однозначное соответствие . Определим множествоследующим образом. Для каждоговключимa в B в том и только в том случае, если . Пусть, гдеb-элементы множества A , для которого . Зададимся теперь вопросом, является лиb элементом множества B? Если , топо построению множестваB. А если , тоопять таки по построению множестваB. Таким образом, одновременно имеет место и. Полученное противоречие и доказывает невозможность установления взаимно однозначного соответствия междуA и 2^A.

Контрольные вопросы.

1. Что называется множеством?

2. Дайте определение пересечения множеств.

3. Что называют мощностью множества?

4. Дайте определение прямого произведения множеств.

5. Приведите примеры множества.

Тест 1.

1. Объединением множеств А и В называется множество…

а){или}; б) {и};

в) {и}; в) {и};

2. Какая операция над множествами А, В, и С изображена на диаграмме

а) ; б); в); г);

3. Даны множества ,и. Результатом операции (А\В)С будет множество:

а) ; б); в); г){Ø}.

3. А={1, 2, 3}, В={а, в}. Какая пара чисел не принадлежит декартовому произведению АB

а) (1, а); б) (2, в); в) (3, а); г) (а, 2).

3. Является ли множество целых чисел счётным?

а) да; б) нет.

Глава II. Отношения, функции, алгебраические

структуры, морфизмы.

2.1. Бинарные отношения.

Пусть A- множество. Если задано некоторое подмножествоего декартового квадрата, другими словами, задано некоторое подмножество упорядоченных пар, где, то говорят, что на множествеAзадано бинарное отношениеR. Пишутили.В качестве примеров бинарных отношений на числовых множествах можно рассмотреть хорошо известные из арифметики отношения: ,,=”, ,,<”, ,,”, ,,>”, ,,”.

Бинарное отношение называется:

- рефлексивным, если для любого

- иррефлексивным, если для любого ;

- симметричным, если из следует;

- антисимметричным, если иследуетa=b;

- транзитивным, если из иследует;

Отношение ,,=” рефлексивно, симметрично и транзитивное, отношения ,,<” и ,,>” транзитивны и иррефлексивны, отношения ,,” и ,,”. рефлексивны, антисимметричны и транзитивны. Последние свойства выбираются в качестве определяющих для отношения частичного порядка на множестве A.

Определение. Бинарное отношение R на множестве A называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно,

Если , то будем считать элементa предшествующим элементу b и записывать отношение aRb в виде . Если для любых двухэлементов имеет место хотя бы одно из отношенийили, то частичный порядок называется полным или линейным порядком.

Примером частичного порядка является система множеств, упорядоченных по включению: . Числовые множества с обычным отношением ,,” дают примеры линейных порядков.

Пусть <A,  > - частично упорядоченное множество. Элемент называется минимальным, если изследует. Минимальных элементов может быть больше одного. Элементназывается наименьшим, еслидля любого. Если вA имеется наименьший элемент, то он единственен. Аналогично определяются максимальный и наибольший элемент.

Обобщением понятия равенства является отношение эквивалентности.

Определение. Бинарное отношение R на множестве A называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности разбивает множество Aна непересекающиеся подмножества, называемые классами эквивалентности. Если в качествеAрассмотреть множество людей, проживающих в домах некоторого города, то отношение проживания в одном доме будет отношением эквивалентности. Более математическим примером является отношение сравнения по модулюnв множестве целых чиселZ: , еслиделится наn. При этомZразбивается на классы, характеризуемые остатками от деления наn. Более общим примером является эквивалентность элементов группыGпо подгруппеH:если. Классами эквивалентности здесь являются правые смежные классы по подгруппеH.