дискретная математика1 - теория множеств

1 Множества. Способы задания множеств. Парадокс Рассела В «наивной» теории множеств по Г. Кантору: «Под многообразием или множеством я понимаю вообще все многое, которое возможно мыслить как единое, т.е. такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое.» Иначе говоря, множеством называется объединение различных объектов по указанному свойству, присущему всем элементам множества. При этом множество, содержащее только числовые элементы называется числовым; множество, содержащее множества называется классом или семейством. При этом элемент множества, являющийся записью какого-либо числа принято называть индивидной константой, а произвольный, заранее не определённый элемент множества называют индивидной переменной. Обозначение множества как правило — прописная латинская буква; элемент множества как правило — строчная латинская буква. Пример: A — множество, а — элемент множества. Принадлежность элемента к множеству обозначается:

а∈ А , элемент а принадлежит множеству А. Отрицание принадлежности:

a ∉ A , либо a ∈ A , элемент а не принадлежит множеству А. Равенство множеств: Множество А равно множеству B тогда и только тогда, когда

∀ a ∈A⇒ a ∈B ∧ ∀ b∈B ⇒ b∈A Пустое множество: ∅ - множество, не содержащее ни одного элемента. Некорректные записи, связанные с пустым множеством:

x ∈∅ Множество натуральных чисел: ℕ={1,2 ,3,4 ,.. } , 0 ∉ℕ ℕ0 ={0,1 ,2 ,3 , .. } Множество целых чисел: ℤ={−1,0,1 , .. } Множество рациональных чисел:

p q

ℚ={ ∣ p ∈ℤ , q ∈ℕ } 1 q

Множество действительных (вещественных чисел):

ℝ=− ∞ ,∞  Непринадлежность периодической дроби (9..):

1,999 .. ∉ℝ Множество комплексных чисел: ℂ ,

ℕ⊃ℤ⊃ℚ⊃ℝ⊃ℂ Конечность множества:

Множество А называется конечным, если ∃ k ∈ℕ : A ={a 1, a 2, a 3, ... , a k } , при этом число

k называется мощностью множества, ∣ A∣=k

Множество А называется бесконечным, если ∀ k ∈ℕ можно предъявить любое количество b ,b ∈ A ,b k ∈ A Способы задания множеств: 1. Непосредственное перечисление

A={a , b , c , d } , B ={1,2,3 , ..,999} 2. Порождающая процедура: Алгоритм, позволяющий построить множества из множеств, известных ранее или по элементам этого множества, известным ранее.

M 3 ={3 n∣n ∈ℤ} n

3. Распознающая процедура: Алгоритм, который ∀ a , ∀ A определяет, принадлежит ли элемент а множеству А. Парадокс Бертрана Рассела: Множества можно разделить на два класса:

A={ X ∣ X ∈ X } , множество, содержащее себя в качестве элемента; B ={ X ∣ X ∉ X } , множество, не содержащее себя в качестве элемента. B ∉ B ⇒ B∈ B B∈B ⇒ B∉B

2 q

2 Объединение, пересечение, разность, дополнение, симметрическая разность множеств. Теорема о четырёх возможностях Объединение множеств:

A∪ B={x∣x∈ A∨x ∈B} Пересечение множеств:

A∩ B ={ x∣x ∈ A∧ x ∈ B } Разность множеств

A∖ B={x∣x∈A∧ x∉B} Симметрическая разность множеств:

A B= A∖ B∪ B ∖ A Дополнение множества:

A={ x∣ x ∈U ∖ A } , или A' ;C A где U — универсальное множество. Диаграммы Эйлера-Венна:

A∖ B

A∪ B

A∩ B

AB

Отношения множеств: Включение:

A⊂ B ⇒ ∀ x  x ∈ A  x ∈ B  Строгое включение:

A⊂ B ⇒ A ⊆ B ∧ A ≠ B Собственное подмножество: A — собственное подмножество B, если

A⊂ B ∧ A≠∅ 3 q

Равносильность симметричности включения и отношения равенства:

A⊆ B ∧ B ⊆ A ⇒ A = B Свойство транзитивности включения:

A⊆ B ∧ B ⊆C ⇒ A⊆C Доказательство:

x ∈ A , A⊆ B ⇒ x ∈ B , B ⊆C ⇒ x ∈ C Проверим

A ∈ B ∧ B ∈ C ⇒ A ∈ C , свойство доказано;

пусть, A={ x } , тогда из

A⊆ B

B ={{ x } , y } ,

из

B ∈C

C ={{{ x } , y } , z }

значит

A∉C

Свойство включения пустого множества ∀ A : ∅⊆ A Отношение общего положения: Говорят, что множества

A и B находятся

в общем положении A °° B , если выполняются следующие условия: 1.

∃ a , a ∈ A∧ a ∉ B

2.

∃ b , b ∈ B ,b ∉ A

3.

∃ c , c ∈ A ∧c ∈ B

Теорема о четырёх возможностях: Для любых

A и B справедливо хотя бы одно из следующих утверждений:

1.

A⊆ B

2.

B⊆ A

3.

A∩ B =∅

4.

A°° B

Доказательство: Пусть ∃ A∃ B для которых ни одна из возможностей не выполняется. 1.

∃ a , a ∈ A∧ a ∉ B

2.

∃ b , b ∈ B ∧b ∉ A

3.

∃ c , c ∈ A ∧c ∈ B

Из этого следует, что А и B находятся в общем положении, что противоречит предположению.

4 q

3 Вектор. Декартово произведение. Декартова степень множества. Проекции. Теорема о количестве различных двоичных наборов размерности n Вектор (кортеж):

 = a 1, a 2, a 3, .. , a n a i - компонента вектора (координата)

n - размерность вектора. Проекция: i-ой проекцией (компонентой) кортежа называется элемент a i Равенство векторов (кортежей): Для  = b1, b 2, b 3, .. , b n

 = ⇔ ∀ i : a i =b i График: графиком называется множество, элементами которого являются упорядоченные пары (кортежи размерности n=2):

G ={ 1,1  , .. ,  n , n } Декартово произведение: декартовым произведением множеств А и B называется

A× B ={ a , b ∣a ∈ A ∧b ∈ B } A1× A2×.. × A n={ a 1, a 2, .. , a n ∣∀ i : a i ∈ Ai } Декартова степень множества:

An= A× A ×..× A n раз 1

A = A , A2 - декартов квадрат. Свойства декартова произведения:

A× B ≠ B × A - не транзитивно;

A× B ×C ≠ A × B ×C - не ассоциативно. Теорема о мощности декартовых произведений конечных множеств: Мощность декартова произведения конечных множеств равна произведению мощностей этих множеств. ∣ A1∣= m1, ∣ A2∣= m 2 ...∣ A n∣= m n , тогда

5 q

∣ A1 × A 2 × A 3 ... × A n∣= m1 × m 2 ×m 3 .. × m n Доказательство: Методом математической индукции: 1. При n=1

∣A 1∣=m1 , верно.

2. Предположим, что ∣A1× A 2× A3×..× A n∣=m1×m 2×m 3×..×m n верно. 3. Проверим истинность для

∣A1× A 2× A3×..× A n× A n1∣=m1×m2×m3×..×mn×mn1

 x 1, x 2, .. , c 1 m 1×m2×...×mk  x 1, x 2, .. ,c 2 m 1×m2×...×mk .....................  x 1, x 2, .. , c m  m1×m2×...×mk k1

∣A1× A 2× A3×..× A n× A n1∣=m1×m2×m3×..×mn×mn1 , теорема доказана Теорема о количестве различных двоичных наборов размерности n n

n

∣{0,1 } ∣= 2

Доказательство: по теореме о мощности декартовых произведений конечных множеств: n раз

 {0,1 }×{0,1 }×{0,1 }×...×{0,1 }= 2× 2 ×2... ×2 = 2n n раз

6 q

4 Инверсия и композиция графиков. Свойства операций над графиками Инверсия:

