Концептуальный анализ и проектирование Введение в аппарат ступеней и его применение Концепт Москва 2010 Серия «Концептуальный анализ и проектирование»


Раздел 1.3. Абстрактная теория ступеней



бет5/19
Дата16.07.2016
өлшемі1.91 Mb.
#202556
1   2   3   4   5   6   7   8   9   ...   19

Раздел 1.3. Абстрактная теория ступеней


Раздел представляет ряд работ разных авторов, которые так или иначе формулируют абстрактную теорию систем.

С. П. Никаноров кратко вводит читателя в теорию типов Б. Рассела, позволяющую понять особенности теорий ступеней как метатеории над ступенями.

Д. Б. Персиц в четырех работах представил: вариант абстрактной теории ступеней (без термов); теорию развития в абстрактной теории ступеней; эквивалентность родов структур (как в теории структур Н. Бурбаки, так и в метатеории ступеней); сводимость родов структур.

А. Ю. Иванов разработал вариант абстрактной теории ступеней, ориентированный на обеспечение теоретической поддержки рядов гомоморфных ступеней, который содержит 45 классов термов.

А. В. Тищенко показал, что шкалы множеств могут рассматриваться как алгебры, он также рассмотрел шкалы множеств без констант и шкалы множеств с константами, что является шагом в исследовании теоретико-модельных теорий ступеней.

А. В. Никитин предложил идею применения терм-функций к проблеме построения сложных ступеней на примере многоуровневого гиперграфа, важного для экспликации развития.

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

Теория типов Б. Рассела и аппарат ступеней


Согласно Большому энциклопедическому словарю (изд. Б. Росс. энц., изд. 2, 2002, с. 997) Бертран Рассел (1872 — 1970) — английский философ, логик, математик, общественный деятель. Основоположник английского неореализма и неопозитивизма. Развил дедуктивно-аксиоматическое построение логики в целях логического обоснования математики. Автор (совместно с А. Уайтхедом) основополагающего труда по математической логике — «Основания математики» в 3-х томах, 1913 г. Один из инициаторов Пагуошского движения. Нобелевский лауреат по литературе 1950 г.

В ходе освоения теории множеств, открытой и разработанной Георгом Кантором (1845 — 1918), выяснились так называемые «парадоксы теории множеств». Один из таких парадоксов, замеченный Б. Расселом, называется «каталог всех каталогов». Принадлежит ли каталог всех каталогов к множеству каталогов? Если принадлежит, то он не является каталогом всех каталогов. Если же не принадлежит, то он не является каталогом. Для разрешения этого противоречия Б. Рассел предложил «теорию типов множеств». Его идея состояла в предположении существования множества типов множеств, причем множество одного типа не имеет ни одного элемента, который бы принадлежал множеству какого-либо иного типа. Множества разных типов полностью изолированы друг от друга, они не пересекаются.

Заметим, что в этом предположении Б. Рассела скрыто принимается отсутствие одной-единственной предельной абстракции, например, «всё материально». Заметим также, что иллюстрация парадокса опирается на нечисловой пример…

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

Решить задачу различения множеств можно разными способами. Например, с помощью хорошо сформулированного соглашения, нормирующего семантику слова «множество» при его применении как 1-го типа или как 2-го типа. Смысл этого слова в таком случае определяется операциональным контекстом. Можно также условиться, что ступени — это предметы, хорошо известные, их теоретико-множественная природа игнорируется. Но можно, сохраняя для 1-го типа множеств (для базисных множеств) термин «множество», для 2-го типа — множества ступеней (как его производных), принять термин «многество». В результате возникнут термины «многество базисных множеств», «многество подмножеств ступеней», «булеан на подмногестве ступеней трех смежных шкал множеств».

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

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

Различение касается и обозначений множеств. Например, множества — латинскими буквами, а многества — греческими.


Абстрактная теория ступеней4

Статус настоящей работы


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

Используемые обозначения


Род структуры обозначается буквой W с индексом и, если необходимо, указанием в скобках обозначений базисных множеств и отделенных от них точкой с запятой родовой структуры, возможно, с типизацией (т.е. ступенью). Аксиома, определение (внутренний терм) и теорема обозначаются, соответственно, буквами A, D, T с индексами. Комментарии к ним даются в круглых скобках и предваряются буквой К с точкой. В остальном обозначения стандартные.

1. Род структуры схемы конструкции ограниченной шкалы множеств


W1 = W1(V, R; w), w  B(R  V  V)  B(R  R).

(K. V — множество вершин, а R — множество стрелок ориентированного мультиграфа, играющего роль схемы конструкции ограниченной шкалы множеств. Термин «ограниченной» означает конечность трех множеств: V, R, X, где Х — объединение ступеней, фигурирующее в следующем пункте).

А1. V .

А2. card V  .

A3. card R  .

D1. g = pr1(w).

D2. l = pr2(w).

A4. g : R → V  V.

D3. gi = pri g (i = 1, 2).

(К. gi : R → V; g1 сопоставляет каждой стрелке начальную вершину, а g2 — конечную).

D4. b : V → B(R), где b(v) = r  Rv = g1(r).

(К. Можно сказать, что b = g1-1; b(v) — множество стрелок, исходящих из вершины v).

D5. e : V → B(R), где e(v) = r  R  v = g2(r).

(К. Можно сказать, что e = g2-1; e(v) — множество стрелок, входящих в вершину v).

D6. Vb = V \ g2(R).

(К. Множество начальных вершин мультиграфа).

D7. Ve = V\ g1(R).

(К. Множество конечных вершин мультиграфа).

D8. P = ., где

Pn = R при n = 1; Pn = (r1, … rn)  Rn  g2(ri) = g1(ri + 1), i = 1, …, n — 1) при n  1.

(К. Множество ориентированных путей; при длине пути больше 1 как последовательностей стрелок таких, что конечная вершина каждой стрелки, кроме последней, совпадает с начальной вершиной последующей стрелки, само множество стрелок объявляется как множество путей длины 1).

D9. vb : P→ V, где vb(p) = g1(p) при n = 1; vb(p) =l \ g1(r1) при n  1.

(К. Сопоставление пути его начальной вершины).

D10. ve : P→ V, где ve(p) = g2(p) при n = 1; ve(p) = g2(rn) при n  1.

(К. Сопоставление пути его конечной вершины).

D11. Pc = p  Pvb(p) = ve(p).

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

А5. Pc .

(К. мультиграф циклов не имеет).

(К. Таким образом, на обычном математическом языке схема конструкции ступени ограниченной шкалы множеств — это ориентированный мультиграф без ориентированных циклов с конечным непустым множеством вершин и с конечным (но, возможно, пустым) множеством стрелок, причем множество стрелок, входящих в одну вершину, линейно упорядочено, если оно непусто (см. ниже аксиому А6)).

Т1. Vb   Ve .

(К. множества начальных и конечных вершин непусты).

А6. v  V \ Vb : (e(v)  e(v))  l — линейный порядок на е(v).

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

А7. l =  ((e(v)  e(v))  l).

v  V \ Vb.

(К. Стрелки, входящие в разные вершины, не сравнимы, т.е. не находятся между собой в отношении l).

D12.  = l.

(К. r1  r2  (r1, r2)  l).

D13. V = g1(r)  g2(r).

(К. Множество стрелочных вершин мультиграфа).

D14. Vc = V \ V.

(К. Множество изолированных вершин мультиграфа).

Т2. card P  .

(К. Множество путей конечно).

Т3. P   => (  n  N : Pn     k  N : Pn+k = ).

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

D15. ret: g2(R) B(V)  B(R)  B(R  V  V)  B(R  R), где

ret(v0) = (V(v0), R(v0), w(v0)), где

V(v0) = g1(R(v0))  g2(R(v0)),

R(v0) = r  R   p  P : ve(p) = v0   i  N : r = pri(p),

