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

2.1. Варианты построения оснований математической общей теории систем

В основу математической общей теории систем могут быть положены те или иные системные концепции математики. Наиболее общие из них опираются на теорию множеств и теорию отношений. Имеющиеся до нас­тоящего времени варианты построения математической общей теории сис­тем непосредственно или косвенно опираются на теорию множеств и от­ношений. В настоящее время различают теоретико-множественный, струк­турно-математический, логико-алгебраический и категорийно-функторный варианты построения оснований математической общей теории систем.

Перечисленные варианты в основном исходят из сложившихся наибо­лее общих конструкций математики. Задача математической общей тео­рии систем состоит в трансформации соответствующих фундаментальных положений математики, связанных с данными конструкциями, в общие за­дачи исследования абстрактных и материальных систем. При нашем изло­жении будем придерживаться в основном теоретико-множественного под­хода [7-9].

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

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

Объекты, которые образуют множество, будем называть элементами множества и обозначать, как правило, малыми буквами латинского ал­фавита, сами множества – большими латинскими буквами А, В, С, О, X, У и т.д. Принадлежность элемента х к множеству X фиксируется за­писью . Противоположное утверждение записывается в виде Мно­жество У называется подмножеством (частью множества) X, если оно содержит только элементы, входящие в X. Формальная запись при атом имеет вид Два множества X и У равны тогда, когда имеет мес­то и т.е. множества состоят из одинаковых элементов (при этом наличие повторяющихся элементов не принимается во внимание). Если и множество У называется собственным подмножеством X.

Различают конечные множества, состоящие из конечного числа эле­ментов, и бесконечные множества, число элементов которых бесконеч­но. Если множество не содержит ни одного элемента, то оно называет­ся пустым и обозначается

Множество может быть задано различными способами: конечное множество может быть задано простым перечислением его элементов, записываемых в фигурных скобках: другой способ, используемый при задании как конечных, так и бесконечных множеств, состоит в указании свойства Р(х), которым обладают элементы дан­ного множества

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

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

B(M) = (2.1)

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

Декартовым произведением n множеств называет­ся множество упорядоченных n-ок (упорядоченных наборов длины n, кортежей длины n), таких, что первый элемент принадлежит вто­рой – В частности, если имеет место декартово произведение называется n-кратным или декартовой n-й сте­пенью и обозначается . Для декартовых произведений может исполь­зоваться геометрическая интерпретация. В атом случае множества называются осями координат n-мерного пространства, а кортежи <х₁, х₂,..., х_n > – точками этого пространства. Случай n = 2 декартова произведения множеств А и В приведен на рис. 2.1.

Рис. 2.1

Дальнейшее обобщение понятия, декартова произведения возможно путем введения булеанов как от исходных множеств, так и от формируемых декартовых произведений. Н.Бурбаки назвал конструируемое таким обра­мим множество ступенью шкалы, строя­щийся над базисными множествами Определение множества производится за шагов путем последовательного построения множеств в соответствии с задан­ной схемой образования (схемой конст­рукции) ступени Элемент последнего кортежа представляют собой пары определяющие по следующему правилу:

а) если и принимается

б) если и принимается

в) если и принимается

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

Например, пусть – базисные множества. Если имеем если имеем если то

Множества X к У называются эквивалентными, или множествами одинаковой мощности , если между их элементами существует вза­имно однозначное соответствие, т.е. каждому элементу соответ­ствует один и только один элемент и наоборот. Данное опреде­ление является основой для анализа важнейшей характеристики множеств – их мощности. Конечное множество можно поставить во вза­имно однозначное соответствие с частью натурального ряда чисел путем перенумеровки членов данного множества.

Мощность множеств характеризуется так называемыми кардинальны­ми числами. Кардинальное число конечного множества , состоящего из элементов, равно (card ). Кардинальное число булеана данного множества определяется следующим образом: card Бёсконечным множествам соответствуют бесконечные числа. Бесконечные множества делятся на счетные (бесконечностные) и несчетные. Счетные множества – это такие множества, которые могут быть поставлены во взаимно однозначное соответствие с натуральным рядом чисел и имеют, следовательно, мощность данного ряда. Последняя выражается бесконечным кардинальным числом Алеф₀ является наименьшим числом в ряду бесконечных чисел, оценивающих мощность бесконечных множеств, так называемы: трансфинитов. В качестве следующего числа обычно рассматривается (алеф₁), равный кардинальному числу булеана натурального ряда чисел Такую мощность имеет множество вещественных чисел, находящихся в пределах отрезка [0,1]. Множества, кардинальные числа которых равны , называются континуальными, или множества мощности континуума. Следующими рассматриваются множества с кардинальными числами и т.д. [1. 7].

