Электронный Научно - Информационный Журнал Системное Управление. Проблемы и Решения
 

Об эквивалентной представимости рода структуры с помощью заданной типовой характеристики

Выпуск 10 Тестовый

Пономарев

Аннотация

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

Содержание

 

1 Введение. Постановка задачи

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

Будем говорить, что род структуры ?  эквивалентно представим с помощью типовой характеристики d ? S [x1, ...xn]  , если имеется род структуры, эквивалентный ?  , с типовой характеристикой d ? S [x1,...xn]  .

Известно, что даже самые примитивные конструкты эквивалентно представимы внешне разными типовыми характеристиками. Например, даже при определении рода структуры отображения из x1   в x2   выбор типовой характеристики d ? P(x1 ? x2)  , а не, скажем, d ? P (x2 ? x1)  , есть дело только лишь традиции. Этот пример тривиален, но есть и более интересные (см. [1, с. 220]):

  • род структуры разбиения множества на типовой характеристике d ? P P (x)  эквивалентен роду структуры эквивалентности на типовой характеристике d ? P (x ?  x)  ;
  • род структуры топологического пространства может быть с точностью до эквивалентности родов структур определён как на характеристике d ? P P (x )  (множество открытых множеств пространства), так и на характеристике d ? P (P(x ) ? P (x))  (операция замыкания множества);
  • род структуры решётки может быть определён как на отношении порядка d ? P (x ? x)  , так и с помощью пары алгебраических операции ? и ? , задаваемых характеристикой d ? P ((x ? x) ? x) ? P((x ? x ) ? x)  .

Хотя один и тот же конструкт и может быть описан с помощью совершенно разных ступеней, неверно, что всякий конструкт может быть описан всякой ступенью. Например, интуитивно кажется ясным, что для рода структуры разбиения множества (на классы эквивалентности) нельзя указать эквивалентный род структуры с типовой характеристикой d ? x  или d ? P (x)  — эти характеристики кажутся «слишком примитивными» для конструкта «разбиение множества». Далее будет доказано, что это действительно так, и будут рассмотрены некоторые общие условия, позволяющие доказывать несуществование способов представления родов структур, эквивалентных заданным, на заданной типовой характеристике.

Заметим, что практический интерес представляет разговор именно о возможности или невозможности представления заданной типовой характеристикой лишь некоторого конструкта, ещё ранее представленного с помощью какой-либо типовой характеристики, поскольку с формальной точки зрения ступень сама по себе ни в коей мере не является фактором, определяющим класс типовых характеристик родов структур, эквивалетных родам структур, которые с её помощью можно построить. Действительно, справедливо следующее утверждение: для любой пары схем конструкций ступеней S
 1   и S
 2   на не более чем n  множествах могут быть построены два рода структуры ?1   и ?2   такие, что d?1 ? S1[x1,...xn]  и d?2 ? S2 [x1,...xn ]  есть, соответственно, типовые характеристики ?1   и ?2   , а ?1   и ?2   эквивалентны. В самом деле: пусть ?1   содержит базисные множества x1, ...xn  , типовую характеристику d?  ? S1 [x1,...xn ]
   1  и аксиому d ? =  ?
   1  . Пусть ?2   содержит те же базисные множества, типовую характеристику d?2 ? S2[x1,...xn ]  и аксиому d ?2 = ?  . ?1   и ?2   эквивалентны.

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

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

 

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

Напомним определение эквивалентности родов структур ([1, с. 220], [2], [3]).

Пусть дан род структуры ?  на n  базисных множествах x ,...x
 1     n  с типовой характеристикой T?   вида d? ? S ?[x1, ...xn]  и аксиомой R ?   . Пусть также дан род структуры ?  , который построен на базисных множествах xn+1   ,…xn+m  , с типовой характеристикой T?   вида d? ? S ?[xn+1,...xn+m ]  и аксиомой R ?   .

Терм (?1,...?m, ?)  называется способом вывода структуры рода ?  из структуры рода ?  , если он

 

  1. биективно переносим при типизации T?   ;
  2. не содержит никаких параметров, кроме, возможно, x1,...xn, d?   ;
  3. соотношение (?  | x   )...(?   | x   )(? | d )(T  & R  )
  1   n+1       m   n+m       ?    ?     ?  является теоремой ?  .

Всякий терм, удовлетворяющий первым двум из перечисленных условий, называется внутренним термом ?  .

Если дан ?  -объект (?1,...?n,?)  и способ вывода (?1,...?m, ? )/upload/images/images/  структуры рода ?  из структуры рода ?  , то, очевидно, терм

