Теория множеств

Теория множеств

Теория множеств (наряду с математической логикой) является фундаментом всей современной математики. Конечные множества чаще всего встречаются в дискретной математике, особенно в таких разделах как комбинаторика и теория графов, а бесконечные множества чаще являются предметом исследования теории чисел, алгебры и математического анализа. Создателем теории множеств считается Георг Кантор (1845 – 1918), хотя основные понятия и результаты теории множеств появились задолго до него. Его же заслуга в том, что он впервые систематически рассмотрел бесконечные множества.

Множества и подмножества

Понятия множества и его элемента в математике являются не определяемыми, то есть не выражаемыми через другие понятия. Под множеством понимают совокупность различных объектов, обладающих определённым общим свойством. Объекты множества называют его элементами. Множества обычно принято обозначать прописными латинскими буквами (A, B, C, …, X, Y, Z), а элементы этих множеств – строчными (a, b, c, …, x, y, z). Если x является элементом множества X, то говорят, что x принадлежит множеству X и пишут x X . В противном случае говорят, что x не принадлежит X и пишут x X . Совокупность объектов не являющаяся множеством носит название класса.

Множество, элементы которого используются при составлении других множеств, называют

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

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

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

При небольшом количестве элементов элементы множества могут быть просто перечислены. Например, если во множестве X четыре элемента a, b, c и d, то множество X можно описать так: X ={a ,b ,c ,d } . Следует обратить внимание на то, что порядок перечисления элементов множества не важен, при изменении порядка перечисления элементов мы не получаем другого множества.

Для описания множеств с большим количеством элементов, в том числе бесконечном, может применяться запись с так называемым характеристическим предикатом, то есть условием, которое позволяет выделять из универсума только определённые элементы. Например, множество всех чётных натуральных чисел можно задать так: X ={x : x делится на 2} .

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

={n :n :=1 ;while true do yield n ; n :=n+ 1 end } .

Говорят, что два множества X и Y равны или совпадают, если они состоят из одних и тех же элементов, и записывают этот факт так: X =Y . Другими словами, X =Y , если x X , то x Y , и, если y Y , то y X . Если же множества не совпадают, то пишут X ≠Y .

Если все элементы одного множества X являются также элементами другого множества Y, то тогда говорят, что множество X является подмножеством Y, и пишут X Y . Другими словами, X Y , если для любого x X справедливо, что x Y .

Пустое множество является подмножеством любого другого множества: X .

Если X Y , но X ≠Y , то говорят, что X собственное подмножество Y, и пишут X Y .

Множество подмножеств некоторого множества X называют семейством и обозначают M(X). Множество всех подмножеств множества X называют булеаном множества X и обозначают

2X .

Мощность множества

Количество элементов множества X называют мощностью множества и обозначают X . Множества с конечным числом элементов называют конечными множествами. Множества, число элементов которых бесконечно, называют бесконечными. Бесконечные множества, элементы которых можно пронумеровать числами натурального ряда, называют счётными множествами. Об остальных множествах говорят, что их мощность континуум. Мощность пустого множества равна нулю: =0 .

Если X Y , то X Y (если X – подмножество Y, то очевидно, что элементов в X не больше чем элементов в Y, более того, если X =Y , то количество элементов одинаково). Но будет ли справедливым более строгое неравенство: если X Y , то X <Y ?

Нетрудно показать, что для двух конечных множеств X и Y таких, что X Y , это неравенство справедливо: X <Y . В самом деле, так как X – собственное подмножество Y, то в нём должен отсутствовать хотя бы один элемент из Y, иначе бы множества X и Y совпадали, таким образом по крайней мере справедливо: X +1 Y . Отсюда, учитывая, что X и Y конечные значения, следует, что X<Y .

Но так ли это для бесконечных множеств X и Y? Сравним, например, мощности множеств всех натуральных чисел и всех чётных натуральных чисел M. Очевидно, что M . Поставим теперь в соответствие каждому числу n чётное по правилу: n→2×n .

