Начальные понятия теории множеств 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Начальные понятия теории множеств



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

Человеческое мышление устроено так, что мир представляется состоящим из отдельных «объектов». Философам давно ясно, что мир – единое неразрывное целое, и выделение в нем объектов – это не более чем произвольный акт нашего мышления, позволяющий сформировать доступную для рационального анализа картину. Но как бы там ни было, выделение объектов и их совокупностей – естественный способ организации нашего мышления, поэтому не удивительно, что он лежит в основе главного инструмента описания точного знания – математики.

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

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

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

Обычно множества обозначают прописными буквами латинского алфавита: A, B, C, …; а элементы множеств – строчными буквами: a, b, c, ….

Если объект х является элементом множества М, то говорят, что х принадлежит М: хÎМ. В противном случае говорят, что х не принадлежит М: хÏМ.

Пример 1. Это может быть множество студентов, присутствующих на лекции, множество четных чисел и т. д.

Определение. Множество А называется подмножеством множества В, если всякий элемент из А является элементом В. обозначают

Если А является подмножеством В и В не является подмножеством А, то говорят, что А является строгим (собственным) подмножеством В. обозначают

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

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

Определение. Множества А и В считаются равными, если они состоят из одних и тех же элементов, пишут А=В, А¹В – в противном случае.

Определение. Множества А и В считаются равными, если

Способы задания множеств:

  • перечислением элементов: М={a1, a2, …, ak}, т. е. списком своих элементов;
  • характеристическим предикатом: М={x | P(x)}(описанием характеристических свойств, которыми должны обладать его элементы);
  • порождающей процедурой: M={ x | x=f}, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. В таком случае элементами множества являются все объекты, которые могут быть построены с помощью такой процедуры. Например, множество всех целых чисел, являющихся степенями двойки.

Замечание. При задании множеств перечислением обозначения элементов обычно заключают в фигурные скобки и разделяют запятыми. Перечислением можно задавать только конечные множества (число элементов множества конечно, в противном случае множество называется бесконечным). Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае – не принадлежит. Порождающая процедура – это процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определяемого множества. Бесконечные множества задаются характеристическим предикатом или порождающей процедурой.

Пример 2.

1. М={1, 2, 3, 4} – перечисление элементов множества.

2. - характеристический предикат.

3. Числа Фибоначчи задаются условиями (порождающей процедурой):

а1=1, а2=2, an=an-1+an-2 для n>2.

Определение. Мощность конечного множества А - это число его элементов.

Мощность множества обозначают|A|.

Пример 3.

|Æ|=0, |{Æ}|=1.

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

Определение. Множество всех подмножеств множества А называется булеаном P(A).

Известно, что если множество А содержит n элементов, то множество P(A) содержит 2n элементов. В связи с этим используется также обозначение множества-степени множества А в виде 2А.

Пример 4.

А={0, 1, 2}, P(A)={ Æ, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

 

1.2. Операции над множествами. Диаграммы Эйлера-Венна

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Операции над множествами рассматриваются для получения новых множеств из уже существующих.

 

 

Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

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

Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

 

Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

Определение. Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):

 

 
 

Пример 5. С помощью диаграмм Эйлера – Венна проиллюстрируем справедливость соотношения (рис. 6).

 
 

 

 

Рис. 6.
Убедились, что в обоих случаях получаем равные множества. Следовательно, исходное соотношение справедливо.

 

1.3. Основные тождества алгебры множеств

Для произвольных множеств А, В, и С справедливы следующие соотношения (табл. 1):

Таблица 1

1. Коммутативность объединения 1’. Коммутативность пересечения
2. Ассоциативность объединения 2’. Ассоциативность пересечения
3. Дистрибутивность объединения относительно пересечения 3’. Дистрибутивность пересечения относительно объединения
4. Законы действия с пустым и универсальным множествами 4’. Законы действия с пустым и универсальным множествами
5. Закон идемпотентности объединения 5’. Закон идемпотентности пересечения
6. Закон де Моргана 6’. Закон де Моргана
7. Закон поглощения 7’. Закон поглощения
8. Закон склеивания 8’. Закон склеивания
9. Закон Порецкого 9’. Закон Порецкого
10. Закон двойного дополнения

 

Пример 6.

Доказать следующее тождество .

Решение.

Докажем это тождество двумя способами: аналитически (используя равносильности алгебры множеств) и конструктивно (используя диаграммы Эйлера-Венна).

