Функции как отношения на множествах

С привычным понятием функции мы знакомы со школьной скамьи. Однако такое понятие сложилось в результате долгого пути развития. Впервые оно появилось в 17-ом веке в работах Ферма и Декарта и окончательно сформировалось в современном (привычном) виде у Дирихле в первой половине 19-го века.

Современное представление о функции основано на том, что оно является частным случаем отношений. Пусть отношение Ф на множестве А таково, что для всякого существует ровно один элемент для которого выполняется отношение х Ф у. Тем самым каждому элементу сопоставляется некоторый элемент определенный этим условием. Такое отношение называется функцией или отображением (иногда однозначным соответствием). Элемент соответствующий элементу , называется значением функции Ф на элементе х (более привычно вместо Ф писать f). Эту зависимость (отношение) между х и у записывают в виде

Множество Ф тех пар для которых выполнено отношение х Ф у, называется графиком функции.

Например, если А – числовая прямая, а отношение Ф есть отношение равенства (у = х), то график состоит из всех точек вида и является биссектрисой координатного угла, т.е. обычным графиком функции у = х. Если отношение Ф выполнено для тех пар для которых , то график этой функции есть обычная синусоида.

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

Выше мы рассмотрели случай, когда элементы х и у принадлежали разным множествам. Рассмотрим отношения на таких парах где , а . Отношение Ф опять таки называют функцией или отображением, если для каждого элемента существует единственный элемент , для которого выполнено отношение х Ф у. Такую функцию символически записывают как Здесь А называется областью отправления функции Ф, а В – областью прибытия. Отображение называют также отображением множества А во множество В. Элемент , который соответствует элементу обозначается Ф (х) и называется образом элемента х. Сам элемент х называется прообразом элемента Ф (х).

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

Поясним сказанное примерами.

1. Пусть А – множество людей, а N – множество натуральных чисел. Далее, пусть – отображение, которое каждому человеку ставит в соответствие его рост, выраженный в сантиметрах, округленный до целочисленных значений. Ясно, что каждому человеку соответствует только одно единственное значение роста. Но значение роста, например в 300 см, не соответствует никакому человеку. С другой стороны, существует много людей, у которых рост – 175 см.

2. Пусть А – множество живущих в настоящее время людей, В – множество всех когда-либо живущих людей, а отображение ставит в соответствие каждому человеку его отца. Ясно, что у каждого человека имеется единственный образ – отец. Но не у всякого человека есть прообраз, так как не всякий человек есть отец (если у – женщина или у – бездетный мужчина). Кроме того, несколько человек могут иметь одного отца.

В зависимости от того, какое число образов элемент множества А имеет во множестве В и какое число прообразов элемент множества В имеет во множестве А отображения называют инъективными, сюръективными и биективными.

Отображение называют инъективным или взаимно-однозначным, если для каждого элемента существует не более одного прообраза во множестве А. Другими словами, график функции (отображения) является инъективным, если он не содержит упорядоченных пар с разными первыми и одинаковыми вторыми элементами.

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

Если отображение одновременно инъективно и сюръективно, то оно называется биективным. Множества А и В, для которых существует биективное отображение, называются равномощными, т.е.

На рис. 2.8. приведены примеры рассмотренных видов отображений

 

А В А В

 

 

 

а) b)

 

c) d)

Рис. 2.8

 

Отображение на рис. 2.8 a) не инъективно, так как имеет два прообраза – элементы и не сюръективно, так как это отображение не является функцией в силу того, что образами элемента являются три прообраза –

Отображение, представленное на рис. 2.8 b) является сюръективным, так как ни один элемент множества А не имеет больше одного образа, но не инъективным, поскольку элемент имеет два прообраза – элементы .

Отображение на рис. 2.8 с) не сюръективно, так как элемент имеет три прообраза и инъективно, поскольку ни один элемент множества В не имеет более одного прообраза во множестве А.

И, наконец, отображение на рис. 2.8 d) является инъективным и сюръективным, а потому – биективным.

 

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

 

