Декартово произведение множеств. Соответствия. Бинарные отношения и их свойства. Отображения

Рассмотрим следующую реальную ситуацию. Школьникам дали цветную бумагу и попросили вырезать украшения для новогодней елки. Обозначим через А множество видов украшений: А={звездочка, снежинка, фонарик, гирлянда}, через В – множество предлагаемых цветов: В={красная, синяя, голубая, зеленая, розовая, белая}. Посмотрим, какие украшения можно получить, учитывая возможные для них расцветки. Для этого составим список всех пар из элементов множества А и элементов множества В таким образом, что сначала будем записывать элемент множества А, затем элемент множества В. получим множество С упорядоченных пар элементов множеств А и В. Возможные изделия можно перечислить с помощью таблицы. Итак, мы имеем дело с особым множеством, составленным из элементов двух данных множеств. Такое произведение называется декартовым произведением двух множеств.

В А	звездочка	снежинка	фонарик	гирлянда
красная	звездочка – красная	снежинка – красная	фонарик – красный	гирлянда – красная
синяя	звездочка – синяя	снежинка – синяя	фонарик – синий	гирлянда – синяя
голубая	звездочка – голубая	снежинка – голубая	фонарик – голубой	гирлянда – голубая
зеленая	звездочка – зеленая	снежинка – зеленая	фонарик – зеленый	гирлянда – зеленая
розовая	звездочка – розовая	снежинка – розовая	фонарик – розовый	гирлянда – розовая
белая	звездочка – белая	снежинка – белая	фонарик – белый	гирлянда – белая

Опр. 2.6.1. Декартовым ( или прямым) произведением множества А на множество В называется множество всех упорядоченных пар, в которых первая компонента – элемент множества А, а вторая – элемент множества В. Обозначают А×В.

Таким образом, А×В={(x, y) | х ÎА и y ÎВ}.

Может случиться, что множества А и В окажутся одинаковыми. Рассмотрим следующий пример. Школьники делают открытки: отдельно обложку и внутреннюю часть следующих цветов: синий, красный, зеленый, желтый.

Обозначим через А – множество цветов обложки, через В – множество цветов внутренней части. Тогда получим: А=В={синий, красный, зеленый, желтый}. Можно составить список возможных сочетаний цветов для открытки: цвет обложки и цвет внутренней части.

Объединяя всеми возможными способами цвет из А с цветом из В=А, получим элементы прямого произведения множества А «самого на себя», которое называется прямым или декартовым квадратом и обозначается: А×А=А².

Из этого примера видно, что каждая пара прямого произведения должна быть упорядочена: открытка с красной обложкой и с синей внутренней частью отличается от открытки с синей обложкой и с красной внутренней частью.

Для описания прямого произведения множеств бывает удобно использовать «геометрический язык». При этом элементы множества А×В называются точками. Например, если z=(x,y), то х ÎА называется абсциссой, а y ÎВ – ординатой точки z. В связи с этим заметим, что множество точек плоскости по существу являются элементами прямого квадрата R × R = R ² множества R действительных чисел.

На рис.1 точками показаны элементы декартова произведения множеств А={1, 2, 3} и В={4, 5, 6, 7}. Отсюда легко видеть способ нахождения общего числа элементов в декартовом произведении двух множеств: если m (А)= n, m (B)= k, то m (А×В)=n*k (4).

Рис.1.

Пример. Применим формулу (4) для подсчета количества двухзначных чисел. Двухзначное число можно принять за упорядоченную пару, где на первом месте может стоять цифра из множества А={1, 2, 3, 4, 5, 6, 7, 8, 9}, а на втором – из множества В={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, т.е. за элемент прямого произведения этих множеств, тогда получаем: m (А)=9, m (B)=10, то m (А×В)=9·10=90. Итак, всего имеется 90 различных двухзначных чисел. ♦

Перейдем к знакомству с другим новым понятием. Рассмотрим два множества: первое (А), состоящее из 11 учащихся, второе (В), состоящее из 9 городов. Чтобы получить прямое произведение этих множеств, надо составить все пары: (ученик – город). Из множества всех таких пар мы выберем лишь такие, которые «связывают» каждого ученика с тем городом, где он бывал. Очевидно, что «список» таких пар (ученик – известный город) будет являться подмножеством Ω декартова произведения. Такой «список» удобно заменить таблицей, где можно указать все города, в которых побывал каждый ученик:

	Москва	Тула	Одесса	Тамбов	Воронеж	Липецк	Елец	Задонск	Лебедянь
Петя	×	×			×		×
Вася			×			×	×
Коля	×				×		×
Саша			×				×	×
Лена	×			×			×
Таня	×				×		×
Ирина		×					×
Вера	×						×
Андрей	×				×		×
Витя	×	×					×	×
Катя					×		×

Можно сказать, что данная таблица задает определенное соотношение между элементами множеств А и В.

Опр.2.6.2. Будем говорить, что между элементами двух множеств А и В установлено соответствие ρ, если в их произведении А×В выделено некоторое подмножество Ω. Если пара (a,b) Î ΩÍΑ×Β, это означает по определению, что элементы a и b множеств А и В находятся в отношении ρ (пишется aρb).

Еще один пример соответствия: Пусть даны множества А – студентов и В – множество групп. Утверждение “студент a учится в группе b ” задает соответствие между множеством студентов и множеством групп. Здесь а пробегает множество значений А, b – множество значений В. Такое соотношение называется бинарным соответствием, т.е. соответствием между двумя множествами А и В.

Бинарные соответствия можно задавать таблицами (например, расписание занятий) или ориентированными графами.

	Пн.	Вт.	Ср.
Педагогика
Математика
Физкультура

Рис. 2.

Если соответствие ρ задано между элементами одного и того же множества, то говорят, что между элементами этого множества задано отношение ρ. Итак, задать на множестве А 2-хместное (бинарное) отношение означает выделить в прямом квадрате А² этого множества некоторое подмножество Ω.

Опр.2.6.3 Бинарным отношением, заданным на множестве А называется всякое подмножество декартова произведения А×А.

Местность отношения показывает, сколько объектов могут разом находиться в данном отношении. Чаще всего рассматриваются бинарные (двухместные) или тернарные (трехместные) отношения.

Таким образом, бинарные соответствия между X и X называются бинарными отношениями на множестве X, т.е. соответствиями между элементами одного и того же множества (или равных множеств). Например, отношения: “2>1”, “3=3”, “человек х старше человека y” и др.

Пример. Возьмем в качестве элементов множества А случайную группу людей (например, едущих в одном поезде). И выберем бинарное отношение ρ на этом множестве следующим образом: два человека из А будут находиться в данном отношении, если они родились в одном и том же месяце (под одним знаком зодиака; имеют одинаковые имена и пр.). И еще элемент а1 из А будет находиться в отношении δ с элементом а2 из того же множества, если, допустим, первый человек выше ростом, чем второй (старше, тяжелее и пр.).

Из этих примеров можно заметить, что если Таня родилась в том же месяце, что и Петя, то же самое можно сказать и о Пете: Петя родился в том же месяце, что и Таня. С учетом введенных обозначений можно записать: если ТаняρПетя, то ПетяρТаня. Иначе дело обстоит с другим отношением δ: если Таня ростом выше Пети, то неверно, что и Петя ростом выше Тани.

Таким образом, различные отношения могут иметь и различные свойства. Рассмотрим основные из них.

Опр.2.6.4 Бинарное отношение (БО) ρ, заданное на множестве А, называется рефлексивным, если любой элемент этого множества находится в данном отношении с самим собой, т.е. "аÎА: аρа.

Опр.2.6.5 БО ρ называется симметричным, если из того, что пара (a,b) находится в отношении ρ, следует, что и симметричная ей пара (b,a) тоже находится в этом отношении, т.е"a,bÎA: aρb bρa.

Опр.2.6.6 БО называется антисимметричным, если "a,bÎA: aρb bρa a=b.

Опр.2.6.7 БО называется транзитивным, если"a,b,cÎA: aρbbρcaρc.

Примерами рефлексивного и транзитивного отношения является отношение равенства, не симметричного – отношения «больше» или «меньше» на множестве действительных чисел.

БИНАРНЫЕ ОТНОШЕНИЯ (ОПРЕДЕЛЕНИЯ)

БО ρ, заданное на множестве А, является:	Если выполняется следующее условие:
Рефлексивным Симметричным Антисимметричным Транзитивным	"аÎА aρa "a,bÎA aρb bρa "a,bÎA aρb bρa a=b "a,b,cÎA aρb bρc aρc

Опр.2.6.8 Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности (или просто эквивалентностью).

Бинарное отношение ρ можно задать перечислением всех пар из А×А, принадлежащих отношению, указанием характеристического свойства, которым обладают все элементы отношения, а также с помощью так называемого ориентированного графа. Для этого элементы множества А изображают в виде точек и вводят соглашение: если x ρ y, то от точки x проводят стрелку к точке y. Если x ρ х, то начало и конец стрелки совпадают, такую стрелку называют петлей. Выполнив указанные построения, получим фигуру – ориентированный граф. Точки, соединенные стрелками, называются вершинами графа, а сами стрелки – ребрами графа.

Пример. Пусть на множестве М={2,3,4,5,6} задано отношение ρ - кратности элементов, т.е. x ρ y, если x M y (x делится на y без остатка). Построить ориентированный граф данного бинарного отношения.

Решение: Заметим, что по графу наглядно можно судить о свойствах данного отношения:

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

Рассмотрим еще один частный случай общего понятия “соответствие” – отображение множеств.

Рассмотрим два множества X и Y.

Опр. 2.6.9 Если каждому элементу xÎX поставлен в соответствие единственный элемент yÎY, то такое соответствие называется отображением множества Х в множество Y. Т.е., каждому элементу х соответствует только один элемент y Обозначается отображение множеств так: f: X→Y, здесь f – символ самого отображения.

Пример. Пусть Х – множество студентов в аудитории, Y – множество столов в этой аудитории. Соответствие “студент х сидит за столом y ” задает отображение множества Х в множество Y. Это очевидно, так как все студенты сидят за столом, иногда по двое, по трое и т.д., но есть и пустые столы. При таком отображении множества Х в множество Y, элемент yÎY называется образом элемента xÎX, а элемент xÎX называется прообразом элемента yÎY.

Опр.2.6.10 Если при отображении f каждому элементу xÎX поставлен в соответствие один элемент yÎY, при этом соответствии каждому элементу yÎY соответствует единственный элемент xÎX, то такое отображение называется взаимно-однозначным.

Примеры. 1) Пусть Х – множество студентов, Y – множество зачетных книжек. Соответствие “студенту х принадлежит зачетная книжка y ” задает взаимно-однозначное отображение между множествами Х и Y. Это очевидно, так как все студенты имеют зачетные книжки, причем каждый только одну и каждая зачетная книжка принадлежит своему студенту.

