Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Остановимся на трёх указанных способах более подробно.

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

{Иванов, Петров, Сидоров}.

Другая сокращённая запись данного способа – вводят множество индексов

I={1, 2,..., n}

и пишут:

A={a_i}, i I.

При втором способе применяется запись

A={x  M | x – отличник группы},

что читается следующим образом:

“множество A отличников группы состоит из элементов x множества M студентов этой группы, обладающих тем свойством, что x – это отличник

группы”.

Когда нет сомнений, из какого множества берутся элементы x, указание о принадлежности x множеству M можно не делать. Тогда множество A записывается в виде:

A={x | x – отличник группы}.

Приведём ещё примеры ко второму (описательному) способу:

{x | x – чётное} – множество чётных чисел;

{x | x²-1=0} – множество {+1, - 1}.

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

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

Пример для третьего способа:

M={n | for n from 1 to 9}.

Для конечных множеств, заданных перечислением (первым способом), задача нахождения наибольшего и наименьшего элемента множества не представляет труда. Например, для множества T={4, 3, 5, 6}

6 – максимум, а 3 – минимум.

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

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

Пусть S – множество вещественных чисел. Верхней границей S является число C такое, что для любого xS имеет место:

xC.

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

Пример 1.1. В множестве

m<S<M

любое CM является верхней границей.

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

Для множества S обозначение точной верхней границы будет таким:

sup S.

Для примера 1.1 справедливо

sup S=M.

Примечание 1.1. Множество может иметь только одну верхнюю границу.

Пусть S – множество вещественных чисел. Нижней границей S является число с такое, что для любого xS имеет место:

xc.

Определение 1.12. Точной нижней границей (инфинумом) множества называется нижняя граница, не меньшая любой другой нижней границы.

Для множества S обозначение точной верхней границы будет таким:

inf S.

Для примера 1.1 справедливо

inf S=m.

Второй, описательный способ задания множеств, таит некоторые

опасности, поскольку “неправильно” заданные свойства могут привести к противоречию. Укажем один из наиболее типичных теоретико-

множественных парадоксов – парадокс Рассела.

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

Y={X | X X} (*)

Если множество Y существует, то мы должны иметь возможность ответить на следующий вопрос:

YY ?

Допустим, что YY, тогда в соответствии с (*)

YY.

Теперь допустим, что YY, тогда в соответствии с (*)

YY.

Таким образом, приходим к противоречию, известному как парадокс Рассела. Существует три способа избежать этого парадокса.

1. Ограничить используемые описания видом

A{xM | Q(x)},

где M – известное, заведомо существующее множество (универсум).

Для Y универсум не указан, а потому Y множеством не является.

1. Использовать типы.

Объекты имеют тип 0, множества имеют тип 1, множества

множеств – тип 2 и т. д.

Y не имеет типа и множеством не является.

1. Задавать A(x) в виде вычислимой функции (алгоритма).

Способ вычисления значения XX не задан, а потому Y множеством

не является.

В качестве центральных в теории множеств выступают понятия подмножества и надмножества.

Определение 1.13. Множество A называется подмножеством множества B, если любой элемент множества A принадлежит и множеству B.

B в этом случае называется надмножеством множества A.

Определение 1.14. Если множество B включает в себя A, что выражается

AB,

но при этом AB, то A называется собственным подмножеством B.

Очевидно, что часть собственного подмножества данного множества всегда является собственным подмножеством этого множества.

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

собственных подмножеств используется знак , а для несобственных .

Утверждение 1.1. Два множества равны, если они являются подмножествами друг друга.

Применительно к введённым понятиям подмножества и

надмножества действует следующая

Теорема 1.1. (теорема о верхней и нижней границах подмножества).

Если

BA,

то имеет место

inf B inf A, sup B  sup A.

