Решетки замкнутых классов функций на бесконечном множестве тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

СЕМИГРОДСКИХ Александр Павлович

Решетки замкнутых классов функций на бесконечном множестве

.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург, 2003

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета в г. Екатеринбурге.

Научный руководитель:

кандидат физико-математических наук, доцент Е. В. Суханов

Официальные оппоненты: доктор технических наук, профес-

сор В. Г. Лабунец

кандидат физико-математических

наук, доцент И. А. Мальцев

Ведущая организация:

факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова

Защита диссертации состоится 28 октября 2003 года в 15 часов на заседании диссертационного совета Д 004.006.03 при институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. Софьи Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан_сентября 2003 г.

Ученый секретарь

диссертационного совета д.ф.-м.н., с.н.с

В. В. Кабанов

2оо5 -А

1 Общая характеристика работы

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

Данная работа посвящена изучению суперпозиции функций на бесконечном множестве.

Уже в девятнадцатом веке существовал интерес к алгебраическим свойствам суперпозиции вещественных функций. В двадцатом столетии наибольший резонанс в этой области вызвали работы А. Н. Колмогорова [4] и В. И. Арнольда [1], которые доказали представимость всякой вещественной непрерывной функции от п переменных в виде суперпозиции непрерывных функций двух переменных, тем самым опровергнув предположение, высказанное в формулировке тринадцатой проблемы Гильберта [10].

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

Еще одним естественным классом функций, для которого рассматриваются вопросы, связанные с суперпозицией, является класс рекурсивных функций. Одной из важных задач в этой области является нахождение базисов по суперпозиции для некоторых его специальных подклассов (см. обзор [7]).

Как и многие другие конкретные объекты, изучаемые в общей алгебре (например, многообразия групп, полугрупп или колец), замкнутые классы на фиксированном множестве А удобно классифицировать при помощи решетки С а по включению, которую они образуют. Полностью описать решетку т. е. построить ее диаграмму, удалось лишь в одном нетривиальном случае (при |Л| = 2, см. [11]), эта решетка оказалась счетной. Этот результат Э. Поста вряд ли

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

ОЭ

может быть повторен при | > 2. В частности, если множество А бесконечно, мощность множества дуальных атомов решетки С а совпадает с мощностью всей решетки С а и равна 22'Л1 (см. [12]), и неизвестно, является ли Са дуально атомной. Кроме того, при |Л| > 3 в решетку Са изоморфно вкладывается любая решетка, являющаяся прямым произведением не более чем счетного числа конечных решеток [3].

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

1. замкнутые классы на произвольном бесконечном множестве,

2. замкнутые классы на счетном множестве.

В соответствии с этим диссертационная работа разбита на две главы.

В первой главе внимание сосредоточено на замкнутых классах многочленов над полем, поскольку такие многочлены являются одними из наиболее известных и часто используемых функций, и любое бесконечное множество может быть превращено в поле введением подходящих операций. Многие задачи, касающиеся построения функций с помощью суперпозиции, решались в предположении, что в суперпозиции всегда могут участвовать некоторые простые функции. В первой главе в качестве таких простых функций выступают линейные формы над полем К. В терминах решетки замкнутых классов задача первой главы состоит в изучении интервала [Ь°к, Г к] между замкнутым классом Ь°к линейных форм и замкнутым классом Рк всех многочленов над К. В рамках этой задачи естественно возникают следующие вопросы:

1. От каких свойств поля К зависит строение интервала \Ь®К, Р^]?

2. Какова мощность интервала [Ь^^к]?

