предложено Куратовским. Можно было бы использовать и другое определение, важно только, чтобы (а, Ъ) = (с, d) было равносильно (а = с) и (b = d).]

Декартово произведение (cartesian product) двух множеств А и В определяется как множество всех упорядоченных пар, у которых первый элемент принадлежит А, а второй - В. Обозначение: Ах В. Формально можно записать

А x В = {(а, Ъ) : a G А и Ъ G В}

Например, {a, b} x {а,Ь,с} = {(а, а), (а,Ь), (а, с), (6, а), (b,b), (b, с)}. Для конечных множеств А н В мощность их произведения равна произведению мощностей:

\А х В\ = \А\ \В\.(5.4)

Декартово произведение п множеств А\, А2, ., Ап определяется как множество га-ок (ra-tuples)

А\ x А2x.. .x Ага = {(ai, а2,... , ап) : аг- £ Аг- при всех г = 1, 2,... , га}

(формально можно определить тройку (а, Ь, с) как ((а, 6), с), четверку (a,b,c,d) как ((а,Ь, с), d) и так далее).

Число элементов в декартовом произведение равно произведению мощностей сомножителей:

Ai х А2 х ... х An = • \А2\ •... • АП

Можно определить также декартову степень

Ап = Ах Ах ...х А

как произведение га одинаковых сомножителей; для конечного А мощность Ап равна \А\п. Отметим, что га-ки можно рассматривать как конечные последовательности длины га (см. с. 5.3).

Упражнения

5.1-1 Нарисуйте диаграмму Венна для первого из свойств дистрибутивности (5.1).

5.1-2 Докажите обобщение законов де Моргана на случай большего числа множеств:

At П А2 П ... П Ап = At U А2 U ... U А,

5.1-3 Докажите обобщение равенства (5.3), называемое формулой включений и исключений (principle of inclusion and exclusion):

AiU A2U...U An\ = Ai + A2 + ...+ An

- Ai П A2\ - Ai П A3 - ... + \А1Г\А2Г\А3\ + ...

+ (-i)"-1i1ni2n...niB

5.1-4 Доказать, что множество нечётных натуральных чисел счётно.

5.1-5 Доказать, что если множество S конечно и содержит га элементов, то множество-степень 2s содержит 2п элементов. (Другими словами, множество S имеет 2п различных подмножеств.)

5.1-6 Дайте формально индуктивное определение га-ки, используя понятие упорядоченной пары.

5.2. Отношения

Бинарным отношением (binary relation) R между элементами множеств А ж В называется подмножество декартова произведения А x В. Если (а, Ъ) £ R, пишут aRb и говорят, что элемент а находится в отношении R с элементом Ь. Бинарным отношением на множестве А называют подмножество декартова квадрата А x А. Например, отношение «быть меньше» на множестве натуральных чисел есть множество {(а, Ъ) : а, Ь £ N и а < Ь}. Под га-местным отношением (ra-ary relation) на множествах А\, А2, , Ап понимают подмножество декартова произведения А\ x А2 x ... x Ап.

Бинарное отношение R С А x А называют рефлексивным (reflexive), если

aRa

для всех а £ А. Например, отношения «=» и «» являются рефлексивными отношениями на множестве N, но отношение «<» таковым не является. Отношение R называется симметричным (symmetric), если

aRb влечёт bRa

для всех a, b £ А. Отношение равенства является симметричным, а отношения «<» и «» - нет. Отношение R называют транзитивным (transitive), если

aRb и bRc влечёт aRc

для всех а, Ь, с £ А. Например, отношения «<», «» и «=» являются транзитивными, а отношение R = {(а, Ъ) : а, Ь £ N и а = Ь - 1} - нет, так как 3i?4 и 4i?5, но не 3i?5.

Отношение, являющееся одновременно рефлексивным, симметричным и транзитивным, называют отношением эквивалентности (equivalence relation). Если R - отношение эквивалентности на множестве А, то можно определить класс эквивалентности (equivalence class) элемента а £ А как множество [а] = {Ь £ А : aRb} всех элементов, эквивалентных а. Например, на множестве натуральных чисел можно определить отношение эквивалентности, считая числа а и Ь эквивалентными, если их сумма а + Ь четна. Это отношение (назовём его R) действительно будет отношением эквивалентности. В самом деле, сумма а + а всегда четна, так что оно рефлексивно; а + Ь = Ь + а, так что R симметрично; наконец, если а + 6и 6 + с - чётные числа, то а + с = (а + Ъ) + (Ь + с) - 26 также четно, так что R транзитивно. Класс эквивалентности числа 4 есть [4] = {0,2,4,6,...}, а класс эквивалентности числа 3 есть [3] = {1,3,5,7,...}. Основное свойство классов эквивалентности состоит в следующем:

Теорема 5.1 (Отношения эквивалентности соответствуют разбиениям).

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

Доказательство. Чтобы доказать первое утверждение, надо показать, что классы эквивалентности непусты, попарно не пересекаются и в объединении дают всё множество А. По свойству рефлексивности а £ [а], поэтому классы непусты и покрывают всё а. Докажем, что если классы [а] и [6] пересекаются, то они совпадают. Пусть с - их общий элемент, тогда aRc, bRc, cRb (симметричность) и aRb (транзитивность). Теперь видно, что [6] С [а]: если х - произвольный элемент 6, то bRx и по транзитивности aRx. Аналогично, [а] С [6] и потому [а] = [6].

Второе утверждение теоремы совсем очевидно.□

Бинарное отношение R на множестве А называется антисимметричным, если

aRb и bRa влечёт а = 6.

Например, отношение «» на натуральных числах является антисимметричным, поскольку изабиба следует а = Ь. Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного порядка (partial order), и множество вместе с таким отношением на нём называется частично упорядоченным множеством (partially ordered set). Например, отношение