Введение к работе
Актуальность темы и .
Диссертационная работа посвящена изучению структурных свойств верхних полурешеток п-в.п. тьюринговых степеней (далее, Т-степеней, или степеней) для различных натуральных п > 0.
Изучению верхних полу решеток тьюринговых степеней, состоящих из конечных булевых комбинаций перечислимых множеств, посвящены многие работы. В трудах Арсланова, Доуни, Ейтса, Калимуллина, Купера, Лахлана, Лемппа, Ли, Соара, Харрингтона исследуются различные свойства разложимости, изолированности, дополняемости и недополняемости для степеней из этих структур.
В последние несколько десятилетий в теории вычислимости особый интерес представляют теоретико-модельные аспекты различных структур. Многие крупные проблемы для Т-степеней на сегодняшний день связаны с вопросами определимости и элементарной эквивалентности. Изучение структурных свойств нередко приводит к нахождению отличий в элементарных теориях изучаемых структур.
Например, изучая вопросы дополняемости в 2-в.п. степенях и используя теорему Купера и Ейтса о недополняемости в в.п. степенях, Ар-сланов [1-2] доказал различие элементарных теорий верхних полурешеток в.п. и п-в.п. Т-степеней при любом п > 1. Затем Доуни [3] выдвинул гипотезу о том, что элементарные теории п-в.п. и т-в.п. степеней при различных n,m > 1 совпадают. Однако Арсланов, Калимуллин и Лемпп [4] доказали, что верхние полу решетки 2-в.п. и 3-в.п. степеней не являются элементарно эквивалентными. Для общего случая вопрос до сих пор остается открытым.
Широкий подкласс задач составляют вопросы о свойствах частичных порядков низких п-в.п. степеней. Свойства низких степеней изучались в работах Арсланова, Доуни, Купера, Лемппа, Ли, Сакса, Ю (см. [5-9]). Неоднократно упоминалось Доуни [9-10], что неизвестен ответ на вопрос об элементарной эквивалентности частичных порядков 2-низких
в.п. и 2-низких 2-в.п. степеней.
В диссертационной работе изучены свойства разложимости 2-в.п. степеней с избеганием конусов, изучены вопросы сильной недополняемости в низких в.п. степенях, доказано существование низких 2-в.п. степеней с определенными свойствами, что позволяет доказать различие элементарных теорий низких в.п. и низких 2-в.п. степеней. Кроме того, конструкция позволяет автоматически получить различие частичных порядков п-низких в.п. и п-низких 2-в.п. степеней. Таким образом, при п = 2 получаем ответ на упомянутый выше вопрос Доуни.
Цель работы.
Целью настоящей работы является:
Изучение структурных свойств Т-степеней таких, как разложимость, изолированность, дополняемость и недополняемость.
Нахождение полезных взаимосвязей между этими свойствами.
Исследование частичных порядков низких п-в.п. Т-степеней и установление элементарного сходства или различия низких в.п. и низких 2-в.п. Т-степеней.
Нахождение формул, которые бы отличали элементарные теории структур, носителями которых является различные подклассы класса всех Т-степеней.
Методы исследования.
В диссертационной работе используются методы теории вычислимости. Основными методами для доказательства теорем являются методы приоритета с конечными и бесконечными нарушениями и метод деревьев для проведения приоритетных конструкций. Теоремы 1.1, 2.1, 3.1 используют О"-, О'"- и 0'"-приоритетные рассуждения на деревьях, соответственно. При доказательстве теоремы 1.2 используется метод приоритета с конечными нарушениями (метод 0'-приоритета).
Основные результаты диссертации.
Сформулировано и доказано достаточное условие для возможности разложения собственной 2-в.п. степени с избеганием верхнего конуса произвольной ДІ]-степени. Тем самым доказан специальный случай теоремы Сламана и Шора и в разных смыслах обобщены теорема Купера о разложении 2-в.п. степеней и теорема Сакса о разложении в.п. степеней с избеганием конусов.
Доказано существование двух низких невычислимых 2-в.п. степеней d и е таких, что 0 < d < е и для любой 2-в.п. степени w выполняется: [w < е ^ [w < d V d < w]]. В качестве следствия получаем различие элементарных теорий частичных порядков n-низких в.п. и п-низких 2-в.п. степеней для любого натурального п > 0.
Доказано свойство сильной недополняемости в низких в.п. степенях.
Научная новизна.
Все полученные результаты являются новыми, получены автором самостоятельно и снабжены подробными доказательствами. Некоторые их них отвечают на открытые вопросы, сформулированные в ряде публикаций (см. Доуни [9-10]), другие обогащают и дополняют известные факты о таких структурных свойствах тьюринговых степеней, как разложимость, изолированность, дополняемость и недополняемость.
Теоретическая и практическая значимость.
Работа носит теоретический характер. Ее результаты могут быть использованы в теории вычислимости для дальнейших исследований свойств различных степенных структур. Материалы диссертации могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.
Апробация результатов.
Результаты диссертации докладывались
на международной конференции "Logic Colloquium-2006" (Неймеген, Нидерланды, 2006 г.)
на международной конференции "Мальцевские чтения-2007" (Новосибирск, 2007 г.);
на международной конференции "Logic Colloquium-2008" (Берн, Швейцария, 2008 г.);
на международной конференции "Logic Colloquium-2009" (София, Болгария, 2009 г.);
на международной конференции "Мальцевские чтения-2009" (Новосибирск, 2009 г.);
на семинарах "Алгебра и логика" и "Теория вычислимости" (Новосибирск, 2009 г.)
на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского государственного университета им. В.И.Ульянова-Ленина в 2006-2009 гг.
Публикации.
Основные результаты опубликованы в трех статьях [12-14] и семи тезисах [15-21], список которых приведен в конце автореферата. Структура и объем работы.
Диссертационная работа изложена на 86 страницах и состоит из введения, трех глав, и библиографического списка использованных источников, содержащего 31 наименование.
