ТЕОРИЯ СПИСКОВ И ЕЕ ПРИМЕНЕНИЕ В РЕШЕНИИ ЗАДАЧ ТЕОРИИ МНОЖЕСТВ

Введение.

В работе описывается теория списков, которая позволяет решать некоторые задачи теории множеств. Данная теория была использована на интуитивном уровне в [1, c. 15] при решении ряда задач. В данной работе представлен переход от интуитивных размышлений к теории, основанной на теории множеств. Также рассмотрен пример решения системы уравнений относительно заданного множества, как вариант применения данной теории.

Определение α-элементов.

Пусть множества S₁,..,S_n находятся в общем положении. Рассмотрим множество индексов а также множества индексов  Каждое из множеств  представляет собой сочетание из n элементов, взятых по m штук.

Определение 1. Введем множества, определяемые следующим выражением:

Множества α_k будем называть α-элементами.

Используя свойства  и ,

получим

В результате имеем выражение для α-элементов, аналогичное (1):

Таким образом каждому α-элементу мы поставили в соответствие набор элементов x из множества 

Замечание. При наличии в задаче универсального множества U определим нулевой α-элемент следующим образом:

Свойства α-элементов.

Для α-элементов определим следующий набор свойств:

Докажем данные свойства.

Из определения α-элементов можно сделать вывод о том, что верно либо выражение  либо выражение  либо оба этих выражения сразу. Тогда после раскрытия скобок в выражении (*) получим выражение, которое будет содержать конструкцию вида  Так как  то и 

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

Определение списков.

Определение 2. Каждому множеству  поставим в соответствие множество α-элементов  представимое в виде

Данное множество будем называть списком.

По определению, множество можно представить в виде

Но ранее было доказано, что  Таким образом, список  является аналогом разбиения множества  за тем исключением, что подмножества(α-элементы) могут оказаться пустыми в процессе решения задачи.

Определим условия пустоты α-элементов:

Операции над списками.

Таким образом, поставив каждому множеству  из набора множеств  список  , мы можем свести операции над множествами к операциям над списками. Определим данные операции:

 - пересечение списков.

 - объединение списков.

 - разность списков.

 - симметрическая разность списков.

 - дополнение списка.

Пример. Рассмотрим пример решения системы уравнений относительно множества Х с помощью списков.

Решить систему уравнений

Будем полагать, что A = S₁ , B = S₂ , C = S₃ , X = S₄.

Множества индексов:

I₁ = {1}, I₂ = {2}, I₃ = {3}, I₄ = {4}, I₅ = {1, 2}, I₆ = {1, 3}, I₇ = {1, 4}, I₈ = {2, 3},

I₉ = {2, 4}, I₁₀ = {3, 4}, I₁₁ = {2, 3, 4}, I₁₂ = {1, 3, 4}, I₁₃ = {1, 2, 4}, I₁₄ = {1, 2, 3},

I₁₅ = {1, 2, 3, 4}

α-элементы:

α₀ = U\(A∪B∪C∪X), α₁ = A\(B∪C∪X), α₂ = B\(A∪C∪X), α₃ = C\(A∪B∪X),

α₄ = X\(A∪B∪C), α₅ = (A∩B)\(C∪X), α₆ = (A∩C)\(B∪X), α₇ = (A∩X)\(B∪C),

α₈ = (B∩C)\(A∪X), α₉ = (B∩X)\(C∪A), α₁₀ = (C∩X)\(B∪A), α₁₁ = (B∩C∩X)\A,

α₁₂ = (A∩C∩X)\B, α₁₃ = (A∩B∩X)\C, α₁₄ = (A∩B∩C)\X, α₁₅ = A∩B∩C∩X

Составим списки для множеств:

[A] = {α₁ , α₅ , α₆ , α₇ , α₁₂ , α₁₃ , α₁₄ , α₁₅}.

[B] = {α₂ , α₅ , α₈ , α₉ , α₁₁ , α₁₃ , α₁₄ , α₁₅}

[C] = {α₃ , α₆ , α₈ , α₁₀ , α₁₁ , α₁₂ , α₁₄ , α₁₅}

[X] = {α₄ , α₇ , α₉ , α₁₀ , α₁₁ , α₁₂ , α₁₃ , α₁₅}

.

 иТогда 

,

Тогда 

Т.к  и  то пустых α-элементов не осталось.

Итого  Тогда 

Заключение.

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