Упорядоченные множества. Прямое произведение множеств

3.1. Упорядоченные множества

Во многих приложениях необходимо использовать множества,

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

точка в двумерном пространстве (на плоскости) задается двумя ко-ординатами(х, у).Очевидно,чтоэторазныеточки,есликоордина-

ты их не равны, даже при условии, что элементы этих двух элемент-ныхмножеств одинаковы (2, 5) и(5, 2) (см.рис.3.1).

Рис. 3.1. Точки, определяемые их координатами

Другие примеры упорядоченных множеств: любой список (очередь) —

на защиту диплома, получение льгот; множество операторов программы

и т.п.

Наиболее простым упорядоченным множеством является

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

парой. Элементы упорядоченного множества обычно заключают в круглые илиугловыескобки.Например,(2, 5) или<2;5>.

Если(a, b) —упорядоченнаяпара,тоэлемент a называютпервымэлементом или первой компонентой этой пары, а элемент b — вторым

элементом или второй компонентой этой же пары.

Каждое упорядоченное множество можно определить с помощью

неупорядоченных множеств. Например, двойку определяют так (a, b)= { }, { }.

Тройку определяют через двойку (a, b, c)=((a, b), c).

Аналогично, n -ку определяют через двойку

(1, a 2,, an)=((1, a 2,, an -1), an).

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

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

лить новую операцию на множествах.

Прямым (декартовым) произведением множеств A и B называют Множество С = А ´ В,состоящееизвсехупорядоченных пар (a, b) та-

ких, что a Î A, b Î B, то есть

С = А ´ В ={ a, b)| a Î A, b Î B }. Например,пусть А = { х, у } и В = 1,2,3.Тогда

A ´ B = (x,1,(x, 2),(x,3),(y,1,(y,2),(y,3)

Имеется графическая интерпретация прямого произведения мно-

жеств.Пустьмножество A ={ x | a £ x £ b естьинтервалзначенийпере-менной x и B ={ y | c £ y £ d }есть интервал значений y. Ясно, что множе-

ства A и B имеют бесконечное число элементов. Тогда прямое (декарто-

во) произведение множеств A и B есть множество точек прямоуголь-

{

}

a

a, b

a

a

(

}

{

{

}

)

)

}

ника, изображенного на рис. 3.2

A ´ B ={ x, y), x Î A, y Î B }.

Рис. 3.2. Декартово произведение множеств A и B

Если имеется прямое произведение нескольких одинаковых мно-

жеств, то такое произведение кратко записывают так A ´ A = A 2,

A ´ A ´ A = A 3и т.д.

(

Лекция 4 5 6

Дата добавления: 2015-11-16