ГЛАВА 1. Элементы теории множеств и комбинаторики.

Приходовский М.А.

Алгебра (курс лекций)

ИПМКН ТГУ, группы 932024, 932025

Весна -2021, семестр 2.  

ЛЕКЦИЯ 1. 11.2.2021

ГЛАВА 1. Элементы теории множеств и комбинаторики.

Множеством называют совокупность некоторых объектов. Эти объекты называются элементами множества.

Например, множество точек на плоскости, множество чисел, множество матриц.

 

Обозначения:

элемент   принадлежит множеству .

элемент   не принадлежит множеству .

множество   является подмножеством множества .

 множество   является собственным подмножеством множества  (т.е. они не совпадают).

 

 

Объединение    

Пересечение

Объединение и пересечение 2 множеств показаны графически:

 

 

Разность множеств: . Показано на чертеже:

Аналогично, .

 

Универсальное множество , дополнение .

Очевидно, что . 

 

 

Объединение этих двух разностей называется симметрической разностью, и обозначается так:  = , на чертеже:

В то же время, это множество можно получить и другим путём: из объединения удалить пересечение. То есть,

 = .

 

 

Другие обозначения: , .

 

Свойства операций над множествами

 

Законы идемпотентности:  , .

 

Операции с пустым множеством  Ø =  Ø = Ø  

 

Коммутативность:   ,

 

Ассоциативность:   

 

Дистибутивность:  

1)

можно записать в виде . 

 

2) однако, верно также и .  

либо в виде . 

 

Замена разности пересечением: . 

 

Док-во. Если , это означает, что , но при этом .

 означает то же самое - что одновременно выполнены условия , .

 

 

Лемма. (закон де Моргана). Объединение множеств есть дополнение к пересечению дополнений всех этих множеств.

Доказательство. Пересечение дополнений - это множество, содержащее элементы, не принадлежащие ни 1-му, ни 2-му,... ни n множеству. Дополнение к построенному - означает, что противоположно ситуации, когда не принадлежит никакому из них, т.е. принадлежит хотя бы одному из них.

 

1) дополнение к А 2) дополнение к В 3) пересечение дополнений 

 

 

Декартово произведение и декартова степень.

.  

.

Булеан.    или  - множество всех подмножеств множества  (включая пустое множество и само ).

 

 - множество всех функций из  в . 

Если строим подмн-во то отображаем функцией во мн-во из 2 элементов {0,1}. (характеристическая функция)

 

Числовые множества.

натуральные числа

 целые числа

 рациональные числа

 вся действительная ось, действительные числа.

Множество  - иррациональные числа.

.

Функция, аргумент, образ.

Пусть даны 2 множества , . Если задан некоторый способ каждому элементу  поставить в соответствие какой-то , то говорится, что задана ФУНКЦИЯ из  в . Обозначение: .  называется аргументом функции, а  - образом.

 

 

Мощность конечного множества - количество элементов, из которых оно состоит.

 

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

Например, если n=3, множество , то подмножества:

пустое, , , , , , ,  - 8 подмножеств.

Доказательство. Составим характеристическую функцию подмножества: факт вхождения элемента в подмножество обозначен через 1, а не вхождения через 0.

Тогда каждое подмножество может быть задано в виде: 

Для одного элемента есть 2 возможности 0 или 1, для двух элементов соответственно , для трёх , и.т.д (по индукции).

 

Характеристическая функция пересечения равна произведению характеристических функций . 

 

Характеристическая функция дополнения равна . 

 

Лемма.

1) Подмножество счётного множества конечно или счётно.

2) Всякое бесконечное множество содержит счётное подмножество. 

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

1) Представим множество  в виде:   Выбросим те члены последовательности, которые не принадлежат . Оставшиеся элементы образуют либо бесконечную подпоследовательность, либо конечную.

2) Если множество   бесконечно, то можно выбрать последовательность , после выбора каждого  остаётся ещё бесконечное множество неиспользованных элементов, потому что множество бесконечное.

 

