Шкалы потенциалов вычислимости n-элементных алгебр Журков Сергей Валерьевич

Строение шкал потенциалов вычислимости п-элементных алгебр

В этой главе будут исследованы некоторые общие вопросы строения шкал (СТп; ) - как связаны эти шкалы между собой при различных натуральных щ насколько регулярно (являются ли они полурешетками) и насколько сложно (всякая ли решетка вложима в подходящую шкалу) устроены эти шкалы, являются ли плоскими графы диаграмм шкал. Просчитан ряд параметров шкал - их длина, число атомов и коатомов. В главе 1 было отмечено, что шкала (СТп; $С) потенциалов вычислимости n-элементных алгебр является конечным частично упорядоченным множеством, причем для различных натуральных п m имеет место неравенство \СТп\ \СТт\. В силу этого, в случае разрешимости элементарной теории класса Sk — {(СТп; )\п - натуральное число } всех шкал существовал бы алгоритм, решающий все вопросы строения каждой конкретной шкалы {СТп\ $С). Однако, как показывает следующее утвержде- ниє, на столь простое решение всех проблем строения шкал потенциалов вычислимости п-элементных алгебр рассчитывать не приходится. Утверждение 2.1. Элементарная теория класса Sk — {(СТп; ) п Є OJ} неразрешима. Действительно, далее в теореме 2.1 будет доказано, что для любого натурального п решетка разбиений Part(n) n-элементного множества изоморфна некоторому интервалу шкалы (СТт; $С) при достаточно большом т. Тем самым, класс конечных решеток разбиений относительно элементарно определим в классе Sk. Элементарная же теория класса конечных решеток разбиений, как хорошо известно, наследственно неразрешима - в ней очевидным образом интерпретируется наследственно неразрешимая (см. [1]) элементарная теория конечных множеств с двумя отношениями эквивалентности. Тем самым, действительно, элементарная теория класса Sk неразрешима. Заметим, что для любых п т шкала (СТт; ) является ретрактом шкалы {СТп; }. Утверждение 2.2. Для любых m п шкала (CTm; ) является ре-трактом шкалы (СТп; ). Более того, существуют интервал [а; Ь] шкалы, (СТп\ $С) и эпиморфизм, /? шкалы (СТп; } на интервал [а; Ь] такие, что (р тождественен на [а; Ь], и интервал [а; Ь] изоморфен -шкале (СТт: :). Достаточно доказать это утверждение для п = т + 1. Пусть алгебры 21 и 21" таковы, что Sub(W) = {{0,1,..., т}, {О,1,..., т - 1}}, Sub(Q[") = {{0,1,..., т}} U Р(т), где Р(т) - совокупность всех подмножеств множества т — {0,1,... ,т — 1}, Iso(Ql ) состоит из всех тождественных отображений на себя множеств, входящих в Sub(Ql ), a Iso(Ql") -из тождественного отображения на себя множества т+1 и всевозможных биекций между подмножествами из Р(т).

В главе 1 указан критерий, ко гда пара (Р; Q) подмножеств некоторого множества и совокупности биек ций между этими подмножествами является парой вида {Sub($l); Iso(Qi)) для некоторой алгебры 21, то есть являются инвариантом потенциала вы числимости некоторой алгебры. В силу этого критерия очевидно, что шкала (СТШ; ) изоморфна интервалу [СТ(21")/ ; СТ( 21 )/ ] шкалы {CTm+i, ). На совокупности алгебр с основным множеством гп + 1 опре делим отображение ip: если 21 = (гп + 1; а), то (21) - некоторая алгебра с основным множеством гп+1 такая, что Ізо(ір(Щ) — (7so(2l) П Bi(m)) U {idm+i,idm}, где Bi(rn) - совокупность всевозможных биекций между подмножествами множества m, id\ - тождественное отображение на множестве А. Существование алгебры у (А) очевидно в силу указанного выше критерия. Очевидно, что для любых алгебр 2І,2І!,2І2 СТ{ р(Щ/ Є [СТ(2Г)/ ; СТ(2Г)/ Ч если СТ(Я)/ Є CT(ip{%2))/ . Тем самым, действительно, шкала (CTm; ) является ретрактом шкалы (СТп; ) при m $$ п. В работе А.Г.Пинуса [6] найдены все попарно условно рационально не эквивалентные двух- и трехэлементные алгебры Ші,. .., В5 и 211;..., 21,5з, а также инварианты условной рациональной эквивалентности {Sub(Q3j);/so(23i)), (5и6(21г); /so(2lj)) этих алгебр. Исходя из этих инвариантов, непосредственным вычислением отношений включения 7r(Sub(Qii)) С Sub($ij) и 7r_1(/so(2lj))7r Э /so(2lj) для некоторой перестановки 7Г на множестве {0,1,..., п — 1} находятся изображения шкал (СТ2; )и(СЪ; ). Здесь за точками шкал потенциалов вычислимости сохранены названия соответствующих им алгебр из [6]. Шкала (СТп] } содержит наибольший элемент Fn/ , где Fn - совокупность всех функций на множестве п, и наименьший элемент Dn/ , где Dn — CT(Qt) для алгебры 51 = (п; 0), то есть совокупность всех функций на п, получаемых за счет подстановок из функций - селекторов и дискриминаторной функции. Функции из совокупности Dn - это так называемые обобщенно селекторные функции - функции вида где D\(xi,..., xm),... ,Di(x\,..., xm) - всевозможные максимальные попарно несовместимые условия, состоящие из равенств и неравенств между переменными xi,...,xm (при условии, ЧТО Х\,...,Хт Є п) и хч,. .., Хц Є {хі,..., хт}. Заметим также, что для любого Ф Є СТ(п), если Fn/ = Отображение ip : СТ(п) — СТп, определенное как /?(F) — F/ , является монотонным отображением решетки (СТ(п); С) клонов условно термальных функций на множестве п на шкалу (СТп; ). Однако, как показывает следующее утверждение, в отличие от решетки (СТ(п); С), шкала (СТп; $С) при n 3 решеткой не является. Утверждение 2.3. При п 3 шкала (СТп; } не является ни верхней, ни нижней полурешеткой.

Доказательство. В работе [10] определено понятие дыры в частично упорядоченном множестве (A; ). Дырой называется такая четверка различных элементов а\, аг, аз, а из А, что а і аз? ал , а а3) 4! пары оі, 02 и о,3, г/4 состоят из несравнимых элементов и при этом в А не существует элемента Ь такого, что аЛ,а2 Ъ аз, а4. Очевидно, что если {A; $J) имеет дыру, то (A; ) не является ни верхней, ни нижней полурешеткой. Таким образом, для доказательства утверждения теоремы достаточно указать дыру в шкале {СТп; ) при п 3. Покажем это при п — 3. В силу утверждения 2.2 шкалы (СТп; =$С) тогда будут обладать дырой и при любом п 3. Воспользуемся обозначениями элементов множества СТ$, приведенных выше. Непосредственно замечается, что алгебры 21з521ю 21і2,21і5 (а точнее, их классы эквивалентности) образуют дыру в (СТ3; ). Тем самым утверждение доказано. Несмотря на утверждение 2.3, имеет место Теорема 2.1. Для любой конечной решетки L существует натуральное п и элементы -Fi/ ,F2/ шкалы (СТп; ) такие, что L как решетка вложима в интервал [.F\/ ; F%/ ] шкалы (СТп; ), являющийся решеткой. Доказательство. Пусть L - конечная решетка и L - двойственная к L решетка. Тогда, как известно [22], L изоморфно вложима в решетку Part(m) разбиений множества т — (0,1,..., т — 1} для подходящего натурального т. Пусть В(т) - булева алгебра всех подмножеств множества т. Далее будем отождествлять одноэлементные подмножества {і} множества т с числами г. Для любого 0 г т рассмотрим попарно дизъюнктные множества Аг = {і0 = z, г1,... ,гг_1} такие, Кроме того, если х (или у) не входит во множество В(т), то положим xU у = хПу —"х = 0. Функции #0(:г), і 9m-i(x) определим на А следующим образом: J т, если х Є В (га) и г = г ж 1 0, если х В(т) либо і0 = г х Рассмотрим алгебру 21 = (A; U, П,"", 0, ш, /, д0,..., дт-\). Если В = (С; U, П, \ 0, m, f,g0,..., рт_г) - подалгебра алгебры 21, то С П (т) образует подалгебру булевой алгебры В(т), и для любого 0 і т следующие условия эквивалентны: Наличие циклов (Аг, /) и функций до, ,9т-і очевидным образом влечет то, что любой внутренний изоморфизм алгебры 21 суть тождественное отображение некоторой ее подалгебры самой на себя. Кроме того, отображение р, определенное как f(C) = С П В(т), является изоморфизмом решетки Sufe(2l) на решетку Sub(B(m)). Заметим так же, что Sub(B(rn)) = Part (m), где Part (m) - решетка, двойственная решетке Part{m). Для любого разбиения г) Є Part(ni) пусть {b ,... ,bv } - разбиение единицы (множества т) булевой алгебры В(т), соответствующее разбиению г/.

Основные параметры шкал потенциалов вычислимости гг-элементных алгебр

В главе 1 уже указывалось, что мощность шкал потенциалов вычислимости растет очень быстро - ІСТгІ = 5, СТ3 = 53, \СТ4\ = 22610. Результаты раздела 2.1 говорят о том, что какой-нибудь регулярности и простоты строения шкал (СТп; ) ожидать не приходится. В связи с этим представляет интерес нахождение различных параметров этих шкал: длины, числа атомов, коатомов и т.д. Теорема 2.2. Число атомов шкалы (СТп; } равно [] + 1 + R{n), где R(n) - число максимальных транзитивных на п подгрупп полной симметрической группы на п, попарно не сопряженных в этой группе. Чис- ло коатомов равно (п — 1) + К(п), где К{п) - число различных простых делителей числа п, отличных от единицы. Доказательство. Как было отмечено выше, инвариантом для класса F/ Є СТп является пара (5ub(2l);/so(2l)), где 2t = (n;F), и отношение -Fi/ F-ij соответствует существованию перестановки 7г на п такой, что для %\ — (n;Fi) и 2І2 = (п; F?) имеют место включения 5 6() С 5u6(7r(2li)) И 7so(2l2) С iso(7r(2li)). Тем самым, коатомам шкалы (СТп; ) соответствуют либо алгебры 21 = (п; а), имеющие единственную собственную подалгебру и тривиальные внутренние изоморфизмы (таковых с точностью до перестановок на п ровно п — 1 штука), либо алгебры 21 = (що), не имеющие собственных подалгебр, с минимальной группой автоморфизмов (в частности, эти автоморфизмы не имеют неподвижных точек). Таким образом, в последнем случае Aut(Qi) является циклической группой G, порожденной перестановкой 7г и такой, что перестановки, входящие в G = {тх, л2,.. ., п11 — е = id„} не имеют неподвижных точек. Любая такая перестановка 7г имеет вид произведения m независимых циклов простой длины п/тп, где m - делитель п, отличный от единицы. Таким образом, с точностью до перестановок на п число подобных групп G равно числу К(п) - различных простых делителей числа п, отличных от единицы. В итоге число коатомов шкалы Рассмотрим теперь вопрос о числе атомов в шкале (СТп; $С). Пусть F є СТ(п) и F/ - атом в (СГ„; ). Пусть S = Sub{(n; F)) и В = Iso((n;F)). Через Р(п) обозначим совокупность всех подмножеств множества п. В главе 1 описаны условия (обозначим их как ( ) ), при которых пара (S\;B\), где S\ С Р(п), В\ - некоторая совокупность би-екций между множествами из Si, такова, что Si = Sub(Ql), Bi — iso(2l) для некоторой алгебры 21 = (п;а).

При этом если Fi = Stab(Si\Bi), то есть является совокупностью всех функций на множестве п, относи- тельно которых замкнуты подмножества из S\ и которые коммутируют с биекциями из Ви то Si Рассмотрим вначале случай, когда S ф Pin). Пусть также существуют Аі,А2 Є Р(п) \ S такие, что Лі \А2\, и пусть S — S U {С С п \С\ -Аг} Непосредственно замечается, что пара (S ;BU {д \с .9 Є -В, \С\ \А2\}) удовлетворяет условию ( ). Но тогда, если F = Stab(S ;B), то D/ F / F/ в противоречии с тем, что F/ - атом в (СТп; }. Тем самым, если S Ф Р(п), то для любых Аі,А2 Є Р(п) \ S имеет место равенство Л] = \А2\. Через Sym(n) обозначим все перестановки на множестве п. Если В 2 Sym(n), то опять же непосредственно проверяется, что пара (Р(п); Ви{д \с \ 9 Є В, С С п}) удовлетворяет условию ( ) и, значит, для F = Stab(P(n);B) имеет место Р/ F / F/ в противоречии с тем, что F/ - атом. Таким образом, если 5 Ф Р(п), то существует m п такое, что S = 5т = {С С п \С\ Ф т}. При этом, так как S - нижняя полурешетка относительно операции теоретико-множественного пересечения, то m = п — \. Кроме того, В D Sym{n) и, так как для любых д Є В, С Є S ограничение д \с также должно входить в В, то В = Вг{п) - совокупности всех биекций между подмножествами множества п. Обратное, то есть то, что, если F — Stab(Sm; Bi(n)), то F/ есть атом в шкале (СТп; ), практически очевидно. Тем самым, описаны инварианты для одного из атомов шкалы (СТп; ). Для всех других атомов этой шкалы инварианты имеют вид {Р(п); В), где В = В U Bi (n) и В - некоторая максимальная подгруппа группы Sym(n), а Вг (п) - совокупность всех биекций между менее чем п-элементными подмножествами множества п. В силу максимальности В как погруппы группы Sym(n) либо В действует на п транзитивно, либо множество п разбивается на две В -орбиты: п — Аі\ЛА2. В последнем случае ограничения перестановок из В на множества Аг суть полные группы перестановок на Aj, и В = Sym(Ai) х Sym(A2). При этом элемент F/ шкалы (СТп; :) однозначно определяется мощностями множеств Ai и Аг. Тем самым, число различных атомов, соответствующих существованию двух ? -орбит на п, равно Таким образом, для оставшихся атомов шкалы (СТп; ) инвариантами выступают пары (Р(п); В), где В - максимальная подгруппа полной симметрической группы на п, действующая на п транзитивно, а число подобных атомов совпадает с числом попарно не сопряженных в Sym(n) подобных подгрупп. Теорема доказана. Заметим, что вопрос о числе R(n) является открытым и довольно сложным вопросом теории конечных групп. Он связан с вопросом описания конечных простых групп. Более подробную связанную с этим вопросом информацию можно найти в работе [20]. Как было замечено выше, при п — 4 число элементов шкалы (СГ4; ) было посчитано П.Джипсеном и равно 22610, число атомов и коатомов в {СТ4; ) по теореме 2.2 равно соответственно 5 и 5. Напомним, что длиной цепи а0 а і ... ато является число т, а длиной частично упорядоченного множества является максимум длин цепей из этого множества.

Длину частично упорядоченного множества {L; ) обозначим как d((L; =)). Очевидным образом имеет место следующее утверждение: Лемма 2.1. Для любых частично упорядоченных множеств {Ь\\ ) и (L-2; ) имеет место равенство Заметим при этом, что если (L\; ) и (L2; ) имеют наибольшие и наименьшие элементы 0i,02 и 1і,І2 соответственно, d((Li; )) = d\, Таким образом, если А0 = {0, п) С Аг С ... С Adl = Р(п) - наиболее длинная цепь нижних полурешеток в (Р(Р(т?,)); С), В0 С В\ С ... С Bd.2 — Bi(n) - наиболее длинная цепь инверсных полугрупп в (Р(Вг(п)); С), включающих в себя совокупность Во всех биекций между одноэлементными подмножествами множества п и тождественными отображениями подмножеств множества п на себя, то элементы цепи (А0,В0) (АиВ0) ... (Adl,B0) (Adl,B ... {Adl,BdJ удовлетворяют всем условиям а)-ж) определения 1.8. Следовательно, d((CTn; )) — di + о?2, где dx - длина интервала [{0, п); Р(п)} в частично упорядоченном множестве (Р(Р(п));С), а d2 - длина интервала [BQ\ Вг(п)] в частично упорядоченном множестве (Р(Вг(п)); С). Лемма 2.2. d(([{0, п); Р(п)]\ С)) = 2" - 2. Доказательство. Пусть Рт(п) = {D С п \ \D\ — т). Пусть Рт(п) = {D?,...,D%rn} и А0 = {0,n},A! = Pi( ) U P2{n), ,Acl+C2+ +cn-i — P{n). Тогда, так как \АІ+І \ Аг\ = 1 для любого г, то А0 С Ai С .. . С Асг+с2+ +с"-1 будет цепью в интервале [{0,п}; Р(п)] частично упорядоченного множества (Р(Р(п));С), состоящей из нижних подполурешеток полурешетки (Р(п);П) и имеющей максимальную длину Пусть (Part(C); ) - частично упорядоченное множество (решетка) всех разбиений множества С, и А (V) - наименьший (наибольший) элемент в Part (С). Если А = в0 в\ ... 9Г — V - максимальная цепь в Part(m), то очевидно, что переход от #fc+1 к в к (к г) осуществляется за счет разбиения одного из классов - -эквивалентности на два класса ( -эквивалентности. В силу этого без труда замечается, что цепь суть цепь наибольшей длины в {Part(m); С), то есть имеет место следующее утверждение: В работе [19] найдена длина 1п частично упорядоченного по включению множества всех подгрупп полной симметрической группы Sym{n) на множестве п, она равна [Щ ] — ЬП1 где bn = Y1 [fr] md 2 - число единиц в двоичном разложении числа п. Пусть Вгт(п) — { р Є Bi(n) \ \Dom(ip)\ — га}, и пусть G% — {idn} С Gі С ... С G? = Sym(n) - некоторая цепь подгрупп группы Sym(n), имеющая максимальную длину. Если В - некоторая инверсная подполугруппа полугруппы Вг(п) и 1 га п, то очевидным образом является инверсной подполугруппой полугруппы Вг(п). Таким образом, если Id(ri) = {idc\C Сп}и цепь инверсных подполугрупп полугруппы Ві(п), имеющая наибольшую длину в интервале [Вц(п) U Id(n); Вг(п)], то невозможно уплотнение этой цепи за счет добавления полугруппы вида (Е()т, где 1 г di, 1 m п. В силу этого инверсные полугруппы вида Bii(n)U.. .UBik(n)Uld(n) входят в любую цепь инверсных подполугрупп полугруппы Вг(п), имеющую максимальную длину. Тем самым, цепь подполугруппы (2.1) устроена следующим образом: где G0 = {idn} cG1C..CGi„-iCG„ = Sym(n) - цепь подгрупп группы Sym(n), имеющая максимальную длину.

Шкалы потенциалов вычислимости гг-элементных унаров

При более детальном изучении строения шкал потенциалов вычислимости естественно изучение строения различных подмножеств этих шкал, возникающих при тех или иных естественных ограничениях на рассматриваемые универсальные алгебры. И первые из этих ограничений - это ограничения на сигнатуру алгебр: ограничения на число функций в сигнатуре и ограничения на местность этих функций (число их аргументов). Как показывает следующее утверждение, первое ограничение не является на самом деле ограничением, и дальнейшие рассмотрения этой главы будут связаны со вторым из перечисленных ограничений. Утверждение 4.1. Для любой конечной алгебры 21 существует алгебра 21 сигнатуры,, состоящей из одной функции, такая, что СТ{%) = СТ(21 ). Доказательство. В силу известных инвариантов совокупности функций СТ(21) для конечных алгебр 21 = (А; а) достаточно построить алгебру 21 = (Л;сг ), сигнатура о которой состоит из одной функции, такую, что Sub(%) = Sub(W) и /so(2i) = Iso{W). Пусть (B{,b\),..., (В 1 lb 1),..., (Bl,bl),..., (B$T ,bfr) - совокупность всех пар, где В\ = Щ1,..., b\H) пробегает все кортежи попарно различных элементов из Д Щ - элемент из подалгебры алгебры 21, порожденной множеством Щ1,... , frf4}, и при этом для любых і г, р,q й существует ( Є Iso{%) такой, что p(Bf) = Д?, /?(Ю = 6 , а для г Ф j г подобных Lp Є iso(2l) не существует. Определим на Л (п + 1) г-местную функцию /(х{,...,х +1, ?,..., х+1,...,:г ..., +1), гдеп= А, следующим образом: для любых і г, j кі\ Пусть 21 = {A; f). Непосредственно замечается, что Sub( ) — Sub(W) и /so(Ql) = iso(2l ). Утверждение доказано. Далее в данной главе рассматривается шкала (СГ ; ) потенциалов вычислимости n-элементных унаров. Напомним, что уиаром называется универсальный алгебра, сигнатура которой включает в себя только одноместные функции. Пусть СТ - совокупность потенциалов вычислимости n-элементных унаров. Таким образом, базовое множество шкалы {СТТ\; :) является подмножеством базового множества шкалы (СТп; ). Как указано в главе 1, конечная алгебра 21 условно рационально экви валентна некоторому унару тогда и только тогда, когда решетка Sub(2l) является подрешеткой решетки (P(n);D, П), где Р(п) = {С\С С п}, а полугруппа Iso(Qi) обладает свойством амальгами-руемости, то есть для любых (р,ф Є 7so(2l), если отображение ц U ф биективно, то ср U ф Є і so (21). Эти условия будем называть условиями ( ). Заметим, что шкала (СТ ; $С) является ретрактом шкалы (СТп; ).

Действительно, определим отображение ф на совокупности алгебр с п-элементным базовым множеством таким образом: если 21 - алгебра с n-элементным базовым множеством, то ф{Щ - алгебра с п-элементным базовым множеством такая, что БиЬ{ф{Щ) = Sub($l) U {А\А есть объединение некоторой совокупности подмножеств - подалгебр из Sub(Ql)}, Ізо(ф(Щ) = /so(2l) U {х\х - биекция, образованная в результате объединения некоторой совокупности внутренних изоморфизмов из Нетрудно заметить, что (21) Є СТ\. Более того, если алгебра 21 такова, что 21 Є СТ , то (21) = 2І. Очевидно также, что, если Qlj зС 2І2, то -0(21:) Фі )- Следовательно, шкала (СТ ; ) действительно является ретрактом шкалы {СТп; Рассмотрим строение шкал потенциалов вычислимости (СТ\\ ) для п — 2 и п — 3. Рассмотрим сначала шкалу {СТ ; ). Будем считать, что базовое множество имеет вид 2 — Для Sub($l), где 21 = ({0,1}; сг), получаем следующие возможные комбинации: Для варианта 2) существует подвариант: Для варианта 3) существует подвариант: a) /so(2l) = {е,0 -Н- 1, (0,1)}, где О -Н- 1 - изоморфизм подалгебры {0} на подалгебру {1} и обратный к нему. Данные подварианты эквивалентны следующим алгебрам: la) i = (2; х — х,х+х + 1), где операции + и — сложение и вычитание но модулю 2 соответственно. По отношению включения для классов функций СТ[(Ъг) имеет место следующая диаграмма: Рассмотрим теперь случай при п Ъ. Будем считать, что все алгебры определены на множестве 3 = {0,1, 2}. В этом случае имеем следующие варианты для Sub(Ql): В главе 2 было найдено количество атомов и коатомов в шкале (СТП; :). Рассмотрим подобные проблемы для шкалы (СТ ; ). Справедлива следующая Теорема 4.1. а). Количество коатомов шкалы {СТ ; ) равно где К(п) - количество простых делителей п, отличных от единицы, б). Количество атомов шкалы {СТ ; ) равно где D{i) - число делителей числа і, отл,ичных от единицы, Т/ - количество представлений числа і в виде не более чем j ненулевых натуральных слагаемых. Доказательство, а). Рассмотрим наибольший элемент 21 шкалы (CTj]; ), то есть такую алгебру 21, что Sub (ОН) = {п}, І.во(Яі) = {е}. Как замечено при доказательстве теоремы 2.2, в качестве нижних покрытий данного элемента могут выступать элементы 93 вида: 1. Sub( B) — {n}, /so( 8) = { /?, ip2,..., ipp}, где ip - автоморфизм на множестве n, р - некоторый простой делитель п, и множество п есть объединение (р-циклов длины р. 2. Sub( B) = {п, ?}, Iso( B) — {в, id в}, где В - собственное подмножество п, гдв - тождественное отображение В на В. Очевидно, что алгебры 05 вида 1) и 2) удовлетворяют условию ( ), то есть все коатомы шкалы (СТп; } являются элементами шкалы (СТТ\; ). Количество элементов вида 1) равно количеству простых делителей числа п, отличных от единицы, в то время, как количество элементов вида 2) равно количеству непустых собственных подмножеств п разной мощности.

Очевидно, оно равно п — 1. Отсюда получаем формулу количества коатомов шкалы (СТ ; ): где К(п) - количество простых делителей числа п, отличных от единицы. б). Рассмотрим теперь строение атомов шкалы (СТ ; .). Пусть ( -наименьший элемент в шкале унаров, то есть Sub( ) = Р(п) и Iso( ) — Bi(n), и 21 - атом в шкале унаров. Здесь Ві(п) - совокупность всех биекций между подмножествами множества п. Пусть В = {6 Є п (й)зд 2}. Здесь для любого В С п (В)с -подалгебра алгебры (, порожденная множеством В. В силу того, что 1) все одноэлементные подалгебры алгебры 21 изоморфны между собой, 2) 5u6(2l) является подрешеткой решетки (P(n);U, П) и 3) /so(2l) обладает свойством амальгамирования, множество В не пусто. Рассмотрим на В следующее отношение =: 6] = 62 тогда и только тогда, когда существует (/? Є /so(2l) такое, что ip{b\) — 62. Очевидно, что = является отношением эквивалентности на В. Допустим, что \В/= 2. Тогда существуют 6і,&2 Є В такие, что Ьх -ф. 62. Пусть 1{Ьг) = { р{Ьх) у? Є /so(Ql)} и D = {С U Сі С Є 5гіЬ(а),Сг С /(6])}. Тогда D является подрешеткой решетки (P(n); U, П), {62} О и, значит, ) т F(n). Пусть / - совокупность всех амальгам отображений из /so(2l) и всевозможных биекций между подмножествами множества /(6]). Очевидно, что пара { ; /) удовлетворяет условиям ( ), и при этом (5 6(21);/so(2l)) С (D;I) С (Р(п); Вг(п)). Тем самым, существует унар 21 такой, что ( 21 21, что противоречит выбору 21 как атома шкалы унаров. Таким образом, \В/= = 1, то есть биекций из /.so(2t) действуют на В транзитивно. Отсюда, в частности, следует, что для любых 6Ь62 Є В имеет место равенство (6i)a = (62)зі- Определим на В отношение : Ь\ 62 тогда и только тогда, когда {Ьі)а = (62)21- Очевидно что является отношением эквивалентности на В и, как замечено выше, все -классы (пересечения подалгебр, порожденных элементами из В, с множеством В) равномощны. Заметим также, что для любого р Є Iso(QV) Dom( p) П (п \ В) Є Sub(%), ip(Dom(ip) П (n \ В)) С n\ В и (p(Dom(ip) П В) С В, то есть существуют отображения // Є Iso(%) и p" - биекция между подмножествами из В такие, что Dom(ip ) С п \ В, Dom(p ") С В и ip = /? U ip".

Шкалы потенциалов элементарной вычислимости п-элементных алгебр

В данной главе рассмотрен ряд вопросов, связанных со строением шкалы (ЕСТп; ) потенциалов элементарной вычислимости п-элементных алгебр, введенной в рассмотрение в главе 1. Напомним, что роль инварианта для потенциала элементарной вычислимости ЕСТ(Я1) конечной универсальной алгебры 21 играет пара (Sub($l); Au(2l)), состоящая из решетки подалгебр и группы автоморфизмов алгебры 21. Заметим, что отображение рп : СТп — - ЕСТп, определенное как /?„(CT(2t)/ ) = СГ(21)/ , для любой n-элементной алгебры 21 является монотонным отображением шкалы (СТп; ) на шкалу (ЕСТп; ). Исходя из указанных инвариантов для ЕСТ{Щ анализ совокупности СТ3 из работы [6] приводит к равенству \ЕСТ3\ = 26 и к следующему строению шкалы (ЕСТ3] }, где номером г обозначены шкалы элементарных потенциалов алгебр 21г: В частности, {ЕСТ \ ) является решеткой. Заметим, что для шкал {ЕСТп\ :) при п 3 имеют место утверждения, аналогичные утверждениям 2.1, 2.2 и 2.3. Пусть ESk - совокупность всех шкал (ЕСТп; ) (п Є со) потенциалов элементарной вычислимости конечных универсальных алгебр. Утверждение 5.1. Элементарная теория класса ESk неразрешима. Доказательство полностью аналогично доказательству утверждения 2.1 и построено на равномерной для любого п интерпретации решетки разбиений Part(n) в шкале (ЕСТт; $С) для достаточно больших т, указанной далее в доказательстве теоремы 5.1. Утверждение 5.2. Для любых т п шкала (ЕСТт; ) является ре-трактом шкалы (ЕСТп; ). Более того, существует интервал [а;Ь] шкалы (ЕСТп; $С) и эпиморфизм р шкалы (ЕСТп; ) на интервал [а; Ь] такие, что ip тождественен на [а; 6], и интервал [а; Ъ] изоморфен шкале (ЕСТт; ). Доказательство полностью аналогично доказательству утверждения 2.2. Утверждение 5.3. При п 3 шкала (ЕСТп; } не является ни верхней, ни нижней полурешеткой.

Так же, как и в доказательстве утверждения 2.3, достаточно явно указать дыру в шкале (ЕСТ3; ), и тогда в силу утверждения 5.2 дыра найдется и в любой шкале (ЕСТп; } при п 3. Непосредственно замечается, что потенциалы вычислимости алгебр 2l3, 2l10, 2li2, 2lis образуют дыру в шкале (ЕСТ , ). Имеет место для шкал (ЕСТп; Г) и аналог теоремы 2.1: Теорема 5.1. Для любой конечной решетки L существует натуральное п и элементы F\j и F2/ шкалы (ЕСТп; ) такие, что L как решетка вложима в интервал [-Pi/ ;/ 2/ ] шкалы (ЕСТп; ), являющийся решеткой. Доказательство этой теоремы дословно совпадает с доказательством теоремы 2.1 в силу того, что соответствующий интервал в шкале (СТп; ) образован потенциалами вычислимости Ft = СТ(21г) алгебр 2li и 212 таких, что внутренние изоморфизмы алгебр 21, являются тождественными отображениями подалгебр алгебр 21, самих на себя, и, тем самым, интервал [СТ(21і)/ ;СГ(212)/ ] шкалы (СТп; } изоморфен интервалу [ЯСТ(аі)/ ;ЯСТ(2І2)Н шкалы (ЕСТп; ). Для шкал (ЕСТп; ) имеет место и аналог утверждения 2.4. Утверждение 5.4. Графы, соответствующие диаграммам Хассе шкал (ЕСТп; ), не являются планерными при п 3. То, что граф шкалы (ЕСТ3; ) не является планарным, непосредственно замечается из того, что потенциалы элементарной вычислимости алгебр 21і2,21із, 21і8і 21і9і 2І22,2І25 образуют в диаграмме шкалы {ЕСТу, ) подграф, стягиваемый к графу А з,з- Справедливость же утверждения 5.4 для п 3 следует из этого замечания и утверждения 5.2. Заметим, что все коатомы шкалы (СТп; $С) соответствуют алгебрам 21, либо имеющим единственную собственную подалгебру и лишь тривиальные (тождественные) внутренние изоморфизмы, либо алгебры без собственных подалгебр, группа автоморфизмов которых есть циклическая группа простого порядка. Отсюда следует, что потенциал вычислимости СТ(21)/ является коатомом в шкале (СТп; $С) тогда и только тогда, когда потенциал элементарной вычислимости ЕСТ(Я1)/ является коатомом в шкале (ЕСТп; ). Аналогичные замечания верны и относительно атомов шкал (CTn; ) и (ЕСТп; ). Тем самым, имеет место Теорема 5.2. Число атомов и коатомов шкал (СТп; ) и (ЕСТп\ ) совпадает. Отождествляя точки цепи, построенной в шкале (СТп; ) в ходе доказательства теоремы 2.2, имеющие одинаковые решетки подалгебр Sub($L) и группы автоморфизмов Aut($L), непосредственно исходя из рассуждений доказательства теоремы 2.2, убеждаемся в том, что соответствующие потенциалы элементарной вычислимости будут образовывать цепь максимальной длины в шкале (ЕСТп; ). Тем самым, имеет место Теорема 5.3. Длина шкал (ЕСТп; } равна 1п + 2п — 2. Имеет место и аналог теоремы 3.1, однако доказательство соответствующего утверждения требует более существенной корректировки доказательств лемм 3.1-3.6. Пусть EI, как и в главе 3, есть фильтр шкалы (ЕСТп; ), состоящий из потенциалов элементарной вычислимости алгебр, имеющих тривиальную группу автоморфизмов. Таким образом, фильтр (J; ) изоморфен фильтру (EI; $5). Сформулируем и докажем необходимые леммы, формулировки которых аналогичны формулировкам лемм для шкалы Через Й обозначим точки ЕСТ(%)/ шкалы (ЕСТп; ). Через АЫ {Щ обозначим совокупность нетривиальных автоморфизмов алгебры 21. Лемма 5.1. Если ранг точки 21 равен единице и 21 Є EI, то для любого автоморфизма ф шкалы (ЕСТп; =) такого, что 0(21) Є EI, имеет место равенство 0(21) = 21. Доказательство. Пусть, как и при доказательстве аналогичной леммы для шкалы (СТП; ), 21, Я Є EI, ф{Щ = 2Г, Sub(U) = {п,В}, Аиі фі) = 0, Sub(Ql ) = {п, С}, Aut {% ) = 0. Необходимо доказать, что \В\ = \С\. Предположим, что к = \В\ \С\ = I. Случаи, когда 2к п, 21 п или 2/с п, 21 и, рассматриваются аналогично соответствующим случаям из леммы 3.1 и таким же образом влекут равенство к — I. Рассмотрим случай, когда 2к п и 21 п. При этом, как следует из леммы 3.1, 2п-к-3 = 2п-1-2,к = [ \и1 = к + 1. Рассмотрим случай четного п — 2к.

Существует единственная точка 2І2 шкалы (ЕСТп; ) такая, что покрытия диаграммы являются покрытиями в шкале (ЕСТп; }. При этом Здесь С - подмножество из определения точки 212. При этом все покрытия диаграммы являются покрытиями в шкале (ЕСТп; ), и верхняя валентность точки і равна 1. Заметим также, что в шкале (ЕСТп; ) не существует нижней грани точек Щ2іЗі, для которой точка й\2 является покрытием. Покажем теперь, что в шкале (ЕСТп; ) не существует диаграммы, все покрытия которой суть покрытия шкалы (ЕСТп; $$), верхняя валентность точки $ равна 1, и такой, что у точек ЯІ-2, т? в шкале {ЕСТп; ) нет нижних граней, для которых точка 5 является покрытием. Нижние покрытия точки 21 , имеющие верхнюю валентность 1 - это точки вида такие, что Sub($) — {п, С}, Aut ($) — {if, р2,..., j)v x}-, где p - простой делитель числа п— \С\ — к, if - перестановка на п, тождественная на С и такая, что множество п\С суть объединение -циклов длины р. Других видов нижних покрытий точки 2І2 верхней валентности 1 нет. Инфину-мом точек 2І2 и $ является точка 0 такая, что Sub( 3) = {п, В, С}, В С С, Aut ( 3) — {ср, (f2,..., (рр [}, где ip определяется так же, как и для точки #. Нетрудно видеть, что точка & является нижним покрытием точки J. Из полученного противоречия следует, что \В\ = \С\. Рассмотрим теперь случай нечетного п, то есть когда п = 2к +1. Как и в случае четного п, у точек 21 и 21 , определение которых дано выше, существует нижняя грань, а именно точка 2І2, где Sub(%2) = і77-) В, С}, Aut (21г) = 0. У точки 21 существует нижнее покрытие верхней валентности 1, а именно точка і, где Sub(1)i) = {п, В, В }, \В\ = \Bi\, В П Bi = 0, Лиі (2 і) = 0. В свою очередь, у точек i и 2І2 существует нижняя грань )2, где Sub(1)2) = {п,В,Вх,С}, В С С, ВгПС = 0, Aut { 2) — 0- Очевидно, точка 2 является нижним покрытием точек 2І2 и T i верхней валентности 3.

Похожие диссертации на Шкалы потенциалов вычислимости n-элементных алгебр

Циклические L-операторы, связанные с Uq(sl(n))-алгеброй, и соответствующие интегрируемые моделиМангазеев, Владимир Викторович

Расчет коэффициентов вязкости и диффузии ряда индивидуальных газов (H2,N2,O2,O,CO,N,NO) и бинарных газовых смесей (N2-O2,O-CO,N-NO) в области высоких температур на основе центрального потенциалаТаксеитов Ринат Ревович

Исследование факторов, определяющих длительную потенциацию N-метил-D-аспартат зависимого компонента возбуждающего постсинаптического потенциала в CA1 области гиппокампа крысБаязитов Ильдар Талгатович