1.

2. Построим соответствующие диаграммы Эйлера-Венна (рис. 7).

Рис. 7.
 
 

1.4. Прямое произведение множеств. Отношения и функции

Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов х и у, расположенных в определенном порядке. Две пары <x, y>, <u, v> считаются равными тогда и только тогда, когда x=u, y=v.

Упорядоченная n-ка элементов х1, …, хn обозначается <x1, …, xn>.

Определение. Прямым произведением множеств X и Y называется множество , элементами которого являются все возможные упорядоченные пары <x, y>, такие, что .

Определение. Прямым произведением множеств Х1, Х2, …, Хn называется совокупность всех упорядоченных n-ок <x1, …, xn> таких, что . Если Х12=…Хn, то пишут .

Пример 7.

1. Пусть X={1, 2, 3}, Y={0, 1}. Тогда ; .

2. Пусть Х – множество точек отрезка [0, 1], а Y – множество точек отрезка [1, 2]. Тогда - множество точек квадрата с вершинами в точках (0, 1), (0, 2), (1, 1), (1,2).

Определение. Бинарным (или двуместным) отношением r называется множество упорядоченных пар.

Если r есть отношение и пара <x, y> принадлежит этому отношению, то наряду с записью <x, y>Îr употребляется запись xry. Элементы х и у называются координатами (или компонентами) отношения r.

Определение. N-арным отношением называется множество упорядоченных n-ок.

Определение. Областью определения бинарного отношения r называется множество

Определение. Областью значений бинарного отношения r называется множество

Пусть rÍ X´Y определено в соответствии с изображением на рисунке 8. Область определения Dr и область значений Er определяются соответственно:

Dr={x: (x, y) Î r}, Er={y: (x,y)Î r}.

 
 

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

  1. списком (перечислением) пар, для которых это отношение выполняется.
  2. матрицей – бинарному отношению соответствует квадратная матрица порядка n, в которой элемент cij, стоящий на пересечении i -той строки и j -го столбца, равен 1, если ai и aj имеет место отношение, или 0, если оно отсутствует.

Пример 8.

Пусть M={1, 2, 3, 4, 5, 6}. Задать в явном виде (списком) и матрицей отношение r, заданное на множестве , если r означает «быть строго меньше».

Отношение r как множество содержит все пары элементов a, b из М такие, что a<b. Тогда

r = {(1, 2), (1,3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)}.

Матрица отношения имеет вид:

.

Определение. Бинарное отношение f называется функцией, если из <x, y>Îf и <x, z>Îf следует, что y=z.

Поскольку функции являются бинарными отношениями, то две функции f и g равны, если они состоят из одних и тех же элементов. Область определения функции обозначается Df, а область значений – Rf. Определяются они так же, как и для бинарных отношений.

Если f – функция, то вместо <x, y>Îf пишут y=f(x) и говорят, что y – значение, соответствующее аргументу х, или y – образ элемента х при отображении f. При этом х называется прообразом элемента y.

Определение. Назовем f n-местной функцией из Х в Y если f:Xn®Y. Тогда пишем y=f(x1, x2, …, xn) и говорим, что y – значение функции при значении аргументов x1, x2, …, xn.

Пусть f:X®Y.

Определение. Функция f называется инъективной, если для любых х1, х2, y из y=f(x1) и y=f(x2) следует, что x1=x2, то есть каждому значению функции соответствует единственное значение аргумента.

Определение. Функция f называется сюръективной, если для любого элемента yÎY существует элемент хÎХ такой, что y=f(x).

Определение. Функция f называется биективной, если f одновременно сюръективна и инъективна.

Рисунок 9 иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции.

 
 

Пример 9.

Рассмотрим три функции, заданные на множестве действительных чисел и принимающих значение в этом же множестве:

  1. функция f(x)=ex - инъективна, но не сюръективна;
  2. функция f(x)=x3-x – сюръективна, но не инъективна;
  3. функция f(x)=2x+1 – биективна.

Определение. Суперпозиция функций – функция, полученная из системы функций f, f1, f2, …, fk некоторой подстановкой функций f1, f2, …, fk во внешнюю функцию f вместо переменных и переименованиями переменных.

Пример 10.

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

 

1.5. Свойства бинарных отношений. Специальные бинарные отношения

Определение. Отношение r на множестве Х называется рефлексивным, если для любого элемента хÎХ выполняется хr х.