w(v0) = (g  B(R(v0)  V(v0)  V(v0)), lB(R(v0)  R(v0)).

(К. Ретроспектива вершины есть «подграф» мультиграфа с множествами вершин и стрелок, лежащих на путях, оканчивающихся в ней, и с индуцированными линейными порядками).

T4. w(v0)  B(R(v0)  V(v0) V(v0))  B(R(v0)  R(v0)).



2. Род структуры ограниченной шкалы множеств

W2 = W2(X, V, R, c),

c  B(R  V  V)  B(R  R)  B(V  B(X)).

D1. w = pr1,2(c).

D2. f = pr3(c).

A1. (V, R, w) = W1(V, R; w).

(К. Род структуры схемы конструкции ограниченной шкалы множеств).

A2. f : V  B(X)  = X.

(К. Х-объединение ступеней, сопоставляемых вершинам с помощью отображения f).

D3.  v  g2(R) : v = card e(v).

A3.  v  g2(R) : v = 1  f(v) = B(g1()), где

— единственный элемент множества e(v).

(К. Если в вершину входит одна стрелка, то ей сопоставляется булеан множества, соответствующего началу стрелки (отображением f)).

A4.  v  g2(R) : v  1  f(v) = f(v1)  …  f(vv), где

i  j  ri  rj, если g(ri) = (vi, v) (i, j = 1, …, v).

(К. Если в вершину входит больше одной стрелки, то ей сопоставляется прямое произведение множеств, сопоставляемых начальным вершинам стрелок, взятом в том порядке, в котором эти стрелки упорядочены согласно отношению f (cм. D2(W1) и D12(W1))).

D4. Xb = f(Vb).

(К. Система базисных множеств шкалы).

D5. Xe = f(Ve).

(К. Система конечных ступеней шкалы).

T1. card Xb  .

T2. card Xe  .

3. Род структуры схемы конструкции собственной ступени


W3 получается из W1 операцией усиления одной аксиомой

А1. card Ve = 1.

(К. Схема конструкции собственной ступени есть схема конструкции ограниченной шкалы множеств с одной конечной вершиной).

D1. ve = , т.е. Ve =ve.

Т1. card V = 1  (V, R, W) = ret(ve)

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

Т2. V  1  V = g1(R)  g2(R)

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


4. Род структуры собственной ступени над множествами


W4 =W4(X, V, R; с).

W4 есть W2, в который добавлена аксиома А1(W3).

(К. Собственная ступень есть шкала со схемой конструкции собственной ступени, т.е. с одной конечной вершиной или ступенью).

5. Род структуры нетривиальной ступени над множествами


W5=W5(X, V, R; с).

W5 получается из W2 добавлением аксиомы

А1. g1(R)  g2(R) = V.

(К. W5 эквивалентно W4 с дополнительной аксиомой card V  1).


6. Род структуры тривиальной ступени над множествами


W6=W6(X, V, c), c  ( B(V  B(X))  V).

D1. f = pr1(c).

A1. f : V  B(X).

(К. Сопоставление вершинам тривиального (т.е. без стрелок) мультиграфа базисных множеств).

D2. v0=pr2(c).

D3. X0=f(v0).

(К. Тривиальная ступень над базисными множествами как одно из базисных множеств).

(К. W6 эквивалентно W2 с дополнительной аксиомой R = ).


Операции над оснащенными шкалами множеств


Шкала, рассматриваемая вместе с дополнительной информацией, называется оснащенной шкалой.

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

Свободное произведение: непересекающимся образом объединяются как множества вершин, так и множества стрелок.

Смешанное произведение оснащенных шкал: как множества вершин, так и множества стрелок объединяются заданным пересекающимся образом.

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

Структурные уравнения


Пусть Ор — символ одной из четырех вышеуказанных операций и S, S1, S2 — конкретные оснащенные ограниченные шкалы, а Х — искомая оснащенная ограниченная шкала. Тогда выражения

Ор(S1, X) = S , Op(X, S2) = S

называются простыми структурными уравнениями. Если слева стоит суперпозиция операций от одного неизвестного, то уравнение называется составным.

Возникает естественная проблема определения условий существования и единственности решений структурных уравнений.


Теория развития в абстрактной теории ступеней5

1. Каркас конструкта «развитие»


Понятие «каркас конструкта развитие» в терминах Теории структур Н. Бурбаки соответствует понятию «схема конструкции ступени».

Каркас конструкта «развитие» представляется ориентированным графом

W1 = W1 (V, w1, S1).

Типизация (ступень метатеории)

w1  S1 = B(V  V).

V — множество вершин ориентированного графа W1 без циклов и петель.

w1 — множество дуг графа W1.

D1. b : w1  V, где b = pr1, т.е. d  w1 : b(d) = pr1d.

d — упорядоченная пара вершин графа W1.

Комментарий

Сопоставление дуге графа W1 начальной вершины дуги.

D2. e : w1  V, где e = pr2, т.е. d  w1 : е(d) = pr2d.

Комментарий

Сопоставление дуге графа конечной вершины дуги.

D3. , где

Pn = (v0, …, vn) Vn+1  i  Zn: (vi, vi+1)  w1 (Z+={0,1,2…}, Zn = {0,1,…, n-1}.



Комментарий

P — множество путей графа W1,

Pn — множество путей графа W1 длины n.

D4. gb : P  V, где

gb(v0, …, vn) = V0.

Комментарий

Сопоставление пути графа W1 начальной вершине этого пути.

D5. ge : P  V, где

ge(v0, …, vn) = vn.



Комментарий

Сопоставление пути графа W1 конечной вершине этого пути.

D6. C = p  P  gb(p) = ge(p).

Комментарий

Множество циклов (в том числе, петель) графа W1.

А1. С = .

Комментарий

В графе W1 циклы отсутствуют.

А2. 1  Card V  .

Комментарий

Множество вершин графа W1 конечно и не пусто.

Теорема 1

Card P  .



Комментарий

Множество путей графа W1 конечно.


2. Множество структур рода структуры W1 (булеанизация рода структуры W1)


Пусть W1 = W11, …, Хn; w1, S1) — род структуры.

Булеаном рода структуры W1 называется род структуры W2 = BW1.

W2 = W2 (X0, X1, … Xn; w2, S2), где

S2 = B(X0BX1)  …  B(X0BXn)  B(X0  S1).

A1. i = 1, …, n : (priw2 : X0BXi).

Комментарий

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

A2. prn+1 w2 : X0  S2.

Комментарий

Последняя (n + 1)-ая проекция родовой структуры W2 есть отображение множества X0 (см. комментарий к аксиоме А1) в множество ступеней, соответствующих схеме конструкции ступени структуры рода W1.

А3. х0  X0 : W1(pr1w2 (X0), …, prnw2(X0); prn+1 w2(X0); S1(pr1w2 (X0), …, prnw2(X0))).
Комментарий

Для каждого элемента промножества Х0 соответствующий набор базисных множеств и типизаций образует структуру рода W1.


3. Род структуры абстрактного развития.


Напомним, что W4- род структуры собственной ступени и BW4 - его булеан:

BW4= BW4 (X0, X1, X2, X3; c).

Род структуры абстрактного развития

W3.1= W3.1 (V, X0, X1, X2, X3; d; D),

где D=S(W1) x S(BW4) x B(V x BX0),

где W1 — род структуры каркаса развития,
A1. W1 (V; pr1 d)  BW4 (X0, X1, X2, X3; pr3 d)  pr3 d: VBX0.

Комментарий

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


Эквивалентность родов структур6


Определение 1.1

Пусть даны два рода структуры W1 и W2. Отображение множества, состоящего из базисных множеств и родовой структуры рода W1 в множество внутренних термов рода структуры W2 называется «погружением рода структуры W1 в род структуры W2», если образы правильно переформулированных аксиом и типизаций рода структуры W1 в терминах рода структуры W2 являются теоремами теории рода структур W2.



Теорема 1.1.

Пусть f: W1 W2 - погружение. Тогда ограничение любой структуры рода W2 на образ Im (f) отображения f (или, что то же, на образ рода структуры W1 при погружении f) является структурой рода W1.

Таким образом, возникает отображение класса структур рода W2 в класс структур рода W1, обозначаемого через rf.

Если класс структур рода W обозначить через CW, то теорему 1.1 можно переформулировать так:

Погружение f: W1 W2 индуцирует отображение ограничения rf: CW2 CW1.

Определение 1.2

Два рода структур называются эквивалентными, если существуют погружения

f: W1 W2 и g: W2 W1 такие, что любая структура с1  СW1 изоморфна структуре

rf rg1), и любая структура с2  СW2 изоморфна структуре rg rf2).



