Тема 9. Отображение и отношение множеств

Пусть X и Y - два множества.Если каждому элементу x множества X поставлен в соответствие некоторый элемент f (x) множества Y, то говорят, что задано отображение f из множества X в множество Y. Обозначение: f: X ® Y. При этом, если f (x) = y, то элемент y называется образом элемента x при отображении f, а элемент x называется прообразом элемента y при отображении f ^-1.

Отображение f: X ® Y является сюръективным, если каждый элемент yÎY имеет хотя бы один прообраз.

Отображение f: X ® Y называется инъективным, если для любого элемента yÎY существует не более одного прообраза.

Если отображение f сюръективно и инъективно одновременно, то оно называется биективным (взаимно однозначным соответствием).

Пусть f: X ® Y и g: Y® Z - два отображения. Зададим правило h, применение которого к элементу x из X состоит в том, что мы применяем к x правило f, затем к результату f(x) применяем второе правило g, получая в итоге g(f(x)). То есть h(x) = g(f(x)). Полученное отображение h: X ® Z называют композицией отображений g и f и обозначают h = g ° f. Тогда g ° f(x) = g(f(x)).

Декартово произведение двух множеств А и В - множество упорядоченных пар <a, b> таких, что aÎA и bÎB. Мощность декартова произведения равна произведению мощностей исходных множеств.

Бинарное отношение множеств А и В - подмножество декартового произведения А на В. Область определения отношения (левая область отношения) - множество всех первых элементов пар отношения. Область значений отношения (правая область отношения) - множество всех вторых элементов пар отношения.

Отношение эквивалентности - отношение, являющееся одновременно рефлексивным, симметричным и транзитивным. Рефлексивное отношение на множестве А - отношение, которое справедливо для каждого элемента множества А как отношение этого элемента к самому себе. Например =, ³ - рефлексивные, ¹, > - нерефлексивные.

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

Класс эквивалентности R - набор элементов множества, для которых эквивалентное отношение R будет давать одинаковый результат.

1. Выясните, является ли заданное соответствие
f: {10,20,30,40} ® {а,б,в,г} отображением и если да, то найдите f({10,40}), f({10,20,30}), f^{- 1}(б), f^{- 1} ({а,в}), f^{- 1} ({б,в,г}).

0) 10 а 20 б 30 в 40 г	1) 10 а 20 б 30 в 40 г	2) 10 а 20 б 30 в 40 г	3) 10 а 20 б 30 в 40 г	4) 10 а 20 б 30 в 40 г
5) 10 а 20 б 30 в 40 г	6) 10 а 20 б 30 в 40 г	7) 10 а 20 б 30 в 40 г	8) 10 а 20 б 30 в 40 г	9) 10 а 20 б 30 в 40 г

2. Найдите декартово произведение множеств С = А ´ В:

0)A={1,2,3}; В={7,8,9};	1)A={2,3,4,9}; В={1,7};
2)A= {1,7}; В ={2,4,6,8}	3)A={3,5,10}; В={2,8,9};
4)A={2,3,4,5}; В ={6,10}	5)A={5,6}; В={1,7,9,2};
6)A={10,1,2}; В={1,2,8};	7)A={10,11,12}; В={2,8,9};
8)A={6,9}; В={1,2,3,5};	9)A={2,3,5,6}; В={9,12};

3. Выясните, к какому типу относятся отображения f1: А ®В и
f2: А ® В.

0)A={x, y, z};	B={1, 2, 3, 4};	f1: x® 1;y®2; z®3;	f2: x® 4; y®1; z® 4;
1)X={a,b,c,d,e};	Y={2, 4, 6};	f1: a®2 b®2; c®4; d®6;	f2: a®2; b®4; c®4; d®6; e® 6;
2)A={1,2,3,4};	B={a, b, c, d};	f1: 1®a; 2®b; 3®c; 4®d;	f2: 1® b; 2®c; 3®d; 4®d;
3)X={a, b, c};	B={1,2,3,4,5};	f1: a®1; b®2; c®4;	f2: a® 1; b®1; c®3;
4)A={x, y, z};	B={1, 2, 3, 4};	f1: x® 1; y®2; z®4;	f2: x® 1; y®3; z® 4;
5)A={1, y, z};	B={ 2, 3, 4};	f1: 1® 2; y®2; z®3;	f2: 1® 2; y®3; z® 4;
6)X={a, b, c, e};	Y={2, 5, 6};	f1: a®2 b®2; c®5; e®6;	f2: a®6; b®5; c®5; e®2;
7)A={2,3,4,5};	B={a, b, c};	f1: 2®a; 3®a; 4®b; 5®c;	f2: 2® a; 5®b; 3®c; 4®c;
8)X={2, b, c};	B={ 3, 4, 5};	f1: 2®3; b®5; c®5;	f2: 2®4; b®3; c®5;
9)A={x, y, 3};	B={2, 4, 5, 7};	f1: x® 2;y®2; 3®7;	f2: x® 4; y®5; 3®2;