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

• Название: Лекция 1 Элементы теории множеств. Алгебра множеств
• Дата: 27.10.2022
• Размер: 161 Kb.
• Имя файла: Lektsia_1_1 (1).doc
• Тип: Лекция; #757341

Лекция №1

Элементы теории множеств.

Алгебра множеств

Множество – это одно из основных, фундаментальных понятий математики. Оно в равной степени относится как к дискретной, так и к классической непрерывной математике. Теория множеств – учение об общих свойствах множеств. Универсальность языка теории множеств позволяет применять ее в мат. анализе, теории вероятностей и др областях математики.

Но что же такое множество? Слово это часто встречается в повседневной речи - мы говорим о "множество дел" или "множестве людей", и т.п. И в математике оно фактически подспудно присутствовало с момента ее возникновения. Но лишь во второй половине XIX века в работах немецкого математика Георга Кантора понятие множестваподверглось систематическому изучению.

До этого в математике существовали "натуральные числа" или "целые числа", но не "множество натуральных чисел" и не "множество целых чисел".

Георг Кантор считается основателем теории множеств как математической дисциплины. Он дал следующую формулировку понятию множества: «Множество есть многое, мыслимое как единое». Мы часто говорим о нескольких объектах, объединенных некоторым общим признаком (свойством). Например, множество точек окружности, объединенных признаком одинакового удаления от центра.

Определение. Под множеством S (согласно Кантору) будем понимать любое собрание определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами множества S.

Существенной деталью является то, что для любого объекта можно установить, принадлежит он данному конкретному множеству S или нет.

Обозначают множества прописными латинскими буквами. Общепринятые обозначения: N – множество натуральных чисел, Z – множество целых чисел, R – множество вещественных чисел, Q – множество рациональных чисел. Кроме того будем использовать следующие обозначения:  если …, то…;  … тогда и только тогда, когда…; …  для любых, для каждого…;  существует.

Множество задают (специфицируют) двумя способами:

- перечислением элементов: A= {1,2,3} (в фигурных скобках);

- характеристикой свойств, общих для элементов множества:

А = {x | P(x)} (А – это множество тех и только тех элементов x, для которых P от x есть истинное предложение, т.е. тех x, которые обладают свойством P).

Примеры.

А={1, 2, 3, 4, 5, 6, 7, 8};

А={x | x - целое, 0<x <9}, т.е. А – есть множество всех x, таких, что x – целое и x >0 и x <9.

Если элемент x принадлежит множеству А, то записывают x A, если не принадлежит, то x A. Например, 7 А, 9А.
Определение. Множества А и В считаются равными, если они состоят из одинаковых элементов. Обозначение: А=В, в противном случае АВ.

Например,

{1, 2, 3} = {2, 1, 3} = {2, 3, 1};

2  {1, 2}, {{1, 2}}  {1, 2} .

И даже так 2  {2}! То есть элемент не считается равным множеству, если даже множество состоит только из этого элемента. Элементы множества как бы объединены внутри оболочки. Если включить это множество в другое как элемент, то оболочка сохраняется!
Однако нельзя дать строгого определения абстрактному понятию множества.

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

А какие объекты вообще могут быть элементами множеств? На протяжении столетий развития математики, на этот вопрос неявно отвечали - о всех объектах. Элементами множеств могло быть все. В этом наивном стремлении свести все к множествам и скрывалось внутреннее противоречие. Рассмотрим классический пример такого противоречия.

Парадокс Рассела

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

Можно также указать множества, которые не являются элементами самих себя, например, множество {1, 2}, элементами которого являются числа 1 и 2 (других элементов нет) (т.н. ординарные множества).

Рассмотрим теперь множество А всех ординарных множеств Х, т.е. таких, что ни одно из множеств Х не принадлежит само себе как элемент, Х не есть элемент Х.

А само множество А? Ординарно или нет?

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

С другой стороны, если А экстраординарно (А есть элемент А), то А – одно из ординарных множеств Х, которые не есть элементы самих себя, т.е. А не есть элемент А. Т.е. оно ординарно.