Теорема 1.2

Если W1 и W2 - эквивалентны, то отображения rf и rg являются эпиморфизмами с точностью до изоморфизма структур, а именно, для любой структуры c1 СW1 найдется изоморфная ей структура (а именно, rf rg1)), которая является образом отображения rf и аналогично для rg .

Теорема 1.2 показывает, что выразительные средства эквивалентных родов структур одинаковы.

Можно обосновать и обратные утверждения: если выразительные средства двух родов структур одинаковы, то они (роды структур) эквивалентны.



Комментарий

Эквивалентность родов структур в смысле Н. Бурбаки (см. Бурбаки Н. Теория множеств) является частным случаем сформулированного выше определения 1.2 эквивалентности. А именно:



Теорема 1.3

Любые два рода структур, эквивалентные в смысле Н. Бурбаки, эквивалентны также в смысле определения 1.2.



Теорема 1.4

Существуют два рода структур, эквивалентные в смысле определения 1.2, но не эквивалентные в смысле Н. Бурбаки.

Доказательство.

В качестве примера можно взять разбиение множества на непересекающиеся подмножества (первый род структуры) и сюръекцию (второй род структуры).


Сводимость родов структур7


Определение 2.1

Род структуры W1 называется «сводимым к роду структуры W2», если они эквивалентны, и род структуры W2 имеет меньшее количество базисных множеств.



