Дискретна математика - Функции, Множества и Комбинаторика PDF

Твърдение 1 Обединение на изброима фамилия от изброими множес- тва също е изброимо. Доказателство. Нека {Ai | i ∈ N} е изброима фамилия от множества, S като за всяко i ∈ N, Ai е изброимо. Нашата цел е да покажем, че i∈N Ai също е изб...

Твърдение 1 Обединение на изброима фамилия от изброими множес- тва също е изброимо. Доказателство. Нека {Ai | i ∈ N} е изброима фамилия от множества, S като за всяко i ∈ N, Ai е изброимо. Нашата цел е да покажем, че i∈N Ai също е изброимо множество. Можем да предполагаме, че Ai ̸= ∅, тъй като празни- те множества не допринасят към обединението и можем да ги премахнем от фамилията. По-нататък, за всяко i ∈ N избираме сюрекция gi : N → Ai (такава има, защото Ai е изброимо и непразно). Получаваме следната без- крайна надясно и безкрайна надолу таблица: A0 = {g0 (0), g0 (1), g0 (2),...} A1 = {g1 (0), g1 (1), g1 (2),...} A2 = {g2 (0), g2 (1), g2 (2),...}... Нашата цел е да съберем всички описани елементи в таблицата в едно мно- жество и да покажем, че то е изброимо. По друг начин казано, трябва да предложим обхождане на таблицата, при което всяка нейна клетка се достига на някоя крайна стъпка. Ще постигнем тази цел като дефинираме биекция h : N → N × N. Идеята е, че за всяко фиксирано k ∈ N съществуват крайно много (по-точно k + 1) наредени двойки (i, j) ∈ N × N, такива че i + j = k. Затова можем да ги подредим по нарастваща стойност на k: (0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0),... | {z } | {z } | {z } | {z } | {z } | {z } | {z } h(0) h(1) h(2) h(3) h(4) h(5) h(6) (За домашно съобразете индуктивна дефиниция за h, т.е. такава която по- казва как h(n + 1) се изразява чрез h(n)). Тази дефиниция съответства на обхождане на таблицата по вторите ди- агонали, всеки от които се състои от крайно много елементи. S Да довършим доказателството: дефинираме функция f : N → i∈N Ai , f (x) = gi (j), където h(x) = (i, j). Тъй като h е сюрекция, всеки елемент gi (j) от таблицата е стойност на f в някое x ∈ N или казано иначе, f е сюрекция. С това целта е постигната. Дефиниция 2 Нека A ̸= ∅ и B ⊆ A. Характеристична функция на множеството B наричаме fB : A → {0, 1}, която е дефинирана с: fB (x) = 1, ако x ∈ B, fB (x) = 0, ако x ∈ A \ B. По този начин, от fB можем да разберем дали x ∈ B или x ∈ / B, като поглед- нем стойността fB (x) (тя е 1 в първия и 0 в другия случай). Съпоставянето 1 между подмножества на A и характеристични функции, т.е. функции от типа A → {0, 1} е биективно. По-точно, изображението F : P (A) → {f | f : A → {0, 1}}, F(B) = fB е биекция. Причината е, че всяка функция f : A → {0, 1} е характеристична функция на единствено множество B = {x ∈ A | f (x) = 1}. Пример 1. Нека A = {0, 1, 2, 3}. Можем да си мислим за характерис- тичните функции f : A → {0, 1} като за наредени четворки от битове f (0)f (1)f (2)f (3). Например, на подмножеството {1, 3} съответства четвор- ката 0101, докато на 1110 съответства подмножеството {0, 1, 2}. Пример 2. Нека A = N. Отново можем да си мислим, че характерис- тичните функции f : N → {0, 1} са последователности от битове, но този път са безкрайни: f (0)f (1)f (2)... f (n).... Например, на подмножеството E на четните числа съответства 1010101010.... На крайно подмножество на N съответства битова последователност, която от едно място нататък се състои само от 0. Теорема 3 Множеството P (N) е неизброимо. Доказателство. Тъй като от по-горе, съществува биекция между P (N) и множеството {f | f : N → {0, 1}}, достатъчно е да докажем, че последното не е изброимо. Да допуснем, че съществува сюрекция h : N → {f | f : N → {0, 1}}. С други думи, редицата h(0), h(1),... , h(i),... съдържа всички функции от типа N → {0, 1}, т.е. всички безкрайни последователности от битове. Да си ги представим по-нагледно: h(0) = b00 b01 b02... b0i... h(1) = b10 b11 b12... b1i... h(2) = b20 b21 b22... b2i...... h(i) = bi0 bi1 bi2... bii...... Означили сме bij = h(i)(j) ∈ {0, 1}. Ще получим противоречие, като пост- роим нова функция fD : N → {0, 1}, която не съвпада с никоя от изброени- те h(0), h(1), h(2),... , h(i),.... Процесът на построяването на fD наричаме диагонализация. Идеята е следната: за да гарантираме, че fD ̸= h(i), доста- тъчно е да изберем поне една позиция j, такава че fD (j) ̸= h(i)(j). Разбира се, за различните i трябва да избираме различни j, иначе може да се полу- чи конфликт. Най-просто е да работим с диагоналните позиции (които са 2 подчертани в таблицата). И така дефинираме: fD (i) = 0, ако bii = 1, fD (i) = 1, ако bii = 0 за всяко i ∈ N. Разбира се, fD : N → {0, 1} и от допускането можем да изберем n ∈ N, такова че fD = h(n). Но тогава fD (n) = h(n)(n) = bnn , кое- то е невъзможно от дефиницията на fD. С това достигнахме до търсеното противоречие, т.е. подобна сюрекция h не може да съществува. Като пример как може да изглежда конкретна таблица: h(0) = 0 1 0 1... 0... h(1) = 0 1 1 0... 1... h(2) = 1 1 0 1... 0...... h(i) = 0 0 1 0... 1...... Тогава диагоналната функция fD изглежда така: 1 0 1... 0..., т.е. получа- ва се с преобръщане на подчертаните диагонални позиции. По този начин, fD ̸= h(0), тъй като се различават в позиция 0, също fD ̸= h(1), тъй като се различават в позиция 1 и така нататък. Следствие 4 Ако A е изброимо безкрайно множество, то P (A) е не- изброимо. Доказателство. Нека f : N → A е биекция. Тогава можем да построим биекция g : P (N) → P (A) по следния начин: за всяко X ⊆ N, g(X) = {f (x) | x ∈ X} (g(X) се нарича образ на множеството X при действието на f ). От теоремата P (N) е неизброимо, следователно такова е и P (A). Основни комбинаторни принципи 1. Принцип на Дирихле. Ако A и B са крайни множества, такива че |A| > |B|, то не съществува инекция f : A → B. 2. Принцип на биекцията. За крайни множества A и B: |A| = |B| тогава и само тогава, когато съществува биекция f : A → B (или f : B → A). 3  3. Принцип за събирането. Ако |A| = n, |B| = m и A ∩ B = ∅, то |A ∪ B| = m + n. Доказателство. Нека f : {1, 2,... , n} → A и g : {1, 2,... , m} → B са биекции. Можем да дефинираме h : {1, 2,... , m + n} → A ∪ B с ( f (i), ако i ≤ n, h(i) = g(i − n), ако i > n. Съобразете, че h е биекция (предположението A ∩ B = ∅ е съществено). 4. Принцип за изваждането. Нека U е крайно множество и A ⊆ U. Тогава |U \ A| = |U | − |A|. (Следва директно от принципа за събирането.) 5. Принцип за разбиването. Нека A е крайно множество и {S1 , S2 ,... , Sk } е разбиване на A. k X Тогава |A| = |Si |. i=1 (Доказва се с индукция по k и принципа за събиране.) Вярно е и без предположението Si ̸= ∅, което се изисква в дефиницията за разбиване. 6. Принцип за обединението. За крайни множества A и B: |A ∪ B| = |A| + |B| − |A ∩ B|. (Следва от A ∪ B = A ∪ [B \ (A ∩ B)] и принципите за събиране и изваж- дане.) Забележете, че се налага изваждане на |A ∩ B|, защото елементите на A ∩ B ги броим два пъти, един път като елементи на A и още един път като елементи на B. 7. Принцип за включване и изключване. Нека A1 , A2 ,... , An са крайни множества. Тогава X X |A1 ∪ A2 ∪... ∪ An | = |Ai | − |Ai1 ∩ Ai2 | 1≤i≤n 1≤i1