Файл: Учебника по курсу Основы дискретной математики и логики.pdf

при условии, что скорость движения постоянна. Начальная школа помогает учащимся установить соответствие между заданными выражениями и их числовыми значениями, между числом, характеризующим площадь данной фигуры, и самой этой фигурой и т. п.
Соответствием между множествами A[а ] и B[бэ] называется правило, в силу которого каждому элементу из некоторого подмножества множества
A[а] сопоставляется один или более элементов из множества B [бэ]. Задание соответствия между множествами A[а] и B[бэ] равносильно заданию некоторого подмножества в их декартовом произведении.
Таким образом, для задания и обозначения соответствия, используются правила, аналогичные соответствующим правилам для множеств.
Формула (1.39) представляет конкретные множества A[а]и B[бэ], а в формуле (1.40) приведен пример соответствия между ними.
Пусть G[жэ] − подмножество в декартовом произведении множеств
A[а] и B[бэ], задающее соответствие между ними. Первой проекцией множества G[жэ] будем называть множество всех тех элементов из A[а], каждому из которых соответствует хотя бы один элемент из B[бэ].
Аналогично второй проекцией множества G[жэ] назовем множество всех тех элементов из B[бэ], каждый из которых соответствует хотя бы одному элементу из A[а]. Обозначения для первой и второй проекций представлены в формуле (1.41).
Если соответствие задано как подмножество декартова произведения, то первую проекцию составляют первые координаты упорядоченных пар, а вторые координаты образуют вторую проекцию.
В формуле (1.42) приведены проекции множества G[жэ] из соответствия, заданного формулой (1.40).

Cлайд 14
Пусть соответствие между множествами A[а] и B[бэ] определяется подмножеством G[жэ] их декартова произведения.
Если график соответствия R[эр] между множествами A[а] и B[бэ] совпадает со всем декартовым произведением, то соответствие называют полным. Если же график пуст, то R[эр] называют пустым соответствием.
Соответствие называется всюду определенным, если в нем задействованы все элементы множества A[а]. С учетом введенного определения первой проекции соответствие является всюду определенным, если первая проекция совпадает с множеством A[а].
Соответствие называется функциональным, если каждому элементу из первой проекции множества G[жэ] соответствует единственный элемент из
B[бэ].
Соответствие называется инъективным, если различным элементам из первой проекции множества G[жэ] соответствуют различные элементы множества B[бэ].
Соответствие называется сюръективным, если в нем задействованы все элементы множества B[бэ], то есть вторая проекция совпадает с множеством
B[бэ].
Соответствие называется взаимно однозначным, или биективным, если оно всюду определено, функционально, инъективно и сюръективно.
Формулы (1.43) и (1.44) определяют всюду определенное и сюръективное соответствия с помощью математических символов.
Если элементы множеств изобразить как точки, а соответствие в виде линий со стрелками, то для всюду определенного соответствия стрелки будут выходить из каждой точки множества A[а]. Для функционального соответствия из каждой точки множества А[а] будет выходить не более одной линии.

Для сюръективного соответствия линии будут входить во все точки множества В[бэ]. Соответствие является инъективным, если в каждую точку множества В[бэ] входит не более одной стрелки.
Представленное на рис. 1.2 соответствие всюду определенно, не функционально, не сюръективно, не инъективно.
Слайд 15
На слайде представлен пример соответствия между конечными множествами X[икс] и Y[игрек], задаваемого с помощью множества G[же].
Рассматриваемое соответствие всюду определено, поскольку первая проекция G[жэ] совпадает с множеством X[икс]. Так как первые координаты всех пяти пар из G[жэ] различны, то данное соответствие функционально.
Соответствие сюръективно, поскольку вторая проекция G[жэ] совпадает с множеством Y[игрек]. Наконец, данное соответствие не является инъективным, так как множество G[жэ] содержит две пары элементов с одинаковыми вторыми координатами – единицами.
Рассуждения, приведенные для данной задачи, применимы и в общем случае. Если рассматриваемое соответствие задано множеством пар, все первые компоненты которых различны, то можно сделать вывод о функциональности соответствия. В случае, когда все вторые компоненты пар различны, можно утверждать, что соответствие, определяемое данным множеством, является инъективным.
Cлайд 16
Рассмотрим еще один пример соответствия, которое теперь задано на бесконечных множествах. Каждому многочлену второй степени с действительными коэффициентами сопоставляется вещественное число, являющееся его корнем.
Так как существуют многочлены, не имеющие действительных корней, т. е. в X[икс] есть элементы, которые не участвуют в соответствии, то это соответствие не является всюду определенным.