3. Удовлетворяет ли интервал [Ь°к,Рк\ какому-нибудь нетривиальному решеточному тождеству?

Именно на эти вопросы отвечает первая глава диссертации.

Во второй главе рассматриваются примитивно рекурсивные функции, которые образуют очень широкий и важный класс вычислимых функций. Решетка £рг замкнутых классов примитивно рекурсивных функций слабо изучена, поэтому в работе акцент сделан на построении некоторого континуального "каркаса" V этой решетки, т. е. ее подмножества такого, что любой ее элемент находится в решеточном интервале между подходящими замкнутыми классами из этого подмножества. Рассматривая эти интервалы, можно более подробно изучить строение решетки £рг. Отправной точкой для построения частично упорядоченного множества V служит решетка Сс 1 замкнутых подклассов замкнутого класса, порожденного функциями О, х и х + 1, которые являются базовыми при построении примитивно рекурсивных функций. Множество V строится как множество замыканий классов решетки Сс\ относительно примитивной рекурсии и суперпозиции. При выбранном подходе к изучению замкнутых классов примитивно рекурсивных функций прежде всего возникают следующие вопросы:

1. Каковы основные элементы строения решетки £с|?

2. Каково строение частично упорядоченного множества VI

3. С помощью каких естественных свойств функций без использования рекурсивного замыкания можно задать элементы множества VI :

Ответам именно на эти вопросы и посвящена вторая глава диссертации.

В работе используются методы, конструкции и результаты теории клонов, а также теории полугрупп, решеток и колец.

Все основные результаты диссертации являются новыми и снабжены полными доказательствами.

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

Основные результаты диссертации опубликованы в работах [13]--[21]. Эти результаты докладывались на алгебраической конференции памяти Фадцеева (Санкт-Петербург, 1997 г.), конференции

Свердловского областного конкурса студенческих работ (Екатеринбург, 1997 г.), XX конференции молодых ученых механико-математического факультета МГУ (1998 г.), конференции " Мальцевские чтения" (Новосибирск, 1998 г.), конференции "Логика и приложения" (Новосибирск, 2000 г.), XXVII конференции молодых алгебраистов (Кайзерслаутерн, Германия, 2002 г.), конференции "Структурная теория автоматов, полугрупп и универсальная алгебра" (Монреаль, Канада, 2003 г.). Также результаты диссетрации излагались на семинарах "Алгебра и логика" и "Алгебраические системы" Института математики СО РАН и Новосибирского государственного университета, семинарах "Алгебра" и "Спецификация дискретных процессов" Технического университета г. Дрездена (Германия), математических коллоквиумах Университета г. Потсдама и Университета г. Росто-ка (Германия), семинарах "Алгебраические системы" и "Дискретная математика" Уральского государственного университета (Екатеринбург).

Диссертация состоит из введения, двух глав, библиографии, указателя обозначений и содержит 8 теорем. Общий объем диссертации составляет 103 страницы. Каждая глава диссертации делится на 4 параграфа. Библиография содержит 53 наименования.

2 Краткое изложение основных результатов

Введем необходимые обозначения и определения. Через О а обозначается множество всех функций над множеством А. Итеративной алгеброй всех функций над множеством А называется алгебра (Од;*,г, £,Д, V) типа (2,1,1,1,1), где символы *, г, Д, V обозначают соответственно операции подстановки вместо первого аргумента, транспозицию первого и второго аргументов, циклический сдвиг кортежа аргументов, отождествление первых двух переменных и добавление первой фиктивной переменной. Итеративной алгеброй называется любая ее подалгебра. Наконец, клон — это итеративная алгебра, содержащая все проекции (т.е. функции, имеющие вид егп(х\,... ,хп) = хг). Термины "замкнутый класс" и "итеративная алгебра" в данной работе используются как синонимы. Наименьший замкнутый класс, содержащий множество ^ С О а называется за-

мкнутым классом, порожденным множеством F, и обозначается через (F).

2.1 Основные результаты первой главы

Пусть К — произвольное ассоциативно-коммутативное кольцо с единицей. Мы рассматриваем алгебраические полиномы над К от произвольного (конечного) числа переменных и замкнутые классы таких полиномов. Рассмотрим основные для первой главы диссертации замкнутые классы:

Fk — класс всех полиномов над К\

Ftf — класс всех .полиномов из Fk без свободного члена;

Ьк — класс всех линейных полиномов из Fk',

Ь°к — класс всех линейных полиномов из Ьк без свободного члена.

Мы ставим перед собой задачу выяснения решеточной структуры интервала [Ь°к, Fk] в случае, когда К — бесконечное поле. В [5] было показано, что в случае кольца вычетов по любому модулю весь решеточный интервал [Ь\, Fk] есть подпрямое произведение интервалов [Ь'к, F^] и [Ь°к, Ьк]- Соответствующее доказательство проходит и для произвольного кольца К. Поэтому исследование интервала [Ük,Fk] в каком-то смысле сводится к изучению интервалов [L°K, F^-] и [Ь°к, Ьк]. В [5] для случая кольца вычетов показано, что интервалы \Ь°к,Ьк] и [F¡^,Fk] изоморфны решетке идеалов кольца К (а значит и между собой). Доказательство и этого факта без изменений переносится на произвольное кольцо К. Поэтому, если К — поле, то интервал [L°k,Fk] есть подпрямое произведение интервала [L^kjFk] и двухэлементной цепи [Ь°к,Ьк]- Если учесть этот факт, то следующий результат диссертации позволяет свести описание интервала , Fk] в случае нулевой характеристики поля к описанию решетки Sub(N; +) подполугрупп аддитивной полугруппы натуральных чисел.

Теорема 1. Если К — поле характеристики0, то интервал [Ьк, Fk] прост, а интервал [Ьак,^] изоморфен решетке Sub(N;+).

Решетка Sub(N; +) счетна и не удовлетворяет ни одному решеточному тождеству (см. [8]). Отсюда легко получается следующее

утверждение.

Следствие 1. Если К — поле характеристики 0, то интервал [Ь^, -Ра:] счетен и не удовлетворяет ни одному нетривиальному решеточному тождеству.

Мы видим, что если поле К имеет характеристику 0, то строение интервала [Ь°к,Рк] не зависит от других свойств поля. Значит Теорема 1 и Следствие 1 дают для полей характеристики 0 ответы на все три вопроса, сформулированные в общей характеристике работы для замкнутых классов многочленов. Центральным результатом первой главы диссертации является следующее утверждение, дающее полный ответ на первый из этих вопросов в общем случае.

Теорема 2. Если К\ и Кг — бесконечные поля, то интервалы ,^к,] и [Ь°к^,Рк2] изоморфны тогда и только тогда, когда характеристики полей К\ и К> совпадают.

Другими словами, строение интервала [Ь^, Рц] зависит только от характеристики бесконечного поля К, а разным характеристикам поля соответствует различное строение интервала. Следующие две теоремы позволят дать ответы на оставшиеся два из упомянутых трех вопросов (о мощности интервала \Ьйк,Рк] и выполняющихся в нем тождествах) в случае простой характеристики бесконечного поля К.

