Декартово (прямое) произведение множеств. Отношения и функции

Лабораторная работа № 2.

 

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

 

Цель работы: получить навыки оперирования с отношениями над множествами.

 

Декартово (прямое) произведение множеств. Отношения и функции

Определение 1. Декартовым (прямым) произведением множеств X и Y называется множество , элементами которого являются все возможные упорядоченные пары (x, y) такие, что .

Для упорядоченных пар (x, y) используется также обозначение <x, y>.

Определение 2. Прямым (декартовым) произведением множеств Х1, Х2, …, Хn называется совокупность всех упорядоченных n-ок (x1, …, xn) таких, что . Если Х12=…Хn, то пишут .

Пример1.

1. Пусть X={1, 2, 3}, Y={0, 1}. Тогда ; .

2. Пусть Х – множество точек отрезка [0, 1], а Y – множество точек отрезка [1, 2]. Тогда - множество точек квадрата с вершинами в точках (0, 1), (0, 2), (1, 1), (1,2).

Определение 2. Бинарным (или двуместным) отношением r на паре множеств А и В называется произвольное подмножество множества .

Тот факт, что элементы а и в находятся в бинарном отношении R, записывается следующим образом: или .

Если r есть отношение и пара (x, y) принадлежит этому отношению, то наряду с записью (x, y)Îr употребляется запись xry. Элементы х и у называются компонентами (или координатами) отношения r.

Пример 2.

Приведем примеры бинарных отношений.

1. Отношения на множестве натуральных чисел N:

отношение £ − выполняется, например, для пар (7, 9) и (7, 7), но не выполняется для пар (9, 7);

отношение “иметь общий делитель, отличный от единицы” − выполняется, например, для пар (6, 9), (4, 2), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (9, 7);

отношение “быть делителем” − число а делитель числа в − выполняется, например, для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и (7, 9).

2. Отношения на множестве точек плоскости:

отношение “находиться на одинаковом расстоянии от начала координат”− выполняется для пар точек находящихся на одной и той же окружности с центром в начале координат;

отношение “находиться на разном расстоянии от начала координат” выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение;

отношение “быть симметричным относительно оси Х” выполняется для всех пар точек (х1,y1) и (x2,y2), удовлетворяющих условию х1 = х2 и y1 = −y2.

3. Отношения на множестве людей: “жить в одном городе”, “быть моложе”, “быть сыном”, “быть знаменитым”.

Определение 3. N-арным отношением на множествах Х1, Х2, …, Хn называется произвольное подмножество множества .

Говорят, что элементы находятся в отношении , если ( )ÎR.

Определение 4. Областью определения бинарного отношения r называется множество

Определение 5. Областью значений бинарного отношения r называется множество

Пусть rÍ X´Y определено в соответствии с изображением на рис. 1. Область определения Dr и область значений Er определяются соответственно:

Dr={x: (x, y) Î r}, Er={y: (x,y)Î r}.

 
 

 

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

1. списком (перечислением) пар, для которых это отношение выполняется.

2. матрицей смежности – бинарному отношению соответствует квадратная матрица с = порядка n, в которой элемент cij, стоящий на пересечении i-той строки и j-го столбца, равен 1, если ai и aj находятся в отношении , и − 0, в противном случае:

Пример3.

Пусть M={1, 2, 3, 4, 5, 6}. Задать в явном виде (списком) и матрицей смежности отношение r, определенное на множестве , если r означает «быть строго меньше».

Отношение r, как множество, содержит все пары элементов a, b из М такие, что a<b. Тогда

r = {(1, 2), (1,3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)}.

Матрица смежности отношения r имеет вид:

 

.

Определение 6. Бинарное отношение f на паре множеств X, Y называется функциональным, функциейили отображением множества X в множество Y, если из (x, y)Îf и (x, z)Îf следует, что y=z.

Поскольку функции являются бинарными отношениями, то две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции обозначается Df, а область значений – Rf. Определяются они так же, как и для бинарных отношений.

Если f – функция, то вместо (x, y)Îf пишут y=f(x) и говорят, что y – значение, соответствующее аргументу х, или y – образ элемента х при отображении f. При этом х называется прообразом элемента y.

Определение 7. Назовем f n-местной функцией из Х в Y ,еслиf:Xn®Y.Тогда пишем y=f(x1, x2, …, xn) и говорим, что y – значение функции при значении аргументов x1, x2, …, xn.

Пусть f: X®Y.

Определение 8. Функция f называется инъективной, если для любых х1, х2, y из y=f(х1) и y=f(х2) следует, что х1= х2, то есть каждому значению функции соответствует единственное значение аргумента.

Определение 9. Функция f называется сюръективной, если для любого элемента yÎY существует элемент хÎХ такой, что y=f(x).

Определение 10. Функция f называется биективной, если f одновременно сюръективна и инъективна.

 
 

Рисунок 9 иллюстрирует понятия отношения, отображения (функции), инъекции, сюръекции и биекции.

Пример4.

Рассмотрим три функции, заданные на множестве действительных чисел и принимающих значение в этом же множестве:

1. функция f(x)=ex − инъективна, но не сюръективна;

2. функция f(x)=x3-x – сюръективна, но не инъективна;

3. функция f(x)=2x+1 – биективна.

Определение 11. Суперпозицией функций называется функция, полученная из системы функций f, f1, f2, …, fkнекоторой подстановкой функций f1, f2, …, fk во внешнюю функцию f вместо переменных и переименованиями переменных.

Пример5.

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