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

Объекты, образующие некоторое множество, называются его элементами. Принадлежность некоторого элемента x множеству A обозначается как x Î A — « x есть элемент множества A » или « x принадлежит множеству A ». В свою очередь, непринадлежность некоторого элемента а множеству М обозначается в виде: а Ï М или а  М. Множества принято обозначать заглавными буквами латинского алфавита, а элементы множеств – строчными буквами.

Среди производных понятий теории множеств наиболее важны следующие:

· Пустое множество. Пустым множеством называется множество, не содержащее ни одного элемента. Пустое множество обозначают символом Æ.

· Подмножество и надмножество. Множество A называется подмножеством множества B, если любой элемент, принадлежащий A, также принадлежит B. Это записывается в виде отношения включения: A Í B. Таким образом, ( A Í B ) Û ( x Î A ® x Î B ). Множество B, в свою очередь, называется надмножеством множества A, что записывается в виде отношения обратного включения: B Ê A.

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

· Универсальное множество. Обычно, в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества, своего для каждого случая, которое называется универсальным множеством (универсумом). Универсальное множество обычно обозначается U (от англ. universe, universal set), реже E.

· Мощность множества можно рассматривать как числовую характеристику (метрику) любого множества. Мощностью некоторого конечного множества А является число его элементов. Мощность множества А принято обозначать | А |, например, мощность множества А= { a, b, c } равна | А |=3.

Мощность пустого множества равна нулю: | Æ |=0.

· Конечные и бесконечные множества. Множества, имеющие конечное число элементов и, соответственно, конечное значение мощности, называются конечными, а множества с бесконечным числом элементов и, соответственно, с бесконечной мощностью - бесконечными.

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

· Счетные и несчетные множества. Бесконечные множестваразделяются на счётные и несчетные. Бесконечное множество называется счетным, если его элементы можно пронумеровать, в противном случае, бесконечное множество называется несчетным.

Простейшим примером счетного множества является множество всех натуральных чисел, в связи с чем можно дать другое определение счетного множества: множество называется счетным, если оно равномощно множеству натуральных чисел, т.е. его можно представить в виде { x ₀, x ₁, x ₂, … }, где х _i – элемент множества, однозначно соответствующий его номеру (индексу) i.

В свою очередь, простейшим примером несчетного множества является множество действительных чисел.

Другими примерами счетных множеств являются множества целых и рациональных чисел, а примером несчетного множества – множество комплексных чисел.

В отношении счетных множеств имеют место следующие теоремы:

- любое подмножество счетного множества является либо конечным, либо счетным, иначе говоря, каждое бесконечное подмножество счетного множества также является счетным;

- объединение конечного числа счетных множеств также является счетным множеством.

· Булеан множества . Любое конечное множество содержит и конечное число подмножеств. Связь между произвольным множеством и всеми его подмножествами определяется булеаном.

Булеа­ном множества А называется множество всех его подмножеств. Булеа­н множества А будем обозначать В(А).

Иначе булеан множества А называют множеством - степенью множества А.

Булеан как множество всех подмножеств множества А должен включать в себя:

- пустое множество;

- само множество А;

- отдельные элементы множества А;

- всевозможные комбинации различных элементов множества А.

Замечание. Если множество А содержит n элементов, то число его подмножеств из k элементов представляет собой число сочетаний из n по k и определяется по формуле:

Пример 1.1. Записать булеан (множество – степень) для множества А= { a, b, c }.

B ( A )={ Æ , { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }}.

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

| А |= n ® | B ( A )|= 2ⁿ = 2 ^{| А |}.

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

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

1. Задание множеств списком предполагает перечисление элементов. Например, множество А состоит из букв a, b, c, d: A = { a, b, c, d }или множество L включает цифры 0, 2, 3, 4: L = { 0, 2, 3, 4 }.

2. Задание множеств порождающей процедурой означает описание характеристических свойств элементов множества: X = { x | H ( x ) }, т. е. множество X содержит такие элементы x, которые обладают свойством H ( x ).

Например:

B = { b | b = p / 2 ± k p, k Î N }, N - множество всех натуральных чисел.

3. Задание множества описанием свойств элементов. Например, M - это множество чисел, являющихся степенями двойки.

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