Теорема. Если  бесконечное множество,  конечное или счётное, то  равномощно . 

Доказательство. Если  пересекаются, выбросим пересечение из , получив новое множество , которое снова будет конечным либо счётным. Далее считаем, что они не пересекаются.

Выделим в  счётное подмножество , остаток обозначим . 

. .  

 и  оба счётны, между ними существует взаимно однозначное соответствие. Каждый элемент из  соответствует самому себе. Таким образом, есть взаимно однозначное соответствие между

 и . 

 

Теорема. Счётное множество счётных множеств счётно.

Расположим по горизонтали каждое из множеств.

Из элементов этого множества можно образовать такую последовательность:  

Если исходные множества пересекаются, то часть повторяющихся элементов исключить, получим подпоследовательность, она тоже счётна. При этом она не будет конечна, так как хотя бы одно из исходных множеств счётно.

В обозначениях операций над мощностями, это пишется так: 

ﬡ₀  ﬡ₀ = ﬡ₀

Итак,

1) ﬡ₀ + n = ﬡ₀ 

2) ﬡ₀ + ﬡ₀ = ﬡ_0, ﬡ₀  = ﬡ₀

 3) ﬡ₀  ﬡ₀ = ﬡ₀

Пусть  - мощность множества А,  - мощность множества В, 

Ǿ. Тогда

Сумма    мощностей - это мощность множества ,

Произведение    мощностей - это мощность множества . 

Для бесконечных мощностей, .

Примеры.

Множество рациональных чисел  равномощно .

. Декартово произведение  равномощно , можно пронумеровать:

В каждом из слоёв конечное количество элементов. Начиная от внутренних прямоугольников, можно пронумеровать все элементы с помощью натуральных чисел.

 

ЛЕКЦИЯ 2. 13.2.2021

Теорема (Кантора). Множество всех подмножеств счётного множества не является счётным.

Доказательство.   Допустим, что искомое множество счётно. Тогда все подмножества можно расположить по порядку, представив то или иное подмножество в каждой строке с помощью 0 и 1 (1 если элемент принадлежит подмножеству, 0 если нет).

…

Рассмотрим диагональ: 

Построим такое подмножество: изменим 0 на 1 и 1 на 0 на всех местах. Напр, здесь было бы . Оно не совпадает ни с одним из подмножеств, представленных в этой последовательности: с первым не совпадает на 1-м элементе, со вторым на 2-м и так далее.

Итак, множество всех подмножеств счётного множества не является счётным.

 

Аналогично, докажем, что (0,1) не является счётным множеством.

 

Теорема. Интервал (0,1) не является счётным множеством.

Доказательство. Пусть все действительные числа, составляющие (0,1), образуют счётное множество. Каждое из них представим в виде десятичной дроби,    Расположим по порядку эти числа, если множество счётное:

....

Можно рассмотреть такое число: , взяв значения десятичных разрядов по диагонали.

Если теперь в  изменить каждую цифру на какую-либо другую, то получим новое число, которое не совпадает ни с одним из имеющихся в этом множестве. Таким образом, множество не счётное.

 

Теорема Кантора-Бернштейна.

Если множество  равномощно подмножеству множества , а  равномощно подмножеству множества , то  и  равномощны.

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

Пусть множество  равномощно некоторому  - подмножеству множества . Т.е. существует некоторая функция  , которая инъективна, но не сюръективна. При этом  биекция.

Аналогично  равномощно некоторому подмножеству  множества , и существует инъективная функция , при этом  биекция.

 

Тогда для композиции  есть некоторое множество   - «образ образа» множества . При этом  - биекция.

Так как  равномощно , то нужно фактически доказать, что равномощны  и , то есть построить биективное отображение.

При этом  равномощны.

Применяя функции  и   несколько раз, получим последовательность множеств:   при этом . Пересечение  возможно, непустое множество. 