Для определения подмножества характерно использование следующих символов:

 - символ, называемый квантором и означающий “любой”, “каков бы ни был”, “для всех”;

 - символ следствия (импликации), означающий “влечёт за собой”.

При помощи этих двух символов определение подмножества можно сформулировать так:

 x [xX  xY],

что читается следующим образом: для любого x утверждение “x принадлежит X” влечёт за собой утверждение “x принадлежит Y”.

Отметим некоторые свойства подмножества, вытекающие из его определения:

XX (рефлексивность);

[XY и YZ]  XZ (транзитивность).

Утверждение 1.2. Для любого множества M справедливо

  M.

Естественно, что пустое множество  не содержит элементов. Следовательно, при добавлении к M пустого множества мы фактически не добавляем ничего. Поэтому всегда считается, что любое множество M содержит в себе пустое в качестве подмножества.

Определение 1.15. Совокупность всех подмножеств множества A называется его булеаном или множеством-степенью и обозначается 2^A:

2^A={B | BA}.

Множества удобно изображать графически. В конце XIX века английский учёный Джордж Венн усовершенствовал введённые Эйлером круги для иллюстрации множеств, добавив к изображению объёма рассматриваемого понятия X изображение объёма логически противоположного ему понятия НЕ X (X). Объём понятия X дополняет объём понятия X.

Определение 1.16. Изображение множества в виде областей в прямоугольнике, представляющем универсальное множество, называется диаграммой Эйлера-Венна (см. рис. 1.1).

X

X

Рис. 1.1. Представление множества диаграммой Эйлера-Венна

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

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

Пусть A и B – некоторые числа, A+B – их сумма, AB – их произведение. Сумма и произведение чисел обладают следующими свойствами:

1. A+B=B+A; AB=BA – коммутативный или переместительный закон

2. (A+B)+C=A+(B+C); (AB)C=A(BC) – ассоциативный или

сочетательный закон

1. (A+B)C=AC+BC – дистрибутивный или распределительный закон

Интересно отметить, что в ассоциативном и коммутативном

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

Однако в дистрибутивном законе такой симметрии нет.

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

Определение 1.17. Объединением множеств X и Y называется

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

XY.

Формальное определение объединения множеств имеет вид:

XY={x | xX или xY}.

Пример 1.2. Если X={1, 2, 3, 4, 5} и Y={2, 4, 6, 7}, то XY={1, 2, 3, 4, 5, 6, 7}.

Пример 1.3. Рассмотрим два круга, представленных на рис. 1.2. Если X – это множество точек левого круга, а Y – множество точек правого круга, то объединение XY представляет собой заштрихованную область, ограниченную обоими кругами.

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

Для объединения множеств справедливы коммутативный и ассоциативный законы:

XY= YX;

(XY) Z=X(YZ).

Определение 1.18. Пересечением множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые

принадлежат как множеству X, так и множеству Y, что обозначается так:

XY.

Формальное определение объединения множеств имеет вид:

XY={x | xX или xY}.

Пример 1.4. Для множеств X и Y из примера 1.2: XY={2, 4}.

Пример 1.5. Рассмотрим два круга, представленных на рис. 1.3. Если X – это множество точек левого круга, а Y – множество точек правого круга, то пересечение XY представляет собой заштрихованную область, общую для обоих кругов.

Операция пересечения позволяет установить ряд соотношений между двумя множествами.

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

если они не имеют общих элементов, т. е. если

XY=.

Y

X

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

Непересекающимися множествами, например, являются:

• множества {1, 2, 3} и {4, 5, 6};

• множество отличников и множество неуспевающих студентов в группе;

• множества точек кругов на рис. 1.4.

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

X и Y находятся в т. н. общем положении:

• существует элемент множества X, не принадлежащий Y;

• существует элемент множества Y, не принадлежащий X;

• существует элемент множества, принадлежащий как X, так и Y.

X

Y

Рис. 1.4. Непересекающиеся множества

Характеристики

Список файлов книги