Определение 2.2

Род структуры W1 называется «предельно сводимым к роду структуры W2», если рода структур W1 и W2 эквивалентны в смысле определения 1.2, и, кроме того, род структуры W1 имеет более одного основного базисного множества, а род структуры W2 имеет одно основное базисное множество и не более одного вспомогательного базисного множества.



Теорема 2.1

Любой род структуры предельно сводим.

Иными словами, для любого рода структуры W1 существует такой род структуры W2, к которому W1 сводим.

Доказательство.

Следует взять непересекающееся объединение основных базисных множеств и кортеж вспомогательных.

Теория ступеней8

Аксиоматика


Х – множество предступеней (ступенью становится при вхождении в какую-либо шкалу множеств — если допускать наличие ступеней, не входящих в шкалы множеств)

Y – множество меток (техническое множество, необходимое для различения положения множества при его многократном вхождении в декартово произведение)

D Є B(X * B(X * Y)) — отношение непосредственного образования ступеней или множество «разверток» (для многих шкал множеств добавляется второй булеан)

Ax1 Связность (наличие всеохватной первой шкалы?)

Ax2 Отсутствие циклов и петель

Ax3 Единственность развертки в обе стороны

Ах4 Существуют любые развертки, не приводящие к циклам (?)

Термы по типам ступеней


  1. Исходные ступени (pr2=Ǿ)

  2. Ступени, непосредственно образованные операцией взятия булеана (вторая проекция состоит из одного элемента)

  3. Ступени, непосредственно образованные операцией декартиана (вторая проекция состоит более чем из одного элемента)

  4. Декартианы на одном множестве (т.е. первые проекции элементов второй проекции развертки совпадают)

  5. Декартианы с неоднократным вхождением одного множества (т.е. у некоторых элементов второй проекции развертки совпадают первые проекции)

Термы о цепочках вывода ступеней и месте ступеней в цепочке


  1. Цепочки вывода ступеней

  2. Начальные ступени данной цепочки вывода

  3. Конечные ступени данной цепочки вывода

  4. Промежуточные ступени данной цепочки вывода

Термы о деревьях вывода ступеней и месте ступеней в дереве вывода


Т10 Деревья вывода, т.е. связное множество разверток, образующих множество цепочек вывода с одинаковой конечной ступенью, таких, что между начальными ступенями разных цепочек нет цепочек вывода, не вошедших в данное дерево вывода (?)

Т11 Начальные ступени данного дерева вывода

Т12 Промежуточные ступени данного дерева вывода

Т13 Все деревья вывода данной ступени


Термы о шкалах множеств и месте ступеней в шкале


Т14 Шкалы множеств, т.е. связанный развертками набор ступеней, такой, что для любой ступени набора существует дерево вывода, «принадлежащее набору» (т.е. все ступени которого принадлежат этому набору), такое, что это — дерево вывода этой ступени или эта ступень — начальная ступень в этом дереве; и между начальными ступенями любых деревьев, принадлежащих набору, нет цепочек вывода

Т15 Базисные множества данной шкалы множеств

Т16 Выводимые в данной шкале ступени

Т17 Невыводимые в данной шкале ступени

Т18 Конечные ступени в данной шкале

Т19 Промежуточные ступени в данной шкале


Термы о типах шкал множеств по количеству базисных множеств


Т20 Шкалы множеств на данных базисных множествах, т.е. связанные развертками наборы ступеней, такие, что для любой ступени набора, не являющейся каким-либо из заданных базисных множеств, существует дерево вывода этой ступени, такое, что все его ступени принадлежат набору, а все его начальные ступени являются базисными множествами; и для любого базисного множества существует дерево вывода, принадлежащее набору, начальной ступенью которого является это базисное множество

Т21 Первые шкалы, т.е. шкалы множеств с единственным базисным множеством

Т22 Парето-множество первых шкал, т.е. ни одна из шкал не является подмножеством другой шкалы

Т23 Вторые шкалы, т.е. шкалы множеств имеющих базисное множество, совпадающее с базисным множеством какой-либо из первых шкал, и еще одно базисное множество

Т24 Множество парето-множеств шкал с одинаковым числом ступеней (через взаимно-однозначное соответствие)

Термы о деревьях вывода ступеней в шкалах множеств и рангах ступеней


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

Т26 Ступени 1-го ранга данной шкалы, т.е. образованные из базисных множеств шкалы

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

Т28 Множество наборов равноранговых ступеней в данной шкале множеств (через взаимно-однозначное соответствие)


Термы о подшкалах данной шкалы множеств и сложности подшкал


Т29 Множество всех подшкал данной шкалы, т.е. шкал множеств, являющихся подмножеством данной шкалы и имеющих базисные множества, являющиеся базисными множества данной шкалы

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

Т31 Наборы ступеней «равной сложности» в данной шкале (с равным числом разверток в дереве вывода)

Т32 Подшкала данной сложности данной шкалы множеств, т.е. часть данной шкалы, образованная оставлением ступеней данной сложности и промежуточных для них ступеней


Термы о сравнении шкал множеств (парах шкал)


Т33 Пары шкал, отличающиеся переопределением базисных множеств

Т34 Пары шкал, отличающиеся увеличением базисных множеств

Т35 Пары шкал, отличающиеся уменьшением базисных множеств

Т36 Пары шкал, отличающиеся выводом дополнительных ступеней


Термы о соотношении деревьев вывода


Т37 Множество деревьев вывода, «включающих данное», т.е. деревьев вывода той же ступени, что и данное дерево, и для которых данное дерево является подмножеством

Т38 Множество деревьев вывода, входящих в данное


Термы о типах изоморфных ступеней


Т39 Наборы декартианно-изоморфных ступеней, т.е. наборы ступеней, образованных декартовым произведением одинакового числа ступеней, сопоставленных одним и тем же меткам; в случае если ступени, входящие в один из декартианов набора совпадают, у всех других декартианов набора совпадают ступени, приписанные тем же меткам, что и ступени в указанном декартиане

Т40 Наборы булеанно-изоморфных ступеней, т.е. наборы ступеней, образованных одинаковым числом операций взятия булеана

Т41 Наборы непосредственно изоморфных ступеней

Термы об изоморфных деревьях вывода ступеней


Т42 Множество наборов равноранговых ступеней («рангов») в данном дереве вывода

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

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

Термы о гомоморфных ступенях


Т44 Ступени, изоморфные данной ступени в данной шкале, т.е. ступени, для которых существует шкала множеств, в которой выражение этой ступени изоморфно выражению заданной ступени в заданной шкале

Т45 Ступени, гомоморфные данной ступени в данной шкале, т.е. ступени, дерево вывода которых включает дерево вывода какой-либо ступени, изоморфной заданной ступени


Шкалы множеств и теории родов структур9


Работа посвящена теоретическим и математическим вопросам, возникающим при работе с концептуальными схемами, а именно, при исследовании шкал множеств, которые введены Н. Бурбаки в монографии «Теория множеств» в разделе «Теория структур». Предложено шкалу множеств рассматривать как алгебру с одной унарной и одной бинарной операцией. Доказаны две теоремы, которые показывают, как соотносятся между собой две различные шкалы множеств, если базисные множества одной из них отображаются в некоторые ступени другой шкалы.

1. Введение