Например: S - множество успевающих студентов. Разрешающей процедурой включения во множество S является отсутствие неудовлетворительных оценок в последней сессии.

4. Графическое задание множеств осуществляют с помощью диаграмм Эйлера-Венна.

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

 

 

 

На рис. 1.1 приведена диаграмма Эйлера-Венна, на которой показаны универсальное множество U и множества A и B.

                                                               

 

 

Отношения между множествами

Два множества A и B могут вступать друг с другом в различные отношения.

· Множество Aвключено в B, если каждый элемент множества A принадлежит также и множеству B (рис. 1.2 а), 1.2 б). Частным случаем отношения включения может быть и равенство множеств A и B, что отражается символом Í: A Í B Û " a Î A ® a Î B.

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

· Множество Aстрого включено в B, если A включено в B, но не равно ему (рис. 2а), что отражается символом Ì: A Ì B Û ( A Í B ) и ( A ¹ B ).

В этом случае множество А называют собственным (строгим, истинным) подмножеством множества В . Примерами использования строгого включения могут являться: A Ì U, B Ì U, Æ Ì B, Æ Ì B.

 Отношения между множествами могут обладать следующими свойствами: рефлексивностью, симметричностью и транзитивностью.

Свойство рефлексивности является унарным (одноместным), т.е. применительно к единственному объекту (в данном случае к множеству) и означает, что отношение применимо к «себе самому».

Простым примером рефлексивного отношения для чисел могут служить отношения «³ » или «£ », т.к. для любого числа d можно записать d ³ d или d £ d. В свою очередь отношения «> » и «< » этим свойством не обладают, в связи с чем, они называются антирефлексивными.

Свойство симметричности является бинарным (двухместным), т.е. применимо к двум объектам. Отношение является симметричным, если оно выполняется в обе стороны по отношению к паре объектов (в данном случае множеств). Примерами свойства симметричности являются различные геометрические объекты, для которых понятие «симметрии» является наиболее наглядным. Например, отношение: «быть симметричными относительно оси х » в отношении точек плоскости является симметричным. Действительно, если первая точка симметрична второй, то вторая точка обязательно симметрична первой.

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

Если записать бинарное отношение между объектами a и b в общем виде aRb, где R – символ отношения, то для симметричного отношения: aRb ® bRa при любых a и b, а для антисимметричного aRb ® bRa, только, если a = b.

Примером антисимметричного отношения могут служить отношения «³ » или «£ » между числами. Действительно, ( a £ b ) ® ( b £ a ), только, если a = b.

Свойство транзитивности является тернарным (трехместным), т.е. применяется к трем объектам. Отношение R между объектами a, b, с является транзитивным, если из   aRb  и   bR с  следует   aR с, т.е. из выполнения отношения R между парами объектов ( a, b ) и ( b, с ) следует его выполнение и для пары ( a, с ). Примерами транзитивного отношения для чисел являются отношения «> », «³ », «< », «£ ».

Отношение, не обладающее свойством транзитивности, называется нетранзитивным. Примером нетранзитивного отношения между множествами может служить отношение «пересекаться». Действительно для множеств: A = { a, b }, B = { b, c } , C = { c, d } A пересекается с B, B пересекается с C, но A не пересекается с C.

Отношение нестрогого включения обладает свойствами:

- рефлексивности: А Í А;

- антисимметричности: ( A Í В   и   B Í A ) ® ( A = B );

- транзитивности: ( A Í В  и   B Ì C ) ® ( A Ì C ).

Отношение строгого включения обладает свойствами:

- антирефлексивности: А Ë А;

- транзитивности: ( A Ì В  и   B Ì C ) ® ( A Ì C ).

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

Для комбинации отношений строгого и нестрогого включений:

- ( A Í В  и   B Ì C ) ® ( A Ì C );

- ( A Ì В  и   B Í C ) ® ( A Ì C ).

· множество Aравно множеству B, если A и B включены друг в друга или, иначе, между ними существует отношение взаимного включения (рис. 1.2 б.):

A = B Û ( A Í B )  и  ( B Í A ).