В любом случае А есть элемент А и А не есть элемент А. Парадокс, абсурд или логическое противоречие.

Это напоминает известный старинный парадокс брадобрея: если полковой брадобрей по приказу командира бреет всех тех, и только тех солдат, кто не бреется сам, то бреет ли он сам себя? Здесь, аналогично, если он бреет себя, то он не бреет себя, а если не бреет - то бреет. Ни один брадобрей, как бы он не старался, не может выполнить этого условия. Оно противоречиво, и потому невыполнимо. Такого брадобрея не существует. В случае множества A нам ничего не остается, как признать, что множества всех ординарных множеств не существует.

Тем самым, интуитивная теория множеств, где элементами множества позволялось быть всем, чем угодно, противоречива. Причина этого кроется в признании существования множества всех множеств. В математике такие противоречия недопустимы. Следовательно, не все можно называть множеством. Мы описали множество A, а оно не существует. Подчеркнем, не пусто, а именно не существует как таковое.

Существует более строгая формализация теории множеств.

Отношения между множествами (отношения включения)

Определение. Говорят, что А содержится в B или что A есть подмножество множества В, если каждый элемент множества А есть элемент множества В.

Отношение включения между множествами (A содержится в B) обозначается знаком , т.е. A B.

Определение. Если AB и AB, то А есть собственное подмножество В (или строгое включение) и пишут АВ.

Примеры.

1. 
   {1, 2}{1, 2, 3, 4},
   
2. 
   множество четных чисел есть собственное подмножество множества целых чисел A={x|xZ, x=2n, nZ}.
   

Свойства отношения включения

1) AA (свойство рефлексивности (идемпотентности) – множество содержится в себе самом);

2) если AB, BC, то AC(свойство транзитивности);

3) если AB, BA, то A=B (свойство антисимметрии).

Примечание. Не надо путать отношения включения  и принадлежности . Хотя 1{1}, а {1}{{1}}, однако 1{{1}}, так как единственным элементом {{1}} является {1}. Однако, если 1{1, 2} как элемент, то {1}{1, 2} как подмножество.

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

Пусть A – некоторое множество.

Определение. Множество всех подмножеств A называют множеством – степенью или Булеаном и обозначается B(A).

Пример.

Если А ={1, 2, 3}, то B(А)={,{1},{2},{3},{1, 2},{1, 3},{2, 3}, А}.

Утверждение: если A состоит из n элементов, то B(A) состоит из 2ⁿ элементов.

Доказательство. Перенумеруем все элементы множества А от 1 до n. Введем описание любого подмножества множества А в виде строки из n бит (ячеек, содержащих цифры 0 или 1).

0

1

0

0

…

1

0

1

0 на i-том месте означает, что i-тый элемент множества А не принадлежит данному подмножеству, 1 – что принадлежит. Например, пустое множество обозначается строкой нулей, само множество А – строкой единиц. Каждая комбинация из 0 и 1 это различные двоичные числа.

Тогда число различных подмножеств множества А, равно числу различных комбинаций нулей и единиц, что соответствует количеству различных двоичных чисел, которые можно записать в n битах, т.е. 2ⁿ.

Действия над множествами

Результатом действий над множествами является новое множество.

Иллюстративно операции над множествами можно представить с помощью диаграмм Эйлера-Венна (рис. 1.1).

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

Универсум обозначается квадратом. Другие множества обозначаются кругами (или другими геометрическими фигурами) внутри этого квадрата.


A


Рис. 1.1. Диаграмма Эйлера-Венна
1. Объединением множеств А и В называется множество всех элементов, которые являются элементами хотя бы одного множества А или В (рис. 1.2): AB={x |xA или xB}.


A B

A

B


Рис. 1.2. Диаграмма Эйлера-Венна для операции объединения

Некоторые свойства объединения: AAB, BAB.
2. Пересечением множеств А и В называется множество всех элементов, которые являются одновременно элементами обоих множеств А и В (рис. 1.3):