2) Перечислить все элементы декартова произведения множеств А={-2, 1, 3} и В={-1, 0, 2, 5}.

Решение: А×В={(-2,-1), (-2,0), (-2,2), (-2,5), (1,-1), (1,0), (1,2), (1,5), (3,-1), (3,0), (3,2), (3,5)}.

Заметим, что точки на координатной плоскости, изображающие элементы декартова произведения В×А, будут симметричны соответствующим точкам из А×В относительно биссектрисы первого и третьего координатных углов.

3) Выяснить, какими свойствами обладает бинарное отношение η - «отношение больше» на множестве N.

Решение: Для любых натуральных чисел хηу, если х>у.

а) х>х – неверно для всех х ÎΝ, т.е. данное отношение не является рефлексивным;

б) для всякой пары натуральных чисел из х>у не следует у>х, т.е. БО не является симметричным;

в) для любых х,у ÎΝ выполняется одно из неравенств: х>у или у>х, т.е. отношение антисимметрично;

г) если х>у, а у>z, то справедливо х>z, т.е. БО транзитивно.

Задания для самостоятельного решения.

Задание 1. Найдите А ∩ В, B\A, AΔB, если

а) А = (0; 5), B = (5; 8);

б) А = (–∞; +∞), В = (–1; 9);

в) А — множество простых чисел, В — множество положительных четных чисел;

Задание 2. С помощью таблицы вхождения элементов определите верно ли следующее равенство (В U С) \ А = С ∩А.

Задание 3. Определить множества A U B, A ∩ B, A\B, B\A, A Δ B, если:

а) A = {x: 0 ≤ x ≤ 4}, B = {x: 2 ≤ x ≤ 8};

б) A = {x: |x - 1| < 2}, B = {x: |x - 1| + |x - 2| < 3};

в) A = {x: x2 - 3x < 0}, B = {x: x2 - 4x + 3 ≥ 0}.

Задание 4. Изобразите следующее множество с помощью диаграммы Венна:

а) АU((ВUС)’);

б) В\(АUС);

в) (А\С)U(В∩С);

г) (ВΔС)\А;

д) В\(АU(С\B)).

Задание 5. Заданы множества А, В и С такие, что А ∩ В = {2; 3}, АUВ={1, 2, 3, 5, 7, 8}, А∩С={1}, CU В= {1, 2, 3, 5, 6, 7, 8}. Найдите множества А, В и С.

Задание 6. Считая универсальным множество всех действительных чисел R, найдите дополнение множества A = { х: 3 < х ≤ 5} до R. Изобразите множество А на координатной прямой.

Задание 7. В студенческой группе 25 человек. Во время летних каникул 9 из них выезжали в турпоездки за границу, 12 – путешествовали по России, 15 – отдыхали в Сочи, 6 – путешествовали за границей и по России, 7 – были и за границей и в Сочи, 8 – и путешествовали по России и были в Сочи и 3 – участвовали во всех трех поездках. Сколько студентов никуда не выезжало?

Задание 8. По итогам экзаменов из 37 студентов отличную оценку по математике имели 15 студентов, по физике – 16, по химии – 19, по математике и физике – 7, по математике и химии – 9, по физике и химии – 6, по всем трем предметам – 4. Сколько студентов получили хотя бы по одной отличной оценке?

Задание 9. Староста курса представил следующий отчет о физкультурной работе: Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек, футбольная и баскетбольная – 16, футбольная и шахматная – 18, баскетбольная и шахматная – 17. В трех секциях одновременно занимаются 15 человек. Объясните, почему отчет не был принят?

Дата добавления: 2014-01-07