Множества, отображения, логика (стр. 3 )

§ 3. Отображения

 

3.1. Говорят, что задано соответствие

f : X ¾® Y

множества Х на множество Y , если задано подмножество G Ì X ´Y, причем элементу соответствует элемент (обозначение: xGy), если и только если (x, y)ÎG. Таким образом, соответствие f есть триада

f = [XÅ Y Å G],

в которой X — множество отправления (область определения), Y — множество прибытия, G — график соответствия f. Образом элемента x Î X в соответствии f : X ¾® Y называется множество . Полным прообразом элемента yÎY в соответствии f : X ¾® Y называется множество .

Пример. Соответствие f удобно понимать с помощью графа, который представляет собой триаду

Граф = [начала Å концы Å ребра],

при этом ребра обозначаются стрелками, начала — элементы множества Х, концы — элементы множества Y. Вершина и ребро называются инцидентными, если вершина является началом или концом стрелки. Каждое ребро инцидентно ровно двум (возможно, совпадающим) вершинам, одна из которых — начало стрелки, другая — конец.

Пусть Х ={a, b, g}, Y ={1, 2, 3, 4} — множества, и пусть G = {(a, 1), (a, 2), (b, 2), (b, 4), (g, 3)} Ì X ´Y — подмножество. Тогда определено соответствие f : X ¾® Y, которое в виде графа изображено на рис. 5.■

3.2. Отображением множества X на множество Y называется соответствие  f : X ¾® Y, такое, что образ любого  состоит ровно из одного элемента.

Упражнение. Какие из указанных на рис. 6 соответствий являются отображениями?

Два отображения f : X ¾® Y, g : X ¾® Y считаются равносильными, если  для всех х Î Х. Для равносильных отображений f, g используется запись: f = g.

3.3. Отображение f : X ¾® R называется функцией на множестве X.

3.4. Если X Ì R  — числовое множество, то функция f : X ¾® R называется числовой функцией.

3.5. Отображение f : X ¾® Y называется сюръекцией (отображением на), если для любого элемента у Î Y справедливо неравенство ||1.

Упражнение. Какие из указанных на рис. 6 соответствий являются сюръективными отображениями?

3.6. Отображение f : X ¾® Y называется инъекцией (отображением в), если для любого элемента уÎY справедливо неравенство ||1. Инъективное отображение два различных элемента отображает на два различных элемента.

Упражнение. Какие из указанных на рис. 6 соответствий являются инъективными отображениями?

3.7. Отображение называется биекцией (взаимно однозначным соответствием), если оно одновременно является инъекцией и сюръекцией.

Упражнение. Какие из указанных на рис. 6 соответствий являются биективными отображениями?

Два множества называются равносильными, если между этими множествами существует биекция.

3.8. Биекция множества на себя называется преобразованием (автоморфизмом) данного множества.

3.9. Пример. Тождественным преобразованием множества называется преобразование f : X ¾® Х, такое, что  для всех х Î Х. Тождественное преобразование обозначается idX; оно является биекцией.■

3.10. Соответствие D: X ¾® X называется отношением на множестве X.

3.11. Отношение D на множестве Х называется

рефлексивным, если хDх,

симметричным, если из хDу следует уDх,

транзитивным, если из хDу и уDz следует хDz для любых х, у, z Î X.

Упражнение 1. Докажите, что отношение параллельности || на множестве всех прямых евклидовой плоскости является рефлексивным, симметричным и транзитивным.

Упражнение 2. Докажите, что отношение включения Ì на множестве P (Х) рефлексивное, не симметричное, транзитивное.

Упражнение 3. Докажите, что отношение / на множестве R действительных чисел рефлексивное, не симметричное, транзитивное.

Упражнение 4. Докажите, что отношение > на множестве R действительных чисел не рефлексивное, не симметричное, транзитивное.

3.12. Отношение ~ на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно. Если два элемента х, у Î Х находятся в отношении эквивалентности, то говорят, что они эквивалентны между собой: х ~ у. Все элементы, эквивалентные данному элементу х Î P (Х), образуют подмножество  Î P (Х) — класс элемента х. Легко доказать, что классы двух элементов либо совпадают, либо не пересекаются. Это позволяет рассматривать классы эквивалентности как элементы множества, которое называется фактор-множеством[5] и обозначается .

3.13. Пример. Отношение равносильности в классе K всех множеств является отношением эквивалентности. Любому классу эквивалентности приписывается так называемое кардинальное число, называемое мощностью любого из множеств этого класса. Например, мощность пустого множества равна 0, мощность непустого конечного множества равна числу n его элементов, мощность множества N равна а, мощность множества R равна с. При этом выполняются неравенства 0 < n < a < c. Множество мощности а называется счетным, а мощности с — континуумом. Более ста лет не решена континуум-проблема: существует ли множество мощности b, такой, что a < b < c?■

3.14. Пример. Будем говорить, что два числа  сравнимы по модулю , если их разность m – n делится на  без остатка (обозначение , читается «m сравнимо с n по модулю p»). Например, 2005 º 1 mod 12, 3 º 1 mod 2, 2 º 0 mod 2. Для любого k Î Z справедливы сравнения: 2k º 0 mod 2, 2k + 1 º 1 mod 2. Очевидно, отношение сравнения является отношением эквивалентности, поэтому по нему можно факторизовать Z. Фактор-множество

 

состоит из p классов, которые называются классами вычетов по модулю p.■

3.15. Упражнение. Докажите, что в множестве

 

можно ввести операции сложения и умножения; докажите, что .

Задание 2. Даны множества А = {n Î Z| p £ n £ q}, В = {n Î Z| r £ n £ s} (данные брать в табл. 1). Найти множество отправления и множество прибытия соответствия D: В ¾® А, график которого состоит из элементов (x, y) Î B ´ A, таких, что х < y2. Построить граф соответствия D.

§ 4. Простейшие понятия математической логики