Обозначим , ,... При этом . 

Биективное отображение  можно построить следующим образом.  для нечётных  и для ,  для чётных . При этом  перейдёт в ,  в   и так далее.

А равномощно А1, А1 равномощно В.

Континуум-гипотеза (проблема континуума) — выдвинутое в 1877 году Георгом Кантором предположение о том, что любое бесконечное подмножество континуума является либо счётным, либо континуальным. Другими словами, гипотеза предполагает, что мощность континуума — наименьшая, превосходящая мощность счётного множества. 

Континуум-гипотеза (первый несчётный кардинал имеет мощность континуума):

      

 

Аксиома выбора

Для всякого семейства X непустых множеств существует функция f, которая каждому множеству семейства сопоставляет один из элементов этого множества.

Аксиома выбора была сформулирована и опубликована Эрнстом Цермело в 1904 году. Новая аксиома вызвала бурную полемику и до сих пор не все математики принимают её безоговорочно.

Аксиомы теории множеств.

Система аксиом ZFC (Цермело-Френкеля с аксиомой выбора).

0. Аксиома пустого множества . 

 

1. Условие равенства множеств (аксиома объёмности).

 верно, что если :  то . 

 

2. Существование множества из двух элементов (аксиома пары).

, такое что :  или . 

 

3. Аксиома объединения. Из любого семейства  множеств  можно образовать как минимум одно такое множество , каждый элемент  которого принадлежит хотя бы одному множеству  данного семейства . 

. 

 

4. Аксиома пересечения. Из любого семейства  множеств  можно образовать как минимум одно такое множество , каждый элемент  которого принадлежит всем множествам данного семейства . 

. 

 

5. Существование подмножества, элементы которого удовлетворяют некоторому свойству.

. 

 

6. Существование бесконечного множества.

 = {Ø, {Ø}, {Ø,{Ø},... }  

 

7. Существование образа функции

   

т.е. если кратко, то . 

 

8. Аксиома регулярности.  Любое непустое семейство множеств  содержит множество , все  элементы которого не принадлежат семейству . 

 

9. Аксиома выбора. Для любого класса не пересекающихся непустых множеств существует множество, содержащее только по одному элементу из каждого множества.  

Прим – бесконечное мн-во прямых на пл-ти (континуум). Не сущ пр, пересекающ со всеми только в 1 точке.

 

10. Аксиома степени (аксиома булеана). Можно образовать  множество всех подмножеств данного множества.

Упорядоченные множества.

       Говорят, что на множестве М задано бинарное отношение R,  если задано подмножество декартового произведения: .

Примеры. Отношения на множестве

Отношение равенства:

Можно перечислить все пары элементов, находящихся в данном отношении: .

ЛЕКЦИЯ 3.

18.2.2021

Приходовский М.А.

Алгебра (курс лекций)

ИПМКН ТГУ, группы 932024, 932025

Весна -2021, семестр 2.  

ЛЕКЦИЯ 1. 11.2.2021

ГЛАВА 1. Элементы теории множеств и комбинаторики.

Множеством называют совокупность некоторых объектов. Эти объекты называются элементами множества.

Например, множество точек на плоскости, множество чисел, множество матриц.

 

Обозначения:

элемент   принадлежит множеству .

элемент   не принадлежит множеству .

множество   является подмножеством множества .

 множество   является собственным подмножеством множества  (т.е. они не совпадают).

 

 

Объединение    

Пересечение

Объединение и пересечение 2 множеств показаны графически:

 

 

Разность множеств: . Показано на чертеже:

Аналогично, .

 

Универсальное множество , дополнение .

Очевидно, что . 

 

 

Объединение этих двух разностей называется симметрической разностью, и обозначается так:  = , на чертеже:

В то же время, это множество можно получить и другим путём: из объединения удалить пересечение. То есть,

 = .

 

 

Другие обозначения: , .