Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
ОТОБРАЖЕНИЯ. ОБРАТНЫЕ ОТОБРАЖЕНИЯ Эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах. Мы очень много будем говорить о множествах, а также о связях между элементами разных множеств или в рамках одного множества. Разобраться в этой теме несложно. Для начала нужно ввести те понятия, которые мы будем использовать. Отображением множества А во множество В называется всякое соотнесение, при котором каждому элементу из А ставится в соответствие ровно 1 элемент из В. Для записи применяется выражение f: A -> B. Множество A называется областью определения функции f, множество B – областью значений функции f. Наглядный способ представления отображений является представление в виде диаграмм: Здесь видно, что любому элементу из А соответствует какой-то один элемент из В. Элементы на диаграмме обозначаются точками, а отображение f, сопоставляющее элементам А элементы В – ориентированными дугами, соединяющими элементы А с соответствующими им элементами В. Если какому-то элементу a из А соответствует элемент b из В, то в этом случае применяется запись f(a) = b. Далее, отображения бывают инъективными и сюръективными. Отображение f: A-> B называется инъективным, если ∀ a, b ∈A (a ≠b→f(a)≠f(b)). Это означает, что разным элементам из А соответствуют разные элементы из В. То есть нельзя найти два таких разных элемента из А, которые бы соответствовали одному и тому же элементу из В. На диаграмме это означает, что, в любой элемент из множества В идёт не больше одной стрелки из множества А. Если найдётся хотя бы один такой элемент из В, в который идут 2 стрелки, то тогда отображение будет неинъективным. Пример инъективного отображения: Отображение f: A-> B называется сюръективным, если ∀ b ∈B ∃ a ∈A (f(a)=b). Это означает, что для любого элемента из множества В всегда найдётся элемент из А, который будет ему соответствовать. На диаграмме это означает, что в любой элемент из В идёт хотя бы одна стрелка. Если есть хотя бы один такой элемент из В, в который не идёт стрелка из А, то такое отображение является несюръективным. Пример сюръективного отображения: Это отображение, к слову, неинъективно, так как в элемент С идут две стрелки. Следующее понятие будет встречаться в дальнейшем очень часто. Отображение f: A-> B называется биективным, если f – инъективно и f – сюръективно. Другими словами, так как определение инъективности говорит о том, что в любой элемент из В идут не более 1 дуги из А, а определение сюръективности – не менее 1 дуги из А, то при биективном отображении из любого элемента множества А идёт 1 дуга в соответствующий ему элемент В. По-другому это называется биекцией или взаимно однозначным соответствием. Теперь поговорим про обратные отображения. Пусть нам дано отображение f: A-> B. Для каждого элемента b из В определим для него множество Ab={a | a∈A & f(a)= b}. То есть берём любой элемент из В и определяем для него такое множество, которое содержит элементы из А и они соответствуют этому элементу b. Например, для точки 3 в этом множестве будет элемент b, для точки 1 – элементы a и d, для точки 2 - элемент с: Если вдруг так оказалось, что для любого элемента из B такое множество является одноэлементным, то существует отображение g: B -> A, которое называется обратным отображением к f. Обозначается как f-1 : B -> A. Перед тем, как обсудить первую теорему, хочется сказать, какие идеи могут помогать при доказательстве различных теорем. 1) Метод математической индукции. Этот метод основывается на аксиоме индукции: Если какое-либо предложение доказано для 0 (база индукции, но может быть и не 0, а другое начальное значение) и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа (индукционное предположение), то это предложение верно для всех натуральных чисел. 2) Доказательство методом от противного. Предполагается, что теорема неверна, и путём некоторых рассуждений следует прийти к противоречию. Если ни то, ни другое не помогает в доказательстве теорем, то можно рассуждать так. 1) Часто теоремы состоят из двух частей: то, что нам в ней дано (то, чем мы можем пользоваться), и то, что нам нужно доказать, опираясь на то, что нам дано. Это нам поможет, например, при доказательстве критерия существования обратных отображений, который будет немного позже. 2) Также при доказательстве теорем используются теоремы, доказанные ранее. Нужно по максимуму пытаться как-то использовать эти два пункта, они очень помогают. Именно на них и держатся все доказательства. Теперь перейдём к критерию существования обратных отображений. КРИТЕРИЙ. Для отображения f: A -> B существует обратное отображение f-1 : B -> A тогда и только тогда, когда f является биективным отображением. Если в утверждении какой-то теоремы есть фраза «тогда и только тогда», то очень часто приходится доказывать теорему в одну и в другую сторону. В одну сторону утверждение представлено выше, а в другую сторону утверждение будет звучать так: Отображение f является биективным тогда и только тогда, когда для отображения f: A -> B существует обратное отображение f-1 : B -> A. ДОКАЗАТЕЛЬСТВО. Сначала докажем в одну сторону. Пусть для отображения f: A -> B существует обратное отображение f-1 : B -> A. Тогда для любого элемента b из В можно определить множество Ab={a | a∈A & f(a)= b}. Мы должны доказать, что f инъективно и сюръективно. 1) Если f не является инъективным отображением, то множество Ab не будет одноэлементным, так как найдутся хотя бы 2 элемента, которым соответствует элемент b, а это противоречит допущению существования обратного отображения. Значит, f – инъективно. 2) Если f не является сюръективным, то найдётся такой элемент b из В, для которого множество Ab не будет содержать никаких элементов, что опять же противоречит допущению существования обратного отображения. Значит, f – сюръективно. Таким образом, f является биективным отображением по определению, что и требовалось доказать. Теперь докажем утверждение в другую сторону. Пусть f – биективное отображение. Покажем, что для f существует обратное отображение. Так как f – биективно, то f и инъективно, и сюръективно. Используем это здесь: 1) f – инъективно, значит, ∀ a, b ∈A (a ≠b→f(a)≠f(b)) (здесь в определении инъективного отображения элемент b тоже из множества А). А значит, в каждый элемент множества В отображается не более одного элемента из А. 2) f – сюръективно, значит, ∀ b ∈B ∃ a ∈A (f(a) = b). А значит, в каждый элемент множества В отображается не менее одного элемента из А. Таким образом, в любой элемент из В отображается ровно 1 элемент из А, следовательно, множество для любого элемента b из B Ab={a | a∈A & f(a)= b} одноэлементно. Таким образом, существует обратное отображение f-1 : B -> A, что и требовалось доказать. МОЩНОСТЬ МНОЖЕСТВ Сначала нужно ввести понятия, которыми мы будем пользоваться. Множества А и В называются равномощными, если существует биективное отображение f: A -> B Мощностью множества А (обозначается |A|) называется семейство всех множеств, равномощных А. Определение мощности множества звучит немного странно, но всё же здесь просто нужно понять, что мощность - это семейство множеств, равномощных исходному, но мощность не равна количеству этих множеств. Например, если дано множество А = {1, 2, 3, 4}, то существует бесконечно много множеств с четырьмя элементами, и поэтому возникает неразбериха. Нужно просто запомнить, что численно выразить мощность мы можем только для конечных множеств, для бесконечных же не можем. Множества, равномощные множеству N натуральных чисел, называются счётнобесконечными. Множества, равномощные некоторому началу множества N, называются конечными. Множество называется счётным, если оно конечное или счётно-бесконечное. Надеюсь, определения, которые выше, более менее понятны. Теперь введём понятие множества всех подмножеств определённого множества. Да, я довольно много раз сказал слово «множество», но сократить это никак нельзя. На самом деле, это вещь довольно-таки простая. Для начала поймём, что такое подмножество. Подмножество В множества А – это такое множество, каждый элемент которого является элементом множества А. Думаю, это более менее ясно. Нам понадобится ещё понятие пустого множества (это множество, которое не содержит никаких элементов). Всякое пустое множество является подмножеством любого множества. Множество всех подмножеств множества А обозначается как 2^A (почему именно так – будет написано ниже). Далее, разберём понятие подмножества на примере. Например, если есть множество А то множество всех подмножеств множества А будет состоять из всевозможных комбинаций элементов множества А, например: А = {1, 2, 3}. Множество 2^A будет включать в себя следующие элементы: прежде всего, это элементы самого множества А (то есть 1, 2, 3). Далее, мы можем составить различные попарные комбинации между этими числами, то есть в 2^A будут входить подмножества {1, 2}, {2, 3}, {1, 3}. И наконец, мы можем составить тройку этих чисел, и тогда появляется ещё один элемент множества 2^A: {1, 2, 3}. И также, элементом 2^A, как и любого другого множества, будет являться пустое множество. Всего у нас насчиталось элементов 3 + 3 + 1 + 1 = 8 (3 одноэлементных подмножества, 3 двухэлементных, 1 трёхэлементное и 1 пустое). С этим понятием, думаю, разобрались. Теперь о том, почему обозначается именно как 2^A. Допустим есть множество А, которое имеет n элементов. Тогда множество всех подмножеств будет включать в себя 2^n элементов. Можем, например, убедиться в этом с помощью прошлого примера. Там множество состояло из 3 элементов, а множество всех подмножеств включало в себя 8 = 2^3 элементов. Следующий абзац для тех, кому интересно, почему именно такая формула. Если говорить о доказательстве формулы вычисления количества элементов во множестве всех подмножеств, то здесь просто суммируется количество способов взять 1 элемент, потом 2 элемента, и так далее, потом n элементов. Если записывать математически, то это записывается как Сn 0 + Сn 1 + Cn 2 + Cn 3 + … + Cn n (Сn 0 = 1 – пустое множество). Но здесь записана формула бинома Ньютона, поэтому это можно свернуть в скобку (1 + 1)^n = 2^n. Бином Ньютона - очень важная вещь, поэтому лучше погуглить его, если не знаете. ТЕОРЕМА. Множества A и 2^A неравномощны. Кому-то может показаться, что это утверждение очевидно. Например, для множества А = {1, 2, 3, 4} множество всех подмножеств включает сами элементы из А и их комбинации, а значит, второе множество имеет большую мощность. Но это очевидно только для конечных множеств, с бесконечными множествами всё сложнее и непонятнее, поэтому теорему доказывать надо ДОКАЗАТЕЛЬСТВО. Эта теорема доказывается от противного. Допустим, что теорема не выполняется. Тогда существует взаимно однозначное соответствие между этими множествами. То есть существует биекция h: A -> 2^A. Рассмотрим два наших множества. Одно из них будет А (там будут элементы наши искомые), другое - 2^А (это подмножества множества А). Очевидно, если мы предположили, что будет взаимно однозначное соответствие, то мы можем любому элементу x поставить в соответствие ему определенное подмножество BX. Далее, предлагается рассмотреть одно экзотическое множество, которое нам поможет прийти к противоречию. Множество D = {x | x не принадлежит BX}. Как до него додуматься? До него не нужно додумываться, нужно просто запомнить, что при доказательстве этой теоремы используется именно это множество. Что это множество значит? Возьмём, например, из множества 2^А его элемент BZ. Утверждение такое: у множества А найдётся элемент z, который соответствует BZ, но не принадлежит ему. И так для всех остальных элементов А. Например, есть множество А = {1, 2, 3, 4} и есть во множестве 2^А подмножество, содержащее числа 1, 2 и 3, значит мы можем поставить в соответствие элемент из множества А, равный 4. И очевидно, что он не принадлежит этому подмножеству, потому что там только 1, 2 и 3, поэтому все условия выполняются, а значит, элемент 4 входит в D. Далее, нам понадобится тот факт, что такое множество D будет существовать. Этот факт не очевиден, но нам просто необходимо существование этого множества, чтобы мы смогли прийти к противоречию. Оказывается, что множество D будет существовать всегда. Докажем это. Для этого нам понадобится тот факт, что пустое множество является подмножеством любого множества. Утверждение такое: если есть элемент y принадлежащий А, и вдруг так оказалось, что соответствующий ему элемент BУ это пустое множество (а такое будет всегда, потому что пустое множество является подмножеством любого множества), то y принадлежит D. Игрек не принадлежит BУ, потому что BУ пустое множество, и варианта принадлежности игрека всего два: либо есть в D, либо нет. Но так как его нет в BУ, то он будет в D (по нашему определению множества D). Далее, возьмём такой элемент c из А, чтобы ему соответствовало множество BС такое, что BС = D. Что это значит? Напомню: Множество D = {x | x не принадлежит BХ}. В нем содержатся все элементы, обладающие следующим свойством: в тех подмножествах, которым эти элементы соответствуют, сами элементы в них не находятся. Но так как это тоже подмножество множества А, то мы можем ему поставить по предположению (которым мы можем пользоваться) элемент из множества А. Таким образом, BС = D. Равенство BС = D обозначу как (1), нам оно сейчас понадобится. И тут возможны 2 варианта, самых очевидных. Либо c принадлежит Bc, либо не принадлежит, третьего не дано. 1) если c принадлежит BС, то он принадлежит и D тоже (из равенства (1)), но тогда c не принадлежит BС (по определению D) 2) если c не принадлежит BС, то он не принадлежит и D (по равенству (1)), но тогда, раз он не принадлежит D, то принадлежит BС (либо тому принадлежит, либо тому, из определения D это видно) В обоих случаях противоречие, поскольку мы получили, что элемент c одновременно и принадлежит подмножеству BС, и не принадлежит. Теорема доказана. Из этой теоремы следует факт, что не существует самой большой мощности. Это легко понять. Допустим, есть множество А, тогда для него есть множество подмножеств 2^A. Теперь обозначим 2^A за множество B, и для него будет своё множество подмножеств 2^B, и так далее. Очевидно, что процесс этот бесконечен. ОТНОШЕНИЯ. ПРЕДСТАВЛЕНИЕ И ОПЕРАЦИИ НАД ОТНОШЕНИЯМИ. Теперь рассмотрим то понятие, которое поможет нам связывать тем или иным образом элементы между двумя (или более) множествами или в рамках одного множества. Оно нам поможет при рассмотрении свойств различных объектов и их взаимосвязи. Это понятие отношения. Пусть нам даны два множества А и В. Для двух множеств мы можем определить так называемое декартово произведение. Это просто множество всевозможных пар элементов, первый элемент которых – элемент из А, второй – из В. Множество декартового произведения обозначим как A × 𝐵. Пусть например А = {Петя, Коля}, B = {3, 4, 5}. Тогда множество декартового произведения состоит из элементов {Петя, 3}, {Петя, 4}, {Петя, 5}, {Коля, 3}, {Коля, 4}, {Коля, 5}. Запись 𝜌 ⊆ A × 𝐵 будет означать, что множество 𝜌 является подмножеством множества A × 𝐵. Теперь само определение. Отношением на множествах А и В называется всякое подмножество 𝜌 ⊆ A × 𝐵. Множество 𝜌 может включать в себя самые разные множества пар элементов из множеств А и В в зависимости от ситуации (а может вообще совпадать с декартовым произведением). На примере выше можно определить, например, отношение Получил оценку. После этого высказывания передаются «параметры» (в данном случае тот, кто получал оценку, и какую оценку он получил): Получил оценку (Петя, 5). И если Петя и 5 лежат в отношении Получил оценку, то утверждение «Петя получил оценку 5» будет истинным, иначе – ложным. Если пара (a, b) находятся в отношении 𝜌 ((a, b) ∈ 𝜌), то это можно записать как a𝜌b. Теперь поговорим про представления отношений. Отношения можно представлять в виде диаграммы и табличного задания. 1) Диаграммы Здесь всё просто. Если элементы множеств А и В находятся в отношении 𝜌, то эти множества можно представить в виде множеств точек из двух непересекающихся областей, обозначаемых как А и В. Если пара (a, b) ∈ 𝜌 (а из А и b из В), то эти два элемента соединяются ориентированной дугой. 2) Табличное задание Отношения между элементами двух множеств можно представлять в виде таблицы. Пусть А = {a1, a2, a3, a4}, B = {b1, b2, b3}. a1 a2 a3 a4 b1 𝛿 11 𝛿 21 𝛿 31 𝛿 41 b2 𝛿 12 𝛿 22 𝛿 32 𝛿 42 b3 𝛿 13 𝛿 23 𝛿 33 𝛿 43 Причём вместо 𝛿 𝑖𝑗 (i = {1, 2, 3, 4}, j = {1, 2, 3}) подставляются значения 0 (если элементы ai и bj не находятся в отношении 𝜌) и 1 (если элементы ai и bj находятся в отношении 𝜌). В общем случае это выглядит так (множество А состоит из n элементов, а множество В – из m элементов): a1 a2 … an b1 b2 … 𝛿 𝑖𝑗 bm 𝛿 𝑖𝑗 = { 1, если (ai, bj) ∈ 𝜌 0, если (ai, bj) не ∈ 𝜌 (Тут везде должен быть символ 𝜎 вместо 𝛿, просто я это понял уже потом и переделывать уже лень). Теперь рассмотрим операции над отношениями. 1) Обращение отношений Пусть даны множества А и В, а также отношение 𝜌 ⊆ A × 𝐵. Тогда множество {(y, x)(x, y)} называется отношением, обратным к отношению . То есть здесь элементы в своих парах просто меняются местами. Обозначается как -1⊆ B × 𝐴. 2) Композиция (произведение) отношений Пусть теперь даны множества А, В и С. Если 𝜌 ⊆ A × 𝐵 и 𝛾 ⊆ B × 𝐶, то отношение 𝜇 ⊆ A × 𝐶 называется произведением отношений 𝜌 и 𝛾. Обозначается как 𝜇 = 𝜌 ° 𝛾. Например, если отношение 𝜌 Работает(a, b), а отношение 𝛾 Учится(b, c), то отношение 𝜇 – Работает и учится(a, c). Математически определение отношения 𝜇 записывается так: 𝜇 = {(x, z) | ∃ 𝑦 (𝑥𝜌y & y𝛾𝑧)}. Отображения являются частным случае отношений: 𝜌 = {x, f(x) | x ∈ A} БИНАРНЫЕ ОТНОШЕНИЯ НА МНОЖЕСТВЕ. Рассмотрим отношение 𝜌 ⊆ A × 𝐵. Если A = B, то 𝜌 ⊆ A × А называется бинарным отношением на множестве А. Рассмотрим свойства бинарных отношений. 1) Рефлексивность: 𝜌 ⊆ A × А – рефлексивно, если ∀ 𝑥 ∈ 𝐴 𝑥𝜌𝑥 На диаграмме отношений рефлексивность обозначается петлёй, чтобы показать, что элемент, находится в отношении с самим собой. 2) Симметричность: 𝜌 ⊆ A × А – симметрично, если ∀ 𝑥, 𝑦 ∈ 𝐴 𝑥𝜌𝑦 → 𝑦𝜌𝑥 На диаграмме отношений симметричность выглядит как пара противоположно направленных ориентированных дуг: первая идёт из x в y, вторая – из y в x. 3) Транзитивность: 𝜌 ⊆ A × А – транзитивно, если ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐴 𝑥𝜌𝑦 & 𝑦𝜌𝑧 → 𝑥𝜌𝑧 4) Антисимметричность: 𝜌 ⊆ A × А – антисимметрично, если ∀ 𝑥, 𝑦 ∈ 𝐴 𝑥𝜌𝑦 & 𝑦𝜌𝑥 → 𝑥 = 𝑦 То есть антисимметричность отношения означает, что в отношении допускается вхождение одинаковых противоположно направленных дуг только в случае, если эти дуги совпадают. |