P − график , P −1−инверсия графика P −1={ y , x ∣ x , y ∈ P } Композиция:

P ° Q ={ x , y ∣∃ a  x , a ∈ P ∧ a , y ∈Q } композиция двух графиков не коммутативна:

P ° Q ≠Q ° P Свойства действий над графиками: Двойная инверсия:

 P −1−1=P Доказательство: −1 −1

 x , y ∈ P  ⇒ y , x ∈ P

−1

⇒ x , y ∈ P

Связь композиции и инверсии: −1

 P °Q =P

−1

°Q

−1

Доказательство:

 x , y∈ P °Q−1 ⇔ y , x∈P °Q ⇔ ∃ a ¿ y , a∈ P∧a , x∈Q⇔ ∃ x , a∈Q−1∧a , y∈P −1 ¿⇔¿  x , y∈P−1 ° Q−1 Ассоциативность композиции:

 P °Q °T = P °Q °T  Доказательство:

 x , y∈ P °Q° T ⇔∃a  x , a∈P °Q∧a , y∈T ⇔ ∃a ∃b x , b∈P∧b , a∈Q∧ a , y∈P ⇔ ∃b x , b∈P∧b , y∈Q °T ⇔ x , y∈P °Q °T 

7 q

5 Соответствия. Свойства соответствий. Отображения и биекции Соответствие:

Г = X ,Y , G

X — область отправления; Y — область прибытия; G — график соответствия. G⊆ X ×Y Если  x , y∈G , то y - образ элемента x ; x - прообраз элемента y A⊆ X , Г  A={y∣ x , y∈G , x∈ A} - образ соответствия; B⊂Y , Г  B={x∣ x , y∈G , y ∈B} - прообраз соответствия. Областью определения называется первая компонента кортежа графика, Областью значений называется вторая компонента кортежа графика. Основные свойства соответствий: 1. Всюду определённость:

пр 1 G= X 2. Сюръективность:

пр 2 G=Y 3. Функциональность:

 x , y 1 ∈G∧ x , y 2 ∈G ⇒ y 1= y 2 4. Инъективность:  x 1, y ∈ G ∧ x 2, y ∈ G ⇒ x 1= x 2 Соответствие называется отображением функционально.

X в Y , если оно всюду определено и

Соответствие называется отображением функционально и сюръективно.

X на Y , если оно всюду определено,

Соответствие называется взаимооднозначным, если оно функционально и инъективно. Соответствие называется биекцией, если оно всюду определено, сюръективно, функционально и инъективно.

f : X  Y - соответствие, действующее из X в Y .

8 q

6 Теорема о равномощных конечных множествах. Теорема о мощности множества всех подмножеств конечного множества Между конечными множествами можно установить биекцию тогда и только тогда, когда их мощности равны: ∣ A∣=∣B∣⇔ A ~ B Доказательство: 1. Докажем, что если ∃ 2 конечных множества одинаковой мощности, то между ними можно установить биекцию

A={a 1, a 2, a 3, .. , a n }

B={b 1, b 2, b 3, .. , bn } , a i ~ bi Очевидно, что между множествами установлена биекция. 2. Докажем, что если установлена биекция, то множества имеют одинаковую мощность а) ∣ A∣∣B∣ , так как ∀ a : a ∈ A существует единственный образ, а количество элементов множества A меньше количества элементов множества B , то некоторые из элементов множества B не получат прообраза, что противоречит условию сюръективности. б) ∣A∣∣B∣ , так как ∀ b : b∈B существует единственный прообраз, а количество элементов множества A больше количества элементов множества B , то некоторые из элементов множества A не получат прообраза, что противоречит условию всюду определённости. Следовательно оба из предположений не верны, ∣ A∣=∣B∣ Если между бесконечными множествами установлена биекция, то эти множества равномощны. Множество всех подмножеств (булеан):

P  A , 2 A - множество всех подмножеств множества A Содержит все возможные множества, являющиеся подмножеством для множества А.

9 q

