Материал: Ответы на экзаменационные вопросы по дискретной математике

Биективное отображение. Пусть . Функция биективна, если она одновременно инъективна и сюръективна. То есть осуществляет взаимно однозначное (один к одному) соответствие между двумя множествами и .

Примеры. ()

— инъективна, но не сюръективна (так как всегда выше оси ).

— сюръективна, но не инъективна ().

— биективна.

Рисунок 17

Пример. Пусть — множество пальто в гардеробе, — множество крючков. Отображение, при котором каждому пальто сопоставляется крючок, на котором оно висит, является инъективным, если на каждом крючке висит не более одного пальто (некоторые крючки могут быть пустыми). Отображение является сюръективным, если на каждом крючке висит хотя бы одно пальто (на некоторых крючках может быть несколько пальто). Отображение является биективным, если на каждом крючке висит ровно одно пальто.

Если существует биективное отображение конечного множества в конечное множество , то в множествах и поровну элементов. Если в множестве больше элементов, чем в множестве , то не существует инъективного отображения в . Если существует сюръективное отображение в , то в не меньше элементов, чем в .

Так как функция — бинарное отношение, то можно построить обратное бинарное отношение , которое не обязательно будет функцией. Условие однозначности может быть нарушено.

Пример. На множестве вещественных чисел задано отношение — функция. Но обратное отношение уже функцией не является, так как ему, например, принадлежат пары и .

Чтобы условие однозначности выполнялось для , функция должна быть биективной. (Если функция будет инъективной, то может не найтись какой-нибудь для , а если будет сюръективной, то могут найтись два или более для .)

Так как всякая функция — бинарное отношение, то композиция функций строится как композиция бинарных отношений.

Пусть и . Их композиция определяется обычным образом:

Рисунок 18

Вместо «» некоторые пишут «». На деле же математики, как ни странно, не могут, да и не пытаются, прийти к общему соглашению относительно этого обозначения. Поэтому важно заранее обозначить композицию так, как будете её использовать в дальнейшем.

Композиция взаимно однозначных функций — взаимно однозначная функция, при этом .

Пример. Пусть , тогда

Из примера видно, что композиция — некоммутативная операция:

3. Бинарное отношение. Свойства. Матрица смежности и граф отношения. Отношение эквивалентности. Примеры

Бинарные отношения и их свойства описаны в предыдущем (втором) вопросе.

Матрица смежности описана в вводном (нулевом) и предыдущем (втором) вопросах.

Граф отношения описан в предыдущем (втором вопросе).

Отношение эквивалентности

Отношение эквивалентности (смежности) — бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности.

Если на множестве задано отношение , то множество разбивается на классы эквивалентных между собой элементов, которые называются классами эквивалентности (сам процесс разбиения множества на классы эквивалентных элементов называется факторизацией). В силу свойства транзитивности любые два класса эквивалентности либо совпадают, либо не пересекаются. Каждый класс эквивалентности можно рассматривать как один элемент нового множества — множества классов эквивалентности. Это множество классов эквивалентности называется фактор-множеством множества по отношению эквивалентности и обозначается . Так как классы эквивалентности не пересекаются, то каждый из этих классов однозначно определяется указанием любого его элемента.

Примеры:

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

2. Отношение «иметь тот же возраст», заданное на множестве всех людей, есть отношение эквивалентности. «Эквивалентные» люди принадлежат к одной и той же возрастной группе. Фактор-множество — номера годов.

3. В множестве всех студентов страны можно рассмотреть отношение принадлежности одному учебному заведению. Тогда эквивалентны студенты одного учебного заведения, а фактор-множество — множество этих учебных заведений. Среди студентов одного вуза можно рассматривать отношения принадлежности одному факультету или принадлежности одному курсу, или обучения в одной группе. В этих случаях классы эквивалентности — это студенты одного факультета, или одного курса, или одной группы, а фактор-множества — множество факультетов, или множество курсов, или множество групп этого вуза (каждую группу можно упомянуть, указав, например, её старосту).

4. В множестве дней одного года можно рассмотреть отношение принадлежности одному месяцу или отношение принадлежности одному дню недели. Тогда классы эквивалентности — это дни одного и того же месяца или дни, приходящиеся на один день недели, а фактор-множества — это 12 месяцев или 7 дней недели, то есть множество из семи элементов: понедельника, вторника, …, воскресенья.

Отношение эквивалентности можно интерпретировать как отношение достижимости на неориентированном графе. Тогда классам эквивалентности будут соответствовать компоненты связности графа: любые вершины из разных компонент связности не достижимы друг из друга, а вершины одной компоненты связности достижимы. Фактор-множеством является множество компонент связности.

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

Отображение называется мономорфизмом, или инъекцией, или отображением «в», если у каждого элемента имеется не более одного прообраза.

Отображение называется эпиморфизмом, или сюръекцией, или проекцией, или отображением «на», если у каждого элемента имеется хотя бы один прообраз.

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

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

Говорят, что множество имеет меньшую мощность, чем множество , а множество — большую мощность, чем множество , если не существует биекции между и , но существует биекция между и некоторым собственным подмножеством множества .

Мощность множества — символ, который сопоставляется всем множествам одинаковой мощности. Обозначение мощности множества или («двойное абстрагирование») или какой-нибудь греческой буквой, например, . В частности, мощностью конечного множества считается число его элементов. Например, если — множество клеток шахматной доски, то , а если — множество дней недели, то .