Понятие эквивалентности в нашем сознании ассоциируется с одинаковостью или равенством каких-то объектов. Э естественно, так как само слово «эквивалент» с латинского языка переводится как равносильный.

Математическое понятие эквивалентности, сохраняя его содержательный смысл, четко формулируется в терминах теории множеств. При этом можно дать две не противоречащих друг другу формулировки понятию эквивалентности: конструктивную и аксиоматическую.

Конструктивная формулировка опирается на выделение из некоторого множества М таких объектов х, которые обладают некоторым общим свойством или признаком. Иначе говоря, выбирают сходные, в чем-то одинаковые (равные) объекты. Такие объекты относят к одному классу. Именно так строят всевозможные классификации. Сам процесс отнесения объекта к какому-либо классу в теории множеств называется разбиением множества М.

Систему непустых подмножеств { М ₁, М ₂, …, М _n} множества М называют разбиением этого множества, если выполняются условия:

1. .

2. при

Подмножества называются классами данного разбиения. Отсюда вытекает такое определение эквивалентности: отношение Ф на множестве М называется отношением эквивалентности, если существует разбиение {М₁, М₂, …, М_n} множества М такое, что отношение x Ф y выполняется тогда и только тогда, когда х и у принадлежат некоторому об щему классу М_i данного разбиения.

Аксиоматическая формулировка определяется через свойства (аксиомы), которые выделяют отношения эквивалентности среди прочих бинарных отношений. Отношение Ф на множестве М называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Можно доказать, что обе формулировки отношения эквивалентности являются равносильными.

Рассмотрим примеры отношений эквивалентности.

1. Отношение равенства в любой системе чисел.

2. Отношение подобия во множестве всех треугольников в евклидовой плоскости.

3. Отношение параллельности на множестве прямых в евклидовой плоскости.

Рассмотрим пример отношения, которое не является отношением эквивалентности. Пусть на декартовом произведении рассматривается отношение x < y. Это отношение не является отношением эквивалентности по следующим причинам. Во-первых, не выполняется свойство рефлексивности, так как х, так же как и у, не может быть меньшим самого себя. Во-вторых, не выполняется и свойство транзитивности, так как если х < y, то у не может быть меньше х. Хотя свойство транзитивности и выполняется, но этого недостаточно, чтобы данному отношению быть эквивалентностью.

Еще одним характерным примером отношения, не представляющим эквивалентность, является отношение перпендикулярности прямых в евклидовой плоскости . Действительно, это отношение обладает следующими свойствами.

1. Оно антирефлексивно, так как прямая х не может быть перпендикулярной сама себе.

2. Оно симметрично, поскольку если , то .

3. Оно не транзитивно, поскольку если и , то х ǀǀ z, т.е. невозможно .

 

Отношения порядка

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

Пусть Х – произвольное множество. Отношение Ф на множестве называют отношением частичного порядка, если оно обладает следующими свойствами:

· рефлексивности – х Ф х;

· антисимметричности – отношения х Ф у и у Ф х выполняются только при х = у;

· транзитивности – если х Ф у и у Ф z, то х Ф z.

Отношение частичного порядка обозначают символом «≤» При этом элементами x, y и z могут быть объекты любой природы: числа, геометрические фигуры, слова и т.д. Например, упорядочивание слов, терминов,понятий в различных словарях осуществляется в соответствии с отношением частичного порядка и называется лексикографическим порядком.

Содержательный смысл частичной упорядоченности означает предшествование одного элемента множества относительно другого.

Если бинарное отношение Ф на множестве Х антирефлексивно и транзитивно, то оно называется отношением строгой упорядоченности и обозначается символом «<». Доказано, что для отношения строгого порядка определяющими свойствами являются его антирефлексивность и транзитивность, а антисимметричность следует из этих двух свойств. Таким образом, отношение строгого порядка всегда антисимметрично.

В качестве отношений частичного порядка можно привести следующие примеры.

1. Отношение на множестве действительных чисел R. Так как действительные числа являются расширением множества Z целых чисел, то это отношение является частичным и для Z.

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

