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

• Автор: Семигродских, Александр Павлович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Екатеринбург
• Количество страниц: 103 с.

Содержание
Содержание
Введение

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

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

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

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

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

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

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

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

§2. Клоны многочленов над полями характеристики 0.
Доказательство Теоремы
§3. Клоны многочленов над бесконечными полями простой
характеристики
3.1. Основные сведения о р-одночленах
0 3.2. Клоны, порожденные и Т-порожденные р-одночленами.
Доказательство Предложения
3.3. Покрытия в Мр и 8иЬ(Н; +)
3.4. Доказательство Предложения 3 и Теоремы
3.5. Доказательство Теоремы 3 и Теоремы
§4. Дополнительные результаты
Глава 2. Замкнутые классы примитивно рекурсивных
функций
§1. Замкнутые классы некоторых простейших одноместных
функций
1.1. Основные факты. Доказательство Теоремы
1.2. Строение интервала 10. Доказательство Теоремы
§2. Частично упорядоченное множество V. Доказательство
Теоремы
2.1. Частично упорядоченное подмножество Ф(Ьо)
2.2. Частично упорядоченные подмножество Ф(1ч)
2.3. Частично упорядоченное подмножество Ф(Ьд)
2.4. Описание частично упорядоченных множеств Ф(Ц) и V ■ ■

§3. Замкнутые классы финально периодических функций.
Доказательство Теоремы
3.1. Первая часть доказательства Теоремы
3.2. Вторая часть доказательства Теоремы
§4. Дополнительные результаты
Литература
Указатель обозначений
Введение
1. Общая характеристика работы
Суперпозиция является одной из основных операций над функциями. Изучение суперпозиции функций, определенных на конечном множестве, привело к возникновению теории замкнутых классов. В термине ’’замкнутый класс” слово ’^замкнутый” означает именно ’’замкнутый по суперпозиции”. К настоящему времени эта теория обрела четкие контуры, собственную богатую проблематику и содержит большое число результатов. Имеющаяся литература весьма обширна, поэтому упомянем лишь несколько работ обзорного характера и монографий [19, 27, 28, 37, 44]. С начала 90-х годов эта область развивается и в Екатеринбурге. Обзору полученных здесь результатов посвящены работы [29, 30].
Исходной проблемой для теории замкнутых классов является проблема функциональной полноты. Она заключается в том, чтобы для произвольного набора функций (с аргументами и значениями в некотором фиксированном основном множестве) определить, можно ли из этих функций путем суперпозиций получить все функции с аргументами и значениями в этом множестве. Эта проблема была решена Постом для случая двухэлементного основного множества [38], Яблонским для случая трехэлементного множества [27] и Розенбергом для произвольного конечного основного множества [41].
Перейдем теперь к рассмотрению суперпозиции функций на бесконечном множестве.
Прежде всего отметим, что уже в девятнадцатом веке существовал интерес к алгебраическим свойствам суперпозиции вещественных функций. В двадцатом столетии среди результатов, относящихся к этой области, наибольший резонанс вызвали работы А. Н. Колмогорова [14] и В. И. Арнольда [1], которые доказали, что всякая вещественная непрерывная функция от п переменных представима в виде суперпозиции непрерывных функций двух переменных. Этот результат не только удивителен сам по себе, но и опровергает предположение, высказанное в формулировке тринадцатой проблемы Гильберта [33]. Подчеркнув фундаментальность этого вопроса и напомнив его историю, известный спе-циаист по универсальной алгебре У. Тейлор в своем докладе на алгебра^ ической конференции в Праге в 1995 году призвал исследовать суперпозицию непрерывных функций с алгебраической точки зрения. Более

а0,. ..,ап_і Є {0,.... р — 1}. Из определения операции * вытекает, что для некоторого одночлена т», получающегося из тп несклеивающим переименованием переменных, имеем 7П1Д * /2 = /2 771,. Далее, ИСПОЛЬЗуЯ тождество (і! + х2)р = з% + х2 нашего поля простой характеристики, получаем
п—1 { п—
/2т* = 771* П /£р = т* П (т2,1 + • • - + т2м)аіР' =
^ 1=1 1=
= ТП, П (тії + ■ ■. + т£*а)°

Теперь, раскрывая скобки и записывая т1:1*/2 в виде суммы одночленов, получаем, что каждый одночлен из этой суммы имеет вид
п-1 <ц
ат.ПП<„- (10)
і=0 2=
где а Є К и 1 < «у < к2 для г = 0,..., п — 1 к j = 1,..., ад Нам достаточно доказать, что при действии тг(, на каждый такой одночлен получится одночлен из (7гр(тід) и лр(/2)). Рассмотрим одночлен
п-1 а»
М = атп, пп щ'
1=0 2=
где для і = 0,..., п — 1, і = 1,..., а* одночлен Му получен из одночлена т2і„- таким несклеивающим переименованием переменных, что одночлены Му не имеют между собой и с одночленом тп, общих переменных. Ясно, что одночлен (10) получается из одночлена М обратным переименованием переменных. Поскольку включения (7) и (9) выполняются для любого многочлена /і, то справедливо следующее
Утверждение 3. Пусть / — многочлен над К, получающийся из многочлена д переименованием переменных. Тогда 7ГР(/) С {кр(д)).
Из этого утверждения, в частности, вытекает, что при действии тгр на одночлен (10) получается одночлен из (7ГР(М)). Это означает, что теперь нам достаточно доказать, что п'р(М) є (яДтщ) и7Гр(/2)). Используя пункты 2 и 3 Предложения 5, имеем
тг;(М)=т',ПП(М'Г