(?1 | x1) ...(?n | xn)(? | d?)(?1,...?m, ? )

будет являться ?  -объектом. Мы будем говорить, что ?  -объект рассматриваемого вида является подчинённым ?  -объекту (?1,...?n,?)  посредством способа вывода (?1,...?m, ? )  .

Если имеется способ вывода ?  из ?  , то для всякой теоремы B  рода структуры ?  формула (?1 | xn+1 )...(?m | xn+m )(? | d?)B  будет, как легко убедиться, теоремой рода структуры ?  .

Пусть ?  и ?   — два рода структуры с родовыми константами d?   и d?   , удовлетворяющие следующим условиям:

 

  1. ?  и ?  имеют одни и те же базисные множества x1,...xn  ;
  2. имеются способ вывода (x1, ...xn,?)  ?  из ?  и способ вывода (x1,...xn, ?)  ?  из ?  ;
  3. соотношение ?(?(d? )) = d ?   является теоремой ?  и соотношение ? (?(d?)) = d?   является теоремой ?  .

В этом случае говорят, что роды структур ?  и ?  эквивалентны посредством способов вывода (x ,...x  ,?)
  1      n  и (x  ,...x ,?)
   1     n  .

 

3 Первое необходимое условие эквивалентной представимости

Пусть терм ? ?(x1,...xn)  представляет собой множество возможных родовых констант рода структуры ?  с аксиомой R
  ?   при фиксированных базисных множествах, т. е.

?   = {d ? S  [x ,...x ] | R (x ,...x ,d)}.
  ?          ?  1     n    ?   1     n

Аналогично определим ? ?(x1,...xn )   — множество возможных родовых констант рода структуры ?  с аксиомой R?   при фиксированных базисных множествах.

Пусть, далее, ?  и ?  эквивалентны, а термы ?  и ?  задают соответствующие способы вывода. Рассмотрим множество

e = {(u, v) ? ? ? ? ? ? | u = ?(v)}.

По определению эквивалентности, при этом справедливо, что

e = { (u, v) ? ?  ? ?   | v = ?(u)},
               ?     ?

откуда следует, что e : ?  ? ?
     ?     ?    — биекция между множествами ?
 ?   и ?
 ?   , т. е. множества ? ?   и ? ?   равномощны.

Оценкой сверху для мощности терма ? ?   является мощность ступени S?   , откуда следует

Теорема 1. Для рода структуры ?  не существует эквивалентного ему рода структуры с типовой характеристикой d ? ? S?[x1,...xn ]  , если имеются такие термы ?1,...?n   , что

|{d ? S?[?1,...?n] | R? }| > |S? [?1,...?n]|.

 

Например, если ?  — род структуры разбиения множества x  на классы эквивалентности, то, как известно из комбинаторики, при конечном x  мощность соответствующего терма ? ?   всевозможных разбиений x  равна B
  n  , где n  — число элементов x  , B
 n  n  число Белла, вычисляемое, например, по формуле       1 ? ?   kn
Bn  = e   k=0 k!   . Начиная с B0 = B1  = 1  первые несколько чисел Белла равны 1, 1, 2, 5, 15, 52, 203, 877, 4140…Как видим, уже при n = 3  имеет место Bn > n  и при n = 5  Bn >  2n  , т. е. в пятиэлементном множестве можно выделить 32 подмножества и построить 52 отношения эквивалентности, из чего следует невозможность применения типовых характеристик d ? x  и d ? P (x )  для построения родов структур, эквивалентных ?  .

С другой стороны, мощность ступени P P (x)  , равная    |x|
2(2 )   , при любом x  , состоящем из по крайней мере четырёх элементов, больше или равна мощности ступени |P (x ? x)| = 2 (|x|2)   . Но из этого не следует, что всякое бинарное отношение на одном множестве, в котором мощность базисного множества необходимо превышает 3, эквивалентно представимо в виде рода структуры с типизацией P P(x )  (контрпример будет приведён ниже). Отсеять достаточно мощные, но при этом всё ещё не подходящие по структурным характеристикам ступени позволяет рассматриваемое далее условие.

 

4 Второе необходимое условие эквивалентной представимости

Пусть ?  — род структуры с типовой характеристикой d ? S[x1,...xn ]  , а ? = (?1,...?n,?)  есть ?  -объект ([1, с. 204], [3]). Тогда биекции f1 : x/upload/images/images/1 ? x1   ,…fn : xn ? xn  определяют автоморфизм ?  в объект

