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

Размещено на http://www.allbest.ru/

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

В. Л. Чечулин

Пермский государственный университет, Россия, 614990, Пермь, ул. Букирева, 15

chechulinvl@mail.ru; (342) 2-396-424

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

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

On the orders of the sets of subsets of finite sets with selfconsidering

V. L. Chechulin

Perm State University, Russia, Perm, 614990, Bukirev st., 15

chechulinvl@mail.ru; (342) 2-396-424

Proved by applying the concept of characteristic functions of subsets, the theorem on the orders of a set of subsets of a finite set for two special cases: a) for a finite unselfconsidering set with simple structure and b) for selfconsidering set whose interior is the set of item a). The scheme of the overall algorithm for determining the order of the set of subsets of a finite set with selfconsidering.

Key words: finite set; he set of subsets; he characteristic function; elfconsidering; theorem on the transitivity of identity; he order of the set of subsets.

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

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

В. Л. Чечулин, 2011, относящиеся к несамопринадлежащим множествам и множествам с самопринадлежностью, обладающим относительно простой структурой.

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

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

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

А={a1, a2, a3,… , аn}. (1)

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

, (2)

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

Значения характеристической функции (2) дадим записью (1) под соответствующими объектами ai из А; строка записи соответствует подмножеству Bj и является некоторым двоичным числом. В этой записи упорядочим двоичные строки-числа, получим запись вида

А={a1, a2, a3,… , аn}

1 0 0 … 0 -- B1 = {a1}

0 1 0 … 0 -- B2= {a2}

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

…

1 1 1 1 -- Bm= A.

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

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

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

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

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

То же самое проделаем с характеристической функцией, построенной аналогично (2) для объектов из С и подмножеств Dj, Dj 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 - D2= {a2}

1 1 0 … 0 0 - D3 = {a1, a2}

…

1 1 1 1 0 - Dr-1= A

1 1 1 1 1 - Dr= C

1 1 1 … 1 1 - Dr+1 ={a1, C}=C

…

1 1 1 1 1 -- Ds= C.

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

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

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

Теорема 3. Для самопринадлежащего конечного множества F такого, что его s-ая внутренность VS(F)=А несамопринадлежаща, АА, и состоит из единичных объектов, a, aA, |a| = 1, порядок множества его подмножеств Exp(F) равен |Exp(F)| = 2k-s+s-1, где k=|F|. ?

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

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

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

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

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

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

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

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

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

множество порядок конечный простой

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

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

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

Список литературы

1. Френкель А., Бар-Хиллел И. Основания теории множеств / пер. с англ.; под. ред. А.С.Есенина-Вольпина. М.: Мир, 1966. 366 с.

2. Чечулин В.Л. О множествах с самопринадлежностью // Вестник Перм. ун-та. Сер. Ма-тематика. Механика. Информатика. Пермь, 2005. С.133-138. (реферат в РЖ Математика. 2006. №7, 7А48).

3. Чечулин В.Л. Об упорядоченных структурах в теории множеств с самопринадлежностью // Вестник Перм. ун-та. Сер. Математика. Механика. Информатика, 2008. С.37-45.

4. Chechulin V.L. About the selfconsidering semantic in the mathematical logic // Bull. Symbolic Logic. Issue 1 (2010). Vol.16. P.111-112

Размещено на Allbest.ru