Определение. Отношение r на множестве Х называется симметричным, если для любых х, уÎХ из хr у следует уr х.

Определение. Отношение r на множестве Х называется транзитивным, если для любых х, у, zÎХ из хr у и уr z следует хr z.

Определение. Рефлексивное, симметричное, транзитивное отношение на множестве Х называется отношением эквивалентности на множестве Х.

Пример 11.

1. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

2. Отношение подобия на множестве треугольников есть отношение эквивалентности.

3. Отношение «строго меньше» на множестве действительных чисел не рефлексивно, не симметрично и транзитивно на этом множестве.

4. Отношение перпендикулярности прямых не рефлексивно, симметрично, не транзитивно.

Пусть r - отношение эквивалентности на множестве Х.

Определение. Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов yÎY, для которых хrу. Класс эквивалентности, порожденный элементом х, обозначается через [x]:

Определение. Отношение r на множестве Х называется антисимметричным, если для любых х, уÎХ из хr у и уr х следует х=у.

Определение. Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного порядка на множестве Х.

Пример 12.

1. Отношение «х £ у» на множестве действительных чисел есть отношение частичного порядка.

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

Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если у покрывает х, то точки х и у соединяют отрезком, причем точку, соответствующую х, располагают ниже у. Такие схемы называются диаграммами Хассе. На рис. 10 показаны две диаграммы Хассе, причем вторая соответствует линейно упорядоченному множеству.

1.6. Операции над бинарными отношениями

Так как отношения на Х задаются подмножествами rÍX´Y, для них определимы те же операции, что и над множествами:

  1. Объединение r1Èr2: r1Èr2={(х, у)| (х, у)Îr1 или (х, у)Îr2}.
  2. Пересечение r1Çr2: r1Çr2={(х, у)| (х, у)Îr1 и (х, у)Îr2}.
  3. Разность r1\r2: r1\r2={(х, у)| (х, у)Îr1 и (х, у)Ï r2}.
  4. Дополнение : .
  5. Обратное отношение r -1: х r -1 у тогда и только тогда, когда уrх, r -1={(x, y)| (y, x)Îr}.

Пример 13.

Если r - «быть моложе», то r -1 – «быть старше».

6. Составное отношение (композиция) r1 · r2. Пусть заданы множества М1, М2 и М3 и отношения R1 Í М1 ´ М2 и R2 Í М2 ´ М3. Составное отношение действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2, то есть (a, b) Î R1·R2, если существует такое с Î М2, что (а, с) Î R1 и (a, c) Î R2.

7. Транзитивное замыкание r°. Транзитивное замыкание состоит из таких и только таких пар элементов а и b из М, то есть (a, b)Îr°, для которых в М существует цепочка из (k+2) элементов М, k³ 0, что а, с1, с2, …ck, b, между соседними элементами которой выполняется r. Другими словами а r с1, с1 r с2, …, сk r b.

Пример 14.

Для отношения «быть сыном» транзитивным замыканием является отношение «быть прямым потомком по мужской линии».

1.7. Алгебраические операции

Пусть дано множество М.

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

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

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

  х1 х2 х3 х4
х1 х1 х2 х3 х4
х2 х2 х3 х1 х1
х3 х2 х3 х1 х2
х4 х4 х2 х1 х3

Фактическое задание алгебраической операции на множестве может быть произведено различными методами. Возможно также непосредственное перечисление всех результатов операций для конечных множеств. Его удобно описать с помощью, так называемой таблицы Кэли (табл.2). Слева и сверху квадратной таблицы выписывают все элементы множества. На пересечении строки, соответствующей элементу a, и столбца, соответствующего элементу b, записывают результат операции над a и b.

Будем употреблять следующую терминологию и символику: операцию называть умножением, а результат применения операции к элементам a и b – произведением ab.

Определение. Если для любых элементов a и b множества М справедливо равенство ab = ba, то операцию называют коммутативной.

Определение. Если для любых элементов a, b, c множества М справедливо равенство a(bc) = (ab)c, то операцию называют ассоциативной.

В ряде случаев множество М, на котором определена алгебраическая операция, обладает единичным элементом, т. е. таким элементом e, что ae = ea = a для всех a из М. Единичный элемент единственен.

Теорема. Если операция, определенная на М, ассоциативна, то результат ее последовательного применения к n элементам множества не зависит от расстановки скобок.



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 228; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.222.92.134 (0.091 с.)