Курс содержит четыре раздела элементы теории множеств, алгебра логики, элементы комбинаторики и теория графов

• Название: Курс содержит четыре раздела элементы теории множеств, алгебра логики, элементы комбинаторики и теория графов
• Дата: 08.07.2018
• Размер: 2 Mb.
• Имя файла: Lektsii_diskr_matem_konspekt.doc
• Тип: Документы; #48405
• страница: 7 из 8

Алгебраические числа (A) - это корни алгебраических уравнений



с рациональными (целыми) коэффициентами.

Пусть R - множество действительных чисел,

Q - множество рациональных чисел,

J - множество иррациональных чисел,

А - множество алгебраических чисел,

T - множество неалгебраических (трансцендентных) чисел.

Тогда:

R=QJ и из того, что множество R является континуальным, то тем самым доказывается существование иррациональных чисел, более того, множество иррациональные числа представляют собой континуальное множество, в то время как множество рациональных чисел (как это было показано ранее) счетно;

R=AT и из того, что множество R является континуальным, то тем самым доказывается существование неалгебраических (трансцендентных) чисел, более того, множество трансцендентных числа представляют собой континуальное множество, в то время как множество алгебраических чисел (как это было показано ранее) счетно.

Примерами трансцендентных чисел являются числа: e, (число Эйлера) , где а -иррациональное число, а в - целое, с=0,1234567891011...(число Малера) и др.
И снова житейский парадокс. Мощность континуума имеет,

например, множество точек прямой или множество действительных

чисел, что то же самое. Более того, любой отрезок числовой оси,

даже такой малюсенький отрезок, как отрезок от 0 до 1, имеет

мощность континуума, то есть на нем больше чисел, чем найдется

чисел в счетном множестве. А раз этот отрезок имеет мощность

континуума, как и вся (бесконечная) прямая и, естественно, любой

ее отрезок, то можно сказать, что на отрезке от 0 до 1 ровно

столько же точек, сколько на отрезке прямой от Земли до Юпитера.
. Дополнить задачами из папки практ_зан_по теор_множеств/z2.pdf

5.4. Дополнение.
Разбиения. Классы эквивалентности. Фактормножества.
Разбиения. Классы эквивалентности.
О п р е д е л е н и е 1. Разбиением множества А называют любое семейство непустых и попарно непересекающихся множеств, если объединение множеств семейства равно А, т.е. .

Сами множества B_i называют элементами разбиения .

Например, множества образуют разбиение отрезка [0,1].
Пусть на множестве А задано отношение эквивалентности R. Тогда можно разбить множество А на классы эквивалентных элементов. Действительно, возьмем произвольный элемент и образуем класс В₁, состоящий из а₁и всех элементов, эквивалентных а₁. Затем выберем (если такой найдется) и образуем класс В₂ , состоящий из а₂ и всех элементов, эквивалентных а₂ и т.д. Получается система классов В₁, В₂,…. (возможно бесконечная) такая, что любой элемент из А входит хотя бы в один класс, т.е.



Эта система классов обладает следующими легко проверяемыми свойствами:

1. 
   система образует разбиение А, такое, что классы попарно не пересекаются;
   
2. 
   любые два элемента из одного класса эквивалентны;
   
3. 
   любые два элемента из разных классов неэквивалентны.
   

Построенное разбиение, т.е. система классов называется системой классов эквивалентности по отношению к R .

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

П р и м е р.

1. 
   Все классы эквивалентности D по отношению равенства состоят из одного элемента.
   
2. 
   Разбиение множества треугольников на классы эквивалентности по отношению подобия.
   
3. 
   Разбиение N по отношению "иметь общий остаток от деления на 3":
   

В₀ = {3,6,9,...}, В₁ ={1,4,7,...}, В₂ ={2,5,8,...}.
Дадим более строгое математическое определение классов эквивалентности.
О п р е д е л е н и е 2. Пусть А некоторое множество, а R отношение эквивалентности на мно­жестве А. Для каждого элемента определим подмножество К_а множества А следующим образом

и

Подмножество К_аназовем классом эквивалентности множества А по R, относительно элемента а. Элемент а назовем представителем этого класса.
Коротко это понятие можно сформулировать так:

Классом эквивалентности элемента a называется подмножество элементов, эквивалентных a.
Замечание. Далее отношение эквивалентности часто будем обозначать знаком .

_{П р и м е р. Пусть А ={1,2,3} и R = {(1,1),(2,2,),(3,3),(1,3),(3,1)}, тогда К1 =К3={1,3}, К2={2}.}

Т е о р е м а 1. Любые два класса эквивалентности либо не пересекают­ся, либо совпадают.

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

Пусть два класса эквивалентности Ka и Kb имеют общий элемент с т.е. . Тогда са и сb. В силу симметричности отношения имеем ас и сb. В силу транзитивности отношения получим аb.

Пусть , тогда ha. Так как аb, то hb и, следовательно .

Если же , то в силу симметричности получим hb, ba и в силу транзитивности - ha, т.е. .

Таким образом, K_a =K_b.

Фактормножества.
О п р е д е л е н и е 3. Пусть А – некоторое множество, а R – эквивалентность на А. Множество всевозможных классов эквивалентности множества А по отношению R называется фактормножеством множества А по отношению Rи обозначается А/_R(не путать с A\R).
Т е о р е м а 2. Пусть А — множество, a R , R₁ , R₂ — эквивалентности на А. Тогда:

