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

1.    Предисловие

Описание множеств с самопринадлеж-ностью, введенных Миримановым [1], приведено в работах с [2] по [4], где дано качественное изложение свойств множеств. Интерес представляют и количественные результаты по определению порядка (мощности) множеств подмножеств конечных множеств. Ниже приведены результаты 1 , относящиеся к несамопринадлежащим множествам и множествам с самопринадлежностью, обладающим относительно простой структурой.

2.    Несамопринадлежащие множества

Рассмотрим для начала несамопринад-лежащие множества. Пусть А ∉ А и А – конечно, |A| = n, n ∈ N , и для всех a, a ∈ A, a – единичный объект, |a| = 1. Требуется определить порядок множества всех подмножеств множества А, – |Exp(A)|.

При перенумерации всех объектов из А, это множество в записи представимо так:

А={a 1 , a 2 , a 3 ,… , а n }.            (1)

Для каждого подмножества В j из А, В j ⊆ А, и каждого объекта а i из А определима характеристическая функция χ (B j , а i ):

χ (B_j, а_i) = { 1; а i ∈ b j ; 0; а i ∉ b j ,

(2) которая принимает единичные значения, если объект а i принадлежит подмножеству В j , и нулевые – если не принадлежит этому подмножеству.

Значения характеристической функции (2) дадим записью (1) под соответствующими объектами a_i из А; строка записи соответствует подмножеству B j и является некоторым двоичным числом. В этой записи упорядочим двоичные строки-числа, получим запись вида А={a₁, a₂, a₃,… , а_n}

1 0 0 …  0 — B1={a

0 1 0 …  0 — B2={a

• 1  1  0 …  0 — B3= {a1, a2}(3)

3.    Самопринадлежащие множества

1… 1 1     1 — Bm=A.

В записи (3) m строк; строка, состоящая из одних нулей, соответствующая пустому множеству ∅ , в эту запись не входит, так как по его свойствам, приведенным в работах [2], { ∅ } = [ ∅ ] = ∅ ("ничто" ∅ множеств не образует). Таким образом, в записи (3) всего m = 2ⁿ – 1 двоичных строк. Доказана теорема.

Теорема 1. Для любого несамопринад-лежащего конечного множества A, А ∉ А, |A| = n, n ∈ N , состоящего из единичных объектов, ∀ a, a ∈ A, |a| = 1, порядок множества его подмножеств Exp(A) равен |Exp(A)| = 2ⁿ – 1. □

Рассмотрим самопринадлежащее множество С такое, что его внутренность2 равна множеству из условия теоремы 1, V(C) = A; т.е. С есть простой последователь3 от А; перенумеруем все объекты из С, тогда получим запись, аналогичную записи (1):

C = Сk = {a1, a2, a3,… , аk–1, Сk}. (4)

То же самое проделаем с характеристической функцией, построенной аналогично (2) для объектов из С и подмножеств D j _, D j ⊆ C.

Запись двоичных слов, аналогичная (3), в первом приближении имеет вид

C=Сk= {a1 , a2, a3,… , аk–1, Сk}            (5) 1  0 0 0 0 – D1 = {a1} 0  1 0 0 0 – D2= {a2} 1   1 0 … 0 0 – D3 = {a1, a2} 1… 1 1 1 0 – Dr–1= A 0 0 0 0 1 – Dr= C 1  0 0 0 1 — Dr+1 ={a1, C}=C 1… 1 1 1 1 – Ds= C, где s=2k. В этой записи имеются одинаковые подмножества – это те подмножества, которые содержат С, поскольку в этом случае, по тереме о транзитивности отношения принадлежности [2], подмножество С, содержащее С, совпадает с С.

Если быть точными, то, "подправляя" характеристическую функцию в соответствии с теоремой о транзитивности принадлежности, следует записать предыдущую таблицу (5) иначе.

Последние строки, начиная с r-й, будут одинаковы:

C=Сk={a1, a2, a3,…	, аk–1, Сk}.		(6)
1 0 0 …	0	0  – D1 = {a1}
0 1 0 …	0	0  – D 2 = {a 2 }
1  1 0 …	0	0  – D3 = {a1, a2}
1… 1  1	1	0  – D r–1 = A
1   1   1	1	1  – D r = C

2 Внутренность множества X – это множество всех объектов из Х, за исключением самого Х, см. подробнее в [3].

3 См. там же – [3].

• 1  1  1 …   1    1  – D r+1 ={a 1 , C}=C

1^… 1  1     1    1  — D s = C.

Поэтому количество разных подмножеств множества С определяется первыми r k–1 строками, количество их равно r = 2 –

1+1 = 2k–1. Доказана теорема.

Теорема 2. Для самопринадлежащего конечного множества С такого, что его внутренность V(C)=А несамопринадлежаща, А ∉ А, и состоит из единичных объектов, ∀ a, a ∈ A, |a| = 1, порядок множества его подмножеств Exp(C) равен |Exp(C)| = 2^k–1, где k=|C|. □

Очевидно, что если F=P(C)=P2(A) (см. условия теорем 1, 2), то |Exp(F)| = 2k–2 + 1, где k = |F|. Доказана теорема.

Теорема 3. Для самопринадлежащего конечного множества F такого, что его s-ая внутренность V^S(F)=А несамопринадлежаща, А ∉ А, и состоит из единичных объектов, ∀ a, a ∈ A, |a| = 1, порядок множества его подмножеств Exp(F) равен |Exp(F)| = 2^k–s+s–1, где k=|F|. □

Рассуждения о самопринадлежащих множествах более сложной структуры в общем случае довольно многообразны ввиду разнообразия структуры конечных самопри-надлежащих множеств. При сложности описания структуры конечных самопринадлежа-щих множеств в общем виде заключение о порядках множеств их подмножеств представляется очень громоздким. Однако алгоритм формирования подмножеств (с учетом теоремы о транзитивности принадлежности), показанный на примерах построения упорядоченного списка подмножеств (3), (6), пусть и с повторяющимися строками, относительно более прост. Посредством этого алгоритма представляется выполнимым калькулятор порядков самопринадлежащих множеств.

Для вычисления порядка множества подмножеств конечного самопринадлежащего множества требуется:

• а)    перенумеровать объекты, его составляющие,

• б)    построить множество двоичных слов, соответствующее теоретическим подмножествам,

• в)    пользуясь теоремой о транзитивности принадлежности, уточнить значения характеристической функции (подправить двоичные строки),

• г)    вычеркнуть повторяющиеся двоичные строки,

• д)    подсчитать количество оставшихся строк.

4.    Заключение

Это количество строк и будет порядком множества подмножеств исходного множества.

Описание реализации этого алгоритма – вне рамок этой статьи.

Теорема 1 о порядке множества подмножеств несамопринадлежащего множества, состоящего из единичных объектов, аналогична подобным теоремам из наивной и аксиоматической теорий множеств. Теоремы 2, 3 о порядке множества подмножеств определенного вида самопринадлежащих множеств весьма специфичны.

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