У многочлена второй степени могут быть два различных действительных корня, т. е. возможна ситуация, когда одному и тому же многочлену – элементу из X[икс] – соответствуют разные элементы из множества Y[игрек], поэтому соответствие не функционально.
Любое действительное число является корнем хотя бы одного многочлена, т. е. все элементы множества Y[игрек] участвуют в соответствии, следовательно, оно сюръективно. А так как разные многочлены могут иметь одинаковые корни, т. е. разным элементам из X[икс] могут соответствовать одинаковые элементы из Y[игрек], то рассматриваемое соответствие не инъективно.
Cлайд 17
Соответствие между множествами A[а] и B[бэ] называется отображением, если оно всюду определено и функционально. В формуле
(1.45) приведено обозначение отображения множества А[а] на множество
В[бэ]. Множество А[а] называют областью определения отображения.
Подмножество множества В[бэ] элементов, участвующих в отображении, называется множеством значений отображения.
Формулы (1.46) и (1.47) представляют примеры отображений для конкретных множеств A[а] и B[бэ].
Первое из них, определенное на множестве всех действительных чисел
R[эр], является сюръективным, но не инъективным. Действительно, каждое число, не превосходящее по модулю единицы, является синусом некоторого угла. Таким образом, отображение является сюръективным. С другой стороны, у разных углов могут быть одинаковые синусы, а это означает, что отображение не является инъективным.
Второе отображение задано на множестве всех натуральных чисел
N[эн], оно инъективно, но не сюръективно. В самом деле, при разных значениях аргумента значения показательной функции также будут

различными. В то же время не каждое натуральное число является некоторой натуральной степенью двойки.
Отображения, заданные на числовых множествах, чаще всего называют функциями.
Cлайд 18
Пусть Г[гамма] – соответствие между множествами A[а] и B[бэ], определяемое подмножеством G[жэ] в их декартовом произведении.
Если в каждой упорядоченной паре (a, b)[а, бэ], принадлежащей множеству G[жэ], поменять элементы местами, то получится множество F пар вида (b, a)[бэ, а], определяющее некоторое соответствие между множествами B[бэ] и A[а]. Это соответствие называется соответствием, обратным к Г[гамма].
Обозначение обратного соответствия приведено в формуле (1.48).
Формула (1.49) представляет пример соответствия между конкретными множествами A[а] и B[бэ], а формула (1.50) задает обратное к нему соответствие.
Из определения обратного соответствия вытекает, что если исходное соответствие всюду определено, то обратное соответствие сюръективно. В случае, когда исходное соответствие сюръективно, обратное соответствие является всюду определенным.
Слайд 19
Пусть Г[гамма] – соответствие между множествами A[а] и B[бэ].
Рассмотрим некоторое подмножество
M[эм] множества A[а]. Образом множества M[эм] при соответствии Г[гамма] будем называть совокупность всех тех элементов из B[бэ], каждый из которых соответствует хотя бы одному элементу из M[эм]. Если S[эс] – некоторое подмножество множества
B[бэ], то прообразом множества S[эс] при соответствии Г[гамма] называется совокупность всех тех элементов из A[а], каждому из которых соответствует хотя бы один элемент из S[эс].

Обозначения для образа и прообраза множества приведены в формулах
(1.51), (1.52).
Рассмотрим следующий пример. Возьмем соответствие, заданное формулой (1.53), и найдем образ множества М[эм], содержащего два элемента – 2 и 7. Элементу 2 соответствует элемент нуль, а элементу 7 – элемент три. Значит, образ множества М[эм] состоит из двух элементов – нуля и трех.
Теперь определим прообраз множества S[эс], которое состоит из одного элемента −1[минус один]. Во множестве G[жэ] находим пару, в которой вторая координата равна минус одному. Первая координата в этой паре равна 8. Следовательно, множество, содержащее единственный элемент восемь, является прообразом множества S[эс].
В формулах (1.54), (1.55) представлены образ и прообраз рассмотренных множеств для указанного соответствия.
Слайд 20
Отображение, которое одновременно является сюръективным и инъективным, называется биективным отображением, или биекцией. Такое отображение также называют взаимно однозначным. С помощью взаимно однозначного отображения понятие мощности, введенное для конечных множеств, можно распространить на бесконечные множества.
Простейшими бесконечными множествами являются счетные множества.
На слайде представлено определение счетного множества. В соответствии с данным определением для доказательства счетности множества А[а] необходимо установить биективное соответствие между множеством А[а] и множеством натуральных чисел, или, иначе говоря, занумеровать элементы множества А[а].

Нумерация элементов множества А[а] предполагает определение порядка перебора элементов данного множества, при котором все они получат натуральные номера.
Все счетные множества имеют по определению одну и ту же мощность.
Установим некоторые свойства счетных множеств.
1.
Всякое подмножество счетного множества конечно или счетно.
2.
Объединение конечного или счетного числа счетных множеств есть счетное множество.
3.
Всякое бесконечное множество содержит счетное подмножество.
Множества M[эм] и N[эн] называются эквивалентными, если между ними можно установить взаимно однозначное соответствие. Два конечных множества эквивалентны между собой в том и только в том случае, когда число элементов у них одинаково. Ясно, что два множества, эквивалентные третьему, эквивалентны между собой; в частности, любые два счетных множества эквивалентны между собой.
Слайд 21
Обратимся к примерам счетных множеств. Сначала рассмотрим множество целых чисел. Нумерацию всех целых чисел проведем следующим образом.
Элементу нуль поставим в соответствие номер один, наименьшему положительному числу один поставим в соответствие номер два. Далее перейдем к отрицательным числам и наибольшему из них припишем номер три. Затем вновь обратимся к положительным числам и следующему за единицей числу два присвоим номер четыре. Пятым в нашей нумерации будет ближайшее к нулю отрицательное число, которое еще не было занумеровано, а именно, минус два. Продолжая этот процесс, мы занумеруем все целые числа.
Таким образом, мы установили взаимно однозначное соответствие между множествами целых и натуральных чисел. Построенное отображение

