Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
• O x y Рис. 1.3 x ∈ A и y ∈ B, связанные отношением P , соеди- няются стрелками. Пример 1.2.4. На рис. 1.4 графически пока- зано отношение P 1 = {(a, 2), (b, 1), (c, 2)} между множествами A = {a, b, c} и B = {1, 2, 3}, а так- же отношение P 2 = {(a, b), (b, b), (c, a)} на множе- стве A. ¤ Для любого множества A определим тожде- ственное отношение id A {(x, x) | x ∈ A} и универсальное отношение U A A 2 . Отношение id A называется также диагональю, а U A — полным отношением. Пусть P — некоторое бинарное отношение. Областью определения отно- шения P называется множество δ P dom P {x | (x, y) ∈ P для некоторого y}, а областью значений отношения P — множество ρ P rang P {y | (x, y) ∈ P для некоторого x}. ' & $ % ' & $ % P 1 @ @ @ @ @ @ R -•2 • a • c ¡ ¡ ¡ ¡ ¡ µ • b •1 •3 A B ¢ ¢ ¢ ¢ ¢ ¢¸ • a ¾ •c • b n ¾ P 2 Рис. 1.4 22 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Обратным к P отношением называется множество P −1 {(y, x) | (x, y) ∈ P }. Образом множества X относительно предиката P называется множество P (X) {y | (x, y) ∈ P для некоторого x ∈ X}, прообразом множества X относительно P — множество P −1 (X) или, другими словами, образ множества X относительно предиката P −1 Пример 1.2.5. Для отношения P из примера 1.2.1 и множества X = {3} имеем δ P = {2, 3}, ρ P = {2, 3, 4, 6, 8}, P −1 = {(2, 2), (4, 2), (6, 2), (8, 2), (3, 3), (6, 3)}, P (X) = {3, 6}, P −1 (X) = {3}. ¤ Произведением бинарных отношений P 1 ⊆ A × B и P 2 ⊆ B × C, или композицией P 1 и P 2 называется множество P 1 ◦ P 2 {(x, y) | x ∈ A, y ∈ C, и найдется элемент z ∈ B, для которого (x, z) ∈ P 1 и (z, y) ∈ P 2 } (рис. 1.5). В дальнейшем произведение P 1 ◦ P 2 будем также обозначать через P 1 P 2 Предложение 1.2.1. Для любых бинарных отношений P , Q и R выполняются следующие свойства: 1) (P −1 ) −1 = P ; 2) (P ◦ Q) −1 = Q −1 ◦ P −1 ; 3) (P ◦ Q) ◦ R = P ◦ (Q ◦ R) (ассоциативность композиции). ' & $ % ' & $ % ' & $ % • • • A B C x z y P 1 P 2 - - P 1 ◦ P 2 µ Рис. 1.5 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 23 Доказательство. 1. По определению обратного отношения условие (x, y) ∈ P равносильно условию (y, x) ∈ P −1 , что в свою очередь выполняет- ся тогда и только тогда, когда (x, y) ∈ (P −1 ) −1 . Следовательно, P = (P −1 ) −1 2. Предположим, что (x, y) ∈ (P ◦Q) −1 . Тогда (y, x) ∈ P ◦Q и, следователь- но, (y, z) ∈ P и (z, x) ∈ Q для некоторого элемента z. Значит, (x, z) ∈ Q −1 , (z, y) ∈ P −1 и (x, y) ∈ Q −1 ◦ P −1 . Включение Q −1 ◦ P −1 ⊆ (P ◦ Q) −1 доказы- вается аналогично. 3. Пусть (x, y) ∈ (P ◦ Q) ◦ R. Тогда для некоторых u и v имеем (x, u) ∈ P , (u, v) ∈ Q, (v, y) ∈ R. Таким образом, (u, y) ∈ Q ◦ R и (x, y) ∈ P ◦ (Q ◦ R). Включение P ◦ (Q ◦ R) ⊆ (P ◦ Q) ◦ R доказывается аналогично. ¤ Ассоциативность композиции позволяет обозначать композицию (P ◦ Q)◦ R = P ◦ (Q ◦ R) через P QR. По этой же причине однозначно опре- делена композиция P 1 P 2 . . . P n двухместных предикатов P 1 , P 2 , . . . , P n . Отме- тим, что существуют предикаты P и Q, для которых не выполняется закон коммутативности P ◦ Q = Q ◦ P (приведите примеры таких предикатов). Отношение f ⊆ A × B называется функцией или отображением из мно- жества A в множество B, если δ f = A, ρ f ⊆ B и из (x, y 1 ) ∈ f , (x, y 2 ) ∈ f следует y 1 = y 2 . Если вместо δ f = A выполняется δ f ⊆ A, то f называется частичной функцией. Функция f из A в B обозначается через f : A → B или A f → B. Если (x, y) ∈ f , то пишем y = f (x) (y — значение функции f при значении аргумента x) или f : x 7→ y (функция f ставит в соответствие элементу x элемент y). Пример 1.2.6. Отношение {(1, 2), (2, 3), (3, 2)} ⊆ {1, 2, 3} 2 — функция, отношение {(1, 2), (1, 3), (2, 3)} не является функцией, а отношение {(x, x 2 − 2x + 3) | x ∈ R} — функция, которая обычно обозначается через y = x 2 − 2x + 3. ¤ Пример 1.2.7. Тождественное отношение id A = {(x, x) | x ∈ A} является функцией id A : A → A, для которой id A (x) = x при всех x ∈ A. Другими при- мерами функций являются проекции π A,B 1 : A × B → A и π A,B 2 : A × B → B, которые задаются по следующим правилам: π A,B 1 ((a, b)) a, π A,B 2 ((a, b)) b. ¤ Функция f называется разнозначной, инъективной (инъекцией) или 1-1-функцией, если отношение f −1 является частичной функцией, т. е. для любых элементов x 1 , x 2 ∈ δ f из x 1 6= x 2 следует f (x 1 ) 6= f (x 2 ). Если f — инъекция, то будем писать f : A 1−1 −−→ B. 24 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ - x 6 y O 1 1 f 1 f 3 f 4 f 2 Рис. 1.6 Функция f : A → B называется функцией A на B или сюръективной функцией (сюръекцией), если ρ f = B. Если f — сюръекция, то будем писать f : A на −→ B. Функция f называется взаимно однозначным соответствием между множествами A и B или биективной функцией (биекцией), если f — раз- нозначное отображение A на B. Таким образом, функция является биекци- ей, если она инъективна и сюръективна. Если f — биекция между A и B, то будем писать f : A ↔ B. Биекция f : A ↔ A называется подстановкой множества A. Простейшим примером подстановки является функция id A Пример 1.2.8. На рис. 1.6 графически показаны функции f i : [0, 1] → [0, 1], i ∈ {1, 2, 3, 4}. Функция f 1 сюръективна, но не инъективна, функция f 2 инъективна, но не сюръективна, функция f 3 биективна и явля- ется подстановкой, а функция f 4 не инъективна и не сюръективна. ¤ Пример 1.2.9. Рассмотрим три функции f i : R → R, i = 1, 2, 3: 1) функция f 1 (x) = e x инъективна, но не сюръективна; 2) функция f 2 (x) = x · sin x сюръективна, но не инъективна; 3) функция f 3 (x) = 2x − 1 биективна. ¤ Пример 1.2.10. Биекцией между множеством натуральных чисел N = {0, 1, 2, . . .} и множеством целых чисел Z = {0, ±1, ±2, . . .} является функция f : N → Z, для которой f (n) = ( m, если n = 2m − 1, −m, если n = 2m. ¤ 1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ 25 Предложение 1.2.2. 1. Если f : A → B и g: B → C, то f ◦ g: A → C. 2. Если f : A → B, то id A ◦ f = f , f ◦ id B = f . 3. Если f : A на −→ B, g: B на −→ C, то f ◦ g: A на −→ C. 4. Если f и g — разнозначные отображения, то f ◦ g — разнозначное отображение. 5. Если f : A ↔ B, g: B ↔ C, то f ◦ g: A ↔ C. 6. Если f : A ↔ B, то f −1 : B ↔ A, f ◦ f −1 = id A , f −1 ◦ f = id B . Доказательство. Утверждения 1 и 2 очевидны. 3. Достаточно доказать, что для любого c ∈ C найдется элемент a ∈ A такой, что (f ◦ g)(a) = c. Поскольку g — сюръекция, найдется элемент b ∈ B, для которого g(b) = c, а так как f — сюръекция, существует искомый эле- мент a ∈ A такой, что f (a) = b. Следовательно, f ◦ g: A на −→ C. 4. Предположим противное, т. е. найдутся элементы x 1 , x 2 , y такие, что x 1 6= x 2 , (x 1 , y) ∈ f ◦ g и (x 2 , y) ∈ f ◦ g. В силу разнозначности f имеем f (x 1 ) 6= f (x 2 ). Отсюда в силу разнозначности g получаем g(f (x 1 )) 6= g(f (x 2 )), а это противоречит предположению g(f (x 1 )) = y = g(f (x 2 )). Доказательство пп. 5 и 6 оставляется читателю в качестве упраж- нения. ¤ Если f — отображение и X ⊆ δ f , то множество {f (x) | x ∈ X} называет- ся образом множества X при отображении f и обозначается через f (X), а отображение f ∩ (X × ρ f ) называется ограничением f на X и обозначается через f | X или f ¹ X. Функция f : N → B называется последовательностью. Ее можно пред- ставить в виде f (0), f (1), f (2), . . . , f (n), . . . или b 0 , b 1 , . . . , b n , . . ., где b n = f (n), n ∈ N. Множество всех функций из A в B обозначается через B A : B A {f | f : A → B}. Функция f : A n → B называется n-местной функцией из A в B. Если y — значение n-местной функции f при значении аргумента (x 1 , x 2 , . . . , x n ), то пишем y = f (x 1 , x 2 , . . . , x n ). Функция f : A n → A назы- вается n-местной алгебраической операцией на множестве A. При n = 1 операция f называется унарной, при n = 2 — бинарной, а в общем слу- чае — n-арной. При n = 0 операция f : A 0 → A есть множество {(∅, a)} для некоторого a ∈ A. Часто 0-местную операцию {(∅, a)} на A будем называть константой на A и отождествлять с элементом a. 26 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пример 1.2.11. Операция сложения вещественных чисел является двух- местной, т. е. бинарной операцией +: R 2 → R, которая паре чисел (a, b) ста- вит в соответствие число a + b по обычному правилу: +(a, b) = a + b. Любой выделенный элемент множества R, например √ 2, является 0-местной опера- цией, т. е. константой на R. ¤ Очевидно, что n-местная операция на множестве A является (n + 1)- местным отношением на том же множестве A. § 1.3. Натуральные числа. Принцип математической индукции Рассмотрим два подхода к заданию множества натуральных чисел. Пер- вый подход — конструктивный — позволяет представлять натуральные чис- ла в виде объектов, построенных из пустого множества. Второй подход — ак- сиоматический. Согласно этому подходу натуральные числа образуют мно- жество, удовлетворяющее некоторому набору свойств (аксиом), и при этом природа элементов множества не важна. Таким образом, с одной стороны, указывается множество натуральных чисел, а с другой стороны — все суще- ственные (определяющие) свойства этого множества. Положим по определению 0 ∅, 1 {0} (т. е. 1 = {∅}), 2 {0, 1} (т. е. 2 = {∅, {∅}}), . . ., n {0, 1, . . . , n − 1}, . . . Множества, обозначаемые 0, 1, 2, . . . , n, . . ., называются натуральными числами. Объединив эти мно- жества, получаем множество всех натуральных чисел {0, 1, 2, . . . , n, . . .}, обозначаемое через ω. В силу обозначений предыдущего параграфа, если A = n = {0, 1, . . . , n − 1}, B = 2 = {0, 1}, то 2 n = B A = {f | f : n → {0, 1}}. Обозначение B A согласуется с тем, что в множестве B A имеется ровно 2 n функций. Действительно, поскольку функция f на каждом аргументе i ∈ n может принимать одно из двух значений 0 или 1 и таких элементов i ровно n, то всего имеется 2 · 2 · . . . · 2 = 2 n различных функций. Аналогично имеем 2 ω = {f | f : ω → {0, 1}} — множество, состоящее из всех последовательностей нулей и единиц. 1.3. НАТУРАЛЬНЫЕ ЧИСЛА. ПРИНЦИП МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ 27 Как уже отмечалось, второй подход к определению множества нату- ральных чисел является аксиоматическим. Мы рассмотрим аксиоматику Дедекинда—Пеано. Пусть имеется некоторое множество N, в котором выбран элемент, обо- значаемый через 0, и функция, которая произвольному элементу n ∈ N ставит в соответствие элемент n 0 ∈ N, называемый непосредственно сле- дующим (элемент n 0 играет роль числа n + 1). Таким образом, с помощью функции n 7→ n 0 можно однозначно найти элементы 0 0 , 0 00 , 0 000 и т. д. (элемент 0 (n) играет роль числа n). Множество N называется множеством натураль- ных чисел, если система N hN; 0, 0 i удовлетворяет следующим аксиомам: 1) для любого m 6= 0 найдется n ∈ N такой, что n 0 = m; 2) для любых m, n ∈ N, если m 0 = n 0 , то m = n; 3) n 0 6= 0 для любого n ∈ N; 4) (аксиома математической индукции) для любого свойства P (унар- ного отношения на множестве N), если P выполняется на элементе 0 (т. е. 0 обладает свойством P ), и для любого n ∈ N из выполнимости P на элементе n следует выполнимость P на элементе n 0 , то свойство P вы- полняется на любом элементе n ∈ N. Последняя аксиома является наиболее содержательной, она символиче- ски записывается следующим образом: |