Например, кардинальное число множества всех вещественных функций равно Предположения о том, что кардинальное число непосредственно следует за (континуум-гипотеза), - за (обобщенная континуум-гипотеза), не могут быть не доказаны, ни опровергнуты, и поэтому эти предложения вводятся как аксиомы [1-7].

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

или

или (2.2)

или

х у х у

Рис. 2.2

Вводится также операция взя­тия симметрической разности определяе-мая следующим образом:

(2.3)

Путем непосредственного обобщения определяются операции объедине­ния и пересечения семейства множеств где – множество индексов; – это множество элементов, каждый из которых принадлежит хотя бы одному – это множество элементов, принадлежащих сразу всем При этом выполняются следующие алгебраические законы:

1) (идемпотентность);

2) (коммутативность);

3) (ассоциативность);

4) (поглощение);

5) Если то – модулярность;

6) (дистрибутивность);

7) (универсальные границы);

здесь S – универсум;

8) – дополняемость;

9) (инволютивность);

10) (законы де Моргана).

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

1)

2)

3)

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

1) рефлексивностью:

2) симметрией:

3) транзитивностью:

Всякое отношение со свойствами 1, 2, 3 называется эквивалентностью. В свою очередь, эквивалентность определяет, очевидно, разбиение множества X на множества вида (где х₀ – дання точка Х). Множество А_і называют классом эквивалентности, содержащим х₀.

Пример 1. Пусть Р – целое число; пишем если х и у – два целых числа, отличающихся слагаемым, кратным Р. Ясно, что это отношение – эквивалентность.

Пример 2. Если две прямые Д и Д^/ параллельны или совпадают, то пишем Д ׀׀ Д^/; очевидно, ׀׀ есть отношение эквивалентности.

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

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

Многозначное отображение Г множества X в множество У есть закон, по которому каждому элементу ставится в соответствие некоторое подмножество ; при этом не исключается возможность

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

Пусть Г – отображение данного множества X в У. При на­зовем образом множества А множество

Можно проверить, что если - подмножества Х, то

(2.4)

Если Г и ∆ – отображения множества X в Х , то результат компози­ции Г∆ есть отображение, определяемое следующим образом: (Г∆) х = Г(∆х). Отображения Г², Г³,… – определяются так:

Г²х = Г (Гх);

Г³х = Г (Г²х);

…………….

Транзитивным замыканием отображения Г называется следующее отобра­жение множества Х в Х [1]:

(2.5)

Отображение Г^-1, обратное отображению Г, определяется так:

Если В , то полагаем

Пример 1. Возьмем в качестве множество людей и для обозначим через Гх множество детей человека х. Тогда: Г² – множество внуков х; ^х – множество, состоящее из х и всех его по­томков; Г^-1 – родители и т.д.

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

Пример 2. Рассмотрим шахматную игру; каждое положение задается диаграммой (местонахождением фигур в данный момент) и ходом (указанием, кто из игроков должен в этот момент играть).

Пусть – множество возможных положений, Гх (где ) – множество положений, которые по правилам игры можно получить непосредственно из х; если положение х – матовое или патовое, то Гх = . Имеем: Г³х – множество положений, которые можно получить из х тремя ходами; Г – множество положений, которые вообще можно рано или поздно получить, отправляясь от х; Г'^-1А (где А X – множество тех положений, из которых возможно одним ходом получить какое-либо положение, входящее в А). Такая система обозначений позволяет выразить формулой множество выигрышных положений и вывести отсюда ряд свойств. В случае шахмат правила игры полностью определяются множеством X и отображением Г; однако здесь мы имеем дело с таким большим числом положений, что изобразить все их точками, а отноше­ние Г – стрелками, соединяющими некоторые точки, практически невозможно. Тем не менее некоторые свойства, общие для правил шахматной игры и для отношений родства в группе людей, можно выявить, обращаясь к аксиоматическому методу.