Этот пример показывает, что суперпозиция бинарных отношений, вообще говоря, не обладает свойством коммутативности.

Доказательство.

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

Здесь E_M – бинарное отношение равенства в множестве M.

5. Свойства суперпозиций бинарных отношений

1. Свойство объединения. Пусть во множестве A заданы бинарные отношения   и , I. Здесь I - конечный или бесконечный набор индексов. Тогда

,  .        (2)

Заметим, что в вышеприведенных соотношениях значки нельзя заменить на .

Доказательство.

Пусть  и .

2. Свойство ассоциативности. Для любых бинарных отношений , заданных на некотором множестве A, справедливо равенство:

.                         (3)

Доказательство.

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

Это утверждение говорит о том, что какими бы двумя различными способами ни расставлять скобки в выражении , чтобы получить суперпозицию двух отношений, получим равные отношения.

3) Суперпозиция обратных отношений.

Определение 11.

Пусть на множестве A задано бинарное отношение , тогда отношением, обратным к ,  называется отношение ,  также заданное на A, которое состоит из тех и только тех пар , для которых справедливо, что .

ПРИМЕР 7.

Пусть на множестве A={0,1,2,3} задано бинарное отношение ={(0,1); (2,3); (1,3)}, тогда = {(1,0); (3,2); (3,1)}.

Для обратных отношений справедливы следующие равенства:

,  .               (4)

Заключение

- отношение на множестве есть множество;

- бинарные отношения могут быть заданы на декартовом произведении множеств;

- отношения могут быть рефлексивными, симметричными, антисимметричными и транзитивными;

- над отношениями можно делать такие же операции, как и над множествами;

- суперпозиция определяет новое связное множество;

- операция суперпозиции не коммутативна.

Литература

1. Яблонский Я. В. Введение в дискретную математику. – М.: Высшая школа, 2001. - 384 с.

2. Москинова Г.И. «Дискретная математика». – М.: Логос, 2002. – 240 с.

3. Ильин В.А., Позняк Э.Г. «Л инейная алгебра». – М.: Физматлит, 2001.

4. Самсонов Б.Б. и др. «Компьютерная математика». – Ростов-на-Дону: Феникс, 2002. – 512 с.

Функции, заданные на множестве

Понятие функции на множестве

Мощность множеств

Мощность континуума

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

Роль и место лекции

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

1. Понятие функции на множестве

Введем понятие функции через бинарное отношение.

Определение 1.

Функцией называется любое бинарное отношение, которое не содержит двух пар с одинаковыми первыми элементами и разными вторыми.

Если f – функция, то множество D_f мы будем называть областью определения функции f, а множество R_f  – областью значения функции.

ПРИМЕР  1.

1. {(1,1); (2,3); (3,2)}, есть функция с областью определения {1,2,3} и это же множество является ее областью значений;

2. Бинарное отношение {(1, 2); (2, 2); (пешка, ферзь); (ладья, слон)} – есть функция с областью определения {1, 2, пешка, ладья} и областью значения {2, ферзь, слон};

3. Бинарное отношение {(1,2); (1,1); (2,3)} не является функцией, поскольку содержит пары с одинаковыми первыми и разными вторыми элементами;

4. {((x, y), x+y) : (x,y) } - функция с областью определения в  и областью значений в .

Определение 2.

Функции f и g равны между собой тогда и только тогда, когда они состоят из одних и тех же элементов:

 и .

Итак, пусть задана область определения функции f – множество D_f. Часто возникает задача – найти область значений этой функции - множество R_f. Точно это сделать бывает трудно, поэтому иногда проще указать множество Y, такое, что R_f Y. Удобно ввести следующие определения.

Определение 3.

Если D_f  X и R_f  Y, то говорят, что функция f определена в множестве X и принимает свои значения в множестве Y.

Определение 4.

Если D_f = X и R_f  Y, то говорят, что функция f определена на множестве X и принимает свои значения в множестве Y.

Определение 5.

Если, кроме того, что D_f = X, выполнено еще условие R_f = Y, то отображение (функцию) f называют отображением множества X "на" Y, или сюръекцией. Заметим, что каждая функция f является сюръекцией множества D_f на R_f.

Определение 6.

Функция f называется инъективной, или инъекцией, если из того, что f(a) = f(b), следует, что a = b.

Определение 7.

 Инъективное отображение множества X на множество Y называется однозначным (биективным), или просто биекцией типа X Y.

1. Для заданной квадратичной функции f = {(x,y) : y = x² } проверить, является ли она биекцией. Функция f является отображением множества R на множество . Для проверки биективности функции f необходимо проверить, является ли она еще и инъекцией. Квадратичная функция f такова, что f(1) = f(-1), однако отсюда не следует, что 1 = -1. Таким образом, показали, что отображение f не является инъекцией. Следовательно, биективным такое отображение f также не является.

2. Рассмотрим функцию g, которая каждому элементу x  ставит в соответствие число g(x) = 2x+1. Покажем, что заданная таким образом функция g является взаимно-однозначным соответствием между Z и множеством нечетных целых чисел. Действительно, из того, что 2x₁+1 = 2x₂+1, следует, что x₁ = x₂.

В последнем примере было установлено взаимно-однозначное соответствие между множеством Z и его собственным подмножеством. Вообще говоря, справедливо следующее утверждение.

Теорема 1.

Множество M бесконечно тогда и только тогда, когда существует взаимно-однозначное соответствие между самим множеством M и его собственным подмножеством.

Важно!!!

Из определения суперпозиции бинарных отношений f и g следует, что когда f и g являются функциями, то значение их суперпозиции fg на элементе x вычисляется следующим образом:  – и означает, что если f: , а g: , тогда fg : .

Определение 8.

Когда для заданной функции f отношение f ^-1 является также функцией, то это отношение называется функцией обратной к f и обозначается f ^-1.

Теорема 2.

Для любой заданной функции f обратная ей функция f ^-1 существует тогда и только тогда, когда f – инъективна.

Доказательство.

Необходимость. Предположим, что для заданной функции f обратная к ней функция f ^-1 существует. Покажем, что в этом случае f – инъективна.

Доказательство будем проводить от противного. Пусть f не является инъективным отображением. Это означает, что существует, по крайней мере, две пары (a, c) f, (b, c) f, a . Следовательно, f ^-1 содержит пары (c, a), (c, b) и поскольку , бинарное отношение f ^-1 не является функцией. Таким образом мы получили противоречие. Значит, исходное предположение о том, что f не является инъективным отображением, ложно. На этом и завершается доказательство необходимости приведенного утверждения. Доказательство достаточности будет приведено немного позднее.

Теорема 3.

Два конечных множества имеют одинаковую мощность тогда и только тогда, когда они эквивалентны.

Доказательство.

Необходимость. Пусть два конечных множества имеют одинаковую мощность |A|=|B|= n, т.е. A = {a₁, a₂,..., a_n}, B = {b₁, b₂,..., b_n}. Отображение f: A B, определенное по формуле f(a_k) = b_k, k = 1, ..., n, является биекцией и, следовательно, A~B.

Достаточность. Пусть A~B и f: A B – биекция, устанавливающая эту эквивалентность. Если A = {a₁, a₂,..., a_n }, то B = { f(a₁), f(a₂),..., f(a_n)}и элементы f(a_k) попарно различны. Следовательно, |A|=|B|= n. Доказательство завершено.

Определение 11.

Множество A называется счетным, если оно эквивалентно множеству натуральных чисел: A~N. В этом случае говорят, что множество A имеет счетную мощность.

Теорема 4.

Множество A имеет счетную мощность тогда и только тогда, когда элементы этого множества можно перенумеровать, используя все натуральные числа.

Доказательство.

Необходимость. Пусть множество A счетно. Это означает, что A~N. По определению эквивалентности существует биекция f: . Положим, что a_n= f(n), . Тогда A={a₁, a₂,... }, и тем самым мы перенумеровали элементы множества A.

Достаточность. Пусть элементы множества A перенумерованы, т.е. A={a₁,a₂,...}. Определим отображение f:  или f(n)=a_n, . Очевидно, что f – биекция и поэтому N~A. Доказательство завершено.

Теорема 5.

Объединение конечного или счетного набора конечных или счетных множеств конечно или счетно.

Теорема 6.

Множество Q рациональных чисел счетно.

Доказательство этого утверждения сводится к правилу пересчета всех рациональных чисел.

Итак, мы познакомились с конечными и бесконечными множествами. Было показано, что надо понимать под мощностью множеств в каждом из рассмотренных случаев. Однако возникает вполне естественный вопрос – а существуют множества с мощностью большей, чем счетная?

3. Мощность континуума

Теорема 7.

Множество M = (0,1) несчетно.

Предположим, что множество M - счетно и, следовательно, элементы этого множества можно перенумеровать, используя все натуральные числа, т.е. M = {x₁,x₂,... }. Запишем числа  в виде десятичных дробей (без 9 в периоде):

...

здесь ; верхний индекс обозначает номер числа, а нижний – порядковый номер знака. Теперь образуем новое число   по следующему правилу: , если , и 0, если . Тогда очевидно, что , но образованное таким образом новое число не совпадает ни с одним из пересчитанных чисел x_i. Следовательно, интервал (0,1) содержит, как минимум, на 1 точку больше, чем есть натуральных чисел, и его мощность не равна мощности множества натуральных чисел. Мы доказали, что множество точек интервала (0,1) не счетно.

Множество A имеет мощность континуума, если оно эквивалентно множеству точек интервала (0,1). Мощность континуума обозначают буквой c.

ПРИМЕР 4.

Пусть a<b – два действительных числа. Покажем, что интервал (a,b) имеет мощность континуума. В качестве биекции, устанавливающей эквивалентность множеств (a,b) и (0,1), можно рассматривать функцию f(x) = (b-a)x+a: (0,1) (a,b).

Теорема 8.

Существуют иррациональные числа. Более того, множество иррациональных чисел имеет мощность континуума.

Доказательство.

Поскольку  и , а , мы получаем, что .

Заключение

В лекции заканчивается тема «Дискретная математика», однако на протяжении всего курса к ней необходимо будет возвращаться с целью расширения объема понятий и знаний. С целью лучшего восприятия остальных тем высшей математики объединим некоторые разделы дискретной математики с остальными темами. При этом нам придется столкнуться с такими разделами дискретной математики, как «Теория графов», «Логика», «Векторные пространства» и др. Важно целостное понимание всех разделов высшей математики на основе пройденного материала. Отметим следующее:

- функция – это множество пар, у которых одному первому элементу соответствует единственный второй элемент;

- как и у отношений, у функций есть обратная функция;

- суперпозиция функции есть «сложная функция» в классическом понимании;

- бесконечные множества имеют мощность;

- мощность . 

Литература

1. Яблонский Я. В. Введение в дискретную математику. – М.: Высшая школа, 2001. – 384 с.

2. Москинова Г.И. Дискретная математика. – М.: Логос, 2002. – 240 с.

3. Ильин В.А., Позняк Э.Г. Линейная алгебра. – М.: Физматлит, 2001.

4. Самсонов Б.Б. и др. Компьютерная математика. – Ростов-на-Дону: Феникс, 2002. – 512 с.