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

• Семигродских, Александр Павлович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Семигродских, Александр Павлович

Содержание.

Введение.

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. С помощью каких естественных свойств функций без использования рекурсивного замыкания можно задать элементы множества Р?

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

Список литературы диссертационного исследования кандидат физико-математических наук Семигродских, Александр Павлович, 2003 год

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.