Теорема о количестве различных подмножеств конечного множества ∣ A∣=n ⇒∣ P  A ∣=2

n

Доказательство: установим биекцию между множеством всех подмножеств множества и множеством двоичных векторов размерности n Пусть Ao⊆ A и e ={e 1, e 2, .. , e n} ,

A

∣ A∣=∣e∣=n

e i =0, если a i ∈ Ao , биекция установлена e i =1, если a i ∉ Ao Тогда ∣P  A ∣= 2 n

10 q

7 Теорема о счётном подмножестве бесконечного множества. Критерий бесконечности множества Множество называется счётным, если оно равномощно множеству натуральных чисел.  A~ℕ Теорема о счётном подмножестве бесконечного множества Каждое бесконечное множество содержит счётное подмножество.

∣A∣=∞ ⇒ Ao⊆ A: A o~ℕ Доказательство: выделим из множества

A элементы a i

а 1∈ A a 2 ∈A∖ {a 1} ⋮ a n ∈A∖ {a 1, a 2, ... , a n−1} Продолжая процесс выделения a (бесконечный при данном ∣A∣=∞ )

Ao={a 1, a 2, a 3, ... , a n } . Это множество, являющееся подмножеством для множества A счётно, так как ∀ n∈ℕ∃ Ao~ℕ Тогда

Критерий бесконечных множеств Множество бесконечно тогда и только тогда, когда оно равномощно собственному подмножеству. o

o

∣ A∣=∞ ⇔ ∃ A ⊆ A ∧ A ~ A Доказательство: 1. Пусть Ao⊂ A , A o~ A , ∣ A o∣= n. Тогда Ao ⊂ A ,∣ A o∣∣ A∣ , по теореме о равномощных множествах между множествами установить биекцию. 2.

∣ A∣=∞

Ao , A нельзя

⇒ M ~ℕ ∧ M ⊆ A

M ={a 1, a 2, a 3, ... , a n } A= A∖ M ∪M M o={a 2, a 4, .. , a 2n } Ao= A∖ M ∪M o o A ⊂A

f  x = x x =a i , f  x =a 2i

Если x ∈ A ∖ M Если x ∈ M

Ao ~ A 11 q

8 Теорема о счётности множества рациональных чисел. Теорема Кантора о несчётности множества точек интервала (0,1) Теорема о счётности множества рациональных чисел Множества рациональных чисел равномощно множеству натуральных чисел

ℚ~ℕ Доказательство: пронумеруем все рациональные числа с помощью следующей схемы:

...−3 −2 6  −1 5 0 1  12  2 3 ...  4 −3 −2 − 1 0 1  3 2 3 ...   ... 2 2 2 2 2 2 2 7   8 − 3 −2 −1 0 1 9  2 10  3 ...     ... 3 3 3 3 3 3 3 Очевидно, что таким образом можно пронумеровать все рациональные числа, значит между множествами ℕ и ℚ можно установить биекцию, значит множество рациональных чисел равномощно множеству натуральных чисел. ℕ - счётно. Теорема Кантора о несчётности множества действительных чисел интервала (0,1) Множество действительных чисел (в частности его подмножество, интервал (0,1)) не счётно. 0,1~ℕ Доказательство: Предположим, что удалось пронумеровать все действительные числа

1= 0, a 11 a 12 a 13 ... a 1,n ...  2=0, a 21 a 22 a 23 ... a 2,n ... ⋮⋮

 n=0, a n1 a n2 a n3 ... a n , n ...  =0, b 1 b 2 b 3 ... b n ... b 1≠a 1, b 1≠9 b 2≠ a 22, b 2≠9 ⋮⋮

bn ≠a nn , b n≠9 Число  не включено в начальную таблицу несмотря на свою принадлежность к множеству действительных чисел. Очевидно, что невозможно установить биекцию между множеством натуральных чисел и множеством действительных чисел. 12 q

9 Теорема о мощности множества всех подмножеств бесконечного множества Теорема о мощности множества всех подмножеств бесконечного множества Мощность бесконечного множества равна мощности множества всех его подмножеств.