1. 
   A/_R является разбиением множества А;
   

1. 
   Если эквивалентности R₁ и R₂ на множестве А различны, то различны и фактормно­-
   жества ^A/_R1 и ^А/_R2.
   

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

1. 
   Так как R— эквивалентность на А, то из теоремы 1 следует, что два различных класса по Rне пересекаются. Далее, так как объединение всех классов по Rсовпадает со всем множеством А, то, согласно определению 1, фактормножество A/_Rявляется разбиением А.
   
2. 
   Пусть R₁ ≠R₂. Значит R₁и R₂ состоят из различных пар. Пусть, для определенности, и , где . Предположим, что . Значит найдется такой, что . Так как , то . Это означает, что для любого тогда и только тогда, когда . Однако, для у = bэто не так. Значит наше предположение неверно, то есть .Но, так как , то .
   

Т е о р е м а 3. Для всякого разбиения множества А существует единственная эквивалентность R на А такая, что = A/_R. И наоборот.

Таким образом, эта теорема отождествляет понятия эквивалентности и разбиения: любая эквивалентность определяет единственное разбиение и наоборот.

Доказательство. Построим бинарное отношение R следующим образом: для любых элементов , пара тогда и только тогда, когда a и b принадлежат одному и тому же подмножеству из . Легко понять, что R является отношением эквивалентности и = A/_R. Предположим, что существует еще одна эквивалентность Q на А такая, что Q≠ Rи = A/_Q. Однако, по условию теоремы, = A/_R. Тогда A/_R. = A/_Q , что невозможно в силу п.2 теоремы 2. Следовательно, R– единственная эквивалентность на А такая, что = A/_R.

П р и м е р. Указать все эквивалентности на множестве A = {1,2,3}

Разбиение множества А на классы эквивалентности	Соответствующая ему эквивалентность
А = К1U К2U К3 = {{1},{2},{3}}	R1 = ЕА
A = К1U К3 = {{1,2},{3}}	R2= {(1,1), (2,2), (1,2), (2,1), (3,3)}
A = К1 U К2 = {{1,3},{2}}	R3= {(1,1), (3,3), (1,3), (3,1), (2,2)}
A = К1U К2 = {{1},{2,3}}	R4 = {(1,1), (2,2), (3,3), (2,3), (3,2)}
A = К1 = {{1,2,3}}	R5= A×A

Проверка осуществляется так: заданы А и R , требуется определить разбиение А на классы эквивалентности, как это было в примере, приведенном выше в этом параграфе.

Мощность множества.
О п р е д е л е н и е 4. Два непустых множества называются равномощными, если существует биективное отображение одного из них на другое.
Т е о р е м а 4.Равномощность есть отношение эквивалентности на любой непустой совокупности множеств.

Обозначим символом ≈ отношение равномощности. Покажем, что оно обладает всеми свойствами отношения эквивалентности. Пусть М, М₁, M₂, M₃- множества из данной совокупности. Так как тождест­венное отображение Id : М —> М есть биекция, то М ≈ М, т. е. выпол­нено условие рефлексивности. Пусть, далее, М₁≈ М₂. Тогда существует биекция f: М₁→ М₂ . Однако для всякой биекции существует обратная биекция f^-1: М₂→ M₁. Таким образом. М₂≈ M₁, т. е. выполнено условие симметричности. Предположим теперь, что M₁ ≈ M₂и М₂ ≈ M₁Тогда существуют биекции f: М₁→М₂ и f: М₂→M₃. Их композиция f₂◦f₁: M₁ —> Мз также является биекцией, поэтому M₁ ≈ Мз, т. е. выполнено и условие транзитивности.
Используя теоремы 1 и 2, можно любую совокупность множеств раз­бить на попарно непересекающиеся классы эквивалентности. Тем самым вводится понятие мощности множества.
О п р е д е л е н и е 5. Мощностью множества М будем называть класс множеств, равномощных с множеством М .
Для обозначения мощности используются различные символы, напри­мер, такие: card, #. Условимся, однако, в этом пункте мощность множества М обозначать символом |М|. Основным свойством, отличающим бесконечные множества от конечных, является то, что всякое бесконечное множество равномощно некоторому его соб­ственному подмножеству. Например, множество всех точек отрезка ОМ равномощно множеству всех точек отрезка OQ(рис. 9). Но очевидно, что .
О п р е д е л е н и е 6. Непустое множество М называется конечным,, если оно не равномощно никакому его собственному подмножеству.

Суще­ствует связь между тремя понятиями — отображением мно­жества, отношением эквивалентности на множестве и разбие­нием множества. Любая эквивалентность определяет единственное разбиение и наоборот. Но неверно, что существует взаимно одно­значное соответствие между отображениями и отношениями эквивалентности. Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображениезадает на А одно и то же разбиение — тривиальное разбиение на одно­элементные множества.
следует различать общее понятие отношения эквивалентности и его частный случай — экви­валентность, или равномощность, множеств.
В обобщение этого факта определяют количественную эквивалентность, или равномощность, двух бесконечных множеств как возможность установить между ними такое соответствие.

Выражаясь формально, множество А равномощно множеству В, если существует биекция Факт равномощности множеств А и В будем записывать так:

Говорят, что множество имеет ту же мощность, что и множество , если существует взаимно однозначное соответствие между элементами этих множеств. Можно писать , поскольку определённое таким образом отношение есть отношение эквивалентности. (Символом обозначается мощность множества ). Говорят также, что и равномощны.