ОБЗОР ТЕОРИИ КОМПЛЕКТОВ

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

Теория комплектов была разработана в [50, 237].

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

В теории множеств основным понятием является отношение включения. Это отношение связывает элементы и множества и определяет, какие элементы являются членами каких множеств. Основным понятием теории комплектов является функция числа экземпляров. Эта функция определяет число экземпляров элемента в комплекте. Обозначим число экземпляров элемента х в комплекте В через (читается «число х в В»).

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

А.1. Членство

Функция определяет число экземпляров элемента х в комплекте В. Отсюда следует, что для всех Мы различаем нулевой и ненулевой случаи. Элемент х является членом комплекта В, если Это мы будем обозначать через Аналогично, если то

Определим пустой комплект 0, не имеющий членов (для всех

А.2. Мощность

Мощность комплекта В есть общее число экземпляров элементов в комплекте

А.3. Включение и равенство комплектов

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

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

Комплект А строго включен в комплект если Отметим, что не следует из хотя и .

А.4. Операции

Над комплектами определяются четыре операции. Для двух комплектов мы определим:

объединение комплектов

пересечение комплектов

сумму комплектов ;

разность комплектов

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

Различие между объединением и суммой очевидно:

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

А.5. Пространство комплектов

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

1. Из следует

2. Для любого

Множество есть множество всех комплектов над областью без какого-либо ограничения на число экземпляров элемента в комплекте.

А.6. Отображения Париха

Для конечной области существует естественное соответствие между каждым комплектом В над и -вектором определяемым соотношением

Этот вектор известен как отображение Париха [229].

А.7. Примеры

Пусть область. Тогда для следующих комплектов имеем: