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

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

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

Таким образом, А • В = { (х, у)х еАиу еВ}.

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

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

Таблица 2.4

Таблица всех возможных елочных украшений.

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

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

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

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

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

Рис. 2.29. Декартово произведение множеств А = { 1, 2, 3} иЯ = {4, 5, 6, 7}.

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

Таблица 2.5

Таблица, показывающая, в каких городах побывали

ученики.

Окончание табл. 2.5

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

Будем говорить, что между элементами двух множеств А и В установлено соответствие р, если в их произведении А • В выделено некоторое подмножество Q. Если пара (а, Ь) е ОсЛ В, это означает по определению, что элементы а и b множеств А и В находятся в отношении р (пишется apb).

Еще один пример соответствия: пусть даны множества А (студент) и В (множество групп). Утверждение «студент а учится в группе Ь» задает соответствие между множеством студентов и множеством групп. Здесь а пробегает множество значений А, b — множество значений В. Такое соотношение называется бинарным соответствием, т. е. соответствием между двумя множествами А и В.

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

Рис. 2.30. Расписание занятий в виде ориентированного графа

Расписание занятий в виде таблицы.

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

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

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

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

Например, возьмем в качестве элементов множества А случайную группу людей (например, едущих в одном поезде). И выберем бинарное отношение р на этом множестве следующим образом: два человека из А будут находиться в данном отношении, если они родились в одном и том же месяце (иод одним знаком зодиака; имеют одинаковые имена и пр.). И еще элемент а_Л из А будет находиться в отношении 8 с элементом а₂ из того же множества, если, допустим, первый человек выше ростом, чем второй (старше, тяжелее и пр.).

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

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

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

Бинарное отношение р называется симметричным, если из того, что пара (а, b) находится в отношении р, следует, что и симметричная ей пара (Ь, а) тоже находится в этом отношении, т. е.

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

Бинарное отношение называется транзитивным, если.

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

Таблица 2.7

Бинарные отношения (определения).

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

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

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

Рис. 231. Ориентированный граф бинарного отношения.

кратности.

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

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

Рассмотрим два множества X и У. Если каждому элементу х еХ поставлен в соответствие единственный элемент у е У, то такое соответствие называется отображением множества X в множество У. То есть каждому элементу х соответствует только один элемент#. Обозначается отображение множеств так:/: X —" У, где/ — символ самого отображения.

Например, пусть X — множество студентов в аудитории, У — множество столов в этой аудитории. Соответствие «студент х сидит за столом у» задает отображение множества X

в множество У. Это очевидно, так как все студенты сидят за столом, иногда по двое, по трое и т. д., но есть и пустые столы. При таком отображении множества X в множество Y элемент у е Yназывается образом элемента ieX, a элемент х g X называется прообразом элемента у е У.

Если при отображении / каждому элементу х gX поставлен в соответствие один элемент у g У, при этом соответствии каждому элементу у g У соответствует единственный элемент х еХ, то такое отображение называется взаимно однозначным.

Пример 2.46. Пусть X — множество студентов, У — множество зачетных книжек. Соответствие «студенту х принадлежит зачетная книжка у» задает взаимно однозначное отображение между множествами X и У. Это очевидно, так как все студенты имеют зачетные книжки, причем каждый только одну, и каждая зачетная книжка принадлежит своему студенту.

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

Решение:

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

Пример 2.48. Выяснить, какими свойствами обладает бинарное отношение г| — «отношение больше» на множестве N.

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

• а) х > х — неверно для всех х е N, т. е. данное отношение не является рефлексивным;
• б) для всякой пары натуральных чисел из х > у не следует у > х, т.е. БО не является симметричным;
• в) для любых х, у е N выполняется одно из неравенств: х > у или у > х, т. е. отношение антисимметрично;
• г) если х > у, а у > 2, то справедливо х > 2, т. е. Б О транзитивно.