Таким образом мы не пропустили ни одного чётного числа, и их количество оказалось таким же как и количество всех натуральных чисел.

Итак, мы показали, что для бесконечных множеств X и Y, X Y , неравенство X<Y , вообще говоря, несправедливо.

Задание на дом. Рассмотрите как соотносятся мощности множеств и , и и .

Ответ. В случае множеств и , , поставим в соответствие каждому n номер из по правилу:

если n=0 , то его номер 1;

Таким образом мы занумеровали все целые числа, воспользовавшись всеми натуральными числами. Значит = .

Теперь рассмотрим множество рациональных чисел . Несмотря на то, что рациональные числа на числовой прямой распределены несравнимо «гуще» чем числа из натурального ряда, при этом между любыми двумя рациональными числами найдётся ещё бесконечно много рациональных чисел, однако рациональных чисел столько же, сколько и натуральных! Покажем это. Для этого занумеруем рациональные числа по следующей схеме: сначала выпишем все положительные рациональные числа, имеющие в знаменателе 1, затем – 2, …:

Нумерацию будем вести по правилу:

11 →1 , 21 →2 , 12 →3 , 31 →4 , 32 →5 , … При этом нам будут попадаться повторения, но мы не будем их нумеровать.

После того как мы научились нумеровать все положительные рациональные числа, мы сможем занумеровать все рациональные числа по тому же принципу, по которому мы нумеровали целые числа.

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

Определим некоторые операции над множествами.

Объединением двух множеств X и Y называется множество Z, элементами которого являются все элементы как из множества X, так и из множества Y: Z =X Y ={z : z X или z Y } .

Например, пусть X ={a ,b ,c} и Y ={b ,c ,d } , тогда X Y ={a ,b ,c ,d } .

Пересечением двух множеств X и Y называется множество Z, элементами которого являются все совпадающие элементы из множеств X и Y: Z =X ∩Y ={z : z X и z Y } .

Например, пусть множества X и Y те же самые, тогда X ∩Y ={b ,c} .

Операции объединения и пересечения множеств обладают свойствами коммутативности:

X Y =Y X , X ∩Y =Y ∩X

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

(X Y ) Z =X (Y Z ),( X ∩Y )∩Z = X ∩(Y ∩Z ) .

Эти свойства аналогичны арифметическим (алгебраическим) свойствам коммутативности и ассоциативности операций сложения и умножения:

a+b=b+a ,a×b=b×a .

(a +b)+c=a+(b+c),(a×b)×c=a×(b×c)

Объединение и пересечение двух множеств связаны между собой свойствами

дистрибутивности:

X ∩(Y Z )=(X ∩Y ) ( X ∩Z )

X (Y ∩Z )=(X Y )∩( X Z ) .

Здесь также есть аналогия с дистрибутивностью арифметической (алгебраической) операции умножения относительно сложения:

a×(b+c)=a×b+a×c .

Разностью двух множеств X и Y называется множество Z, состоящее из элементов множества X, не встречающихся во множестве Y: Z =X Y ={z : z X и z Y } .

Например, при тех же множествах X и Y X Y ={a } .

Симметрической разностью двух множеств X и Y называется множество Z, состоящее из не совпадающих элементов этих множеств: Z =X Y ={z :(z X и z Y )или(z Y и z X )} .

На примере тех же X и Y X Y ={a ,d } .

Если X Y , то дополнением множества X до множества Y называется множество X Y =Y X . Если множество Y является универсумом, то фразу «до множества» опускают и применяют обозначение X =U X .

Пусть в нашем примере U ={a ,b ,c ,d } , тогда X ={d } .

Законы де Моргана. Если X U и Y U , то

XY = X ∩Y

X∩Y = X Y

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

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

Декартовым произведением множеств X 1 , X 2 ,… , X n называют множество всех упорядоченных совокупностей (x1 , x2 ,…, xn ) , где xi X i ,i [1,n ] :

n

∏ X i= X 1× X 2×…×X n={(x1 , x2 ,…, xn): xi X i ,i [1, n]} .

i=1