Содержание к диссертации
Введение
1. Клоны многочленов над бесконечными полями 20
1. Одночлены клонов многочленов над бесконечными полями 21
2. Клоны многочленов над полями характеристики 0. Доказательство Теоремы 1 22
3. Клоны многочленов над бесконечными полями простой характеристики 26
3.1. Основные сведения о /ьодночленах 27
3.2. Клоны, порожденные и L-порожденные р-одночленами. Доказательство Предложения 2 31
3.3. Покрытия в М% и Sub(N; +) 38
3.4. Доказательство Предложения 3 и Теоремы 2 43
3.5. Доказательство Теоремы 3 и Теоремы 4 49
4. Дополнительные результаты 52
2. Замкнутые классы примитивно рекурсивных функций 57
1. Замкнутые классы некоторых простейших одноместных функций 57
1.1. Основные факты. Доказательство Теоремы 5 57
1.2. Строение интервала /о- Доказательство Теоремы 6 60
2. Частично упорядоченное множество V. Доказательство Теоремы 7 66
2.1. Частично упорядоченное подмножество Ф(Ьо) 68
2.2. Частично упорядоченные подмножество Ф(Ьі) 68
2.3. Частично упорядоченное подмножество Ф(Ь'0) 76
2.4. Описание частично упорядоченных множеств Ф(І^) и V 78
3. Замкнутые классы финально периодических функций. Доказательство Теоремы 8 79
3.1. Первая часть доказательства Теоремы 8 80
3.2. Вторая часть доказательства Теоремы 8 85
4. Дополнительные результаты 91
Литература 98
- Клоны многочленов над полями характеристики 0. Доказательство Теоремы 1
- Доказательство Предложения 3 и Теоремы 2
- Частично упорядоченное множество V. Доказательство Теоремы 7
- Вторая часть доказательства Теоремы 8
Введение к работе
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] следует, что в La изоморфно вкладывается любая решетка, являющаяся прямым произведением не более чем счетного числа конечных решеток.
Предлагаемая диссертация посвящена дальнейшему изучению замкнутых классов функций, заданных на бесконечном множестве А. Мы рассматриваем два направления:
замкнутые классы на произвольном бесконечном множестве,
замкнутые классы на счетном множестве.
В соответствии с этим диссертационная работа разбита на две главы. Далее мы кратко охарактеризуем их содержание.
Поставим задачу выделения такого вида функций, уже используемых в математике, что на множестве любой бесконечной мощности определены представители этого вида. При возникновении такого вопроса первыми претендентами являются многочлены над полями: любое бесконечное множество может быть превращено в поле введением подходящих операций, многие из первых изучаемых еще в школе функций являются многочленами, и многочлены над полями очень широко применяются. Именно классификации замкнутых классов многочленов над бесконечным полем и посвящена первая глава диссертации.
Под классификацией замкнутых классов многочленов над бесконечным полем К мы будем понимать описание подрешетки этих замкнутых классов в решетке всех замкнутых классов на основном множестве поля К. Полное описание этой подрешетки вряд ли может быть получено. Поэтому мы ограничим эту задачу следующим образом. Отметим, что многие задачи, касающиеся построения функций с помощью суперпозиции, решались в предположении, что в суперпозиции всегда могут участвовать некоторые простые функции. В классе автоматных функций в качестве таковых рассматривались булевы функции, в классе рекурсивных функций — 0, х, х + 1 или нумерационные функции, в классе вещественных функций — сложение. Наиболее часто в качестве таких простых функций выступают одноместные функции из рассматриваемого в задаче класса. В первой главе данной диссертации в качестве таких простых функций выступают линейные формы над полем К. В терминах решетки замкнутых классов это означает, что задача первой главы будет состоять в описании интервала [LK, Fk] между замкнутым классом
LK линейных форм и замкнутым классом Fk всех многочленов над К. Отметим, что в точности такая же ограниченная задача классификации замкнутых классов многочленов над некоторыми конечными кольцами была рассмотрена в [16, 26]. В рамках этой задачи для случая бесконечного поля естественно возникают следующие вопросы:
От каких свойств поля К зависит строение интервала [LK, Fk]?
Какова мощность интервала [LK, F#]?
Удовлетворяет ли интервал [Lk,Fk\ какому-нибудь нетривиальному решеточному тождеству?
Ответы именно на эти вопросы даются в первой главе диссетрации.
Перейдем теперь к постановке еще одной задачи, которая (в отличие от предыдущей) касается только замкнутых классов на счетном множестве. Главным доводом для такого выбора основного множества является то, что счетные множества имеют среди бесконечных множеств наименьшую мощность.
Среди функций на счетном множестве наибольшую значимость имеют рекурсивные функции, поскольку в определенном смысле только рекурсивные функции на счетном множестве являются вычислимыми. Кроме того, замкнутые классы рекурсивных функций уже рассматривались ранее, что является еще одним обоснованием для выбора в их пользу. Выше было отмечено, что ранее проводилось изучение только некоторых специфических классов рекурсивных функций. Классы иерархии Гже-горчика, которым было уделено наибольшее внимание, образуют лишь счетную цепь в решетке замкнутых классов на счетном множестве, которая имеет весьма сложное строение и мощность 22 . Во второй главе данной диссертации мы обратим наше внимание на замкнутые классы рекурсивных функций за пределами этой цепи.
Мы будем рассматривать замкнутые классы примитивно рекурсивных функций, поскольку примитивно рекурсивные функции являются наиболее часто встречающимися в математической практике рекурсивными функциями. Обозначим через рГ решетку упорядоченных по включению замкнутых классов примитивно рекурсивных функций. Можно показать, что в решетку рг вкладываются все решетки замкнутых классов на конечных множествах, и, следовательно, найти ее описание
вряд ли удастся. Тем не менее, некоторое прояснение строения этой решетки все же возможно.
Главным результатом второй главы диссертации является построение некоторого частично упорядоченного множества V замкнутых классов примитивно рекурсивных функций, "пронизывающего" решетку рг и могущего служить ее "каркасом". Рассматривая интервалы решетки СрТ, находящиеся между элементами множества V, можно более подробно изучить ее строение. Кроме того, по ходу построения множества V возникают новые интересные примеры замкнутых классов примитивно рекурсивных функций. Отправной точкой для построения частично упорядоченного множества V служит решетка С& замкнутых подклассов замкнутого класса, порожденного функциями 0, х и х + 1, которые являются базовыми при построении примитивно рекурсивных функций. Множество V строится как множество замыканий классов решетки Сс\ относительно примитивной рекурсии и суперпозиции. При выбранном подходе к изучению замкнутых классов примитивно рекурсивных функций прежде всего возникают следующие вопросы:
Каковы основные элементы строения решетки ci?
Каково строение частично упорядоченного множества VI
С помощью каких естественных свойств функций без использования рекурсивного замыкания можно задать элементы множества "Р?
Ответам на эти вопросы и посвящена вторая глава диссертации.
2. Формулировка основных результатов
Введем необходимые обозначения и определения. Через О а обозначается множество всех функций над множеством А. Итеративной алгеброй всех функций над множеством А называется алгебра (Од; *,т, , А, V) типа (2,1,1,1,1), где символы *, т, , Д> V обозначают соответственно операции подстановки вместо первого аргумента, транспозицию первого и второго аргументов, циклический сдвиг кортежа аргументов, отождествление первых двух переменных и добавление первой фиктивной переменной. Итеративной алгеброй называется любая ее подалгебра. Такой подход к изучению суперпозиции восходит к А. И. Мальцеву [19].
Операции *, т, , Д, V называются итеративными операциями. Наконец, клон — это итеративная алгебра, содержащая все проекции (т.е. функции вида e*n(xi,..., хп) = Хі). Наименьший клон на множестве А состоит из всех проекций, определенных на Л, и обозначается через J а-Термины "замкнутый класс" и "итеративная алгебра" в данной работе используются как синонимы. Наименьший замкнутый класс, содержащий множество F С О а называется замкнутым классом, порожденным множеством F, и обозначается через (F).
2.1. Основные результаты первой главы
Пусть К — произвольное ассоциативно-коммутативное кольцо с единицей. Мы рассматриваем алгебраические полиномы над К от произвольного (конечного) числа переменных и замкнутые классы таких полиномов. Рассмотрим основные для первой главы диссертации замкнутые классы:
Fk — класс всех полиномов над К;
Fj<- — класс всех полиномов из Fk без свободного члена;
LK — класс всех линейных полиномов из Fk',
LK — класс всех линейных полиномов из Ьк без свободного члена.
Мы ставим перед собой задачу выяснения решеточной структуры интервала [Lk,Fk] в случае, когда К — бесконечное поле. Отметим, что замкнутый класс LK содержит все проекции, т. е. является клоном. Клонами являются и все замкнутые классы из [Lk,Fk].
При изучении строения той или иной решетки часто является желательным построение как можно более подробной диаграммы этой решетки. К этому мы будем стремиться и при рассмотрении интервала [LK, Fk]- Для случая произвольного кольца К этот интервал изображена на Диагр. 1. Знаки вопросов на ней означают, что указанные интервалы могут содержать замкнутые классы, не совпадающие с четырьмя отмеченными. Это зависит от свойств кольца К.
Диагр. 2
В [16] было показано, что в случае кольца вычетов по любому модулю весь решеточный интервал [Lk,Fk] есть подпрямое произведение интервалов [LK,FK] и [LK,LK]. Соответствующее доказательство проходит и для произвольного кольца К. Поэтому исследование интервала [LK, Ffc] в каком-то смысле сводится к изучению интервалов [LK, FK\ и [LK, Lk\- В [16] для случая кольца вычетов показано, что интервалы [Lk,Lk] и [FkjFk] изоморфны решетке идеалов кольца К (а, следовательно, и между собой). Доказательство и этого факта без изменений переносится на произвольное кольцо К. Поэтому, если К — поле, то интервал [LK, FK\ имеет вид, изображенный на Диагр. 2. Если учесть этот факт, то следующий результат диссертации позволяет свести описание интервала \LQK, Fk] в случае нулевой характеристики поля к описанию решетки Sub(N; +) подполугрупп аддитивной полугруппы натуральных чисел.
Теорема 1. Если К — поле характеристики 0, то интервал [#-, Fk] прост, а интервал [LK,FK] изоморфен решетке Sub(N;+).
Таким образом, в случае нулевой характеристики поля К диаграмма интервала [Lk,Fk] выглядит следующим образом.
%-г
Sub(N; +у
Диагр. 3
Решетка Sub(N; +) счетна и не удовлетворяет ни одному решеточному тождеству (см. [25]). Отсюда легко получается следующее утверждение.
Следствие 1. Если К — поле характеристики 0, то интервал [LK, Fk] счетен и не удовлетворяет ни одному нетривиальному решеточному тождеству.
Мы видим, что если поле К имеет характеристику 0, то строение интервала [LK, Fk] не зависит от других свойств поля. Значит, Теорема 1 и Следствие 1 дают для полей характеристики 0 ответы на все три вопроса, сформулированные в общей характеристике работы для замкнутых
классов многочленов. Центральным результатом первой главы диссертации является следующее утверждение, дающее полный ответ на первый из этих вопросов в общем случае.
Теорема 2. Если К і и К2 — бесконечные поля, то интервалы [LKl, Fxt] и [LK2,Fk2] изоморфны тогда и только тогда, когда характеристики полей Ki и К2 совпадают.
Другими словами, строение интервала [Lk,Fk] зависит только от характеристики бесконечного поля К, а разным характеристикам поля соответствует различное строение интервала.
Как и для полей характеристики 0, было бы желательно получить полное описание интервала [Lk,Fk] в общем случае. Однако в случае простой характеристики бесконечного поля К получить такое описание интервала [LK, Fk] вряд ли удастся в силу следующих утверждений.
Теорема 3. Если К — бесконечное поле простой характеристики, то в интервал [LK, Fk] изоморфно (как подрешетка) вкладывается решетка подполугрупп аддитивной полугруппы натуральных чисел.
Теорема 4. Если К — бесконечное поле простой характеристики, то в интервал [LK, Fk] изоморфно (как частично упорядоченное подмножество) вкладывается ч.у.м. подмножеств счетного множества.
Как показано в первой главе диссертации, каждый клон из интервала [Lk,Fk] в случае простой характеристики бесконечного поля К определяется подмножеством некоторого счетного множества одночленов, поэтому он не более чем континуален. Решетка Sub(N; +) не удовлетворяет ни одному нетривиальному решеточному тождеству (см. [25]). Эти факты в сочетании с Теоремами 3 и 4 позволяют получить следующий результат, дающий в случае полей простой характерстики ответ на второй и третий вопросы, сформулированные для первой главы в начале работы.
Следствие 2. Если К — бесконечное поле простой характеристики, то интервал [LK, Fk] континуален и не удовлетворяет ни одному нетривиальному решеточному тождеству.
2.2. Дополнение к основным результатам первой главы
Ниже будут сформулированы отдельные свойства интервала [LK, Fk], которые не относятся к главным, но могут представлять интерес. Нам понадобятся следующие термины и обозначения. Пусть С — замкнутый класс из [LK,Fx]. Тогда С может быть порожден совокупностью всех линейных форм (то есть полиномов из Ьк) и какими-то функциями fi, /2,... из Fk', другими словами — С = ({/1,/2,---} U Ьк). В этом случае мы будем писать С = ((/1,/2,--)) и говорить, что этот класс Ь-порожден функциями /1,/2,... (не упоминая Ьк).
Если К — бесконечное поле простой характеристики, то справедливы следующие утверждения.
Интервал [Lk,Fk] изоморфно вкладывается в интервал [LK, F^]-
Клон ((1,хур)) — единственный атом интервала [Lk,Fk]. Клон ((хр, ^1^2^3, Х1Х2Х3Ж4)) — единственный атом интервала [Ь^-, ?#]
В интервал [Lk,Fk] изоморфно вкладывается ч.у.м. подмножеств счетного множества.
Интервалы \LK, ((хр))] и [Ьк, ((1, хр))] изоморфны решетке Sub(N; +).
Ни один элемент из интервалов [Ьк,((хр))] и [Ьк, ((1,хр))] не покрывается элементами соответственно из [LK, Fk] \ [LK, ((хр))] и [Lk,Fk]\[Lk,((1,xp))}.
Каждый из интервалов [I^Fr-] и [Lk,Fk] содержит континуум элементов, не имеющих покрытий соответственно в [LK, FK] и [Lk,Fk].
Для любого С Є [Ьк, Fk], не равного Ьк, имеем
\[Ьк,С]Г) [^,((1,^))]|= N0-
8. Есть континуум клонов С Є [LK, FK] таких, что
[Ьк,С]П[Ьк,((хр))] = {Ьк}.
Чтобы не удлиннять текст работы, мы приведем полное доказательство лишь для первого из этих свойств.
2.3. Основные результаты второй главы
Обозначим через N0 множество {0,1,2,3,...}. Такое обозначение является нетрадиционным для теории рекурсивных функций, но оно используется нами для согласования с обозначением N = {1,2,3,...}, принятым в большинстве других областей математики.
Рассмотрим первый из вопросов, сформулированных для второй главы диссертации, т. е. вопрос о строении решетки ci замкнутых подклассов класса (0, ж, ж + 1). Этому вопросу посвящены Теорема 5 и Теорема 6. Теорема 5 констатирует представимость решетки Сс\ в виде прямого произведения ее интервала Iq = [0, (0, ж + 1)] и двухэлементного интервала [0, (х)], описывает общий вид замкнутых классов из Сс\ и дает формулы для вычисления решеточных пересечений и объединений ее элементов. Используя эту теорему, легко построить и простейшую диаграмму решетки Сс\\
Диагр. 4
Отметим, что функции 0, х, х + 1 являются унарными. Поэтому функции в (0, х, х + 1) могут отличаются от унарных лишь наличием фиктивных переменных. Это значит, что замкнутые подклассы класса (О, ж, ж + 1) можно рассматривать как подполугруппы полугруппы преобразований множества No, порожденной функциями 0, х, х + 1. Так мы и поступим. Также для упрощения рассуждений везде далее на конста-ны мы будем смотреть и как на элементы из No, и как на константные функции от подходящего числа переменных.
Теорема 5 сводит задачу описания решетки ci к задаче описания интервала Iq. Используя замкнутые классы (No) и (ж+1), мы разделим интервал IQ на пять частей, как показано на Диагр. 5. Части 1, 2, 3 и 4 суть интервалы [(ж +1), (0,ж +1)], [0,(ж + 1)]; [0,
Диагр. 5. Интервал Iq
Через Р$ мы обозначаем часть 5 интервала Iq, т. е.
n = /o\([(x + l),(O,x + l)]U[0,(x + l)]U[0,(No)]U[(No),{O,x + l>]).
Строение интервала Iq проясняется в Теореме 6. В частности, в Теореме 6 утверждается, что части 2 и 4 интервала /0 изоморфны решетке Sub(N; +), о часть 3 — решетке подмножеств счетного множества. Из этого (аналогично результату для [LK,FK]) следует, что интервал 10 континуален и не удовлетворяет ни одному нетривиальному решеточному тождеству.
Как мы уже отмечали выше, основной целью второй главы диссертации является построение и описание некого "каркаса" решетки рг замкнутых классов примитивно рекурсивных функций. Для этого нам понадобится операция p(f, g) примитивной рекурсии. Результатом ее применения к fc-местной функции / и {k + 2)-местной функции g является (к + 1)-местная функция h, определяемая рекурсивно:
h(xit...,xk,0) = f(xi,...,xk) цч
Л(я?і,..., хк, у + 1) = g(xh..., xfc, у, h(xu..., хк, у))
Для всех других пар функций (f,g) полагаем p(f, g) = /.
Замкнутые классы, которые замкнуты еще и относительно примитивной рекурсии, мы будем называть рекурсивно замкнутыми. Наименьший рекурсивно замкнутый класс, содержащий множество F С Onq назовем рекурсивно замкнутым классом, порожденным множеством F, и обозначим через (F)p.
Центральным результатом второй главы диссертации является полное описание частично упорядоченного множества
V = {{К)р | К є с1}.
Легко видеть, что наибольший элемент (0, х, х + 1) множества V есть замкнутый класс всех примитивно рекурсивных функций, который также является наибольшим элементом решетки рг. Ясно, что пустой замкнутый класс является наименьшим элементом и для V, и для рг. Остальные элементы множества V распределены по различным частям решетки рг. Все эти свойства и позволяют нам назвать ч.у.м. V "каркасом" решетки рг.
Для любой функции д Є Ощ обозначим через 1т(д) множество ее значений. Для произвольного множества F С О^ положим по определению
Im(F) = (J Im(/).
f&F
Если М С N0, то через PRF(M) мы обозначаем множество всех примитивно рекурсивных функций, у которых области значений содержатся в М. Через М обозначим дополнение множества М в множестве No- По аналогии с Iq положим 1г = [(х), (0,х,х 4-1)]. Решетку Сс\ разделим на четыре части следующим образом:
Lo = [0,(No)], In = /о \ Lo,
Ц = [<*),«*) и {*})],
l; = /i\l0.
Зададим отображение Ф : Сс\ —> Срт формулой Ф(К) = (К) .
Мы будем называть cu-цепью и а;'-цепью соответственно цепь положительных и цепь отрицательных целых чисел с естественным порядком.
Искомое описание множества V будет состоять из теоремы, дающей основную информацию оР,и диаграммы, которая проясняет детали его строения.
Теорема 7.
Ч.у.м. Ф(Ьо) изоморфно решетке подмножеств множества No. Функция Ф изоморфно отображает Lo на Ф(Ьо).
Ч.у.м. Ф(1а) дуально изоморфно решетке конечных подмножеств множества No- Для каждого замкнутого класса К є Li имеем (K)p=PRF(lm(K)).
3. Ч.у.м. Ф(Ь0) изоморфно oj-цєпи с внешнеприсоединенным наибольшим элементом. Множество Ф(Ь0) состоит из замкнутого класса ({No) U {х}) и замкнутых классов (т,х) , где т Є N0, которые упорядочении следующим образом:
(О,х)р С (1,х)р С (2,х)р С ... С (
4- Множество Ф(Ьі) одноэлементно и состоит из замкнутого класса всех примитивно рекурсивных функций.
5. Следующие интервалы просты:
[(0,1,...,т)р, (т,х)р] для всех т Є No; [{М)р, PRF(M)] для всех М С N0 таких, что М конечно; b>p,«N>> и {*}>,], fo>U{x»p)PRF(N0)].
Диаграмма частично упорядоченного множества V изображена ниже:
ь и {*})-
<0,*+1>„
Диагр. 6
На диаграмме полукруг над верхней прерывистой линией символизирует ч.у.м. Ф(1п). Вертикальные линии между Ф(Ь0) и Ф(1п) символизируют простые интервалы \{М) , PRF(M)] для всех М с No таких, что М конечно. Аналогично можно установить соответствие между остальными элементами диаграммы и пунктами Теоремы 7.
Помимо строения V как частично упорядоченного множества, представляет интерес и описание замкнутых классов из V не как замыканий элементов решетки ci, а как множеств функций, обладающих какими-либо свойствами. В частности, мы видели, что единственный замкнутый класс из Ф(Ьі) есть класс всех примитивно рекурсивных функций, а замкнутые классы из Ф(1п) имеют вид PRF(M) для всех М С No таких, что М конечно. Для замкнутых классов из Ф(Ь0) мы также получим столь же явное описание. Как оказалось, эти классы тесно связаны с понятием периодичности.
Периодические функции — это стандартный математический объект. Нередко встречаются и такие непериодические функции, подходящие ограничения которых являются периодическими. Понятие периодичности также можно распространить и на функции от многих переменных. Мы сделаем это следующим образом.
Определение 1. Функцию / : Nq —> No назовем финально периодической с периодом р Є N, если существует т Є No такое, что для любых і < к и а\, ...,а* Є N0 функция
g{x) = /(oi,..., щ-і,х + га, ai+u ..., ak)
периодична с периодом, делящим p.
Число р из определения финально периодической функции мы будем называть ее периодом. Очевидно, что такой период не единственен. Описание замкнутых классов из Ф(Ьо) дает следующее утверждение.
Теорема 8.
Пусть Co,--, c„_i — п попарно различных констант из множества N0. Тогда {со,...,Сп_і) есть в точности класс всех принимающих значения из {cq, ..., c„_i} финально периодических функций с периодами, делящими натуральные степени числа п\.
Пусть {co,ci,...} — бесконечное множество констант из No- Тогда (со, с\,...) есть в точности класс всех принимающих значения из {co,ci,...} финально периодических функций.
2.4. Дополнение к основным результатам второй главы
Мы имеем явное описание функций, принадлежащих замкнутым классам из Ф(Ьо), Ф(1п) и ФЩ). Такого описания не получено лишь для замкнутых классов из Ф(Ьо). Можно показать, что это описание сводится к описанию класса (х). Для любого п Є N произвольная п-местная функция / Є (х)р обладает свойством
/(a?i,...,arB)
Функции со свойством (2) мы будем называть max-ограниченными. Автору удалось показать, что класс (х) содержит самые разнообразные max-ограниченные функции, в частности, константу 0, арифметическое вычитание, целочисленное деление, целую часть двоичного логарифма, целую часть квадратного корня и многие другие. В книге [36] приведена таблица наиболее используемых примитивно рекурсивных функций. Для всех max-ограниченных функций из этой таблицы удалось показать, что они лежат в классе (х) . Для каждой n-местной функции /, присутствующей в этой таблице и не являющейся max-ограниченной, удалось показать, что в классе (х) лежит функция
mf(x, 1,..., хп) = min(ar, f(xu...,я„)).
Функция m,f в некотором смысле содержит всю информацию о функции /. Чтобы не увеличивать длину текста, мы поставим своей целью привести соответствующее доказательство лишь для одной достаточно нетривиальной функции. В качестве такой функции мы выберем функцию верхней целой части квадратного корня. По ходу доказательства соответствующие рассуждения будут проведены и для более простых, но важных функций, среди которых арифметическое вычитание, умножение, знак числа, минимум и максимум.
Полученные результаты позволяют сформулировать следующую гипотезу.
Гипотеза. Класс (х)р есть класс всех max-оераниченных примитивно рекурсивных функций.
Таковы основные результаты диссертации. Они опубликованы в работах [45]-[53]. Эти результаты докладывались на алгебраической конференции памяти Фаддеева (Санкт-Петербург, 1997 г.), конференции Свердловского областного конкурса студенческих работ (Екатеринбург,
1997 г.), XX конференции молодых ученых механико-математического факультета МГУ (1998 г.), конференции "Мальцевские чтения" (Новосибирск, 1998 г.), конференции "Логика и приложения" (Новосибирск, 2000 г.), XXVII конференции молодых алгебраистов (Кайзерслаутерн, Германия, 2002 г.), конференции "Структурная теория автоматов, полугрупп и универсальная алгебра" (Монреаль, Канада, 2003 г.). Также результаты диссетрации излагались на семинарах "Алгебра и логика" и "Алгебраические системы" Института математики СО РАН и Новосибирского государственного университета, семинарах "Алгебра" и "Спецификация дискретных процессов" Технического университета г. Дрездена (Германия), математических коллоквиумах Университета г. Потсдама и Университета г. Ростока (Германия), семинарах "Алгебраические системы" и "Дискретная математика" Уральского государственного университета (Екатеринбург).
Работа выполнена под руководством доцента Евгения Витальевича Суханова, которому автор глубоко признателен за постоянное внимание и всестороннюю поддержку.
Клоны многочленов над полями характеристики 0. Доказательство Теоремы 1
Главным результатом данного параграфа является следующее утверждение. Теорема 1. Если К — поле характеристики 0, то интервал [Ьк, FK] прост, а интервал [LK, FK] изоморфен решетке Sub(N; +). Далее в данном параграфе К обозначает поле характеристики 0, и мы можем считать, что К содержит поле рациональных чисел Q. Как мы выяснили, каждый клон из [l\, FK] / порождается своими одночленами. В данном параграфе нам понадобятся одночлены специального вида. Одночлен вида Х\...хп, являющийся произведением п различных переменных, будем называть простым (1 также считаем простым одночленом). Следующая лемма дает нам важное свойство исследуемых клонов. Лемма 2. Если клон из [LK, FK] содержит одночлен степени D, то он содержит и простой одночлен той же степени. Доказательство. Возьмем произвольный одночлен т клона С Є [LK, FK] Не ограничивая общности можно считать, что т = xfmifa, ...,xr),d 0. Подставив вместо ж і сумму из d переменных у і + ... + y j Є LK, получим где Л є N и многочлен g не содержит одночленов, подобных уi--.yd- По Лемме 1 имеем куі...уцгп\ Є С. Подставляя вместо переменной у і одночлен /с_12/1 є LK с С (Аг1 Є Q С К), получим Применяя в полученном одночлене к переменным Х2, —,хп рассуждения, аналогичные проведенным для х\, получим Отождествляя подходящим образом переменные в простом одночлене, с помощью итеративных операций легко получить любые одночлены той же степени. Поэтому доказанная лемма дает нам основание утверждать, что любой клон из [LK, FK] L-порождается своими простими одночленами. Кроме того, теперь легко доказать простоту интервала [LK,FK], о которой говорится в Теореме 1. Следствие 3. Интервал [LK, FK] прост. Доказательство. Рассмотрим произвольный клон С из [LK, FK] отличный от Ьк- Покажем, что С = FK- Клон С содержит одночлен степени / 1, так как С ф LK. По Лемме 2 он содержит одночлен хі-..xj. Подставляя вместо / — 2 последних переменных одночлен 1 Є LK, получим где — итеративная операция подстановки вместо первого аргумента. Класс С содержит все простые одночлены. Значит, С = FK- Итак, интервал [LK,FK] прост, и нам осталось выяснить устройство интервала [LK,FK]. Назовем длиной одночлена его степень без единицы.
Следующая лемма описывает длины одночленов клонов из [LK, FK]. Лемма 3. Полоокительние длины одночленов клона из [LK,FK] суть в точности элементы подполугруппы из N, порожденной длинами одночленов из произвольного L-порождающего множества этого клона. Доказательство. Рассмотрим клон С = ((/і, -,/ ,)) гДе /ъ / суть одночлены, с ненулевыми длинами /i,..., Ik,..., и S — (h,..., lk,..-) — подполугруппа, порожденная этими длинами. Клон С является подалгеброй, порожденной множеством LK U {/i,..., fk,...} с помощью операций С, т, А, V, . Мы докажем индукцией по построению этой подалгебры, что длины всех одночленов из С лежат в S. База индукции очевидна. Переходя к шагу индукции, отметим, что операции , т, Д, V не изменяют степени одночленов. Поэтому достаточно рассмотреть действие на степени операции . При подстановке га /, где тп = xfm {xi,..., х8) — одночлен степени 1+q, f = 77 +...+771 mi — одночлены, degШІ = l+qi,Tfl,eq,qx,...,qr Є S, получаются одночлены с длинами вида koq + k\q\ + Здесь слагаемое с номером t имеет степень так как degm = 1+д —а. Таким образом, длины всех вновь полученных одночленов лежат в S. Общий случай сводится к предыдущему, так как Чтобы доказать, что положительные длины одночленов из С принимают все значения из S, рассмотрим простые одночлены с длинами li,..., Ik,.... По Лемме 2 такие одночлены в С есть. Заметим теперь, что длины простых одночленов при подстановке складываются: Это, в частности, означает, что длины простых одночленов из С пробегают всю полугруппу S. С учетом Следствия 3 следующее утверждение завершает доказательство Теоремы 1. Предложение 1. Интервал [L0K,FK] изоморфен решетке Sub(N;+). Доказательство. Каждый клон из [LK,FJC] L-порожден своими простыми одночленами. Поставим в соответствие каждой подполугруппе S Є Sub(N;+) клон ф(Я), -порожденный всеми простыми одночленами, длины которых принимают значения из S. По Лемме 3 положительные длины одночленов из замкнутого класса суть в точности элементы подполугруппы из N порожденной длинами одночленов из L-порождающего множества этого замкнутого класса. По Лемме 2 эти длины задают длины простых одночленов замкнутого класса, которые в свою очередь определяют сам класс. Таким образом построенное соответствие есть взаимно-однозначное отображение на [LK,FK\. Легко видеть, что оно сохраняет все включения: VSi, S2 Є Sub(N; +) (Si cS2& 0(Si) С 0(52)). Следствие 4. Любой класс из [LK, FK] L-порожден подходящим конечным множеством. Доказательство. Очевидно, LK = ((1)) и FK = ((1, Xix2)) и L-порождены конечными множествами. Известно также, что любая полугруппа из Sub(N; +) конечнопорождена. В качестве L-порождающего множества для класса из [L -, F%] возьмем множество всех тех простых одночленов этого класса, длины которых принимают все значения из произвольного конечного порождающего множества соответствующей ему полугруппы. Длины таких одночленов при подстановке складываюся и порождают таким образом исходную подполугруппу, которая и определяет класс. Значит, классы из [L ,i ] L-порождены конечными множествами про стых одночленов. 3. Клоны многочленов над бесконечными полями простой характеристики Целью данного параграфа является доказательство следующих трех теорем. Теорема 2. Если К і и К2 — бесконечные поля, то интервалы [LKl, FR-J и [LQK2,FJC2] изоморфны тогда и только тогда, когда характеристики полей К\ и К2 совпадают. Теорема 3. Если К — бесконечное поле простой характеристики, то в интервал [LK, FK] изоморфно (как подрешетка) вкладывается решетка подполугрупп аддитивной полугруппы натуральных чисел. Теорема 4. Если К — бесконечное поле простой характеристики, то в интервал [LK, FK] изоморфно (как частично упорядоченное подмножество) вкладывается ч.у.м. подмножеств счетного множества.
Отметим, что Теорема 2 для полей характеристики 0 следует из Теоремы 1, поэтому основную сложность для нас будет представлять ее доказательство для полей простой характеристики. В этом частном случае Теорема 2 следует из следующих двух утверждений, каждое из которых будет доказано в отдельном пункте данного параграфа. Предложение 2. Если Кх и К2 — бесконечные поля одной простой характеристики, то интервалы [LK F ] и [LKa,FK2] изоморфны. Предложение 3. Если К\ и К2 — бесконечные поля различных простых характеристик, то интервалы [LKl,FKl\ и [LKi,FK2] неизоморфны. Как мы отмечали в первом параграфе, большую роль в доказательстве будут играть некоторые специфические одночлены. Для упрощения обозначений до конца данной главы мы предполагаем, что все рассматриваемые полиномы суть полиномы над фиксированным бесконечным полем К простой характеристики р, за исключением тех частей, где явно говорится обратное. Как это уже было сделано для полей характеристики 0, сначала мы выделим в клонах из [LK, FK] некоторые специальные одночлены. После этого, рассматривая различные L-порождающие множества, состоящие из таких одночленов, приступим к изучению свойств интервала [LK,FK]- Предложение 4. Пусть п N, {а0,..., art-i} С {0,... ,р — 1}, d = Yl а Р1 С Є [ А" FK]- Тогда одночленxfmfa,хТ) лежит в клоне »=о С, если и только если клону С принадлежит одночлен Доказательство. Если в одночлене отождествить все переменные yij с х\, то получится одночлен 77 = xfm(x2,... ,хг). Следовательно, принадлежность клону С одночлена ті влечет принадлежность клону С одночлена іщ- Для доказательства предложения осталось показать, что принадлежность клону С одночлена гаг влечет принадлежность клону С одночлена т\. Очевидно, что (щ + ... + щ) Ь С Си (щ + ... 4- Ud)dm Є С. Поскольку в полях простой характеристики р справедливо равенство (щ + ... + Ud)P = wf +... + upd\ то Воспользовавшись формулой возведения в степень dj, в г-тых скобках получим где Sfc = X)r=0a,., a» ненулевой коэффициент и /І не имеет членов, подобных первому слагаемому.
Доказательство Предложения 3 и Теоремы 2
Для доказательства Предложения 3 нам понадобится некоторая подготовка. До конца данного параграфа под простыми одночленами будут пониматься стандартные простые одночлены. Напомним, что длиной простого одночлена xi-...-xn называется число L(xi ... хп) = п — 1. Каждый одночлен m с коэффициентом 1 может быть получен переименованием переменных из подходящего простого одночлена длины d(m) — 1. Следовательно, если мы удалением непростого одночлена т из множества стандартых р-одночленов клона С С (х )0 получаем множество стан-дартых р-одночленов другого клона, покрываемого клоном С в A4ff, то клон С не должен содержать простой одночлен длины d(m) — 1. Если одночлены mi и т2 просты, то L(m.i гаг) = L(mi) + 1/(77). Поэтому множество всех положительных длин простых одночленов любого фиксированного клона есть подполугруппа аддитивной полугруппы натуральных чисел. Для любого MCN через (М) мы обозначим подполугруппу порожденную множеством М. Как обычно, для любого действительного числа г О целой частью этого числа назовем [г] = тах{тг Є No п г}. Лемма 9. Если /eNuG есть множество то максимальная мощность множеств из G равна [(1-1)/2). Доказательство. Если I = 1 или I = 2, то доказательство очевидно. Предположим теперь, что I 2. Пусть М Є G и к есть произвольный элемент из М. Ясно, что (/ - А;) {1,..., / — 1} и к + (I — к) = I. Поэтому (I — к) М, поскольку / . (М). Если fei, Є М и к± ф к2, то I — &і ф I — к2. Это влечет, что если М содержит п различных элементов из {1,...,1- 1}, то М не содержит п других различных элементов из {1,...,/ — 1}. Поэтому М содержит не более, чем половину элементов из {1,..., I — 1}. Значит, \М\ {l — 1)/2. Пусть теперь Мо есть множество {п Є N [//2]+1 п 1—1}. Очевидно, М0 С {1,... ,/—1}. Сумма любых двух элементов из М0 больше I. Следовательно, I (М0) и М0 є G. Число элементов в Л/0 равно [(1-1)/2]. Ш Лемма 10. 1. Если /eNu (0 есть множество {neNo I (wP(C)\{xi ... xt+i}) - C для некоторого клона СєЬп}, momin(W(l)) = [l/2]. 2. Пусть k — минимальный номер, такой что {изр(С) \ {т}) - С для некоторого клона С Є L и некоторого непростого одночлена т. Тогда k = [(р - 1)/2] + 1. 3. Каждый уровень интервала [JK, (Х1Х2)0] конечен. Доказательство. 1. Предположим, что п Є No, С Є Ln и (wp(C) \ {xi ... X(+i}) С. Легко показать, что одночлен х\ ... хі+і не содержится в клоне, по рожденном всеми другими простыми одночленами из С, или, что эк вивалентно, длина / этого одночлена не содержится в аддитивной по лугруппе, порожденной всеми меньшими длинами простых одночленов из С. По Лемме 9 количество меньших длин простых одночленов из С не больше, чем [(/ — 1)/2].
Поэтому существуют по меньшей мере (1 — 1) — [(1 —1)/2] = [1/2] простых одночленов, не принадлежащих клону С Следовательно, номер п уровня Ln не меньше, чем [1/2]. С другой стороны, если С" — произвольный клон из интервала [JK,{XIX2)] В Лір, и т — простой одночлен из ир(С), минимальный относительно р, то (uip(C) \ {т}) С Поэтому мы можем последовательно удаЛИТЬ ИЗ Wp((xiX2)) ВСе [1/2] ПРОСТЫХ ОДНОЧЛеНОВ ОТ Х\Х2 до Xi ... X[i/2]+i и получить клон из уровня [1/2]. Легко показать, что (этот пример был также использован в доказательстве Леммы 9). Следовательно, Xi . xi+i 2. Пусть т — непростой стандартный р-одночлен. Тогда некоторая переменная в т имеет степень как минимум р. Поэтому d(m) р. Пусть С — клон из Lfc такой, что (шр(С) \ {т}) - С. Клон С не может содер жать простой одночлен длины / = d(m) — 1. Из первого пункта доказы ваемой леммы получаем, что к [1/2]. Имеем Это означает, что к [{р — 1)/2] + 1. С другой стороны, первый пункт леммы влечет, что некоторый клон С уровня [(р — 1)/2] покрывает клон С\ = (о р(С) \ {xi ... хр}). Очевидно, клон Сі принадлежит уровню [(р — 1)/2] + 1. Мы хотим доказать, Это означает, что клон Сз = (/ Є шр(С) / р Xi ... хр) не содержит х\ ... хр. Порождающее множество G = {/ Є OJP(C) \ f р хг ... хр} клона С2 состоит из простых одночленов. Степень каждого одночлена из С? имеет вид где кі,...,кг є No, и її,..., lr суть длины одночленов из G. Легко ви деть, что Сг содержит все простые одночлены таких степеней. Это вле чет, что одночлен xi ... хр не может иметь такую степень. Поэтому Сі не содержит одночленов степени р. В частности, х\ . С2. Очевидно, Сг = {/ Є р(Сі) І І р х У, так как не существует стандартного одно члена / такого, что xi ... хр р f р х\. Значит, (шр{Сі) \ {х\}) - Сі. 3. Очевидно, уровень LQ = {{X1X2Y} конечен. Для любого п Є No Лем ма 7 влечет, что мы получаем множество всех стандартных р-одночленов каждого клона С Є Ln+i удалением некоторого стандартного р-одночлена т из множества шр(С), где С" Ln и С - С. Одночлен т при этом мо жет быть удален Wp(C ), только если С" не содержит простого одночлена длины d(m) — 1. По первому пункту леммы простой одночлен длины d(m) — 1 не может быть удален ни на каком уровне с номером мень ше [(d(m) — 1)/2]. Поэтому мы получаем клоны уровня Ln+1 удалением некоторых элементов конечного множества стандартных р-одночленов степени не более 2п + 1. Поэтому если уровень Ln конечен, то Ln+i так же конечен. Следовательно, все уровни интервала [JK, {#1 2)] конечны, так как уровень LQ конечен. Следующая лемма является главной при доказательстве Предложения 3. Лемма 11. Пусть п Є N. Доказательство. 1. Перед Леммой 9 мы отметили, что множество всех положитель ных длин простых одночленов любого фиксированного клона из ин тервала [Jfc, {xix i)] есть подполугруппа аддитивной полугруппы нату ральных чисел. Это означает, что мы можем определить отображение Мы докажем индукцией по п, что Ln = L+ и Ф(„) = L+ для п [(р- 1)/2] + 1. Очевидно, Zo = \L$\ = 1 и Ф«жіха)) = N. Предположим, что 1 п [(р — 1)/2] + 1, и наше утверждение справедливо для п — 1, то есть \Ln_i\ = ІЬ -хІ и Ф(,„_і) = L+_v По Лемме 10(3) уровень Ln_x конечен. Поэтому ограничение отображения Ф на Ln-i есть взаимно-однозначное соответствие между Ln-\ и Ln_x. Из Леммы 10(2) следует, что если Сі Є Ln, С2 Є Ln i иСн C2, то множество шр(Ря) \ шр(Сі) состоит из некоторого простого одночлена х± ... j+i. Поэтому Ф(С2) \ Ф(Сі) = {1} состоит из одного элемента. Значит подполугруппа Ф(С2) покрывает подполугруппу Ф(Сі) в решетке Sub(N;+). Отсюда следует, что Ф(ге) Q L+. С другой стороны, если Si Є L+, S2 L„_t и Si - Si, то множество S2\Si состоит из некоторого числа /, которое не может быть представлено в виде суммы элементов из Si.
Поэтому, если С2 Ln_i и Ф(С2) = S2, то длина одночлена Xi ... -a +i Є С2 не может быть представлена как сумма длин простых одночленов из ш(С2)\{хі-.. .-хі+і}. Следовательно, клон С2 покрывает клон Ci = (UJ(C2) \ {xi ... xi+i}), так как ир{С2) \ Шр(Сі) состоит из одного элемента. Отсюда следует, Теперь мы докажем, что ограничение отображения Ф на Ln есть взаимно-однозначное соответствие между Ln и L+, чтобы показать, что \Ln\ = L+. Предположим, что Сі,С2 Є Ln и Сі ф С2. Из Леммы 10(2) следует, что каждый из двух клонов содержит все непростые стандартые одночлены. Значит, их множества простых одночленов должны быть различны. Следовательно, множества Ф(Сі) и Ф(С2) длин их простых одночленов также различны. Поэтому ограничение отображения Ф на Ln есть взаимно-однозначное соответствие между L„ и L+. Отсюда Ln = 2. Пусть п = \{р — 1)/2] + 2. По предыдущему пункту доказатель ства \Ln_i\ = L_i, И ограничение отображения Ф на L„_i является взаимно-однозначным соответствием между Ln_i и L+_x. Используя те же рассуждения, что и выше, получаем, что если Si Є L+, S2 Є L+_l: S2 \ Si = {}, С2 Є L„_i и Ф(С2) = S2, то клон С2 покрывает клон Сі = (& (С2) \ {хі ... xj+i}}. Другими словами, мы можем продолжать получать клоны из Ln удалением простых одночленов из множеств стандартных одночленов клонов уровня Ln-i. Следовательно, \Ln\ l nl- По Лемме 10(2) существует непростой стандартный одночлен га такой, что (шр(С) \ {т}) С для некоторого клона С Є n-i-Поэтому В следующей лемме мы перечисляем некоторые свойства интервала [LK, FK], множества Лір и изоморфизма между ними. Лемма 12. Пусть ф : [LK, FK] — Лір — изоморфизм, отображающий каждый клон С є [LK, FK] в клон, порожденный р-одночленами из С. Тогда справедливы следующие свойства: 5. Клон LK — единственный элемент из [LK, FK], покрывающий клон LK. Доказательство. Свойства 1 и 2 следуют непосредственно из определения отображения ф. Легко показать, что клон (хіЖг)0 не содержит одночлен 1 и содержит все другие р-одночлены. Из этого прямо следуют свойства 3 и 4. Очевидно, клон LK покрывает клон LK (см. Диагр. 2).
Частично упорядоченное множество V. Доказательство Теоремы 7
Целью данного параграфа является полное описание частично упорядоченного множества Это описание является центральным результатом второй главы диссертации и состоит из теоремы и диаграммы множества V. Чтобы сформулировать теорему, полезно напомнить некоторые обозначения. Для любой функции д е Oty обозначим через Ъа(д) множество ее значений. Для произвольного множества F С ON,, положим по определению Если М С No, то через PRF(M) мы обозначаем множество всех примитивно рекурсивных функций, у которых области значений содержатся в М. Через М обозначим дополнение множества М в множестве No. По аналогии с /0 положим Д = [(х), {0,х,х + 1)]. Решетку Сс\ разделим на четыре части следующим образом: Зададим отображение Ф : Сс\ — рг формулой Ф(К) = (К) . Сформулируем главную теорему данной главы. Теорема 7. 1. Ч.у.м. Ф(Ьо) изоморфно решетке подмножеств множества N0. Функция Ф изоморфно отображает L0 на Ф(Ь0). 2. Ч.у.м. Ф(Ьі) дуально изоморфно решетке конечных подмножеств множества N0. Для каждого замкнутого класса К Є hi имеем (К)р = PRF(lm(K)). 3. Ч.у.м. $(LQ) изоморфно uj-цепи с внешнеприсоединенным наибольшим элементом. Множество Ф(1 0) состоит из замкнутого класса (No U {х}) и замкнутых классов (т,х) , где т Є N0, которые упорядоченны следующим образом: 4- Множество Ф(Ъ[) одноэлементно и состоит из замкнутого класса всех примитивно рекурсивных функций. 5. Следующие интервалы просты: Диаграмма частично упорядоченного множества V изображена ниже: Доказательство Теоремы 7 будет произведено следующим образом: сначала будут по отдельности описаны части Ф(Ь0), Ф(1а), Ф(Ь0) и Ф(Ь Х) частично упорядоченного множества V, а потом будет показано, как эти части взаимосвязаны. Во введении через О А мы обозначили множество всех функций с аргументами и значениями в множестве А. Поскольку на протяжении всей главы A = N0, то мы будем опускать индекс N0 в этом обозначении, т.е. О = ONQ. Для любого А; Є N обозначим через О множество всех А:-местных функций из О. Легко проверить, что итеративные операции и примитивная рекурсия не расширяют множества значений функций, т.е. для любых f,g є О Следовательно, Ira(F) = Im((F) ) для любого множества функций F С О. Используя этот факт, легко доказать следующие три утверждения. Лемма 15. Пусть FUF2 СО и lm(Fi) ф Im(F2). Тогда (Fi)p ф (F2)p. Следствие 9. Пусть Fi,F2 Є LK — два различных множества констант. Тогда (Fi)p ф (F2)p- Предложение 12. Частично упорядоченное подмножество Ф(Ьо) множества V изоморфно решетке подмножеств множества No. Начнем с некоторых общих свойств.
Первое утверждение следует из определений примитивной рекурсии и рекурсивно замкнутого класса. Утверждение 5. Пусть f Є 0 к\ д Є 0 к+1 и h Є 0 к+1 таковы, что Если использовать это утверждение т раз, то можно получить следующее главное "техническое" утверждение данной главы. Лемма 17. Для любого n 6 N класс (x + n + l)p есть собственный подкласс класса {х + п)р. Доказательство. Очевидно, п Є 1т(х + п), п 1т(х + п + 1), и поэтому Im(x + га) ф Im(x + п + 1). По Лемме 15 замкнутые классы (х + п + 1) и {х + п)р различны. Положим т = п — 1, fi{x) = х + п для г = 0, ...,т — 1 и рассмотрим д(х,у) = у + п. Эта функция принадлежит классу {х + п)р. Определим h Є О следующим образом: Применение Леммы 16 дает, что h Є (х + п)р. Отождествляя переменные в функции h, имеем f(x) = h(x, x) (x + n)p. Легко проверить, что f(x + n) =x + ra+l. Поскольку f(x + n) є (x + n)p, лемма доказана. Следствие 10. 1. Пусть т,п Є N и га п. Тогда (х + п)р — собственный подкласс класса (х + 2. Пусть S — непустое подмножество множества N, ит — минимальный элемент множества S. Тогда замкнутый класс (х + S)p равен (х + т)р. 3. Ч.у.м. Ф([0, {ж + 1)]) изоморфно иі -цепи с внешнеприсоединенным наименьшим элементом. Доказательство. 1. По Лемме 17 2. Для любого п 6 S имеем т п. Поэтому для любого п Є S полу чаем 3. По Теореме 6(3) каждый класс из [0, (х + 1)] порожден некоторым множеством вида х + S, где 5" — подполугруппа аддитивной полу группы N. Используя пункт 2 доказываемого следствия, мы полу чаем, что любой класс из Ф([0, (х + 1)])\{0} имеет вид (х + m)p, где т N. Применение первого и второго пунктов данного следствия дает, что Ф([0, (х + 1)]) изоморфно сі; -цепи с наименьшим внешне- присоединенным элементом. Приступим к доказательству того, что ч.у.м. Ф(Ьі) дуально изоморфно решетке всех конечных подмножеств множества No. Утверждение 6. Класс (0, х + 1}р есть класс всех примитивно рекурсивных функций. Доказательство. Положим h(0) = 0, h(x + 1) = х + 1. Используя Лемму 16, получаем, что h Є (0, х + 1)р. Очевидно, h(x) = х. Поэто му (0, х + 1) = (0, х, х + 1)р. Класс (0, х, х + 1) есть класс примитивно рекурсивых функций. Для любого га Є No через [га, оо] обозначим множество {к Є No к га}. Лемма 18. Для любого га Є No замкнутый класс (га, х + п + 1) равен классу PRF([ra,oo]). Доказательство. Очевидно, Im({n, х + п + 1}) = [п, со]. Нетрудно проверить, что PRF([n, со]) = {/ + п / — примитивно рекурсивная функция}. Поэтому достаточно доказать, что для любой функции / из класса всех примитивно рекурсивных функций функция (/ + п) принадлежит классу (п, х + п + 1)р. Чтобы это доказать, мы следуем порождению класса (О,х + 1)р из функций Оих + 1. Очевидно, функции 0 + п = пи (х + 1) + п = х + п+1 принадлежат классу (п, х + п + 1)_. Рассмотрим функции f,g Є (0, х + 1)р такие, что функции (/ + п) и (д + п) приндалежат клону (п, х + п + 1) . Предположим, что однократное применение итеративных операций или примитивной рекурсии к функциям / и д дало функцию h. Нам нужно доказать, что (h + п) Є {п, х + п + 1) . Мы рассмотрим только применение суперпозиции и примитивной рекурсии. Другие случаи тривиальны. Применение суперпозиции. Пусть / Є 0 к\ д Є 0 т\ Поскольку класс (О, х + 1) замкнут относительно переименования переменных, мы можем предполагать, что Рассмотрим функции Д = / + п и д± = д + п. Определим /2 Є О следующим образом: Используя Лемму 16, получаем /г Є (п, /і) С {п, х + п + 1) . Имеем Следовательно, (h + n) Є (n, x + n + 1) . Применение примитивной рекурсии. Пусть / 0 k\ g Є 0 +2\ fi = f + n, gx = g + п. Положим Определим д2 Є 0(fc+2) следующим образом: Положим по определению Доказательство.
Заметим, что lm{K) = {mi,..., тк} (J[n, со]. По Утверждению 7 имеем га Є (if) . Поэтому, не ограничивая общности, мы можем считать, что га Є К. Поскольку (га, х + п)р С {К)р есть класс всех примитивно рекурсивных функций с областями значений в [га, оо], мы можем полагать, что Теперь докажем лемму индукцией по к. Поскольку п Є К, то база индукции есть Утверждение Шаг индукции. По предположению индукции (m2, ...,mk,x + п)р есть класс PRF(Im(A ) \ {ттн}). Пусть / — примитивно рекурсивная функция такая, что Im(/) С 1т(К) и ті Є Im(/). Нам нужно доказать, что Используя Лемму 16, построим две функции Si, s2 (К)р следующим образом: /і (її,..., ж ) = ах(/(аг1,...,а:Л)). Легко проверить, что Im(/i) С Іш(ііГ) \ {mi}. Положим теперь Утверждение 8. Пусть те Є No, / есть одноместная функция из (х + п)р, и h — одноместная функция такая, что Доказательство. Используя Лемму 16, построим функции hi, h2 Є (х + те следующим образом: Легко проверить, что Л2(0,0) = те и 2(2/ + 1,2/ + 1) = /(у)- Очевидно, Лемма 20. Если та Є N0, то та Є (х + п)р. Доказательство. Пусть функция hi определена следующим образом: hi (г) = та для і = 0,..., та, hi (х + та + 1) = х + та. Используя предыдущее утверждение (та + 1) раз, получим, что hi е {х + п)р. Если х та, то hi (х) = х—1. Теперь положим /(xi) = xi+n, g(xi,x2,x3) = hi(x3) и Следствие 12. &«« та Є N, то (х + п)р = PRF([ra, оо]) Докажем основное утверждение данного пункта. Предложение 13. Ч.у.м. Ф(Ьі) дуально изоморфно решетке всех конечных подмножеств множества No - Доказательство. Легко видеть, что каждый класс из Li порожден некоторым множеством вида К = SiL x + S ), где Si С N0 и 0 ф S2 С N. Используя Следствие 10, Лемму 19 и Следствие 12, мы получаем, что (К) есть класс PRF(Im(AT)). Пусть ті есть наименьший элемент множества 5-2. Тогда [тьоо] С Ъп(К) и, следовательно, множество 1т(К) конечно. Пусть М конечное подмножество множества No, и т2 — наибольший элемент из М. Положим S\ = Ми [тпг + 1,со] и К = Si U {х + т2 + 1}. По Лемме 19 класс {К) равен классу PRF(M). Пусть Ф — отображение из множества всех конечных подмножеств множества N0 в Ф(Гц), переводящее конечное множество М в PRF(M).
Вторая часть доказательства Теоремы 8
Здесь мы докажем, что К$ С Сф. Для этого нам достаточно построить все функции класса К$ применением к константам из стандартных итеративных операций и примитивной рекурсии. Далее мы будем неоднократно пользоваться следующей леммой, которая непосредственно следует из Леммы 16. Лемма 26. Пусть f0, ..., fm — k-местные функции и д — (к + 1)-местная, j — натуральное число, не превосходящее к. Тогда в (g,fo,..., fm)p есть (к + 1)-местная функция h такая, что Дальнейшее доказательство будет происходить следующим образом. Вначале мы покажем, что в классе С$ лежат все функции / Є К$, для которых m(f) = 0. Такие функции мы будем называть периодическими. После этого мы докажем, что К о С С$. Следующее предложение является центральным утверждением второй части доказательства теоремы. Предложение 16. Класс С$ содержит все периодические функции из класса К$. Доказательство предложения будем вести индукцией по числу переменных. База индукции выполнена, т. к., очевидно, все нульместные функции из К $ лежат в С$. Дальнейшие рассуждения, оформленные в виде трех последующих лемм, относятся к шагу индукции. Мы предполагаем, что для fc-местных периодических функций наше утверждение доказано. Нужно доказать его для (к + 1)-местных функций. Для удобства работы с функциями от А; и более переменных мы до конца параграфа вводим обозначение х = (xi,...,Xk). Нам понадобится следующее определение. Определение 6. Циклом (к + 1)-местной периодической функции f, периодичной по последней переменной с периодом р, называется кортеж к-местных функций Лемма 27. Если в С лежит (к + 1)-местная периодическая функция f, периодичная по последней переменной с периодом р, то в С лежит и периодическая функция с циклом Доказательство. Рассмотрим функцию Это А;-местная периодическая функция. Из предположению индукции по числу переменных получаем, что она лежит в С . По Лемме 26 в Сф есть функция h такая, что Имеем Отсюда легко получаем, что h — периодическая функция с циклом, ука занным в (14). Из доказанной леммы вытекает следующее утверждение. Следствие 13. Если в Со лежит (к+ 1)-местная периодическая функция f с периодом р по последней переменной, то для произвольного натурального г такого, что 2 і р — 1, в С$ лежит и периодическая функция с циклом Дальнейшее доказательство предложения будет проводиться индукцией по длине р периода по последней переменной. Более точно, будет доказано следующее утвержение: "Для любого р Є N произвольная (k +1)-местная периодическая функция / из К$ с периодом р по последней переменной лежит в С ". База индукции очевидна, т. к. все (k + 1)-местные периодические функции из К$ с периодом 1 лежат в С ; эти функции не зависят от последней переменной и получаются из соответствующих fc-местных функций, лежащих в С , добавлением фиктивной переменной (при помощи операций V и С).
Предположим теперь, что наше утверждение доказано для всех (к + 1)-местных функций класса К$ таких, что их периоды по последней переменной меньше р. Если р не делит никакую натуральную степень числа га!, то наше утверждение очевидно. Пусть р делит (n!)d, где d Є N. Тогда р = qp\, где q — простое число, не превосходящее п. Число pi меньше, чем р, поэтому в Со лежат все (А+1)-местные периодические функции из К$ с периодом Рх по последней переменной. Лемма 28. Класс С$ содержит одноместную периодическую функцию с циклом Доказательство. Пусть т = гаах{со, -.., c„_i}. Рассмотрим следующую последовательность /о,..., /т одноместных периодических функций с периодом р\. Положим для каждого Q Є S$ если Хі = 0 (mod pi), иначе. Здесь ф — сложение по модулю q. Для k . S положим Д(хі) = Со (эти оставшиеся функции будут мало влиять на дальнейшие построения и вводятся для более формального использования Леммы 26 ). По предположению индукции в классе С лежат все (А; + 1)-местные функции из ЙГ с периодом рі, в том числе имеющие только одну существенную переменную. Это означает, что классу С принадлежат и все одноместные функции из К с периодом рх. Очевидно, все fi (0 і т) периодичны с периодом pi и следовательно принадлежат классам Сф и К$. По Лемме 26 в С есть двуместная функция hx такая, что Лі(хі, г) = /І(ХІ) для всех г Є {0,..., т}, hi(xi,y + m+ 1) = со. Функция hi обладает следующими очевидными свойствами. Построим функцию h2 Є Со следующим образом Сейчас, воспользовавшись свойствами функции hi, мы докажем, что h2 периодична с циклом длины р. Согласно (15) и свойствам 1 и 2 функции hi, имеем т. е. первые р значений функции h-i образуют кортеж (16) и /г2(р) = c,_i. Аналогично, воспользовавшись свойством 3 функции hi, индукцией по / Є NQ легко доказать равенства hvilp + qpi) = c9_i. Это и означает, что h2 периодична с циклом (16). Применяя к h2 следствие из Леммы 27 (для і = р — 1), получаем, что в С лежит искомая одноместная периодическая функция с циклом Лемма 29. Для произвольных к-местных периодических функций /о,... ,/p-i из АГ в классе Доказательство. Из предположения индукции по к мы имеем, что функции /о, ..., /p_i лежат в С . Предположение индукции по р дает нам, что класс С$ также содержит (к + 1)-местные периодические функции hi (0 і q — 1) с циклами имеющими длину pi. По Лемме 26 в С есть (к + 2)-местная функция Н со свойством При этом Лемма 28 гласит, что класс С содержит одноместную периодическую функцию hс циклом Таким образом, функция / периодична с циклом Ш Лемма 29 завершает доказательство предложения, т. к. каждая (к + 1)-местная периодическая функция полностью определяется своим циклом, а каждый элемент ее цикла есть /г-местная периодическая функция. Итак, все периодические функции из K$ лежат в С . Следующая лемма фактически говорит о том, что то же самое относится и к финально периодическим функциям ИЗ KQ. Лемма 30. Для любой k-местной функции f класса К$ и для произоль-ного натурального I, не превосходящего к, найдется функция h из С$ со свойством Доказательство. Рассуждение будем проводить индукцией по к. Вследствие того, что наше утверждение для к = О очевидно, необходимо произвести лишь шаг индукции.
Его мы будем доказывать индукцией по I. Прежде всего заметим, что согласно доказанному предложению в классе С лежит периодическая функция д, определенная равенством Воспользовавшись этим фактом, мы в качестве доказательства базы индукции по I продемострируем, что в классе С лежит функция Доказательства шага и базы индукции совершенно аналогичны друг другу, поэтому мы приведем только доказательство базы. Предположение индукции по к дает нам, что в С$ лежат все (к — 1)-местные финально периодические функции класса К$. В частности, класс С содержит функции /І (0 г m(f) — 1), определенные равенствами Воспользовавшись Леммой 26 , получаем, что в С лежит функция h такая, что h(i,x2,...,xk) = fi(x2,...,xk) для всех г є {0,...,m(f)- 1}, h{y + m(f), x2,..-, Xk) = g(y, x2,..., xk) Воспользовавшись определениями функций fi и g, получим что и требовалось. Доказательство шага индукции по / отличается лишь тем, что вместо функции д используется функция а Лемма 26 используется для j = I. Первый пункт Теоремы 8 доказан. Как мы отмечали, второй пункт Теоремы 8 легко следует из первого. Доказательство этого следствия основывается на том, что любая алгебра есть теоретико-множественное объединение всех своих подалгебр, порожденных конечными подмножествами из порождающего множества этой алгебры. Если в качестве основного множества алгебры взять класс (CQ,CI,...)P, в качестве операций взять , т, Д, V, и / , ав качестве порождающего множества взять {со, с\,...}, то легко получить, что Воспользовавшись первым пунктом Теоремы 8 и этим равенством, легко установить справедливость второго пункта Теоремы 8. Мы имеем явное описание функций из замкнутых классов множеств Ф(Ьо), Ф(Ь»і) и $(1 ). В рассматриваемом нами множестве V такого описания не получено лишь для замкнутых классов из Ф(Ь0). Можно показать, что это описание определенным образом сводится к описанию наименьшего класса (х) множества Ф(Ь0). Главной целью данного параграфа будет высказать гипотезу о том, из каких функций состоит класс (ж) , и привести некоторые факты в пользу этой гипотезы. Для ее формулировки нам понадобится следующее определение. Если га-местная функция / обладает свойством то мы будем называть ее max- ограниченной. Справедливо следующее утверждение. Предложение 17. Каждая функция из (х)р является тах-ограниченной. Доказательство.