Примерами отношений строгого порядка являются:

1. Отношение х < y на множестве R.

2. Расположение спортсменов или команд в турнирной таблице на множестве всех мест (на одном месте не могут находиться более одного спортсмена или команды).

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

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

Упражнения

1.Пусть имеется универсальное множество U = {1, 2, 3, 4, 5}. Записать элементы множества если:

1) 2) 3)

2. Из каких элементов состоит множество если А состоит из чисел вида 4 n а В – из чисел вида 3 n, где .

3. Пусть Записать множества:

1) 2) 3) 4)

5) 6)

4. Записать декартово произведение для множеств:

1) 2) 3)

5. Отношение определено на декартовом квадрате множества Доказать, что Ф – отношение эквивалентности.

6. Привести пример рефлексивного отношения, которое не является симметричным и транзитивным.

7. Привести пример симметричного отношения, которое не является рефлексивным и транзитивным.

8. Привести пример транзитивного отношения, которое не является рефлексивным и симметричным.

9. Привести пример симметричного и транзитивного отношения, которое не является рефлексивным.

10. Является ли отношение определенное на декартовом произведении множеств функцией?

11. Является ли функция инъективной?

12. Является ли отношение определенное на декартовом произведении множеств функцией? Если да, то является ли данная функция сюръекцией, инъекцией?

 

Парадоксы теории множеств

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

Парадокс Рассела в первоначальной формулировке связан с понятием нормального (иногда говорят обычного или ординарного) множества. Напомним, что нормальным является множество, которое не содержит себя в качестве своего элемента. Ненормальным (или экстраординарным) являются множества, которые содержат себя в качестве элемента.

Большинство рассматриваемых множеств относятся к типу нормальных. Однако в природе встречаются и нормальные множества. Примером ненормального множества может служить множество всех абстрактных понятий. Действительно, понятие множества само является абстрактным и поэтому должно принадлежать множеству абстрактных понятий.

Приведем другой пример ненормального множества. Пусть мы имеем дело с множеством простых предложений. Мы хотим объявить об этом предложением, например, таким: «Здесь записано множество всех простых предложений». Для сокращения записи это простое предложение обозначим буквой А, а все другие простые предложения соответствующими малыми буквами с индексами. Тогда, так как само предложение А простое, то оно должно входить во множество всех простых предложений. Таким образом, будем иметь

.

Спрашивается, является ли записанное множество нормальным? В соответствии с определением нормального множества данное множество не является нормальным, так как оно содержит самое себя в качестве элемента, т.е. Этим самым нарушено условие, что множество А должно быть простое. С другой стороны, если мы его не укажем во множестве А, что соответствует то мы не перечислим все простые предложения и тоже нарушим условие. Таким образом, получается, что множество А мы должны включать во множество А и одновременно не должны включать. А это и есть противоречие.

Парадокс Рассела замечателен своей общностью. На его основе можно выявить большое число частных парадоксов. Наиболее известными из них являются: парадокс брадобрея, каталог всех нормальных каталогов, мэр города и др.

Парадокс брадобрея, который предложил, кстати, сам Рассел в качестве практического варианта общего случая, состоит в следующем. Совет одной деревни определил обязанности брадобрею следующим образом: брить всех мужчин деревни, которые не бреются сами. Должен ли он брить сам себя? Если да, то он будет относиться к тем мужчинам, которые бреются сами. Но тогда он нарушит указ совета, по которому он должен брить только тех, кто сам не бреется. Если нет, то он будет относиться к тем мужчинам, кто не бреется сам, и, значит, он должен брить себя.

Таким образом, брадобрей должен себя брить и в то же время не должен себя брить. Но так быть не может. Это и есть явное противоречие.