Теорема 3. Если К — бесконечное поле простой характеристики, то в интервал [Ь^-, изоморфно (как частично упорядоченное подмножество) вкладывается ч.у.м. подмножеств счетного множества.

Теорема 4. Если К — бесконечное поле простой характеристики, то в интервал Рд-] изоморфно (как подрешетка) вкладывается решетка подполугрупп аддитивной полугруппы натуральных чисел.

Как показано в первой главе диссертации, каждый клон из интервала [Ь°к, Рк] в случае простой характеристики бесконечного поля К

определяется подмножеством некоторого счетного множества одночленов, поэтому он не более чем континуален. Решетка 8иЬ(М; +) не удовлетворяет ни одному нетривиальному решеточному тождеству (см. [8]). Эти факты в сочетании с Теоремами 3 и 4 позволяют дать ответы на вопросы о мощности интервала [1РК, и выполняющихся в нем тождествах в случае простой характеристики бесконечного поля К.

Следствие 2. Если К — бесконечное поле простой характеристики, то интервал [Ь°к,Рц\ континуален и не удовлетворяет ни одному нетривиальному решеточному тождеству.

Помимо основных результатов в работе представлены некоторые дополнительные свойства интервала [Ь°к,Рк] в случае простой характеристики поля К. В частности, показано, что интервал [Ьц ,Рц] изоморфно вкладывается в интервал [Ь°к, , и каждый из интервалов [Ь°к, и [Ьк, Рк] содержит континуум элементов, не имеющих покрытий соответственно в [¿к, ^к] и [Ьк,Рк\-

2.2 Основные результаты второй главы

Обозначим через N0 множество {0,1,2,3,...}. Такое обозначение является нетрадиционным для теории рекурсивных функций, но оно используется нами для согласования с обозначением N = {1,2,3,...}, принятым в большинстве других областей математики.

Рассмотрим первый из вопросов, сформулированных для второй главы диссертации, т. е. вопрос о строении решетки £С1 замкнутых подклассов класса (0,х,х + 1). Этому вопросу посвящены Теорема 5 и Теорема 6. Ввиду громоздкости формулировок этих теорем мы в данном автореферате воспроизведем лишь некоторую часть информации из этих теорем. Теорема 5 констатирует представимость решетки Сс\ в виде прямого произведения ее интервала /0 = [0, (0, х + 1)] и двухэлементного интервала [0, (ж)], описывает общий вид замкнутых классов из Сс\ и дает формулы для вычисления решеточных пересечений и объединений ее элементов. Используя эту теорему, легко построить и простейшую диаграмму решетки £с|.

Отметим, что функции 0, х, х + 1 являются унарными. Поэтому функции в (0, х, х + 1) могут отличаются от унарных лишь наличием

фиктивных переменных. Это значит, что замкнутые подклассы класса (0, х, х + 1) можно рассматривать как подполугруппы полугруппы преобразований множества N9, порожденной функциями 0, х, х +1. Так мы и поступим. Также для упрощения рассуждений везде далее на констаны мы будем смотреть и как на элементы из N0, и как на константные функции от подходящего числа переменных.

Теорема 5 сводит задачу описания решетки Сс\ к задаче описания интервала /о- Используя замкнутые классы {N0) и (аг + 1), мы разделим интервал /о на пять частей. Части 1, 2, 3 и 4 суть интервалы [(х + 1), (0,ж + 1)], [0, (х + 1>], [0, {N0)] и [(N0), (0,х + 1)] соответственно. Часть 5 состоит из элементов интервала /0, не вошедших в части 1, 2, 3 и 4. Строение интервала 10 проясняется в Теореме 6. В частности, в Теореме 6 утверждается, что части 2 и 4 интервала /о изоморфны решетке 8иЬ(М; +), а. часть 3 — решетке подмножеств счетного множества. Из этого (аналогично результату для [Ь°к, Рк]) следует, что интервал /о континуален и не удовлетворяет ни одному нетривиальному решеточному тождеству.

Нам понадобится операция р{/,д) примитивной рекурсии. Результатом ее применения к £-местной функции / и (к + 2)-местной функции д является (А; + 1)-местная функция Н, определяемая рекурсивно:

Цх1,...,хк,0) = Дхь.цч ..., хк, у + 1) = д(х1,..., хк, у, Л(хъ , у))

Для всех других пар функций (/, д) полагаем р(/, д) — /.

• Замкнутые классы, которые замкнуты еще и относительно примитивной рекурсии, мы будем называть рекурсивно замкнутыми. Наименьший рекурсивно замкнутый класс, содержащий множество Р £ назовем рекурсивно замкнутым классом, порожденным множеством Р, и обозначим через (Р)р.

Центральным результатом второй главы диссертации является полное описание частично упорядоченного множества

V = {(К)р I К 6 Гс1>.

Легко видеть, что наибольший элемент (0,х, х + 1) множества V есть замкнутый класс всех примитивно рекурсивных функций, который также является наибольшим элементом решетки £рг. Ясно,

что пустой замкнутый класс является наименьшим элементом и для V, и для Срг. Остальные элементы множества V распределены по различным частям решетки £рг. Все эти свойства и позволяют нам назвать ч.у.м. V "каркасом" решетки £рг.

Для любой функции д £ обозначим через 1т(<у) множество ее значений. Для произвольного множества ^ С положим по определению

I ш(^) = у М/)-

/ег

Если М С N0, то через РНР(М) мы обозначаем множество всех примитивно рекурсивных функций, у которых области значений содержатся в М. Через М обозначим дополнение множества М в множестве N0. По аналогии с /о положим 11 = [(ж), (0,х,х + 1)]. Решетку £С1 разделим на четыре части следующим образом:

= /о \ Ьо, Ц = [(*), (Ко и {*})], Ь [=1ЛЦ.

Зададим отображение Ф : Сс\ £рг формулой Ф(К) = (К)р.

Мы будем называть о/-цепью и ц;*-цепью соответственно цепь положительных и цепь отрицательных целых чисел с естественным порядком.

Искомое описание множества V будет состоять из теоремы, дающей основную информацию о V, и диаграммы, которая проясняет детали его строения.

Теорема 7.

1. Ч.у.м. Ф(Ьо) изоморфно решетке подмножеств множества N0. Функция Ф изоморфно отображает Ьо на Ф(Ьо).

2. Ч.у.м. Ф(1а) дуально изоморфно решетке конечных подмножеств множества N0 • Для каждого замкнутого класса К е Ъ, имеем {К)р = РИЕ^ш^)).

3. Ч.у.м. Ф(Ьд) изоморфно ш-цепи с внешнеприсоединенным наибольшим элементом. Множество Ф(Е(',) состоит из замкнутого класса (N0 и {х})р и замкнутых классов {тп, х)р, где

га € N0, которые упорядочении следующим образом:

(0,х)р С (1,х)р С (2,х)р С ... С (РЬ и {*})„ .

4■ Множество Ф^^) одноэлементно и состоит из замкнутого класса всех примитивно рекурсивных функций.

5. Следующие интервалы просты:

[(О,\,...,т)р,(т,х)р] для всехт €

[(М)р, РМХМ)] для всех М СЦ) таких, что М конечно;

Диаграмма частично упорядоченного множества V изображена ниже:

На диаграмме полукруг над верхней прерывистой линией символизирует ч.у.м. Ф(1п). Вертикальные линии между Ф(Ьо) и Ф(1п) символизируют простые интервалы [{0,1,..., т)р, (т, х)р ] для

[<1Н,{* и {*}),],

[{^ и {х^РМ^,)].

(0,х + 1)р

'р

0

Диагр. 1

т £ N0 • Аналогично можно установить соответствие между остальными элементами диаграммы и пунктами Теоремы 7.

Помимо строения V как частично упорядоченного множества, представляет интерес и описание замкнутых классов из Р не как замыканий элементов решетки Сс\, а как множеств функций, обладающих какими-либо свойствами. В частности, мы видели, что единственный замкнутый класс из Ф(1п) есть класс всех примитивно рекурсивных функций, а замкнутые классы из Ф(Ьц) имеют вид РЯР(М) для всех М С N0 таких, что М конечно. Для замкнутых классов из Ф(Ьо) мы также получим столь же явное описание. Как оказалось, эти классы тесно связаны с понятием периодичности.

Определение 1. Функцию / : Кц -» N0 назовем финально периодической с периодом р € М, если существует т € N0 такое, что для любых г < к и а\,...,ак € N0 функция

9{я) = _1,а; + т,а,+1, ...,а,к)

периодична с периодом, делящим р.

Описание замкнутых классов из Ф(Ьо) дает следующее утверждение.

Теорема 8.

1. Пусть ео,...,с„_1 — п попарно различных констант из множества Н)• Тогда (со,..., сп_1)р есть в точности класс всех принимающих значения из {со, ...,с„_1} финально периодических функций с периодами, делящими натуральные степени числа п!.

2. Пусть {оо,С1,...} — бесконечное множество констант из N0. Тогда {сц,с\, ...)р есть в точности класс всех принимающих значения из {со,С1,...} финально периодических функций.

Мы имеем явное описание функций из замкнутых классов из Ф(Ьо), Ф(1н) и Ф(Ь'1). Такого описания не получено лишь для замкнутых классов из Ф(1*о). Можно показать, что это описание сводится к описанию класса (х)р. Для любого п 6 N произвольная п-местная функция / € {х)р обладает свойством

/(хь.. • ,х„) < тах(хг,...,а;п). (2)

Функции со свойством (2) мы будем называть шах-ограниченными. В дополнение к основным результатам второй главы автору удалось показать, что класс (х)р содержит самые разнообразные шах-ограниченные функции, в частности, константу 0, арифметическое вычитание, целочисленное деление, целую часть двоичного логарифма, целую часть квадратного корня и многие другие. Чтобы не увеличивать длину текста, в диссертации соответствующие доказательства приведены лишь для функции верхней целой части квадратного корня, арифметического вычитания, знака числа, минимума и максимума. Полученные результаты позволяют сформулировать гипотезу о том, что класс (х)р есть класс всех шах-ограниченных примитивно рекурсивных функций.

Таковы основные результаты диссертации. Своему научному руководителю доценту Е.В.Суханову автор выражает глубокую благодарность за постоянное внимание и всестороннюю поддержку.

Литература

[1] Арнольд В. И. О функциях трех переменных // ДАН СССР.— 1957.- Т. 114, №4 - С. 679-681.

[2] Бабин Д. Н. О суперпозициях ограниченно-детерминированных функций // Математические заметки.— Т. 47, №3.— 1990..

[3] Булатов A.A. Конечные подрешетки в решетке клонов // Алгебра и логика,- 1994. - Т. 33, №5.- С 514-549.

[4] Колмогоров А. Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // ДАН СССР- 1956 - Т. 108, №2 - С. 179-182.

[5] Крохин A.A., Сафин К. Л., Суханов Е.В. О строении решетки замкнутых классов полиномов // Дискретная математика.— 1997. — Т. 9, т. - С. 24-39.

[6] Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. - М.: Наука.— 1985.

[7] Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций // Мат. вопр. кибернетики. Вып. 3.— 1991.— С. 115-139.

[8] Репиицкий В. Б., Кацман С. И. Коммутативные полугруппы, решетка подполугрупп которых удовлетворяет нетривиальному тождеству // Математический сборник — 1988 — Т. 137, ЛЧ — С. 462-482.

[9] Яблонский С. В. Введение в дискретную математику.— М.: Наука.— 1986.

[10] Hilbert D. Mathematische Probleme // Gesamm. Abh— 1935.— III.- P. 290-329.

[11] Post E. Introduction to a general theory of elementary propositions // Amer. J. Math.- 1921- V.43 - P. 163-185.

[12] Rosenberg I. G. The set of maximal closed classes of operations on an infinite set A has cardinality 2гМ1 // Arch. Math.— 1976 — V.27.— P. 561-568.

Работы автора по теме диссертации

[13] Семигродских А. П. О клонах полиномов над бесконечными полями // Областной конкурс студенческих научных работ. Направление "Естественные науки". Тезисы представленных на конкурс работ. - Екатеринбург, 1997 - С. 15-16.

[14] Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Kurosh Algebraic Conference. Abstracts of talks.— Москва, 1998.— С. 209.

[15] Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Универсальная алгебра и приложения. Тезисы международного семинара, посвященного памяти профессора JI. А. Скор-някова.— Волгоград, 1999.— С. 60.

[16] Семигродских А. П. О клонах полиномов над бесконечными полями // Известия вузов. Математика. — 2000. — №7. — С. 53-58.

[17] Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Логика и приложения. Тезисы международной конференции, посвященной 60-летию со дня рождения академика Ю. JI. Ершова— Новосибирск, 2000 — С. 92.

[18] Семигродских А. П. О замкнутых классах финально периодических функций // Алгебра и логика — 2001.— Т. 40, №2.— С. 202-217.

[19] Semigrodskikh А. P. On closed classes of primitive recursive functions, I // Multiple-Valued Logic - 2002 - V. 8, №2 - P. 149-163.

»1 58 67

[20] Semigrodskikh A. P. On closed classes of primitive recursive functions, II // Multiple-Valued Logic.- 2002.- V. 8, №2.- P. 183-191.

[21] Semigrodskikh A. P. On clones of polynomials over infinite fields of prime chracteristic // Technical report MATH-AL-9-2002, Dresden University of Technology (TU Dresden), 2002.

Подписано в печать 12.09.03. Формат 60 х 84/16. Бумага офсетная. Усл.печ.л. 1,0. Тираж 100 экз. Заказ №243.

Отпечатано в ИПЦ "Издательство УрГУ". 620083, г. Екатеринбург, ул. Тургенева, 4.

Содержание.

Введение.

1. Общая характеристика работы.

2. Формулировка основных результатов.

2.1. Основные результаты первой главы.

2.2. Дополнение к основным результатам первой главы.

2.3. Основные результаты второй главы.

2.4. Дополнение к основным результатам второй главы.

Глава 1. Клоны многочленов над бесконечными полями.

§1. Одночлены клонов многочленов над бесконечными полями

§2. Клоны многочленов над полями характеристики 0.

Доказательство Теоремы 1.

§3. Клоны многочленов над бесконечными полями простой характеристики.

3.1. Основные сведения о р-одночленах.

3.2. Клоны, порожденные и ¿-порожденные р-одночленами. Доказательство Предложения 2.

3.3. Покрытия в М* и 8иЪ(Н; +).

3.4. Доказательство Предложения 3 и Теоремы 2.

3.5. Доказательство Теоремы 3 и Теоремы 4.

§4. Дополнительные результаты.

Глава 2. Замкнутые классы примитивно рекурсивных функций.

§1. Замкнутые классы некоторых простейших одноместных функций.

1.1. Основные факты. Доказательство Теоремы 5.

1.2. Строение интервала /о- Доказательство Теоремы 6.

§2. Частично упорядоченное множество V. Доказательство

Теоремы 7.

2.1. Частично упорядоченное подмножество Ф(Ьо).

2.2. Частично упорядоченные подмножество Ф(Ь1).

2.3. Частично упорядоченное подмножество Ф(Ьц).

2.4. Описание частично упорядоченных множеств Ф(Ц) и V

§3. Замкнутые классы финально периодических функций.

Доказательство Теоремы 8.

3.1. Первая часть доказательства Теоремы 8.

3.2. Вторая часть доказательства Теоремы 8.

§4. Дополнительные результаты.

1. Общая характеристика работы

Суперпозиция является одной из основных операций над функциями. Изучение суперпозиции функций, определенных на конечном множестве, привело к возникновению теории замкнутых классов. В термине "замкнутый класс" слово "замкнутый" означает именно "замкнутый по суперпозиции". К настоящему времени эта теория обрела четкие контуры, собственную богатую проблематику и содержит большое число результатов. Имеющаяся литература весьма обширна, поэтому упомянем лишь несколько работ обзорного характера и монографий [19, 27, 28, 37, 44]. С начала 90-х годов эта область развивается и в Екатеринбурге. Обзору полученных здесь результатов посвящены работы [29, 30].

Исходной проблемой для теории замкнутых классов является проблема функциональной полноты. Она заключается в том, чтобы для произвольного набора функций (с аргументами и значениями в некотором фиксированном основном множестве) определить, можно ли из этих функций путем суперпозиций получить все функции с аргументами и значениями в этом множестве. Эта проблема была решена Постом для случая двухэлементного основного множества [38], Яблонским для случая трехэлементного множества [27] и Розенбергом для произвольного конечного основного множества [41].

Перейдем теперь к рассмотрению суперпозиции функций на бесконечном множестве.

Прежде всего отметим, что уже в девятнадцатом веке существовал интерес к алгебраическим свойствам суперпозиции вещественных функций. В двадцатом столетии среди результатов, относящихся к этой области, наибольший резонанс вызвали работы А. Н. Колмогорова [14] и В. И. Арнольда [1], которые доказали, что всякая вещественная непрерывная функция от п переменных представима в виде суперпозиции непрерывных функций двух переменных. Этот результат не только удивителен сам по себе, но и опровергает предположение, высказанное в формулировке тринадцатой проблемы Гильберта [33]. Подчеркнув фундаментальность этого вопроса и напомнив его историю, известный спе-циаист по универсальной алгебре У. Тейлор в своем докладе на алгебраической конференции в Праге в 1995 году призвал исследовать суперпозицию непрерывных функций с алгебраической точки зрения. Более подробную информацию о результатах по суперпозиции вещественных функций можно найти в обзорах [9, 39].

Проблема представимости функций на бесконечном множестве в виде суперпозиции других функций занимала и специалистов по теории автоматов (см. [18, 28]). Каждому конечному автомату можно поставить в соответствие (автоматную) функцию, отображающую его входные последовательности в выходные. Как и для непрерывных функций, оказалось [2], что любая автоматная функция может быть представлена суперпозицией автоматных функций от двух переменных. Аналогично случаю функций над конечным основным множеством возникает проблема полноты для автоматных функций. Принципиальная невозможность решения этой задачи в общем случае была установлена в [17], а в работе [15] установлена ее алгоритмическая неразрешимость для конечных базисов автоматных функций. Тем не менее, для базисов, содержащих все булевы функции, указанная задача алгоритмически разрешима [3]. На настоящий момент наиболее общие результаты по разрешимости проблемы полноты для различных систем автоматных функций можно найти в [3]-[6].

Еще одним естественным классом функций, для которого рассматриваются вопросы, связанные с суперпозицией, является класс рекурсивных функций. До сих пор наиболее часто решаемой задачей в этой области было нахождение базисов по суперпозиции для некоторых его специальных подклассов (см. обзор [24]). Особенное внимание при этом уделялось классам из иерархии Гжегорчика (см. [7, 13, 21, 22, 23, 32, 34, 35, 40]).

Как и многие другие объекты, изучаемые в общей алгебре (например, многообразия групп, полугрупп и колец), замкнутые классы на фиксированном множестве А удобно классифицировать при помощи решетки С,а по включению, которую они образуют. Если множество А конечно, то решетка С, а дуально атомна, и полное описание ее дуальных атомов, называемых также максимальными классами, играет важную роль в критериях функциональной полноты [38, 41]. В случае бесконечного основного множества удалось привести лишь отдельные конкретные примеры максимальных классов [10, 12, 31, 42]. При этом Гаврилов [11, 12] для счетного множества и Розенберг [43] для произвольного бесконечного множества А показали, что мощность множества дуальных атомов решетки Са совпадает с мощностью всей решетки С а и равна 22'А|. Чтобы еще более подчеркнуть сложность решетки С а, отметим, что из почти очевидной изоморфной вложимости в £д решетки замкнутых классов на произвольном конечном множестве и из результатов работы [8] следует, что в С а изоморфно вкладывается любая решетка, являющаяся прямым произведением не более чем счетного числа конечных решеток.

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

1. замкнутые классы на произвольном бесконечном множестве,

2. замкнутые классы на счетном множестве.

В соответствии с этим диссертационная работа разбита на две главы. Далее мы кратко охарактеризуем их содержание.

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

Под классификацией замкнутых классов многочленов над бесконечным полем К мы будем понимать описание подрешетки этих замкнутых классов в решетке всех замкнутых классов на основном множестве поля К. Полное описание этой подрешетки вряд ли может быть получено. Поэтому мы ограничим эту задачу следующим образом. Отметим, что многие задачи, касающиеся построения функций с помощью суперпозиции, решались в предположении, что в суперпозиции всегда могут участвовать некоторые простые функции. В классе автоматных функций в качестве таковых рассматривались булевы функции, в классе рекурсивных функций — 0, х, х -I- 1 или нумерационные функции, в классе вещественных функций — сложение. Наиболее часто в качестве таких простых функций выступают одноместные функции из рассматриваемого в задаче класса. В первой главе данной диссертации в качестве таких простых функций выступают линейные формы над полем К. В терминах решетки замкнутых классов это означает, что задача первой главы будет состоять в описании интервала [Ь°к, Г к] между замкнутым классом

Ь°к линейных форм и замкнутым классом Рк всех многочленов над К. Отметим, что в точности такая же ограниченная задача классификации замкнутых классов многочленов над некоторыми конечными кольцами была рассмотрена в [16, 26]. В рамках этой задачи для случая бесконечного поля естественно возникают следующие вопросы:

1. От каких свойств поля К зависит строение интервала [Ь°к,

2. Какова мощность интервала [.Ь°к, /^к-]?

3. Удовлетворяет ли интервал [Ь°к, Рк\ какому-нибудь нетривиальному решеточному тождеству?

Ответы именно на эти вопросы даются в первой главе диссетрации.

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

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

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

Главным результатом второй главы диссертации является построение некоторого частично упорядоченного множества V замкнутых классов примитивно рекурсивных функций, "пронизывающего" решетку £рг и могущего служить ее "каркасом". Рассматривая интервалы решетки Срт, находящиеся между элементами множества Р, можно более подробно изучить ее строение. Кроме того, по ходу построения множества V возникают новые интересные примеры замкнутых классов примитивно рекурсивных функций. Отправной точкой для построения частично упорядоченного множества Р служит решетка £С1 замкнутых подклассов замкнутого класса, порожденного функциями 0, х и х + 1, которые являются базовыми при построении примитивно рекурсивных функций. Множество Р строится как множество замыканий классов решетки Сс\ относительно примитивной рекурсии и суперпозиции. При выбранном подходе к изучению замкнутых классов примитивно рекурсивных функций прежде всего возникают следующие вопросы:

1. Каковы основные элементы строения решетки Сс\?

2. Каково строение частично упорядоченного множества Р?

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

Ответам на эти вопросы и посвящена вторая глава диссертации.

1. Арнольд В. И. О функциях трех переменных // ДАН СССР.— 1957.- Т. 114, т.- С. 679-681.

2. Бабин Д.Н. О суперпозициях ограниченно-детерминированных функций // Математические заметки.— Т. 47, №3.— 1990.

3. Бабин Д.Н. Разрешимый случай задачи о полноте автоматных функций // Дискретная математика. — 1992.— Т. 4, №4.— С. 41-56.

4. Бабин Д. Н. О разрешимости проблемы полноты для специальных систем автоматных функций // Дискретная математика.— 1996.— Т. 8, №4,- С. 79-91.

5. Бабин Д.Н. Алгоритмическая разрешимость свойств полноты и А-полноты конечных систем автоматных функций с линейной истинностной частью // Интеллектуальные системы.— 1998.— Т. 3.— С. 51-69.

6. Бабин Д. Н. Конечность множества автоматных базисов Поста с разрешимой проблемой полноты // Дискретная математика.— 1998. Т. 10, №.- С. 57-64.

7. Белътюков А. П. Машинное описание и иерархия начальных классов Гжегорчика // Записки научных семинаров Ленинград, отделения матем. института АН СССР. — 1979. Т. 88. — с.127-158.

8. Булатов A.A. Конечные подрешетки в решетке клонов // Алгебра и логика.- 1994. Т. 33, №5.- С 514-549.

9. Витушкин А. Г. О представимости функций суперпозициями функций от меньшего числа переменных // Труды Международного конгресса математиков.— Москва, 1966.— С. 322-329.

10. Гаврилов Г. П. О некоторых условиях полноты в счетнозначной логике // ДАН СССР.- 1959.- Т. 128.- С. 21-24.

11. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // ДАН СССР.— 1964.— Т. 155, т.- С. 35-37.

12. Крохин A.A., Сафив К.Л., Суханов Е.В. О строении решетки замкнутых классов полиномов // Дискретная математика.— 1997. — Т. 9, №2. С. 24-39.

13. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // ДАН СССР.- 1963.- Т. 151, №3.- С. 493-496.

14. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов.— М.: Наука.— 1985.

15. Мальцев А. И. Итеративные алгебры Поста.- Новосибирск: Изд-во НГУ.- 1976.

16. Мальцев И. А. Некоторые свойства клеточных подалгебр Поста и их основных клеток // Алгебра и логика.— 1972.— Т. 11, №6 — С. 571587.

17. Марченков С. С. Устранение схем рекурсий в классе £2 Гжегорчика // Математические заметки. — 1969. — Т. 5, №5, С. 561-568.

18. Марченков С. С. Об ограниченных рекурсиях // Mathematica Balkanika — 1972,— Т. 2,- С. 124-142.

19. Марченков С. С. Об одном базисе по суперпозиции в классе функций, элементарных по Кальмару // Математические заметки. — 1980. Т. 27, т.- С. 321-332.

20. Марчевков С. С. Базисы по суперпозиции в классах рекурсивных функций // Мат. вопр. кибернетики. Вып. 3— 1991.— С. 115-139.

21. Репницкий В. Б., Кацман С. И. Коммутативные полугруппы, решетка подполугрупп которых удовлетворяет нетривиальному тождеству // Математический сборник — 1988 — Т. 137, №4 С. 462-482.

22. Семигродских А. П., Суханов Е. В. О замкнутых классах полиномов над конечным полем // Дискретная математика.— 1997.— Т. 9, №4. — С. 50 62.

23. Яблонский C.B. Функциональные построения в А-значной логике // Труды МИАН СССР.- 1958.- Т. 51- С. 5-142.

24. Яблонский С. В. Введение в дискретную математику.— М.: Наука.— 1986.

25. Bulatov A. A., Krokbin A. A., Satin К. L., Sukhanov Е. V. On the structure of clone lattices // General Algebra and Discrete Mathematics.— Berlin: Heldermann Verlag.— 1995.— P. 27-34.

26. Bulatov A. A., Krokbin A. A., Satin K.L., Semigrodskikb A. P., and Sukhanov E. V. On the structure of clone lattices, II // Multiple-Valued Logic.- 2001. 7 (5-6).- P. 379-389.

27. Davies R. O., Rosenberg I. G. Precomplete classes of operations on an uncountable set // Colloq. Math.- 1985.— V.50 — P. 1-12.

28. Grzegorczyk A. Some classes of recursive functions // Rozprawy Mat.— 1953.— V. 4. (Русский перевод: Гжегорчик А. Некоторые классы рекурсивных функций // Проблемы матем. логики.— М.: Мир.— 1970,- С. 9-49.)

29. Hilbert D. Mathematische Problème // Gesamm. Abh — 1935 — III — P. 290-329.

30. Jones J. P., Matijasevië Ju. V. A new representation for the symmetric binomial coefficient and its applications // Ann. Sc. math. Québec. — 1982. V. 4, №1. - P. 81-97.

31. Parsons Ch. Hierarchies of primitive recursive functions // Zeitschr. math. Logik u. Grundlag Math.— 1968 — Bd 14, №4.— S. 357-376.

32. Peter R. Rekursive Funktionen.— Budapest: Akademiai Kiado.— 1957.

33. Pöschel R., Kaluznin L.A. Funktionen- und Relationenalgebren. Ein Kapitel der diskreten Mathematik.- Berlin: VEB DVW.— 1979.

34. Post E. Introduction to a general theory of elementary propositions // Amer. J. Math.- 1921.- V.43.- R 163-185.

35. Rassias T.M., Simsa J. Finite sums decompositions in mathematical analysis.— Chichester: John Wiley & Sons Ltd.— 1995.

36. Rödding D. Uber die Eliminierbarkeit von Definitionsschemata in der Theorie der Rekursiven Funktionen // Zeitschr. math. Logik u. Grundlag Math.- 1964.- Bd 10, №4.— S. 315-330.

37. Rosenberg I. G. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken (Struktur der Funktionen von mehreren Veränderlichen auf endlichen Mengen) // Rozpravy Öeskoslovenske Akad. VSd. Rada Mat. Pfirod. VSd.- 1970,- V. 80.- P. 3-93.

38. Rosenberg I. G. Some maximal closed classes of operations on infinite sets // Math. Ann.- 1974.- V.212 P. 157-164.

39. Rosenberg I. G. The set of maximal closed classes of operations on an infinite set A has cardinality 22"1' // Arch. Math.— 1976.— V. 27.— P. 561-568.

40. Szendrei A. Clones in universal algebra.— Montreal: Les presse de l'universite de Montreal.— 1986.Работы автора по теме диссертации

41. Семигродских А. П. О клонах полиномов над бесконечными полями // Областной конкурс студенческих научных работ. Направление "Естественные науки". Тезисы представленных на конкурс работ. — Екатеринбург, 1997 — С. 15-16.

42. Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Kurosh Algebraic Conference. Abstracts of talks.— Москва, 1998.- С. 209.

43. Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Универсальная алгебра и приложения. Тезисы международного семинара, посвященного памяти профессора JI. А. Скорнякова. Волгоград, 1999.— С. 60.

44. Семигродских А. П. О клонах полиномов над бесконечными полями // Известия вузов. Математика. — 2000. — №7. — С. 53-58.

45. Семигродских А. П. О замкнутых классах примитивно рекурсивных функций // Логика и приложения. Тезисы международной конференции, посвященной 60-летию со дня рождения академика Ю. Л. Ершова — Новосибирск, 2000.— С. 92.

46. Семигродских А. П. О замкнутых классах финально периодических функций // Алгебра и логика — 2001.— Т. 40, №2. С. 202-217.

47. Semigrodskikh А. P. On closed classes of primitive recursive functions, 1// Multiple-Valued Logic.- 2002.- V.8, №2.- P. 149-163.

48. Semigrodskikh A. P. On closed classes of primitive recursive functions, II// Multiple-Valued Logic.- 2002,- V. 8, №2 — P. 183-191.