AB={x | xA и xB}.


A B

A

B


Рис. 1.3. Диаграмма Эйлера-Венна для операции пересечения
Некоторые свойства пересечения: ABAAB, ABBAB.
3. Абсолютным дополнением множества А до универсума (отрицанием) называется множество всех элементов, не принадлежащих множеству А (рис. 1.4):

= {x | x A}.


A




Рис. 1.4. Диаграмма Эйлера-Венна для абсолютного дополнения
4. Вычитанием множеств (или разностью множеств BиA или относительным дополнением множества А до множества B) называется множество элементов, принадлежащих множеству В и одновременно не принадлежащих множеству А (рис. 1.5):

B\A={x | xB и xA}.


B \ A

B

A


Рис. 1.5. Диаграмма Эйлера-Венна для операции вычитания
Аналогично разность множеств A иB:A\B={x |xA и xB}.

Эта операция может быть осуществлена с помощью пересечения и абсолютного дополнения: B\A=B .
5. Симметрической разностью называется объединение вычитаний или относительных дополнений B до A и A до B (рис. 1.6):

A+B= (A\B)(B\A).


A + B

A

B


Рис. 1.6. Диаграмма Эйлера-Венна для операции симметрической разности
Замечание. Часто объединение множеств называют суммой множеств. Однако, в отличие от обычной «суммы» элементов, общие элементы в объединение множеств входят один раз.

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

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

относительно объединения относительно пересечения

1	AВ=BA (коммутативность объединения );		1	AB=BA (коммутативность пересечения );
2	A(BC)=(AB)C (ассоциативность );		2	A(BC)=(AB)C (ассоциативность );
3	A(BC)=(AB)(AC) (дистрибутивность  относительно );		3	A(BC)=(AB)(AC) (дистрибутивность  относительно );
4	A=A;		4	A=;
5	A =U;		5	A =;
6	AA=A;		6	AA=A;
7	AU=U;		7	AU=A;
8	= (закон де Моргана);		8	= (закон де Моргана);
9	A(AB)=A (закон поглощения);		9	A(AB)=A (закон поглощения).

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

Пример. АÈÆ=А Þ Þ Þ . Последнее равенство в силу произвольности А (а следовательно и ) можно переписать ВÇU=В для любого множества В из U.

Для доказательства соотношений алгебры множеств возможны два подхода: использование теоретико-множественного аппарата или формул алгебры множеств. Рассмотрим доказательства некоторых свойств.

Доказательство свойства 3 (дистрибутивности объединения относительно пересечения). Согласно свойству антисимметрии отношения включения  , если XY, YX, то X=Y , необходимо доказать справедливость двух утверждений.

1 утверждение. A(BC)(AB)(AC).

(в доказательстве используем понятия подмножества и действия над множествами).

Действительно, если произвольный элемент xA(BC), то xA или xBC.

1) Если xA, то xAB и xAC. Тогда x(AB)(AC).

2) Если xBC, то xB и xC. Тогда xBA и xCA, а значит, с учетом свойства коммутативности x(AB)(AC).

Таким образом, 1 утверждение справедливо по определению, так как из условия xA(BC) имеем x(AB)(AC).

2 утверждение. (AB)(AC)A(BC).

На самом деле, если x(AB)(AC), то xAB и xAC. Тогда xA или xB и (одновременно) xC, т.е. (xВC). Тем самым, xA(BC), т.е. второе утверждение также справедливо.

Из справедливости первого и второго утверждений следует справедливость исходного равенства

A(BC)=(AB)(AC).

Доказательство свойства 8 (закон де Моргана относительно объединения. ( = ).

1) Пусть x . Тогда xU и xAB  xUи xA и xB  x и x  x  (из определения подмножества)  .

2) Пусть x . Тогда x и x  xU и xA и xB  xAB, т.е. x   .

В силу справедливости того и другого утверждения справедливо (из свойства антисимметрии) и доказываемое равенство.

3