Лекции по "Алгебре"

Раздел 2. Алгебра множеств

Тема 2.1 Основные определения теории множеств. Примеры.

Понятие множества является одним из фундаментальных понятий математики, которому трудно дать определение. Дело в том, что определить понятие – это значит найти такое родовое понятие, в которое это понятие входит в качестве вида, но понятие «множество» - это самое широкое понятие математики и математической логики, т.е. категория, а для категории нельзя найти более широкое, т.е. родовое понятие. Ограничимся описательным объяснением этого понятия.

Множество – это набор, совокупность каких-либо вполне различаемых объектов, называемых его элементами, обладающими общими для всех их и только их свойствами, и рассматриваемых как единое целое.

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

Какова же структура множества, чем одно множество отличается от другого, какие математические и логические операции определены для множества?

Прежде всего, каждое множество состоит из того или иного набора объектов, которые называются элементами множества.

Факт, что элемент а принадлежит множеству Х мы будем обозначать :аХ.

Например:

В книжке Милна про Винни Пуха есть фрагмент, когда Кролик перечисляет жителей леса, а Винни несколько раз повторяет: "И еще Иа, я про него чуть было не забыл". И хотя про Иа упоминают несколько раз, в лесу есть только один Иа.

Это одно из важнейших свойств множества: не повторяемость элементов множества. В каком бы порядке не перечислял бы Кролик Обитателей леса, это будет одно и то же множество. Т.е. при задании элементов множества не имеет значения порядок элементов.

При этом, нужно иметь ввиду, что элемент а и множество {а} – это не одно и то же. Первое – это объект, обозначенный а, второе – это множество, состоящее из единственного элемента а. Поэтому можно сказать, что «а принадлежит { а }» – это истинное суждение. В то время как, «{а} принадлежит а» - это ложное суждение.

Порядок элементов в множестве несущественен. Множества {а, в, с} и  {а, с, в} одинаковы.

Множество может задаваться:

1.        путем перечисления его элементов. Обычно перечислением задают конечные множества.

2.        путем описания свойств, общих для всех элементов этого множества, и только этого множества. Это свойство называется характеристическим свойством, а такой способ задания множества описанием. Таким образом, можно задавать как конечные, так и бесконечные множества. Если мы задаем множество каким-либо свойством, потом может оказаться, что этим свойством обладает всего лишь один объект или вообще такого объекта нет. Данный факт может быть совсем не очевиден.

Например:

множество натуральных чисел, больших 1, таких что, уравнение

имеет решение в ненулевых целых числах. Это множество содержит единственный элемент 2, но есть ли у него еще элементы, никто не знает.

Если характеристическим свойством, задающим множество. А не обладает ни один объект, то говорят, что множество А пустое. Обозначается это так: .

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

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

пустое.

Множества бывают конечными или бесконечными. Если число элементов множества конечно – множество называется конечным.

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

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

Например:

множество действительных чисел, множество частных решений дифференциального уравнения  - бесконечные множества.

множество чисел, делящихся без остатка на 3 – счетное множество,

множество букв русского алфавита, множество отличников вашей группы – конечно.

Определение: Два множества равны между собой, если они состоят из одних и тех же элементов. Т.е. любой элемент множества Х является элементом множества Y, и любой элемент множества Y является элементом множества Х.

Тема 2.2 Подмножество. Понятие универсального множества.

Подмножество

Определение: Множество Х является подмножеством Y, если любой элемент множества Х принадлежит множеству Y. Это еще называется нестрогим включением.

Некоторые свойства подмножества:

1.        ХХ - рефлективность

2.        X  Y & YZ      X  Z - транзитивность

3.          X т.е. пустое множество является подмножеством любого множества.

Например:

Пусть Х – множество студентов некоторой группы, Е – множество отличников этой же группы.

EX т.к. группа может состоять только из отличников.

Когда хотят подчеркнуть, что в множестве У есть обязательно элементы, отличные от элементов множества Х, то пишут ХУ. Это называется строгим включением.

Например:

Пусть Х – множество всех курсантов ДВИММУ, Е – множество курсантов электромеханического факультета.

EX т.к. в множестве всех курсантов ДВИММУ, обязательно есть элементы  E.

Упражнение: Самостоятельно определить свойства строгого включения.

Универсальное множество

Определение: Универсальное множество – это такое множество, которое состоит из всех элементов, а так же подмножеств множества объектов исследуемой области, т.е.

1.        Если М  I , то М  I

2.        Если М  I , то Ώ(М)  I , где под Ώ(М) – понимаются все возможные подмножества М, или Булеан М.

Универсальное множество обычно обозначается I.

Универсальное множество может выбираться самостоятельно, в зависимости от рассматриваемого множества, и решаемых задач.

Например:

Рассматривая множество студентов вашей группы, в качестве универсального множества можно взять и множество студентов ДВГМА, и множество всех людей земли, и множество всех живых существ земли.

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

Более подробно о свойствах универсального множества мы поговорим, обсуждая операции над множествами. Скажем только, что если роль нуля в алгебре множеств играет пустое множество. То универсальное множество, играет роль единицы в алгебре множеств.

Тема 2.3 Операции над множествами.

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

1.        Пересечение множеств.

Определение: Пересечением множеств Х и У называется множество, состоящее из всех тех, и только тех элементов, которые принадлежат и множеству Х и множеству У.

