1.2 Абстрактные характеристики некоторых алгебр многоместных функций

В последнее время особое внимание в алгебраической теории суперпозиций функций обращено на изучение алгебраической структуры многоместных функций [1].

В работах Менгера и Глускина изучались многоместные функции от фиксированного числа аргументов. Оказалось, что для таких функций выполняется тождество типа ассоциативности. Позднее такие алгебраически е системы были названы алгебрами Менгера.

В работах Уитлока и Хиона рассматривались алгебраические системы многоместных функций, где число аргументов не фиксировалось, они были названы системами Менгера.

Интересную связь алгебр Менгера и полугрупп установил Б.М. Шайн [5]. Им было показано, что изучение всякой алгебры Менгера сводится к изучению полугрупп некоторого вида. Но такие полугруппы довольно сложно устроены, поэтому во многих вопросах выгоднее непосредственно изучать алгебры Менгера, не переходя к теории полугрупп. В Б.М. Шайном была найдена абстрактная характеристика полугрупп бинарных отношений с выделенными на них отношениями теоретико-множественного включения бинарных отношений и равенства первых проекций.

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

Пусть n -- фиксированное натуральное число, М и А -- некоторые множества. Декартову п-ю степень множества А обозначим через Аⁿ. Частичное отображение г множеств а Аⁿ в А будем называть n-местным преобразованием множества А. Множеств о всех n -местных преобразований множества А обозначим через ? (Аⁿ, А).

Полное (n + 1)-местное преобразование п множества М будем называть {n +1)-операцией на М. Если g₀, g_u ..., g_n M, то образ о {g_u ..., g_n, g₀) будем записывать в виде g₀[g_u..., g_n]; (n +1) - операция о называется сверхассоциативной, если выполняется тождество

x[y₁,…, y_n] [z₁,…,z_n] = x[y₁[z₁,…,z_n],…,y_n[z₁,…,z_n]]. (1)

Упорядоченную пару (М, о), где о - сверхассоциативная (n+1)-операция на М, будем называть алгеброй Менгера ранга n или просто алгеброй Менгера.

Алгебра Менгера (М, о), называется простой алгеброй Менгера, если существуют элементы е₁, ..., е_n М, называемые селекторами, такие, что g [e₁,…,e_n] = g, e_i [g₁,…,g_n] = g_i для любых i = 1,..., n; g, g_k M. Легко показать, что если система селекторов (е₁, ..., е_n) существует, то она единственна.

Пусть (М, о) - алгебра Менгера, Х - множество равномощное М, е_i X для каждого i = 1, n. Над алфавитом Х* = Х {е₁,...,е_n} рассмотрим простую свободную алгебру Менгера F(X*) с селекторами e₁,…, e_n. Пусть - взаимно однозначное отображение Х на М. Рассмотрим определяющие соотношения вида x [y₁,…,y_n] = z, если и только если (х) [ (y₁),…, (y_n)] = (z) и x, y_i, z X. Соответствующее этим соотношениям отношение конгруэнтности на F(X*) обозначим через .

Фактор-алгебру F(X*)/ обозначим через (М*, о*) и будем называть простой алгеброй Менгера, получаемой из (М, о) присоединением полного набора селекторов.

Легко видеть, что (М, о) изоморфно вкладывается в (М*, о*), а подмножество М {e₁,…, e_n} порождает (М*, о*).

На множестве ? (Аⁿ, А), рассмотрим (n+1)-операцию О, которая определяется формулой

₁,…, _n] (a₁,…a_n) = (₁ (a₁,…a_n),…, _n`(a₁,…a_n)), (2)

где для любых a₁,…a_n А обе части равенства определены или не определены одновременно. Легко проверить, что [? (Аⁿ, А), O} является алгеброй Менгера. Гомоморфизм Р алгебры Менгера (М, о) с помощью n-местных преобразований множества А. если Р - изоморфизм, то представление называется собственным.

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

(g₁, g₂) ж P (g₁) P (g₂),(3)

(g₁, g₂) pr_1…n P (g₁) = _1…n P(g₂),(4)

где pr_1…n P (g) - область определения P (g). Алгебраические системы, изоморфные алгебре Менгера будем называть проекционными алгебрами Менгера.

Пусть (М, о) - алгебра Менгера. Бинарное отношение на М называется стабильным, если

(x, y), (x₁, y₁),…, (x_n, y_n) (x[x₁,…,x_n], y[y₁,…, y_n]), (5)

-регулярными, если

(x₁, y₁),…, (x_n, y_n) ) (x[z₁,…, z_n], z[y₁,…, y_n] ) , (6)

l-регулярными, если

(x, y) ) (x[z₁,…, z_n], y[z₁,.., z_n] ) . (7)

Подмножество Н множества М называется i-идеалом, i принадлежит {1,…, n}, если

h H u[x|_i h] , (8)

где x = (x₁,…, x_n) и (x|_i h) есть обозначение вектора (x₁,…, x_i-1, h, x_i+1,…, x_n).

Через Т₀ обозначим множество полиномов алгебры Менгера (М, о) над некоторым бесконечным алфавитом Х, каждая часть которых не имеет вида x[y₁,…, y_n][z₁,…, z_n] и каждая переменная в которых имеет единственное вхождение.

Пусть t T₀, x X. Переменная х называется исходной переменной для полинома t, если за ней непосредственно не стоит левая квадратная скобка, в противном случае х называют неисходной переменной.

Пусть t (x₁,…, x_S, y₁,…, y_r) T₀, где x,…, x_S - полный перечень исходных переменных полинома t, y₁,…, y_r - полный перечень его неисходных переменных, Р (х) - предикат и g - некоторый элемент из М.

Тот факт, что для любых t T_0, i = 1,…, s, a_k, u_k M справедливо условие P (t(g, a₂,… a_s, u₁,…, u_r)), мы будем для краткости записывать просто (t T₀) (P(t(g))). Аналогичное замечание делаем и для квантора существования. Рассмотрим теперь на М бинарное отношение , определяемое формулой

T₀) (g₁ = t (g₂) g₁ = g₂). (9)

Легко убедиться в том, что является l-регулярным.

Определяющей парой алгебры Менгера (М, о) будем называть упорядоченную пару (е, W), где е - частичное отношение эквивалентности на М*, удовлетворяющее условиям:

а) М для каждого i = 1,…, n;

б) если (x₁,…,x_n) е, то g[x₁,…, x_n]=g (e) для всех g;

в) является ?-регулярным в (М*, о*)

(здесь ), а W - подмножество множества М* такое, что если W , то WМ есть i-идеал алгебры (М, о) для каждого i =1,…, n и W является -классом (в противном случае W ).

В случае полугрупп получаются определяющие пары в обычном смысле. С каждой определяющей парой ( будем ассоциировать так называемой простейшее представление Р ₍ алгебры (М, о) следующим образом. Пусть (Н_а)_аА - семейство -классов, отличных от W, заиндексированных взаимно однозначно с помощью элементов множества А, А₀ = {a A| H_a M , e_i H_bi для каждого i = 1,…, n = , B = Mⁿ. Каждому g из М поставим в соответствие n-местное преобразование Р ₍ (g) множества А, определяемое формулой

а = Р ₍ (g) (a₁,...,a_n) (a₁,...,a_n)H_a1,… H_an]H_a (10)

Покажем, что Р ₍ - гомоморфизм. В самом деле,

a = Р ₍(g[g₁,… g_n]) (a₁,…,a_n) (a₁,…,a_n) ??^ g[g₁,… g_n] [H_a1,…

H_an]H_a

(a₁,…,a_n) ??^ g[g₁[H_a1,… H_an],…, g_n [H_a1,… H_an]]H_a

(?c₁,…, c_n)(( a₁,…,a_n), (c₁,…, c_n) ??^ g[H_c1,… H_cn] H_a?))

^ g₁[H_a1,… H_an] ? H_c1^…^ g_n[H_a1,… H_an] ? H_cn)

(?c₁,…, c_n) (a = Р ₍ (g) (c₁,…, c_n)^c_i = Р ₍ (g_i) (a₁,…,a_n))

a = Р ₍ (g) [Р ₍ (g_i),…, Р ₍ (g_n)] (a₁,…,a_n).

Далее легко видеть, что

(g₁, g₂) ж _{(t, W)} (? x B) (g₁ W g₁ = g_2(е)),(11)

(g₁, g₂) _{(t, W)} (? x B) (g₁ W g₁ W).(12)

где ж _{(t, W)} = ж_{Р (t, W)} и _{(е, W)} = ж_{Р (t, W)}.

Необходимо сформулировать и доказать основную теорему: для того чтобы алгебра Менгера вида (М, о, ж, ) и ранга n была собственной проекционной алгеброй Менгера, необходимо и достаточно, чтобы ж было стабильным отношением порядка, а являлось l-регулярным отношением эквивалентности, и чтобы для всех натуральных m и для всех полиномов t_{i, j} T₀ выполнялись условия Г_m, E_m, где

Г_m: g₁ g^g₂ g^ (u_{1, j} [x_l, _j|_ki,j b_{1, j}] = g₁ ^ a_{1, j} =g₁) ^

^{a_{1, 2j-1} b_{1, 2j-1} ^ u_{i, 2j-1} [x_l, _j|_{ki, 2j-1}] v_{i, 2j-1} =

=t_{i, 2j-1} (a_{i+1, j}) ^ a_{1, 2j} b_{1, 2j} ^ u_{i, 2j} [x_l, _j|_{ki, 2j} a_{1, 2j}]

v_i,2j = t_{i, 2j} (u_{i+1, j}[x_i+l, _j|_ki+1,j b_{i+1, j}])}

a_{m, 1} b_{m, 1} ^ u_{m, 1} [x_m, _j|_{km, 1} a_{m, 1}] v_{m, 1} = t _{m, 1} (g₂) g₁ g₂.(12)

E_m: (u_{1, j} [x_l, _j|_{k1, j} b_{1, j}] = g₂^a_{1, j} = g₂^u_{-1, j} [x-_l, _j|_{k-1, j} b-_{1, j}] =

=g₁^a_-1,j = g₁) ^ {a_{i, 2j-1} b_{i, 2j-1}^u_{i, 2j-1} [x_l, _2j-1|_{ki, 2j-1} a_{i, j-1}]

vt_{i, 2j-1} = _{i, 2j-1}(a_{i+1, j}) ^ a_{i, 2j} b_{i, 2j}^u_{i, 2j} [x_l, _2j|_{ki, 2j} a_{i, 2j}] v_{i, 2j}=

= t_{i, 2j} (u_{1+1, j} [x_i+1, _j|_{k i+1, j} b_{i+1, j}])^ a_{-I, 2j-1}

b_{-i, 2j-1} ^ u_{-i, 2j-1} [x_{-I, 2j-1}|_k -_{i, 2j-1} a_{-i, 2j-1}]v_{-i, 2j-1} = t_{-i, 2j-1} (a_{-i-1, j}) ^

^ a_{-i, 2j} b_{-i, 2j} ^ u_{-i, 2j} [x_{-i, 2j}|_{k -i, 2j}] ]v_{-i, 2j} =

= t_{-i, 2j} (u_-i-1 [x_{-i-1, j} |_k -_{i-1, j}])} ^ a_{m, 1}

b_{m, 1} ^ u_m,1 [x_{m, 1}|_{k m,1} a_{m, 1}]v_m,1 = t_{m, 1} (g₁)^

^a_{-m, 1} b_{-m, 1}^ u_{-m, 1} [x_{-m, 1}| _{k -m, 1}a_{-m, 1}] v_{-m, 1} = t_{-m, 1} (g₂) g₁ = g₂,(13)

где g₁g₂ (g₁, g₂) ж, g₁ = g₂ (g₁, g₂) , a_{i, j}, b_{i, j}, v _{i, j}, g_i M, u_i,j

M {e_ki,j}, k_{i, j} {1,…, n}.

Из данной теоремы вытекает следствие: для того чтобы полугруппа (G, ж, ) с выделенными на ней бинарными отношениями ж и была собственной проекционной полугруппой преобразований, необходимо и достаточно, чтобы ж было стабильным отношением порядка, -регулярным слева отношением эквивалентности и чтобы для любого натурального т выполнялись условия D_m, Н_т, где

D_m : g₁ g^g₂g (b_{1, j}x_{1, j} =g₁^ a_1,j = g₁)^

{a_{i, 2j-1} b _{i, 2j-1} ^ a _{i, 2j-1} x _{i, 2j-1 i, 2j-1} = a_i+1 y _{i, 2j-1} ^

^a_{m, 1} b _{m, 1} ^ a _{m, 1} x _{m, 1} v _{m, 1} = g₂ y _{m, 1} g₁ g₂;(14)

H_m : (b_1, j x_{1, j} = g₂ ^ a_{1, j} = g₂ ^ b_{-1, j} x _-1,j = g₁ ^ a _{-1, j} +g₁) ^

{ a_{i, 2j-1} b _{i, 2j-1} ^ a _{i, 2j-1} x _{i, 2j-1 i, 2j-1} = a_i+1 y _{i, 2j-1} ^

^a_{i, 2j} b_{i, 2j} ^ a_{i, 2j} x_{i, 2j} v_{i, 2j} = b_i+1, _j x_i+1, y_{i, 2j}} ^

^ a_{m, 1} b_{m, 1} ^ a_{m, 1} x_{m, 1} v _{m, 1} = g₂ y_{m, 1} g₁ g₂;(15)

H_m: (b_{1, j} x₁, j = g₂ ^ b_{-1, j} x_{-1, j} =g₁^ a_{-1, j} = g₁) ^

{a_{i, 2j-1} b _{i, 2j-1} ^ a _{i, 2j-1} x _{i, 2j-1 i, 2j-1} = a_i+1 y _{i, 2j-1} ^

^a_{i, 2j} b _{i, 2j} ^a _{i, 2j} x _{i, 2j} v _{i, 2j} = b _{i+1, j} x _{i+1, j} y_{i, 2j} ^

^a_{-i, 2j-1} b_{-i, 2j-1} ^ a_{-i, 2j-1} x-_{i, 2j-1} v_{-i, 2j-1} = a_{-i-1, j} y_{-i, 2j-1}^

^ a-_{i, 2j} b_{-i, 2j} ^a_{-i, 2j} x_{-i, 2j} v_{-i, 2j} = b_{-i-1, j} x_{-i-1, j} y _{-1, 2j}}^

^a_{m, 1} b _{m, 1}^ a _{m, 1} x _{m, 1} v _{m, 1} = g₁ y _{m, 1} ^

^a _{-m, 1} b_{-m, 1} ^ x_{-m, 1} v _{-m, 1} = g₂ y_{-m, 1} g₁ = g₂(16)

где x_i,j у _i,j могут быть пустыми символами.

упорядоченный алгебраический многоместный функция