В.А. Носов - Комбинаторика и теория графов, страница 2

Отображение F: А → B называется инъективным, если разным элементам из А ставятся в соответствие разные элементы из B, т.е.F - инъективно ⇔ (x1 ≠ x2 ⇒ F(x1) ≠ F(x2), ∀ x1, x2 ∈ A)Отображение F: А → B называется сюръективным, если каждый элемент из B являетсяобразом некоторого элемента из А, т.е.F - сюръективно ⇔ (∀ y ∈ B, ∃ x ∈ A F(x) = y)Отображение F: А → B называется биективным, если оно одновременно инъективно исюръективно. Пусть N = {1, 2, … } - множество натуральных чисел и Nn = {1, 2, … , n} его начальный отрезок из n элементов. Пусть дано множество А и пусть существует биективное отображение множества А в множество Nn.

В этом случае говорим, что мощность множества А равна n или А является n-множеством (обозначение: A = n).Два отображения F1 : А1 → B1 и F2: А2 → B2 считаются равными, если A1 = A2,B1 = B2 и F1(x) = F2(x), ∀ x ∈ A. Если А = B, то отображение F: А → B называется преобразованием множества А, биективное преобразование F множества А называется егоподстановкой. Если A = n, то говорят, что подстановка множества А имеет степень n.Если А является n-множеством, причем А = {x1, … , xn }, то любое отображениеF: А → B может быть задано в виде двустрочной таблицыx2xn ... xF=  1 F(x1 ) F(x 2 ) ...

F(x n )Пусть А - конечное множество из n элементов и F - произвольное отображение множества А в себя.СправедливаТеорема 1. Следующие утверждения равносильны:1) Отображение F - инъективно2) Отображение F - биективно3) Отображение F - сюръективно.3♦ Пусть F задано в виде двустрочной таблицы:x2xn ... xF:  1 , причем А = {x1, … , xn} F(x1 ) F(x 2 ) ... F(x n )Пусть l0 - число элементов множества А, которые отсутствуют в нижней строке табличного задания F, l1 - число элементов множества А, которые в ней представлены точно 1раз, l2 - число элементов, представленных точно 2 раза и т.д.Имеем следующие отношения:l0 + l1 + … + ln = na)l1 + 2l2 + … + nln = nб)В а) просуммированы все элементы, в б) просуммировано число мест в нижней строкетабличного задания F.Пусть теперь F инъективно, тогда l2 = … = ln = 0 и поэтому из а) и б) имеем l0 + l1 = n,l1 = n.

Значит l0 = 0 и F - сюръективно. Отсюда получаем справедливость 1) ⇒ 2) ⇒ 3).Пусть F - сюръективно. Тогда l0 = 0. Вычтем из б) соотношение а). Имеемl2 + 2l3 + … + (n-1)ln = 0Поскольку все li ≥ 0, то отсюда имеем l2 = l3 = … = ln = 0 и, следовательно, l1 = n, чтоозначает, что F инъективно, т.е. справедливо 3) ⇒ 1). ♦Иногда приходится рассматривать частичные отображения F: А → B, для которых F определено только на элементах подмножества А1 ⊆ A (и не определено на элементахА\A1). Приведем утверждение, известное как диагональный принцип Кантора, часто используемый для доказательства глубоких утверждений теории множеств.Теорема 2.

Пусть А - некоторое множество, F - отображение (вообще говоря,частичное) из А в его булеан B(А). Пусть AF - область определения F и пустьK = {x x ∈ AF и x ∈ F(x)}(т.е. K - множество всех элементов А, для которых F определено и которые не принадлежат своему образу при F). Тогда K не есть значение отображения F, т.е. F(x) ≠ K,∀x ∈ AF.♦ Предположим, что существует b ∈ AF, такое, что F(b) = K. Тогда либо b ∈ K,либо b ∈ K. Если, b ∈ K, K = F(b) то b принадлежит своему образу, и по условию на K,элемент b не может принадлежать K - получили противоречие. Пусть b ∈ K, K = F(b).Тогда b не принадлежит своему образу и, следовательно, по условию на K, он принадлежит множеству K - снова получили противоречие.

Таким образом, K не является значением отображения F. ♦43. Алгебра множеств.Зафиксируем непустое множество E и рассмотрим его булеан B(E). МножествоB(E) замкнуто относительно операций объединения, пересечения и дополнения множеств - элементов B(E). Множество B(E) вместе с введенными операциями ∪, ∩, - называется булевой алгеброй подмножеств множества E. Перечислим основные законы, которым подчиняются эти операции:1. A = A2 .

AI B = BI A3 . AU B = BU A законы коммутативности4 . (AI B)I C = AI ( BI C) 5 .(AU B)U C = AU ( BU C) законы ассоциативности6 . AI ( BU C) = (AI B)U (AI C) 7 . AU ( BI C) = (AU B)I (AU C) 8 . AI B = AU B9 . AU B = AI B10 . AI A = A11. AU A = A законы дистрибутивностизаконы дополнениязаконы идемпотентности12. AI E = A13. AU ∅ = A14. AU A = E15. AI A = ∅Все данные равенства могут быть доказаны по единой схеме, использующей определение равенства двух множеств А и B:A = B ⇔ A ⊆ B и B ⊆ A.В качестве примера приведем доказательство равенства 7.Пусть x ∈ А U (BI C) . Тогда либо x ∈ А, либо x ∈ B I C .

Если x ∈ А, тоx ∈ A U B и x ∈ А U C , следовательно, x ∈ (AU B)I (AU C) . Если x ∈ B I C , то5X ∈ B и x ∈ C, значит x ∈ A U B и x ∈ A U C . Отсюда, x ∈ (A U B)I (AU C) . Такимобразом, установлено включениеA U ( BI C) ⊆ (AU B)I (AU C)(а)Пусть теперь x ∈ (A U B)I (AU C) .

Тогда x ∈ A U B и x ∈ А U C . Если x ∈ A, тоx ∈ A U ( BI C) . Если x ∈ A , то тогда должно быть x ∈ B и x ∈ C. Отсюда следует, чтоx ∈ B I C и, следовательно, x ∈ A U ( BI C)Таким образом, установлено включение(A U B)I (AU C) ⊆ AU ( BI C)(в)Доказанные включения (а) и (в) равносильны равенству 7.Доказательства остальных равенств 1 - 15 предлагается проделать самостоятельно.Мы будем считать допустимыми следующие способы образования множеств:1. Из множества элементов можно выделить его часть посредством точно сформулированного признака.2. Если имеется совокупность множеств, то можно получить новое множество,являющееся объединением множеств этой совокупности.3. Для каждого конечного множества можно образовать множество всех егоподмножеств.4.

Для любой пары множеств можно образовать новое множество, являющеесяих прямым произведением.Известно, что неограниченное использование средств при построении множествприводит к логическим парадоксам (парадокс Рассела, парадокс Кантора и др.).В данном курсе будут применяться только конструкции конечного типа над конечными множествами.Упражнения1. Пусть A1, … , An , B - подмножества некоторого фиксированногомноже-ства E.Доказать равенства:6nni =1i =1nni =1i =1а) ( U A i )I B = U (A i I B)в) ( I A i )U B = I (A i U B)nc)U Ain=i =1i =1nd)I AiI Ain=i =1U Aii =12.

Для произвольных множеств А и B положимA ⊕ B = (AI B)U ( AI B)Доказать равенства:a) A ⊕ B = B ⊕ Ab) (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)c) A ⊕ ∅ = Ad) A ⊕ A = ∅e) AI ( B ⊕ C) = (AI B) ⊕ (AI C)f) A = B ⇔ A ⊕ B = ∅3. Доказать равенства:a) (AU B) × C = (A × C)U ( B × C)b) (AI B) × C = (A × C)I ( B × C)c) (AI B) × (CI D) = (A × C)I ( B × D)4. Установить биективное соответствие между множеством всех отображениймножества А в двухэлементное множество {0, 1} и булеаном множества А.5. Пусть F: X → Y, A ⊆ X, B ⊆ XДоказать:a) A ⊆ B ⇒ F(A) ⊆ F(B)b) F(AU B) = F(A)U F( B)c) F(AI B) ⊆ F(A)I F( B)причем возможно и строгое включение.d) F(AI B) = F(A)I F( B) для любых подмножеств А и B тогда и только тогда,когда F - инъективно.78§ 2.

Принципы перечисления и примеры.Элементарные тождества.При решении перечисленных задач теории множеств широко используются следующие правила для подсчета.1. Правило равенства. Если A и B - конечные множества и существует биективное отображение F: A → B, то A = B2. Правило суммы. Если A1, … , An - конечные, попарно непересекающиесямножества, тоA1 U ...U A n = A1 +...+ A n3. Правило произведения. Если A1, … , An - конечные множества, тоA1 ×...× A n = A1 ×...× A n .Применим данные принципы для решения перечисленных задач, связанных с введенными объектами.1.

Число отображения n-множества в m-множество. Пусть A = {a1, … , an } иB = {b1, … , bm}. Тогда любое отображение F: A → B можно задать набором длины nвида (F(a1), … , F(an)) элементов из множества B. При этом разные наборы такого видаопределяют разные отображения, и разные отображения дают разные наборы. Значит,имеется биективное отображение между множеством всех отображений F: A → B имножеством B× … × B(n раз). Следовательно, число отображений F: A → B дается формулойBA= mnЕсли нас интересует число частичных отображений из A в B, то нетрудно заметить, чтооно дается формулой(1 + B )A= (1 + m)n2.

Число инъективных отображений n-множества в m-множество. Любое инъективное отображение F: A → B однозначно задается набором длины n из элементов множества B вида (F(a1), … , F(an)), где F(ai) ≠ F(aj) при i ≠ j. Элемент F(a1) может приниматьB значений, при фиксированном F(a1) элемент F(a2) может принимать B - 1 значенийи т.д. Следовательно, число инъективных отображений F: A → B равно9B ( B − 1) ⋅⋅⋅ ( B − A + 1) = m(m − 1) ⋅⋅⋅ (m − n + 1)Следствие.

Число подстановок n-множества А равно n! = n×(n-1) … 2×1.3. Число k-элементных подмножеств n-множества. Пусть А = {a1, … , an} и требуется найти число подмножеств B ⊆ A с условием B = k , где 0 ≤ k ≤ n. Обозначим че n kрез   - искомое число, и пусть B1, … , B n  - все k-элементные подмножества А. Каж  kдому Bi можно поставить в соответствие k! (по числу биекций Bi на себя) инъективных 1отображений F: Nk → A, положив F:  a i12a i2⋅⋅⋅ k  , где Nk = {1, 2, … , k},⋅⋅⋅ a i k  nBi = { a i1 ,..., a i k } . Таким образом, всем   k-элементным подмножествам А будет по k nставлено в соответствие   * k! инъективных отображений. Ясно, что различные под kмножества Bi дают попарно различные инъективные отображения F: Nk → A, и каждоеинъективное отображение F: Nk → A может быть получено указанным образом. Значит, n kчисло инъективных отображений F: Nk → A равно числу   * k!, т.е. nn(n-1) …(n-k+1) =   * k! kОтсюда n n( n − 1) ⋅ ⋅⋅ ( n − k + 1)n!= =k!k !( n − k)! k(*) n 0Условимся считать 0! = 1 и тогда   = 1. n k n kКроме того, полагаем   = 0 при k > n.

Тогда функция fn,k =   будет определена для n kвсех целых неотрицательных чисел. Числа   называются биномиальными коэффициентами.Учитывая важность формулы (*), приведем еще одно доказательство ее. Будемдоказывать формулу (*) индукцией по n + k. Для n + k = 1 имеем очевидное утверждение. Пусть даны n, k и пусть формула (*) верна при всех n ′, k ′ , таких, что n ′ + k ′ < n + k.10Фиксируем элемент a ∈ A, где A = n . Разобьем все k-подмножества множества А надва класса:1. Те, которые содержат элемент a2. Те, которые не содержат элемента a. n − 1 подмножеств, и по предположению индукции выполнено k − 1В случае 1. имеем  n − 1( n − 1)!= k − 1 ( k − 1)!( n − k) ! n − 1В случае 2.