? ? = (?1,...?n,?f1,...fn?S(?)),

где ?f1,...fn?S  есть каноническое распространение биекций f1,...fn  по схеме S  . При этом, если имеет место ?f ,...f  ?S (? ) = ?
  1     n  , то мы будем говорить, что биекции f ,...f
 1     n  определяют автоморфизм, сохраняющий родовую константу ?  .

В качестве примера рассмотрим род структуры цикла на множестве x  , состоящем из четырёх элементов a  , b  , c  и d  . Этот род структуры представим как частный случай бинарного отношения (т. е. на типизации d ? P (x ? x)  ) с помощью, например, такого направленного графа, заданного родовой константой {(a,b)  , (b,c)  , (c,d )  , (d,a)} :

a-----
|      b
|      |
|----- |
d      c

Биекции f : x ? x  , циклически сдвигающие элементы (одна из них, например, задаётся множеством {(a,b)  , (b,c)  , (c,d)  , (d,a)} ), не изменяют родовую константу, определяющую граф:

a -----b      b----- c     c -----d      d -----a
 |      |     |      |      |      |     |      |
 |      |     |      |      |      |     |      |
 |----- |     |----- |      |----- |     |----- |
d      c      a      d     b      a      c      b

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

b----- a     c|-----b|
|      |      |      |
       |      |      |
d----- c     d -----a

 

Теорема 2. Если ?  и ?   — эквивалентные роды структур, а (?1,...?n,?? )  , (?1,...?n,??)   — пара эквивалентных объектов этих родов структур, то автоморфизм, задаваемый биекциями f1,...fn   , сохраняет ??   тогда и только тогда, когда он сохраняет и ??   .

? Действительно: пусть ?  и ?  эквивалентны, а термы ?  и ?  задают соответствующие способы вывода. По определению эквивалентности родов структур, ?   — биективно переносимый терм, т. е. при замене объекта (?1,...?n,??)  на                     S
(?1,...?n,?f1,...fn? (??))  , значение ?  изменяется на ?f1,...fn?S(? )  . Но это, по определению — в точности результат переноса ??   с помощью биекций f1, ...fn  . Наглядно показать совпадение результатов соответствующих преобразований можно на следующей коммутативной диаграмме:

      ?  --?--?
       ?       ?|
?f1,...fn?S|        ?f1,...fn?S
           ?
      ??? -----???

Таким образом, если ?  = ??
 ?    ?   , то, в силу однозначности отображения, задаваемого термом ?  ,       ?
?? = ??   . Аналогичным образом доказывается утверждение относительно терма ?  .?

Вернёмся к примеру с циклом на множестве из четырёх элементов. Можно ли воспользоваться отношением типизации P P (x )  для построения эквивалентного рода структуры цикла?

С помощью бинарного отношения на таком множестве возможно построить (4 - 1)! = 6  различных между собой циклов. Мощность ступени P P (x)  в этом случае составляет    4
2(2 ) = 65536  . Всего имеется 4! = 24  перестановки элементов x  , из которых 4  (циклические сдвиги) сохраняют родовую константу, а 20   — не сохраняют. Проверить результат воздействия каждой из 24 перестановок на каждый из элементов P P (x)  с помощью компьютера не составляет труда.

При этом получаются следующие результаты: из 64536 элементов множества P P (x)  всего 64 преобразуются в себя с помощью циклических сдвигов. Из этих шестидесяти четырёх 32 также преобразуются в себя при перестановке элементов a  и b  (например, {{a,b,c} , {a,b,d} , {a, c,d} , {b, c,d }} ) — но такая перестановка не сохраняет родовую константу цикла, и ещё 32 преобразуются в себя при обращении цикла (например, {{a, c},{b,d}} ) — но обращение цикла также не сохраняет родовую константу.

Таким образом, для рода структуры цикла на множестве из четырёх элементов не может существовать эквивалентного ему рода структуры на типовой характеристике P P (x)  , и, следовательно, не может существовать эквивалентного представления и в общем случае.

 

5 Представимость «универсальной ступенью»

Итак, как показано выше, типизации вида d ? x  , d ? P (x )  (в силу недостаточной мощности) и d ? P P (x)  (в силу структурных свойств) в общем случае не пригодны для представления родов структур, представимых бинарным отношением d ? P (x ? x)  . Но в то же время, уже для любого бинарного отношения существует эквивалентный род структуры на типизации d ? P P P (x)  , если рассматривать d  как множество упорядоченных пар по Куратовскому (т. е. каждой паре (a,b) ? x ? x  сопоставлять множество {{a}, {a,b}} ? P P (x)  , см., напр., [1, с. 102]).

Возможность использования упорядоченной пары по Куратовскому наводит на мысль, что вообще любой род структуры с одним базисным множеством может быть представлен ступенью вида   n
P  (x)  , где n  — достаточно большое число. Далее это утверждение будет доказано.

Назовём взвешенным рангом схемы конструкции ступени1 S  натуральное число, обозначаемое как rg(S )  и определяемое по следующему рекурсивному правилу:

  1. если S   — индекс, то rg(S) = 0  ;
  2. если S  имеет вид P (S ?)  , то rg(S) = rg(S ?) + 1  ;
  3. если S  имеет вид S1 ?  S2   , то rg (S) = max (rg(S1),rg(S2 )) + 2  .

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

Теорема 3. Всякий род структуры ?  с одним базисным множеством и типовой характеристикой d ? S[x]  имеет эквивалентный род структуры с типовой характеристикой

e ? Prg(S)(x).

 

? Для доказательства этого утверждения достаточно доказать, что для всякой схемы S  над одним базисным множеством можно построить терм ? (d)  , биективно переносимый при типизации d ? S [x ]  , терм ?(e)  и формулу Rc (x, e)  , биективно переносимые при типизации       rg(S)
e ? P     (x)  , такие, что род структуры, эквивалентный ?  , строится заменой в тексте ?  типовой характеристики d ? S [x ]  на e ? Prg (S)(x)  , всех вхождений родовой константы d  в аксиомы и термы — на терм ?(e)  и добавлением Rc  к аксиомам исходного рода структуры. Построенный таким образом род структуры будет эквивалентен исходному посредством выводов ?  и ?  . Это будет иметь место, если в теории множеств выводимы следующие формулы:

  1. d ? S[x] ? ? (d) ? Prg(S)(x )  ,
  2. e ? Prg(S)(x ) & Rc (x,e) ? ? (d) ? S[x]  ,
  3. Rc(x,? (d))  ,
  4. ?d ? S [x](?(?(d)) = d)  ,
  5.        rg(S)
?e ? P     (x)(Rc(x,e) ?  ?(?(e)) = e)  .

Как видим, аксиома ?  нигде не используется, что и позволяет говорить о всеобщности этой теоремы применительно к любому ?  .

Докажем эти утверждения индукцией по построению схемы S  .

  1. Если S = 1  , то rg (S) = 0  , ?(d) = d  , ?(e) = e  , Rc =  (?  = ? )  (для Rc  здесь годится любая выводимая в теории множеств формула).
  2. Если          ?
S = P (S )  , то              ?
rg (S ) = rg(S ) + 1  и, по предположению индукции, для   ?
S существуют   ?
? ,  ?
? и  ?
Rc  , удовлетворяющие условию теоремы для   ?
S . Иначе говоря, если d ? P (S ?)  , то в силу предположения индукции d  можно считать множеством элементов, каждый из которых взаимно-однозначным образом представим как элемент множества Prg(S)-1(x)  . Но тогда ? (d) = {t ? Prg (S )-1(x) | ?u ? d(t = ? ?(u ))},

     

    ?(e) = {t ? S?[x] | ?u ? e(t = ??(u))},

     

                  ?
Rc =  ?t ? e R c(t).

     

  3. Если S =  S1 ? S2   , то, в силу предположения индукции, можно построить термы        rg(S1)
?1 ? P      (x )  , ?1 ? S1 [x]  и        rg(S2)
?2 ? P      (x)  , ?2 ? S2 [x ]  . Пусть s(x) = {x}  — операция взятия синглетона, а натуральные числа p  и q  определены как p = max (rg(S1),rg(S2)) - rg(S1),

     

    q = max (rg(S1),rg(S2)) - rg(S2).

    Тогда термы sp(?1 (d ))  , sq(?2(d))  будут биективно переносимыми и иметь одинаковую типизацию Pmax (rg(S1),rg(S2))(x)  (здесь, разумеется, sn (? ) = s ...s(?)
        ?n-??ра?з  ,  0
s (?) = ?  ). В этом случае ничто не мешает составить из них биективно переносимую упорядоченную пару по Куратовскому, имеющую типизацию

    Pmax (rg(S1),rg(S2))+2(x) = Prg (S)

    и дающую искомый терм ?  :

               p           p         q              rg(S)
?(d ) = { {s (?1(d))},{s (?1(d)),s (?2(d))}} ? P    .

    Построим ?(e)  и Rc  . Пусть

    ?(?) = {u ? DD  ?(?) | ?v ? DD ?(?)? = {{u },{u,v }},

     

    ?(?) = {v ? DD  ?(?) | ?u ? DD ?(?)? = {{u },{u,v }}.

    Тогда

           (   (?1+p      )    ( ?1+q     ) )
? (e ) =  ?1       ?(e)  ,?2       ? (e)    ? S1 ? S2,

     

             ( ?      )       (?      )
Rc =  Rc1     ?(e)  & Rc2     ?(e)  & |?(e)| = 1 & |? (e)| = 1&
    ||?      ||            ||?p      ||
  & ||   ? (e)|| = 1 & ...& ||    ?(e)|| = 1&
    |?      |            |?q      |
  & |   ? (e)| = 1 & ...& |    ?(e)| = 1.

     

Аксиома Rc  обеспечивает биективную переносимость терма ?(e)  , т. к. терм ?
  ?  биективно переносим в общем случае, если |?| = 1  и ?  имеет характер множества.?

Данную теорему можно распространить на случай произвольного числа базисных множеств. Наметим основные шаги доказательства.

Действительно, определим биективно переносимую операцию

?i(?1,...?i,...?n) ?
  ?  {t ? ? (?1) ? ...?(?i) ? ...?(?n) | ?u ? ?i (?, ...{u},...? ) = t},
?(?i(?1,...?i,...?n)) = P (PD ? (?1) ? ...?  PD ? (?n)).

Например, ?  ({a, b},{c,d}) = {({a}, ?),({b},? )}
  1 , ? ({a,b},{c,d }) = {(?,{c} ),(?, {d} )}
 2 .

Теперь заменим в выражении типизации исходного рода структуры d ? S[x1,...xn]  на выражение

d ? S [P (x1) ? ...? P (xn),...P (x1) ? ...? P (xn)]

и добавим биективно переносимую аксиому d ? S [?1(x1,...xn),...?n (x1, ...xn)]  . Получившийся род структуры, как несложно доказать, эквивалентен исходному. Путём манипуляций, описанных в доказательстве предыдущей теоремы, его можно привести к эквивалентному роду структуры с типовой характеристикой

d ? Prg (S )(P (x1) ? ...? P (xn),...P (x1) ? ...? P (xn)).

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

6 Заключение

В статье рассмотрены и доказаны некоторые необходимые и достаточные условия представимости данного рода структуры эквивалентным ему с заданной типовой характеристикой. Показано, что для того, чтобы род структуры ?  с типовой характеристикой d ? S? [x1,...xn ]  мог быть эквивалентно представлен с помощью типовой характеристики d ? S? [x1, ...xn]  , необходимо, чтобы

  • _|{d ? S? [?1,...?n] | R ?}| > |S ?[?1,...?n ]| ,
  • для всякого ?  -объекта ? = (?1,...?n,??)  существовал такой элемент ?? ? S?   , что изоморфизмы ?  сохраняют ??   тогда и только тогда, когда они сохраняют ??

и достаточно, чтобы S ?   имела вид

  •   rg(S?)
P      (1)  , если ?   — род структуры с одним базисным множеством
  • Prg(S?)(P (1 ) ? ...? P(n ),...P(1) ? ...?  P(n ))  для рода структуры с n базисными множествами.

 

Литература

 

[1]    Пономарев И. Н. Введение в математическую логику и роды структур: учебное пособие. — М.: МФТИ, 2007. — 240 с.

[2]    Бурбаки Н. Теория множеств: Пер. с фр. / Под ред.  В. А. Успенского. — М.: Мир, 1965. — 455 с.

[3]    Павловский Ю. Н., Смирнова Т. Г. Проблема декомпозиции в математическом моделировании. — М.: ФАЗИС, 1998. — 266 с.

[4]    Павловский Ю. Н., Смирнова Т. Г. Шкалы родов структур, термы и соотношения, сохраняющиеся при изоморфизмах. — М.: ВЦ РАН, 2003. — 92 с.

 скачать (3936 скачиваний)

 
© МФТИ
© МЭРТ
© НП Аналитический центр "Концепт"
Сайт разработан:
"Golden CMF" ™ - 2energies ©

Издательство «Концепт» Москва 2004
Дата последней редакции: 16.10.2009

ГЛАВНАЯ   |   ПУБЛИКАЦИИ   |   РУБРИКАТОР   |    АВТОРСКИЙ УКАЗАТЕЛЬ   |   О ЖУРНАЛЕ   |   УЧРЕДИТЕЛИ