∣ A∣=∞ ⇒ ∣P  A ∣=∣ A∣ Доказательство: Определим множество А:

A={a∣ a ∈ A }

A1={{a }∣ a ∈ A } множество одноэлементных подмножеств множества A

A1⊂ P  A  , A1~ A допустим, что

A~ P  A 

b ∈ A , B ∈ P  A Y ={b ∣b ∉ B , b ~ B } 1. y ∈ Y , y ~Y ⇒ y ∉ Y 2. y ∉ Y , y ~Y ⇒ y ∈ Y Противоречие доказывает теорему.

13 q

10 Отношения. Свойства отношений. Операции над отношениями Ф — отношение,

Ф = M ,G  : G ⊆ M n n-местное отношение  a 1, a 2, a 3, ... , a n∈G при n = 2 отношение называется бинарным,  a , b ∈G

G является графиком отношения. Обозначение отношения:

a  b - a вступает в отношение  c b; a  b - a не вступает в отношение  c b Действия над отношениями:

Ф=M , G , = M , F  1.

Ф∪={M , G∪ F }

2.

Ф=M , M 2 ∖ G

Свойства отношений: 1. Рефлексивность любой элемент вступает в отношение сам с собой

∀ x ∈M : x  x  M ={ x , x ∣x∈M } - диагональ Отношение рефлексивно тогда и только тогда, когда  M ⊆G 2. Антирефлексивность любой элемент не вступает в отношение сам с собой

∀ x ∈M : x  x Отношение антирефлексивно тогда и только тогда, когда  M ∩G=∅ 3. Симметричность

∀ x ∈M , y∈M : x  y  y  x Отношение симметрично тогда и только тогда, когда G=G −1 4. Антисимметричность

∀ x ∈M , y∈M : x  y , x≠ y  y  x ∀ x ∈M , y∈M : x  y , y  x  x= y

14 q

5. Транзитивность

∀ x ∈M , y∈M , z ∈M : x  y , y  z  x  z 6. Связность

∀ x≠ y , x∈M , y∈M : x  y∨ y  x

15 q

11 Теоремы о связи разбиения отображения с отношением эквивалентности Отношение эквивалентности — отношение, обладающее свойством рефлексивности, симметричности и транзитивности Разбиение множества — система непустых, попарно не пересекающихся множеств.

m={Ai ∣ ∀ i : Ai ≠∅ ,i ≠k ⇒ Ai ∩ A k =∅ , ∪ Ai = A} Для разбиения m отношение  m , называется сопряжённым с разбиением m, если:

x  y ⇔∀ i : x∈A i , y∈ Ai Теорема о порождении разбиением отношения эквивалентности Для каждого разбиения m ,  m является отношением эквивалентности Доказательство:

∀ x : x m x ∀ x ,∀ y : x  m y  y  m x

∀ x ,∀ y , ∀ z : x m y ∧ y  m z  xm z Отношение обладает свойствами рефлексивности, симметричности и транзитивности, значит отношение является отношением эквивалентности. Теорема о порождении разбиения отношением эквивалентности Если  - отношение эквивалентности, заданное на А, то существует такое разбиение m, что:  m= Доказательство:

[a]=a/  - класс, порождённый элементом a a /={x ∣ x  a} Проолжая процесс нахождения классов до тех пор, пока каждый из элементов А не войдёт в соответствующий класс, образуем фактор-множество:

m={[a] ∣ a∈ A} Мощность фактор-множества ∣m∣=M называется индексом разбиения

[a]≠∅ ∪[a i ]= A Предположим, что [a]∩[b]≠∅ , тогда с∈[a ]∧c∈[b]⇒ c[a]∧c [b]

a  c , c b⇒ a b ⇒ b=a

16 q

12 Отношения эквивалентности. Факторизация отображений Отношение эквивалентности — отношение, обладающее свойством рефлексивности, симметричности и транзитивности Отображение с отношением эквивалентности:

f : X Y x 1  x 2 ⇔ f  x 1= f  x 2  Свойства отношения эквивалентности отображения: 1.

∀ x 1 : f  x 1= f  x 1 

2.

∀ x 1, x 2 : f  x 1 = f  x 2 ⇔ f  x 2= f  x 1 

3.

∀ x 1, x 2, x 3 : f  x 1 = f  x 2 ∧ f  x 2= f  x 3  ⇔ f  x 1= f  x 3

Отношение эквивалентности отображения порождает разбиение на фактормножество.

g : x  x /

g  x =[ x ] - отображение на фактор множество. h : x /  f  x h [ x ]= f  x  - биекция e : f  x  Y e  y = y - взаимооднозначное соответствие Преставление f = g ° h ° e называется факторизацией отношения.

17 q

13 Отношения порядка. Единственность наибольшего и наименьшего элементов частично упорядоченного множества Отношением порядка на множестве A называется бинарное отношение, обладающее свойствами антисимметричности и транзитивности. Отношение, обладающее свойствами рефлексивности, антисимметричности и транзитивности называется отношением частичного порядка. ●

Порядок: антисимметричен, транзитивен;

●

Линейный порядок: рефлексивен, антисимметричен, транзитивен, связан;

●

Частичный порядок: транзитивен, антисимметричен, рефлексивен;

●

Предпорядок (квазипорядок): рефлексивен и транзитивен;

●

Строгий порядок: иррефлексивен, антисимметричен, транзитивен;

●

Строгий предпорядок: иррефлексивен, транзитивен.

Множество с определённым на нём отношением порядка называется частично упорядоченным множеством. Наименьшим элементом упорядоченного множества называется такой элемент I множества А, что ∀ x ∈ A: x ≤ I Наибольшим элементом упорядоченного множества называется такой элемент О множества А, что ∀ x ∈A: x≥O Теорема единственности наименьшего (наибольшего) элемента частично упорядоченного множества Если в частично упорядоченном множестве есть наименьший (наибольший) элемент, то он является единственным для этого множества. Доказательство: Теорема доказывается для наибольшего и наименьшего элемента аналогично, докажем теорему для наименьшего элемента. Предположим, что в частично упорядоченном множестве существуют два различных наименьших элемента O , O ∗ Докажем, что тогда O=O ∗ так как O ∗ - наименьший элемент и O∈ A  O ∗ ≤O так как O - наименьший элемент и O ∗ ∈A  O≤O ∗ по свойству антисимметричности отношения порядка следует, что O ∗=O

18 q

14 Бинарные операции. Свойства бинарных операций Бинарной операцией на множестве называется следующее отображение:

: A2  A Бинарная операция сопоставляет каждому кортежу декартова квадрата множества определённый элемент этого множества. Обозначим определённую бинарную операцию как ∗ Свойствами этой бинарной операции могут являться: 1. Коммутативность

∀ x ∈A ∀ y∈A : x∗y= y∗x 2. Ассоциативность

∀ x , y , z ∈A: x∗ y∗z= x∗y∗z 3. Дистрибутивность

∀ x , y , z ∈A: x∗ y ° z= x∗ y° x∗z  ∀ x , y , z ∈A: x ° y∗z= x ° y∗ x° z

19 q

15 Алгебры. Гомоморфизмы. Виды гомоморфизмов Алгеброй называется A= M , , где M — носитель алгебры, =1,  2, ... ,  n - сигнатура алгебры. Подалгеброй алгебры А называется A' = M ' ,  , где M ' ⊂M , M замкнута относительно каждой из операций сигнатуры. Гомоморфизмом называется отображение f :G 1  G 2, G1 = A ,∗ , G 2= B ,∗ при котором ∀ x , y ∈A: f  x∗y= f  x∗ f  y Изоморфизмом (эпиморфизмом) называется биективный гомоморфизм. Автоморфизмом называется отображение алгебры самой на себя. Эндоморфизмом и мономорфизмом называются соответственно сюръективный и инъективный гомоморфизм.

20 q