Вторая часть равенства указывает на наиболее типичный метод доказательства равенства множеств A и B, который заключается в доказательстве сначала утверждения А Í В, а затем В Í А.

Равные множества содержат одинаковые элементы, причем порядок элементов в множествах не существенен:

A ={1, 2, 3} и В ={3, 2, 1} ® A = B.

· множества A и Bне пересекаются, если у них нет общих элементов (рис. 1.2 в):

A и B не пересекаются Û " a Î A ® a Ï B.

· множества A и Bнаходятся в общем положении, если существуют элемент, принадлежащий исключительно множеству A, элемент, принадлежащий исключительно множеству B, а также элемент, принадлежащий обоим множествам (рис. 1.2 г):

A и B находятся в общем положении Û $ a, b, c: [ ( a Î A ) и ( a Ï B )] и  [( b Î B )  и  ( b Ï A )]  и  [( c Î A )  и  ( c Î B )].

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

S – множество простых чисел;

N – множество натуральных чисел (т. е. N = {1, 2, 3, … });

Z – множество целых чисел;

Z + – множество целых неотрицательных чисел (иногда обозначается N ₀ (т. е. N₀ = {0, 1, 2, 3, … }));

Z – – множество целых неположительных чисел;

R – множество действительных чисел;

R + – множество неотрицательных действительных чисел;

R – – множество неположительных действительных чисел;

V – множество рациональных чисел;

W – множество иррациональных чисел;

К – множество комплексных чисел.

Для этих множеств очевидными являются следующие цепочки отношений включения:

· S Ì N Ì Z + Ì Z Ì V Ì R Ì К;

· W Ì R Ì К.

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

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

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

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

Над множествами определены следующие операции: объединение, пересечение, разность (относительное дополнение), симметрическая разность и дополнение (абсолютное).

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

A È B = {x | x Î A или x Î B }.

Операцию объединения можно распространить на произвольное, в том числе и бесконечное количество множеств, например, М = А È В È С È D . В общем случае используется обозначение   А, которое читается так: “объединение всех множеств А, принадлежащих совокупности S ”.

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

1.  А_i, если S={A₁, A₂, …, A_k};

2.  А_i, если S – бесконечная совокупность пронумерованных множеств;

3.  А_i, если набор индексов множеств задан множеством I.

Пример 1.2.

А= { a, b, c }, B = { b, c, d }, C = { c, d, e }.

A È B= {a, b, c, d}; A È C= {a, b, c, d, e}; B È C= {b, c, d, e}; A È B È C= {a, b, c, d, e}.

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

A Ç B = { x | x Î A и x Î B }.

Аналогично определяется пересечение произвольной (в том числе бесконечной) совокупности множеств. Обозначение для пересечения системы множеств аналогичны рассмотренным ранее обозначениям для объединения.

Пример 1. 3. (для множеств из примера 1.2):

А Ç В= { b, c }; A Ç C = { c }; B Ç C = { c, d }; A Ç B Ç C = { c } .

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

A \ B = { x | x Î A и x Ï B }.

Разность множеств А и В иначе называется дополнением множества А до множества В (относительным дополнением).

Пример 1. 4. (для множеств из примера 1.2)

А\В= { а, b, c } \ { b, c, d } = { a } .

Симметрической разностью множеств А и В называется множество, состоящее из элементов, которые принадлежат либо только множеству А, либо только множеству В (рис. 1.3 г). Симметрическую разность обозначают как   A Δ B, A – B или A Å B:

A Δ B = { x | ( x Î A и x Ï B )  или   ( x Î В   и   x Ï А ) }.

Таким образом, симметрическая разность множеств A и B представляет собой объединение разностей (относительных дополнений) этих множеств: A Δ B = ( A \ B ) È ( B \ A ).

Пример 1. 5. (для множеств из примера 1.2)

A Δ B = { a } È { d } = { a, d } .

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

={ x ç x Ï A }= U \ A.

С учетом введенной операции дополнения, разность множеств А и В можно представить в виде : A \ B=AÇ .

Операции над множествами используются для получения новых множеств из уже существующих. Порядок выполнения операций над множествами определяется их приоритетами в следующем порядке: , Ç , È, \, Δ.

12345678910Следующая ⇒

Поделиться: