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
AB
Отношения множеств: Включение:
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 n1∣=m1×m2×m3×..×mn×mn1
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 k1
∣A1× A 2× A3×..× A n× A n1∣=m1×m2×m3×..×mn×mn1 , теорема доказана Теорема о количестве различных двоичных наборов размерности 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 12 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 xm 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