Сходным с парадоксом брадобрея является парадокс мэр города. Каждый мэр города живет или в своем городе, или вне его. Был издан указ о выделении одного специального города, где бы жили мэры, не живущие в своем городе. Вопрос, где должен жить мэр этого специального города? Если он хочет жить в своем городе, то он не может этого сделать, так как там могут жить только мэры, не живущие в своем городе. Если он не хочет жить в своем городе, то, как и все мэры, не живущие в своих городах, он должен жить в отведенном городе, т.е. в своем. Из приведенных рассуждений следует, что он не может жить ни в своем городе, ни вне его.

Парадокс каталог всех нормальных каталогов получается так. Некая библиотека решила составить библиографический каталог, в который входили бы все те и только те каталоги, которые являются нормальными, т.е. не содержат ссылки на себя. Спрашивается, где должен быть упомянут составленный каталог? Если он будет упомянут в составленном каталоге, т.е. в самом себе, то составленный каталог окажется ненормальным. А по условию этого не должно быть. Если же составленный каталог не будет упомянут, то этот составленный нормальный каталог окажется нигде не зафиксированным, хотя по условию должны быть упомянуты все нормальные каталоги.

С описанными ситуациями, аналогичными приведенным парадоксам, в повседневной жизни мы встречаемся довольно часто. Так в конце или начале любой книги приводится ее содержание или оглавление, где указаны главы, параграфы, пункты с указанием той страницы, с которой начинается соответствующая глава или параграф. Спрашивается, где указывать номер страницы, с которой начинается оглавление? Она, как правило, и не указывается.

1.Аналогичная ситуация возникает в учреждениях, когда характеристики подчиненным подписывает выше стоящий начальник. А кто должен подписывать характеристику этому начальнику? Начальник, стоящий еще выше? А этому последнему начальнику? И так можно дойти до президента. Но кто подписывает президенту? Сам себе?

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

 

Вопросы для самоконтроля

1. Дайте определение множества по Кантору. Определите конечное и бесконечное, счетное и несчетное множества.

2. Какие существуют два основных способа задания множеств? Приведите примеры задания множеств.

3. Поясните понятие подмножество, как символически записывают отношение между множествами?

4. Какими свойствами может обладать отношение включения?

5. Какие подмножества множества называются несобственными?

6. Что такое множество-степень и чему равна его мощность?

7. В чем состоит различие между max и sup, min и inf?

8. Приведите символическую запись операции объединения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

9. Приведите символическую запись операции пересечения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

10. Приведите символическую запись операции вычитания множеств и дайте ее интерпретацию с помощью кругов Эйлера.

11. Приведите символическую запись операции дополнения множеств и дайте ее интерпретацию с помощью кругов Эйлера.

12. Что такое универсальное множество и дайте его интерпретацию с помощью кругов Эйлера.

13. Приведите символическую запись симметрической разности двух множеств и дайте ее интерпретацию с помощью кругов Эйлера.

14. Как определяется сумма двух множеств, дайте ее геометрическую интерпретацию.

15. Приведите формальные записи коммутативности, ассоциативности и дистрибутивности множеств.

16. Приведите формальные записи операций объединения и пересечения для одного множества с пустым и универсальным множествами.

17. Приведите формальные записи идемпотентности множеств, законов де Моргана и поглощения.

18. Поясните сущность отношений на множествах.

19. Что такое кортеж, декартово произведение?

20. Дайте определение отношения и раскройте его содержательный смысл.

21. Что такое область определения, значений и график отношения?

22. Как формально записывается обратное отношение и в чем его смысл?

23. Приведите формальную запись операций объединения, пересечения, разности и инверсии отношений. Приведите примеры.

24. Приведите формальную запись операций композиции и сужения отношений. Приведите примеры.

25. Приведите основные свойства отношений и соответствующие примеры.

26. Охарактеризуйте понятие функции как отношения на множествах.

27. Дайте определение инъективного, сюръективного и биективного отображения. Приведите примеры.

28. Дайте определение отношению эквивалентности. Приведите примеры эквивалентных и неэквивалентных отношений.

29. Поясните понятия отношений частичного и строгого порядка.

30. В чем суть парадоксов теории множеств. Приведите какой-нибудь пример парадокса и объясните его.

 

 

Алгебра логики