В известном Трактате Н. Бурбаки была предпринята попытка дать изложение всей математики в целом на едином основании — теории множеств. В первой книге [1] этого Трактата построена теория родов структур, которая является общей схемой, в рамки которой укладывается любая аксиоматическая математическая теория, построенная на основе теории множеств. В настоящее время математики вполне осознали, что математическое знание не формализуется полностью (см. [1, с. 10-11], [2, с. 64]). Эта мысль также подробно обсуждается Г. Вейлем [3]. Теория родов структур, которая пока математиками практически не разрабатывается и не используется, тем не менее, послужила важной базой для приложений в различных нематематических областях науки [4, 5, 6, 7, 8]. При всех различиях областей этих приложений, авторы сходятся в одном: язык родов структур удобен для описания теорий различных предметных областей. В данном документе даны ответы на вопросы, поставленные С. П. Никаноровым и относящиеся к теории родов структур. Эти вопросы следующие.

  1. Что за объект шкала множеств над данным базисом? Как его удобно представлять?

  2. Как соотносятся между собой шкалы множеств, если их базисы вложены друг в друга?

  3. Как соотносятся между собой шкалы множеств, если базисные множества одной из шкал отображаются в некоторые ступени другой шкалы?

Отметим, что вопрос 2) является частным случаем вопроса 3). Предполагается, что читатель владеет теорией родов структур в объеме [1].

2. Шкала множеств как алгебра


Понятие шкалы множеств было введено в [1]. Пусть X1, ..., Xn — (основные) базисные множества, а C1, ..., Cm — константы, т.е. вспомогательные базисные множества в терминологии [1].

Определение 1. Совокупность Bas = {X1, ..., Xn; C1, ..., Cm} базисных множеств и констант назовем базисом множеств.

С помощью операции взятия булеана данного множества В(Bas) и декартиана двух множеств из базисных множеств и констант можно получить новые множества, которые называются ступенями над данным базисом. Более точное определение ступени можно дать с помощью индукции. А именно, пусть символы B и P обозначают операции булеана декартиана двух аргументов, соответственно.

Определение 2. Всякое базисное множество и всякое константное множество есть ступень веса 1. Если K1 — ступень веса n-1 над базисом множеств Bas, то B(K1) — ступень веса n над базисом Bas. Если К1 и К2 — ступени над базисом множеств Bas веса не более, чем n-1, причем, одна из них имеет вес в точности n–1, то Р(К1, К2) — ступень веса n над базисом Bas. Множество всех ступеней над данным базисом Bas называется шкалой множеств над базисом Bas и обозначается ScBas.

Например, если Bas1 = {X1, X2; C1}, где C1 — множество натуральных чисел, то B(X1), B(P(X1, C1)), P(P(X1, X2), C1) — элементы шкалы множеств ScBas1.

Нетрудно видеть, что шкалу множеств над данным базисом Bas можно рассматривать как универсальную алгебру с двумя операциями — унарной операцией B и бинарной операцией P, с конечным множеством образующих {X1, ..., Xn; C1, ..., Cm}. При этом алгебра ScBas не удовлетворяет никаким тождествам. В частности, P(P(X1, X2), C1) и P(X1, P(X2,C1)) — различные элементы шкалы множеств над Bas.


3. Шкалы множеств без констант


Рассмотрим важный частный случай, который часто встречается в математической прикладной деятельности, а именно, когда базис множеств Bas1 состоит только из базисных множеств и не содержит констант. В этом случае шкала множеств ScBas1 является алгеброй -слов, где  = {B, P}, с n образующими. Согласно [9 теорема 2.6], ScBas — свободная алгебра ранга n свободных образующих. При этом в роли множества свободных образующих выступает базис множеств Bas1. В силу свойства свободных алгебр любое отображение g множества Bas1 свободных образующих в произвольную -алгебру A можно единственным образом продолжить до гомоморфизма g`: ScBas1  A. В частности, если в качестве А взять другую шкалу множеств ScBas2, то справедлива следующая

Теорема 1. Любая шкала множеств ScBas1 над базисным множеством без констант Bas1 = {X1, ..., Xn} является свободной -алгеброй, где  = {B, P}, ранга n. Следовательно, любое отображение g: Bas1  ScBas2 единственным образом продолжается до гомоморфизма g`: ScBas1  ScBas2 -алгебр.

Непосредственно из теоремы 1 вытекает ответ на поставленные во введении вопросы 2 и 3 в нашем важном частном случае.

Следствие 2. Если имеется отображение g: Bas1  ScBas2, то алгебра шкалы множеств ScBas2 содержит гомоморфный образ алгебры шкалы множеств ScBas1. В частности, если g тождественно вкладывает Bas1 в Bas2, то ScBas2 содержит алгебру шкалы множеств ScBas1 как подалгебру.


4. Шкалы множеств с константами


Если базис шкалы множеств Bas1 содержит константы, то алгебра ScBas1 уже не является свободной. В самом деле, если Bas1 = {X1, ..., Xn; C1} и Bas2 = {X1, ..., Xn, X(n+1)}, то отображение g(X1) = Xi (i = 1, ..., n) g(C1) = X(n+1) нельзя продолжить до гомоморфизма. Действительно, если C1 — множество натуральных чисел, то в качестве X(n+1) можно взять множество мощности континуума. Тогда замена C1 на X(n+1) не является эквивалентной. Этот факт показывает следующее определение.

Определение 3. Отображение g: Bas1  ScBas2 назовем допустимым, если все константы Bas1 содержатся в Bas2 и g тождественно действует на константах.

Теорема 3. Любое допустимое отображение g: Bas1  ScBas2 единственным образом продолжается до гомоморфизма g`: ScBas1  ScBas2.

Доказательство. Определим отображение g`, полагая g` = g на Bas1, и далее g`B(K1)) = B(g(K1)), g`(P(K1,K2)) = P(g`(K1), g`(K2)). Таким образом, так как любая ступень есть либо базисное множество, либо константа, либо имеет вид B(K1), либо имеет вид P(K1, K2), и такое представление однозначно, то g` определено для всех ступеней из ScBas1. Корректность определения и однозначность g` легко следует по индукции из определения g`. Тот факт, что g` является гомоморфизмом, следует непосредственно из определений.


Идея применения терм-функций к проблеме построения сложных ступеней на примере многоуровнего гиперграфа10


Имеется построение понятия "многоуровневый гиперграф", путем последовательной замены вершин графа на граф предыдущего уровня. Получаемые объекты последовательно принадлежат ступеням:

B(X1*X1)

B(B(X1*X1)*B(X1*X1))

B(B(B(X1*X1)*B(X1*X1))*B(B(X1*X1)*B(X1*X1)))

И т.д.
Однако класс ступеней, равно как и квалификация этих ступеней представляет определенные трудности.

Предлагается определить следующую терм-функцию:
TF(A) = (B(A)*B(A)), при этом область значений функции включена в область определения, а единственный элемент области определения, который не принадлежит области значений, равен X.
Тогда мы имеем автофункцию, порождающую ступени многоуровневого гиперграфа.
Введем обозначение TF(TF(…TF(X))) — автофункция k-ого порядка, и будем обозначать её TFk(X)
Очевидно, что TFm(TFn(X)) = TFm+n(X).
Поскольку термфункция определена не только как правило синтаксической подстановки знаков, то задание этой термфункции полностью определяет такое понятие, как многоуровневые гиперграфы, поскольку область значений функции совпадает с множеством многоуровневых гиперграфов.

Литература


  1. Бурбаки Н. Теория множеств. — М.: Мир, 1965.

  2. Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.

  3. Вейль Г. Феликс Клейн и его место в математической современности. В кн.: Г. Вейль. Математическое мышление. — М.: Наука, 1989. — с. 256-270.

  4. Никаноров С. П. Концептуальное проектирование организаций как средство решения проблемы управляемости. Труды ЦНИПИАСС. Вып. 17. — М., Госстрой СССР, ЦНИПИАСС, 1977. — с. 12-19.

  5. Персиц Д. Б., Савелов Е. В., Тищенко А. В. Теоретические основы построения автоматизированной системы проектирования систем организационного управления. Труды ЦНИПИАСС. Вып. 17. — М., Госстрой СССР, ЦНИПИАСС, 1977. — с. 20-29.

  6. Никаноров С. П. Характеристика и область применения метода концептуального проектирования систем организационного управления. В сб.: Концептуальное проектирование систем организационного управления (КП СОУ) и его применение в капитальном строительстве. — М., Госстрой СССР, ЦНИИЭУС, 1989. — с. 8-29.

  7. Павловский Ю. Н. Теория факторизации и декомпозиции управляемых динамических систем и ее применение. Изв. АН СССР. Техн. кибернетика. 1984, № 2. — с. 45-57.

  8. Balzer W., Moulenes C. U., Sneed J. D. Architectonic for science (The structuralist program). Synthese library. Vol. 186, 1987.

  9. Кон П. Универсальная алгебра. — М.: Мир, 1968.



Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   19




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет