Алгебра и логика, 40, N 2 (2001), 202-217
УДК 512.56/.57:510.57
О ЗАМКНУТЫХ КЛАССАХ ФИНАЛЬНО ПЕРИОДИЧЕСКИХ ФУНКЦИЙ А. П. СЕМИГРОДСКИХ В ведение
Замкнутым по суперпозиции классам функций над счетным множе ством посвящен ряд работ. В частности, большое внимание уделено за мкнутым классам рекурсивных функций. Обзор результатов, касающихся в основном базисов таких классов, содержится в [1]. В настоящей работе мы приступаем к изучению внутреннего строения замкнутых классов из некоторого частично упорядоченного множества У, "пронизывающего" ре шетку всех замкнутых классов примитивно рекурсивных функций. Опре деление множества IP будет дано ниже, после введения понятия рекурсивно замкнутого класса. Сейчас лишь отметим, что основная часть статьи по священа изучению классов из У, порожденных константами с помощью стандартных итеративных операций и примитивной рекурсии. Как оказа лось, эти классы тесно связаны с понятием периодичности. Периодические функции — это стандартный математический объ ект. Нередко встречаются и такие непериодические функции, подходящие ограничения которых являются периодическими. Понятие периодичности можно распространить и на функции от многих переменных: ОПРЕДЕЛЕНИЕ. Функцию / : N§ -» No назовем финально периоди ческой с периодом p G N, если существует т £ No такое, что для любых г ^ к и а\,...
©
, ak E No функция
Сибирский фонд алгебры и логики, 2001
О замкнутых классах финально периодических функций
203
д(х) = / ( а ь . . . ,at-_i,ar + m,a t - + i,... , ak) периодична с периодом, делящим р. Здесь, как обычно, через N обозначается множество натуральных чи сел и No = NU{0}. В настоящей работе рассматриваются только функции, являющиеся операциями на множестве No. Нульместные функции обыч ным образом отождествляем с константами и считаем их финально пери одическими функциями. Везде далее на константы будем смотреть и как на элементы из No, и как на константные функции от подходящего числа переменных. Число р из определения финально периодической функции будем иногда называть ее периодом. Очевидно, что такой период не будет единственным. Для точной постановки задачи потребуются определения пяти стан дартных итеративных операций. От первоначальных определений из [2] они отличаются лишь тем, что действие указанных операций естествен ным образом распространяется на нульместные функции. Введем вначале наиболее важную из них — подстановку, обозначаемую через *. Для fc-мест ной функции / и m-местной функции g определим (к + т — 1)-местную функцию h = / * g, полагая h(xu
• • • , Xk+m-l)
= /(fffai, • • • , Жт), Ж т + Ь . . . , £fc+m-i).
(1)
Далее, для к > 1 определим операции (, г и Д: (С/)(яь--- ,хк) = / ( ж 2 , . . .
,xkjxi),
( г / ) ( я ь Ж 2 , я з , . . • ,Zk) = /(ж 2 ,Ж1,жз,... ,ж*),
(2)
(А/)(Ж1,... , ^ - i ) = /(ж1,Ж1,ж 2 ,... ,a*_i), и для fc E No определим операцию V: (V/)(a> b ... ,3*+i) = / ( ж 2 , . . . ,a?fc+i).
(3)
Далее необходима и операция /?(/,
204
А. П. Семигродских
ется (к + 1)-местная функция /i, определяемая рекурсивно по схеме: h(xu...
,a*,G) = / ( ж ь . . . ,а*),
h(xu . . . , хк, у + 1) = sr(z b . . . , хк, у, Л(а? ь ... , ж*, у)).
,. ч (4)
Операции *, (, г, Д и р заданы в (1), (2) и (4) для функций только определенных арностей. Для всех остальных случаев полагаем значение каждой из этих операций равным ее первому аргументу (т. е. функции / , если пользоваться обозначениями из (1), (2) и (4)). Замкнутыми
классами будем называть классы функций, замкну
тые относительно стандартных итеративных операций. Замкнутые клас сы, которые замкнуты еще и относительно примитивной рекурсии, будем называть рекурсивно замкнутыми. Пусть F — произвольное множество функций. Замкнутый класс, порожденный F , обозначим через (F). Ана логично, ((F)) будет обозначать наименьший рекурсивно замкнутый класс, содержащий F. Известно, что ((0,ж,х + 1)) — это в точности класс всех примитивно рекурсивных функций. Пусть £ р г — решетка по включению всех замкну тых подклассов этого класса, а £ с — решетка всех замкнутых подклассов класса {0,а;,ж + 1). Частично упорядоченное множество З5, упомянутое в самом начале данной работы, определим как множество
{((С)) I с е М Это множество является частью решетки £ р г , а наибольший и наимень ший элементы из множества У совпадают соответственно с наибольшим и наименьшим элементами этой решетки. Результаты настоящей работы по казывают, что множество 7 континуально, т. е. имеет мощность, совпадаю щую с мощностью решетки £ р г . Данные соображения, на наш взгляд, по зволяют полагать, что элементы из 7 могут быть использованы как опор ные точки при изучении решетки £ р г , а в конечном итоге и всей решетки замкнутых классов над множеством No. В связи с этим было бы инте ресно выяснить строение как самого множества IP, так и его классов. В данной работе совершается первый шаг в этом направлении и дается пол ное описание рекурсивно замкнутых классов, порожденных множествами
О замкнутых классах финально периодических функций
205
констант (класс всех констант, очевидно, содержится в (0, х,х + 1)). При ведем основные результаты статьи: Т Е О Р Е М А . Пусть с 0 , . . . , с п _ х — попарно различные
константы
из множества No. Тогда ((со, • •. , cn_i)) совпадает с классом всех прини мающих значения из {CQ, . . . , c n .-i} финально периодических функций с периодами, делящими натуральные степени числа (п\). С Л Е Д С Т В И Е 1. Пусть { c 0 , c i , . . . } — бесконечное
множество
констант из NQ. Тогда ((со, Ci,...}) совпадает с классом всех принимаю щих значения из {со,Сх,...} финально периодических
функций.
С Л Е Д С Т В И Е 2. Класс ((No)) совпадает с классом всех финально периодических
функций.
Из приведенных результатов вытекает, что различные множества констант порождают различные рекурсивно замкнутые классы. Это озна чает, в частности, что множество У континуально. Основную часть работы составляет доказательство теоремы. Оно естественным образом разбито на две части. В первой (§ 1) докажем, что ((со, -.. , c n _i)) содержит только принимающие значения из {со,... , c n _i} финально периодические функции с периодами, делящими натуральные степени числа п!. Во второй части (§2) покажем, что все такие функции лежат в указанном классе. После этого докажем следствия теоремы. До конца доказательства фиксируем класс ((со,... , Cn-i)) и обозначаем его через С. Множество {со,... , сп_х} обозначим через 5. Класс всех прини мающих значения из 5 финально периодических функций с периодами, делящими натуральные степени числа п!, обозначим через К. Таким об разом, в первой части доказывается, что С С А', а во второй части — обратное включение.
§ 1. Первая часть доказательства теоремы Класс К обладает следующими двумя свойствами. Во-первых, он со держит множество 5. Во-вторых, он рекурсивно замкнут. Первое из этих
206
А. П. Семигродских
свойств очевидно, второе будет доказано далее. Класс С является наи меньшим классом, обладающим этими двумя свойствами. Таким образом, доказав второе свойство для класса ЛГ, мы докажем требуемое включение С С К. Легко проверить, что если все значения двух функций лежат в 5 , то после применения к ним стандартных итеративных операций или прими тивной рекурсии получаются функции, удовлетворяющие этому же усло вию. Значит, достаточно проверить, что упомянутые операции при при менении к финально периодическим функциям с периодами, делящими натуральные степени числа п!, дают функции с таким же свойством. Это утвержение легко проверить для операций ( , г и У . Последующие три лем мы посвящены его доказательству в оставшихся нетривиальных случаях. ОПРЕДЕЛЕНИЕ. Минимальные р и га, при которых выполняется свойство, сформулированное для / в определении финально периодиче ской функции, будем обозначать через p(f) и га(/) соответственно (для каждой константы cG No полагаем т(с) = 0 и р(с) = 1). Будем говорить, что функция f(x\,...
, Xk) финально периодична по i-й переменной с пери
одом р £ N, если это свойство выполняется при данном фиксированном г. Заметим, что если функция финально периодична по всем перемен ным, то она просто финально периодична с периодом, равным наимень шему общему кратному периодов по всем своим переменным. Нам придется достаточно часто рассматривать функции от многих переменных. Чтобы облегчить работу с ними, воспользуемся следующи ми обозначениями. Предположим, что в записи функции / ( # i , . . . ,a?*) участвует последовательность переменных ж/,... , ж т (/ ^ т ^ к). Если у = (ж/,... , ж т ) , то в записи мы будем заменять эту последовательность на у. Например, если i ^ fc, xf = (a?i,... , #t-i) и xfl = (ж,-+1,... , #&), то f(x',Xi,x")
= / ( 3 Ь . . . ,Хк).
Л Е М М А 1. Для любого f € К имеем (Д/) € А'. ДОКАЗАТЕЛЬСТВО. Возьмем произвольную m-местную функцию / из класса К. Если m ^ 1, то Д / = / и наше утверждение очевидно.
О замкнутых классах финально периодических функций
207
Пусть теперь m > 1. Введем Л(а?1,... , £ m - l ) = ( Д / ) ( ж Ь . . . , £ m - i ) = /(Ж1,Ж1,ЯГ 2 ,... , 3 m - l ) -
Легко проверить, что /г финально периодична по а?2,..- , ж т - ь
и ее
пе
риод равен периоду функции / . Докажем, что h финально периодич на по xi с тем же периодом. Возьмем произвольные а 2 , . . . , a m „ i E No, о! = ( а г , . . . , a m - i ) и aj ^ тп(/). Достаточно доказать, что h(ai+p(f),af)
=
= /1(01,5'). Воспользовавшись финальной периодичностью / и тем, что a
i £ m(f)j
получаем h(aua')
= f(auai,
a') = / ( a i + p ( / ) , a b a')
= /(*i + p ( / ) , a i + P ( / ) i S 0 = Mai + P ( / ) , S / ) . Функция / принадлежит /<", функция /i финально периодична с тем же периодом, что и / . Значит, h £ К. Л Е М М А 2. Для любых /, g £ К имеем ( / * # ) € К. ДОКАЗАТЕЛЬСТВО. Рассмотрим fc-местную функцию / и г-местную функцию #, которые принадлежат К. Пусть /i = / * ^ , T . e . Л(а?1,... ,x fc +r~i) = / Ы ^ ъ - - ,а?г),ж г + 1,... ,«jb+r-i). Очевидно, что h финально периодична по # i , . . . ,жг с периодом р(д), а по ж Г + 1 , . . . ,а:^ + г-1 ~~ с периодом р ( / ) . Значит, /i финально периодич на с периодом, равным НОК(р(/),р(^)). Предположим, что <7(/)|(rc!)rf*. Тогда период функции /i делит (n\)df(n\)d^
p(f)\{n\)df,
= (п}.)*1?^, т.е.
делит натуральную степень числа п\. Следовательно, h £ К. Л Е М М А 3* Для любых f^g £ К имеем p(f,g) £ К. ДОКАЗАТЕЛЬСТВО. Рассмотрим произвольные / , д £ К. Если вы полняется равенство p(f,g) = / , то требуемое очевидно. Если / и д явля ются fc-местной и (к + 2)-местной функциями соответственно, то положим Л — p(/,flr). Проверим, что h финально периодична по всем переменным. Сна чала рассмотрим первые к переменных, а потом последнюю. Возьмем
208
А. П. Семигродских
произвольную из первых к переменных. Не ограничивая общности, мож но считать, что это первая переменная. Пусть рь =
HOK(p(f))p(g)),
rrih = max{ra(/), m(#)}, xf = (a; 2 ,... ,#*;). Докажем, что при Х\ ^
тд
для любых у € No выполняется равенство h(xx +рньх',у)
h{xuxf,y),
=
и тогда /i финально периодична по #! с периодом p/j. Доказательство про ведем индукцией по у. При у = 0, учитывая, что / финально периодична, имеем h{xi + ph,xf,Q)
= f(xi +Ph,xf) = / ( ^ ь ^ ) = /1(ж1,ж',0).
Теперь, предположив, что для у требуемое свойство установлено, до кажем его справедливость и для у + 1. Воспользовавшись предположением индукции и тем, что g финально периодична, получаем h{xi + ph, ж', у + 1) =flf(a?i+ рн, ж', У, Л(а?1 + рь, я', у)) = g(x\ + Ph, *', у, h(xux', =
у))
g(xhx',y,h{xux',y))
- h(x1,x',y+
l).
Итак, h финально периодична по a?i,... , а^. Осталось рассмотреть последнюю переменную. Возьмем произвольные a i , . . . , a & 6 No, a — = ( а ь . . . ,a*J. Пусть Ga(y,z) = g(au...
,ak,y,z),
Hu(y) = ft(ab... ,a*,$/).
Функция G« финально периодична с периодом р(у) и m(Ga) ^ гп(у). До кажем, что Я 5 финально периодична с периодом, делящим некоторую на туральную степень числа п\. Согласно (4) имеем #а(0) = Д а ь - - - >а*)> ffa(y+l)=G5(y,tfa(y)). Рассмотрим последовательность 5^ = Ha(m(g) + *p(fif) + 1), t G N. Все зна чения функции Я й лежат в конечном n-элементном множестве 5 . Поэтому найдутся такие t,T £ No, что £ < Т, Т — J ^ n и з* = ST, т. е. Ha{rn{g) + tp(g) + 1) - Я й (ш(у) + Гр( 5 ) + 1).
О замкнутых классах финально периодических
функций
209
Выберем минимальные t и Т с данными свойствами. Воспользовавшись свойствами функции G&, имеем Ha(m(g) + tp(g) + 2) = Gu(m(g) + tp{g) + 1, Я а (ш( 5 ) + tp( fl ) + 1)) = Ga(m(g) + tp{g) + 1, st) = Gu{m{g) + tp(g) + 1,s T ) = Gu{m(g) + Tp(g) +
l,sT)
= G * M $ ) + Tp(flf) + 1, Я й (ш( 9 ) + 2>(y) + 1)) = Hs{m{g) + Tp(g) + 2). Итак, Яа(га(у)+£р(у)+2) = Ha(m(g)+Tp(g)+2). получаем Ha(m(g)+tp(g)
Продолжая по индукции,
+ m) = Яа(т(у) + Тр(у)-|-га) для любого т £ N.
Тогда функция Я 5 (у) = Ha{rn(g) + *р(#) + У + 1) периодична с периодом (Г - t)p(g). При этом m(Ha) ^ m(g) + tp{g) + 1. Итак, для любых a i , . . . , a^ € No функция Я й (у) = fc(oi,... , а*, у) финально периодична с периодом тп5р(у), где 1 ^ гай ^ п. Если удастся доказать, что существует число М £ No такое, что для любого а £ No* функция Нй(у + М) периодична, то тем самым будет доказано, что h финально периодична по последней переменной с периодом, равным по крайней мере п\р{д). Пусть q = max{m(/), m(g)} + HOK(p(/),p(ff)) и M = тах{га(Я б ) | Я а (у) = Л ( а ь . . . ,а*,у), где 0 ^ а 1 : . . . ,а* ^ д}. Пусть теперь a i , . . . ,а* € No. Если 0 ^ ai,...
}a,k
^ #, то Нй{у + М)
периодична. Если щ > q для некоторого г, то для любого такого г имеем а{ = max{m(/),m(flf)} + *f-HOK(p(/),p(flf)) + г,-
(5)
при некоторых fc^r, e No, где г,- < НОК(р(/),р(
{ Функция
а3,
если а,- ^ q,
(б) max{rn(/), га (у)} + Vj в противном случае. h финально периодична по а?1,...,а;* с периодом
НОК(р(/),р(
210
А. П.
Поскольку 0 ^ а[,... Итак,
h
, afk ^ q, функция #«(?/ + М) периодична.
финально
HOK(p(f)}p(g))
Семигродских
периодична
по
#1,...,а;&
с
периодом
и по последней переменной с периодом п\р(д).
чит, h ф и н а л ь н о периодична с периодом n\HOK(p(f),p(g)),
Зна
который,
безусловно, делит какую-нибудь натуральную степень числа п!, так как этим свойством обладают p(f)
и р(д). Лемма доказана.
Таким образом, класс К рекурсивно замкнут. К а к уже говорилось ранее, тогда С С К.
§ 2. В т о р а я часть д о к а з а т е л ь с т в а т е о р е м ы
Д о к а ж е м , что К С С. Д л я этого достаточно построить все функции класса /<", применяя к константам из S стандартные итеративные операции и примитивную рекурсию. Заметим, что с помощью этих операций из fc-местной функции / и (fc-f 1)-местной функции д можно легко получить (&-+-1)-местную ф у н к ц и ю /г, определяемую следующим образом: h(xu...
,ж*,0) = f{xu...
h{xu...
,xk,y+
,xk)>
1) = д(хь...
,xk,y).
Далее неоднократно используется следующая (основанная на этом факте) Л Е М М А 4 . Пусть / о , . . . , / т ная функции}
j
—- натуральное
((в, /о> • • • j / т ) ) содержится
— k-местные
число,
ид
— (к + 1)-.мест
не превосходящее
(к + I)-местная
функция
к.
h такая,
Тогда
в
что
h(xf, г, х") = / , ( я ' , х") для всех г 6 { 0 , . . . , гп}, /г(ж', у + т + 1, ж") = у(я', у, я " ) , г
О замкнутых классах финально периодических функций
211
га(/) = 0. Такие функции будем называть периодическими. После этого докажем, что К С С. Центральным утверждением второй части доказательства теоремы является следующее П Р Е Д Л О Ж Е Н И Е . Класс С содержит все периодические функ ции из класса К. ДОКАЗАТЕЛЬСТВО будем вести индукцией по числу переменных. База индукции выполнена, так как все нульместные функции из К лежат в С. Дальнейшие рассуждения, оформленные в виде лемм 5—7, относятся к шагу индукции. Предполагаем, что для fc-местных периодических функ ций наше утверждение доказано. Следует доказать его для (& + 1)-местных функций. Для удобства работы с функциями от к и более переменных до конца работы вводим обозначение х = (хi,...
, ж&). Нам понадобится следующее
ОПРЕДЕЛЕНИЕ. Циклом (к + 1)-местной периодической функции / , периодичной по последней переменной с периодом р, называется кортеж fc-местных функций (/(ж,О),... , / ( х , р - 1)). Л Е М М А 5. Если в С лежит (к + 1) -местная периодическая функ ция f, периодичная по последней переменной с периодом р, то в С лежит и периодическая функция с циклом (f(x,p-l)J(x,Q),...
J(x,p-2)).
(8)
ДОКАЗАТЕЛЬСТВО. Рассмотрим fc-местную периодическую функ цию /о(ж) = f{x,p - 1). В силу предположения индукции она лежит в С. По лемме 4 в С содержится функция h такая, что Цху0) = /о (ж), h(xyy+l)
=
f(x}y).
Тогда h(x,0) = / 0 (ж) = / ( ж , р - 1) =
h(x,p),
h{x, у + 1) = /(ж, у) = / ( г , y + p) = h(x,y +
p+l).
А. П. Семигродских
212
Поэтому h — периодическая функция с циклом, указанным в (8). Из доказанной леммы вытекает С Л Е Д С Т В И Е . Если в С лежит (к + I)-местная
периодическая
функция f с периодом р по последней переменной) то для произвольного натурального г такого, что 2 ^ г ^ р — 1, в С лежит и периодическая функция с циклом ( / ( х , р - г ) , . . . J{x,p-
1),/(ж,0),.-. J{x,p-i-
1)).
Дальнейшее доказательство предложения будет проводиться индук цией по длине р периода по последней переменной. Более точно, будет доказано следующее утвержение: Для любого р 6 N произвольная (к+1)-местная периодическая функ ция f из К с периодом р по последней переменной лежит в С. База индукции очевидна, так как все (к + 1)-местные периодические функции из К с периодом 1 лежат в С; эти функции не зависят от послед ней переменной и получаются из соответствующих fc-местных функций, лежащих в С, добавлением фиктивной переменной (при помощи операций VHC).
Предположим теперь, что наше утверждение доказано для всех (к + 1)-местных функций класса К таких, что их периоды по последней переменной меньше р. Если р не делит никакую натуральную степень числа п!, то наше утверждение очевидно. Пусть р делит (n!) d , где d 6 N. Тогда р = qp\, где q — простое число, не превосходящее п. Число р\ меньше, чем р, поэтому в С лежат все (к + 1)-местные периодические функции из К с периодом Pi по последней переменной. Л Е М М А 6. Класс С содержит одноместную периодическую функ цию с циклом (с0,... ,ср,... ,сд-г,... ,cg-ij. Pi
Pi
О замкнутых классах финально периодических
функций
ДОКАЗАТЕЛЬСТВО. Пусть га = т а х { с 0 , . . . , cn„i}.
213
Рассмотрим
следующую последовательность / о , . . . , / т одноместных периодических функций с периодом р\. Для каждого С{ Е S положим { с , ф Ь если хг = 0 (mod pi), /c,-(si)= S I Cj в противном случае. Здесь ф —- сложение по модулю q. Для к £ S положим fk{%\) = со (эти оставшиеся функции будут мало влиять на дальнейшие построения и вво дятся для более формального использования леммы 4). По предположению индукции в классе С лежат все (к + 1)-местные функции из К с периодом Pi, в том числе те, которые существенно зависят только от одной пере менной. Значит, классу С принадлежат и все одноместные функции из К с периодом рх. Очевидно, все /t- (0 ^ г ^ т) периодичны с периодом рх и, следовательно, принадлежат классам С и К. По лемме 4 в С имеется двуместная функция hx такая, что hx(xx)i) = fi{xx) для всех г £ {О,... , т } , hi(xi,y
+ m+ 1) = с 0 .
Функция hx обладает следующими очевидными свойствами: 1) hi{lp\, С{) = с,-ф1 для / G N0, 0 ^ г < п - 1. 2) fti(#i,c,-) = С{ для ^i ^ 0 (mod pi), 0 ^ г ^ п - 1. 3) М ж 1 + lpi,Ci) = М ж ь с * ) для / £ No, 0 ^ г ^ n - 1. Построим функцию \i2 G С следующим образом: МО) =
(9)
Л2(У+1)=Л1(У,МУ))«
Теперь, воспользовавшись свойствами функции /&i, докажем, что /г2 периодична с циклом (с 9 _1,сь,... , с о , . . . , c g _ 2 , . . . ,c g -. 2 j c g _i,... ,с 9 _ х ) Ч
"
N*
Р\
длины р.
"
^
^ . .
pi
—
.•
N
^
P!-l
•
(10)
А. П. Семигродских
214
Согласно (9) и свойствам 1 и 2 функции /ii, имеем h2(Q) = cq-U Л2(1) = . . . = M P i )
=
С
О,
M ( ? ~ l)pi + 1) = . . . = h2(qpi) = c g -i, т.е. первые р значений функции h2 образуют кортеж (10) и h2(p) = c g _i. Аналогично, воспользовавшись свойством 3 функции /ц, индукцией по / £ G No, легко доказать равенства h2(lp) = с 9 _ ь /г 2 (/р+1) = . . . = М Ф + Pi) = с 0 ,
М * Р + ( 9 - l)Pi + 1) = . . . = M*P + ?Pi) = ^ „ ь Значит, h2 периодична с циклом (10). Применяя к h2 следствие из леммы 5 (для г = р — 1), получаем, что в С лежит искомая одноместная периодическая функция с циклом (со,... , с 0 , . . . ,
v*——' s ' v Pi
Pi
Л Е М М А 7. Для произвольных k-местных периодических /о? •••> / p - i
W3
-К" в классе С найдется (к + 1)-местная
функций
периодическая
функция с циклом (/о,... , /p-i). ДОКАЗАТЕЛЬСТВО. Из предположения индукции по к имеем, что функции / о , . . . , fp-\ лежат в С. Предположение индукции по р дает, что класс С также содержит (к + 1)-местные периодические функции hi (0 ^ $С г ^ q — 1) с циклами (/, Р 1 ,... , /(t+i) P l -i), имеющими длину р\. По лем ме 4 в С имеется (к + 2)-местная функция Н со свойством H(x,y,Ci) = hi(x,y), где 0 ^ г ^ g - 1. По лемме б класс С содержит одноместную периодическую функцию h с циклом (с 0 , . . . , Сд, .. . ,Сд-1, • Pi
Pi
,Cq-i).
О замкнутых классах финально периодических функций Пусть f{x,y)
= H(x,y,h(y)).
215
Тогда /является искомой функцией. В са
мом деле, возьмем произвольное I 6 No и j € No, меньшее р, и докажем равенство / ( я , /р + j) = /j(&). Представим число j в виде j = ipi + г, где О ^ г ^ # - 1 и 0 ^ г ^ pi - 1. Получим / ( * , ' Р + i ) = Н{х, lp + j , h(lp + j)) = Я(ж, lp + ipi + r, h(lp + ipi + r)) = H(x, lp + ipi + г, с,-) = fef-(»,Zp+ipi + r ) = /1,(ж,г) = /| Р1+Г (ж) =
fj(x).
Таким образом, функция / периодична с циклом (/о, • • • »/p-i)Лемма 7 завершает доказательство предложения, так как каждая (fc + 1)-местная периодическая функция полностью определяется своим циклом, а каждый элемент ее цикла является fc-местной периодической функцией. Итак, все периодические функции из К лежат в С Из следующей леммы вытекает аналогичный результат и для финально периодических функций из К. Л Е М М А 8. Для любой k-местной функции f класса К и произ вольного натурального I, не превосходящего к, найдется функция h из С со свойством h(x) = /(жь . . . , я/, xi+i + m ( / ) , . . . , xk +
m(f)).
ДОКАЗАТЕЛЬСТВО будем проводить индукцией по к. Для к = О лемма очевидна. Рассмотрим шаг индукции — установим его индукцией но /. Прежде всего заметим, что согласно доказанному предложению в классе С лежит периодическая функция #, определяемая равенством д(хи . . . , хк) = f(xx + m ( / ) 7 . . . , хк + m ( / ) ) . Воспользовавшись этим фактом, в качестве доказательства базы индукции по / продемонстрируем, что в классе С лежит функция h(xu ... ,хк) = f{xu х2 + т ( / ) , . . . , хк + ш ( / ) ) .
А. П. Семигродских
216
Доказательства шага и базы индукции совершенно аналогичны друг другу, поэтому приведем только доказательство базы. В силу предположения индукции по к в С лежат все (к - 1)-местные финально периодические функции класса К. В частности, класс С содер жит функции fi (0 ^ г ^ rn(f) - 1), определяемые равенствами Л(Я2, •. • , Хк) = f{h Х2 + m(f),...
, хк + ш ( / ) ) .
По лемме 4 в С лежит функция h такая, что h(i,x2,...
,ж*) = /t(a? 2 ,.. • ,3*) Для всех г Е { 0 , . . . , т ( / ) - 1},
Л(у + т ( / ) , ж 2 ,... , ж*) = flf(y, а? 2 ,... , хк). Из определений функций fi и g получаем h(xu . . . , хк) = / ( ^ i , ж2 + т ( / ) , . . . , xfc + m ( / ) ) , что и требовалось. Доказательство шага индукции по / отличается лишь тем, что вместо функции g используется функция / ( s i , . . . ,а/_1,ж/ + га(/),... ,а?*-г т ( / ) ) , а лемма 4 применяется для j = /. ДОКАЗАТЕЛЬСТВО следствий из теоремы. Первое следствие осно вывается на том, что любая алгебра будет объединением всех своих под алгебр, порожденных конечными подмножествами из порождающего мно жества этой алгебры. Если взять в качестве основного множества алгебры класс ((со, ci,...)), в качестве операций - (, г, Д, V, * и />, а в качестве порождающего мно жества — {со, Ci,...}, то «<*, с ь ...» - (J{«cd,... , с п _!» | n € N}. Воспользовавшись теоремой и этим равенством, легко получаем первое следствие теоремы. Второе следствие является частным случаем первого.
О замкнутых классах финально периодических функций
217
ЗАМЕЧАНИЕ. Выше получено описание довольно большой (по мощ ности) части классов из У. Применив использованную в данной работе технику, можно получить описание и некоторых других классов. Однако в GP имеются классы, которые, по-видимому, требуют для своего изучения несколько иного подхода. К таким классам относятся классы вида ({ж, с)) и ((х + с)), где с является произвольной константой из No- Более того, к опи санию таких классов некоторым образом сводится описание всех классов из 3\ Автору неизвестно строение этих классов, поэтому в явном виде воз никает следующая задача: получить описание классов ((#, с)) и ((х + с)). Ее решение позволит завершить построение частично упорядоченного множе ства У и приступить к более подробному изучению решетки £ р г , "скелетом" которой и является У. В заключение автор благодарит С.С.Марченкова и А.П.Замятина за полезные замечания, которые были учтены при подготовке данной ра боты. Автор также благодарит всех участников семинара "Дискретная ма тематика", руководимого Е.В.Сухановым, принявших активное участие в обсуждении изложенного здесь результата.
ЛИТЕРАТУРА 1. С. С. Марченков, Базисы по суперпозиции в классах рекурсивных функций, в сб. "Математические вопросы кибернетики-3", 1991, 115—139. 2. А. И. Мальцев, Итеративные алгебры Поста, Новосибирск, НГУ, 1974.
Адрес автора: СЕМИГРОДСКИХ Александр Павлович, РОССИЯ, 620061, г. Екатеринбург, ул< Главная, 26-8. Тел.: (3432) 26-74-43, e-mail: [email protected]
Поступило 20 августа 1999 г.