можно охарактеризовать следующим образом. Положительному целому числу n[эн] соответствует четное натуральное число 2n[два эн], а отрицательному числу –n[минус эн] соответствует нечетное натуральное число 2n + 1 [два эн плюс один].
Слайд 22
Следующим примером счетного множества является множество натуральных степеней числа два. Формула, определяющая элементы этого множества, задает биекцию между множеством А[а] и множеством натуральных чисел.
Далее рассмотрим множество рациональных чисел. Для установления взаимно однозначного соответствия между множествами Q[кю] и N[эн] расположим сначала положительные рациональные числа в виде бесконечной таблицы (1.56). Занумеруем теперь эти числа «по диагоналям» в соответствии со стрелками. При этом договоримся включать в наш перечень только различные числа, то есть не будем нумеровать элементы, встречающиеся повторно. В соответствии с нашим соглашением первым элементом будет единица, вторым – двойка, третьим – одна вторая. Номер четыре получит число одна третья, номер пять – число три. Шестым элементом в нашей последовательности будет четверка, седьмым – три вторых. Продолжая нумерацию согласно стрелкам, мы занумеруем все положительные рациональные числа.
Аналогичным образом занумеруем все элементы множества отрицательных рациональных чисел. Рассмотрим последовательность, представленную формулой (1.57). В ней знаком плюс отмечены занумерованные нами положительные рациональные числа, знаком минус – соответствующие им отрицательные числа. Мы расположили все элементы множества рациональных чисел в виде последовательности, а значит, доказали его счетность.

Слайд 23
Отметим, что множество чисел, заполняющих отрезок от нуля до единицы, не является счетным. Мощность этого множества называется мощностью континуума. Два множества называются эквивалентными, если между ними можно установить взаимно однозначное соответствие. Про эквивалентные множества говорят, что они имеют одинаковую мощность.
Все множества, эквивалентные множеству чисел отрезка от нуля до единицы, имеют мощность континуума. Примерами множеств, эквивалентных отрезку от нуля до единицы, являются произвольные отрезки, интервалы, полуинтервалы, вся числовая прямая.
Отношение равномощности обладает рядом свойств, а именно:
• рефлексивностью, каждое множество равномощно самому себе;
• симметричностью, т. е. если множество X[икс] равномощно множеству
Y[игрек], то множество Y[игрек] равномощно множеству X[икс];
• транзитивностью, т. е. если множество X[икс] равномощно множеству
Y[игрек], множество Y[игрек] равномощно множеству Z[зет], то множество Х равномощно множеству Z[зет].
Определение равномощности уточняет интуитивную идею о множествах «одинакового размера». А как формально определить, когда одно множество «больше» другого? Говорят, что множество A[а] по мощности не больше множества B[бэ], если оно равномощно некоторому подмножеству множества B[бэ], возможно, самому B[бэ].
Отношение «иметь не большую мощность» обладает многими естественными свойствами, некоторые из них перечислены на слайде.
Утверждение третьего свойства составляет содержание основной теоремы теории множеств, теоремы Кантора – Бернштейна.

Слайд 24
Тема 1.3. Отношения и их свойства
Мы уже обсудили, что множества играют фундаментальную роль в самой математике и ее многообразных приложениях. Однако описывая окружающий мир, мы не только перечисляем интересующие нас объекты, т. е. задаем множество, но и указываем отношения, которыми эти объекты могут быть связаны. Такие связи могут быть весьма разнообразными, но мы начнем с наиболее общего представления об отношениях элементов множеств.
В отношениях могут находиться элементы самых разнообразных множеств. Например, могут быть родственные отношения между людьми, скажем, один человек другому является братом; между числами – одно число меньше другого; между геометрическими объектами – некоторая точка принадлежит той или иной прямой и т. д.
Совсем не обязательно, чтобы отношение связывало равно два объекта
– человека с человеком, число с числом, точку и прямую. Например,
«отношение точка A[а] лежит между точками B[бэ] и C[цэ]» связывает, как мы видим, три объекта.
Как нередко фиксируются отношения в обыденной жизни? Например, что два человека стали мужем и женой. Идут в ЗАГС, и там им выдают бумагу, в которой так и написано, что эти два человека – муж и жена. Как фиксируется, что такой-то является сыном или дочерью таких-то двух человек? То же самое – выдается бумага, в которой фигурируют эти три человека. Как фиксируется, что данный человек принят на работу на такое-то предприятие?
Заключается договор между этим человеком и уполномоченным представителем предприятия. Что общего во всех этих примерах? В каждом из них просто фиксируется, кто именно или что именно, находится в рассматриваемом отношении. Если отвлечься от того, о чем эти отношения, то становится понятно, что задать отношение – это записать те объекты, которые находятся в данном отношении. Такую запись удобно