Например: Х={1,2,3,4} У={2,4,6} пересечением {2,4}

Определение: Множества называются непересекающимися, если не имеют общих элементов, т.е. их пересечение равно пустому множеству.

Например: непересекающимися множествами являются множества отличников группы и неуспевающих.

Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих одновременно всем множествам.

Свойства пересечения:

1.        X∩Y = Y∩X - коммутативности

2.        (X∩Y) ∩Z =X∩ (Y∩Z)=X∩Y∩Z - ассоциативности

3.        X∩ = 

4.        X∩I = Х

2. Объединение множеств

Определение: Объединением двух множеств называется множество, состоящее из всех и только тех элементов, которые принадлежат хотя бы одному из множеств Х или У.

Например: Х={1,2,3,4} У={2,4,6} объединением {1,2,3,4,6}

Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих хотя бы одному из этих множеств.

Свойства объединения:

1.        XUY= YUY- коммутативности

2.        (X UY)UZ =XU (YUZ)=XUYUZ - ассоциативности

3.        XU = X

4.        XUI = I

Из свойств операций пересечения и объединения видно, что пустое множество аналогично нулю в алгебре чисел.

3. Разность множеств

Определение: Данная операция, в отличие от операций пересечения и объединения определена только для двух множеств. Разностью множеств Х и У называется множество, состоящее их всех тех и только тех элементов, которые принадлежат Х и не принадлежат У.

Например: Х={1,2,3,4} У={2,4,6} разность {1,3}

Как мы уже видели, роль нуля в алгебре множеств играет пустое множество. Определим множество, которое будет играть роль единицы в алгебре множеств

4. Дополнение множества

Дополнением множества Х называется разность I и Х.

Свойства дополнения:

1. Множество Х и его дополнение не имеют общих элементов

2.Любой элемент I принадлежит или множеству Х или его дополнению.

1.        Из формулы 2 вытекает еще одно важное свойство

Тема 2.4
Законы и тождества алгебры множеств

X ∩ Y = Y ∩ X - коммутативности пересечения

(X ∩ Y) ∩Z =X ∩ (Y ∩ Z)=X ∩ Y∩Z – ассоциативности пересечения

X U Y= Y U Y- коммутативности объединения

(X U Y) U Z =X U (Y U Z)=X U Y U Z – ассоциативности объединения

X U  = X

X ∩  = 

X ∩ I = Х

XUI = I

Транзитивности

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

Дело в том, что термин алгебра в своем роде имя нарицательное. Под ним понимается раздел математики, изучающий алгебраические операции, а природа объектов, к которым применяются эти операции, не важна. Говоря об алгебре логики или об алгебре множеств, мы более всего уделяли внимание операциям, определенным над допустимыми в данной теории объектами, свойствам этих операций. Еще одним хорошо известным вам примером алгебры, является алгебра чисел, к которой все выписанные законы также применимы. Проводя аналогии между этими алгебрами, мы можем сказать

И хотя каждая из рассматриваемых нами теорий имеет свои специфические законы, не освещенные или просто неинтересные в рамках другой теории, можно говорить, что утверждения алгебры множеств можно рассматривать с точки зрения алгебры логики и наоборот.

Тема 2.5. Понятие кортежа. Декартово произведение множеств

Определение: упорядоченный набор, конечная последовательность каких-либо объектов, внешне связанных определенным положением, которое они занимают в данной совокупности объектов, называется упорядоченным множеством или кортежем.

Объекты, входящие в кортеж называются компонентами.

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

Например: можно как кортеж рассматривать буквы в слове, слова в фразе, абзацы в тексте.

Определение: Декартовым произведением двух не пустых множеств Х и У называется множество ХхУ, состоящее из всех упорядоченных пар,

                                          ХхУ = {(x,y) /    x  X;   y  Y)

Если одно из множеств пустое, то и ХхУ пустое.

Например:X = {1, 2}

                            Y = {1, 2, 4}

                            XxY = {(1,1); (1,2);(1,4);(2,1);(2,2);(2,4)}

                            YxX =  {(1,1);(1,2);(2,1);(2,2);(4,1);(4,2)}

Обратим внимание, что речь идет об упорядоченных парах, т.е. в отличии от множеств (1,2)(2,1)

Примером декартова произведения является система координат : пара чисел, обозначающие широту и долготу. Частный случай декартова произведения множества самого на себя называется степенью множества. Так, привычная вам система координат на плоскости есть не что иное, как декартово произведение множества вещественных чисел само на себя, или квадрат множества вещественных чисел.

                                                        RxR=R

и любая точка на плоскости задается (х, у) .

Из приведенного примера видно, что 

ХхУУхХ

Тема 2.6 Понятия соответствия, отображения, отношения, функции.

Рассмотрим два множества А и В. Элементы этих множеств могут каким-либо образом сопоставляться друг другу, образуя пары (а, b). Если задан способ такого сопоставления, то говорят что между множествами установлено соответствие. При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множеств А и В.

Определение: Соответствием между множествами А и В называется любое подмножество R= АхВ - декартова произведения множеств.

Например: Рассмотрим два множества:

А={Гагарин, Дунаевский, Носов, Рахманинов}

В={1900,1901,….2000} -  годы 20 века.

Установим соответствие между этими двумя множествами, например, человек – год рождения.