Разрешимые множества их свойства

разрешимые множества их свойства Перечислимые и разрешимые множества Теорема 2. Всякое разрешимое множество натуральных чисел перечислимо. Если  множество A и его дополнение (до множества всех натуральных чисел) перечислимы,  то A разрешимо. Если принадлежность числа к множеству A можно проверить некоторым алгоритмом,  то A и его дополнение перечислимы: надо по очереди проверять принадлежность  чисел 0,1,2,... и печатать те из них, которые принадлежат A (или те, которые не  принадлежат A ). В другую сторону: если у нас есть алгоритм, перечисляющий A, а также  другой алгоритм, перечисляющий дополнение к A, то для выяснения принадлежности  заданного числа n к A надо запустить оба эти алгоритма и ждать, пока один из них  напечатает n (мы знаем, что рано или поздно ровно один из них это сделает). Посмотрев,  какой алгоритм это сделал, мы узнаем, лежит ли n в A. Этот факт называют теоремой Поста Она говорит, что разрешимые множества это перечислимые множества с  перечислимыми дополнениями. Напротив, перечислимыемножества можно определить  через разрешимые: Теорема 3. Множество P натуральных чисел перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества Q пар натуральных чисел.  (Проекция получается, если от пар оставить их первые  компоненты:  .) Проекция любого перечислимого множества перечислима  (перечисляющий алгоритм должен лишь удалять вторые члены пар), так  чтопроекция разрешимого множества тем более перечислима. Напротив, если P перечислимое множество, перечисляемое алгоритмом A, то оно  есть проекция разрешимого множества Q, состоящего из всех таких пар  что x появляется в течении первых n шагов работы алгоритма A. (Это свойство, очевидно, разрешимо.) ,  Перечислимость и вычислимость Мы видели, что перечислимое множество можно определить в терминах вычислимых  функций (например, как область определениявычислимой функции). Можно сделать и  наоборот: Теорема 4. Функция f с натуральными аргументами и значениями вычислима тогда и  только тогда, когда ее график является перечислимым множеством пар натуральных чисел. Пусть f вычислима. Тогда существует алгоритм, перечисляющий ее область  определения, то есть печатающий все x, на которых fопределена. Если теперь для  каждого из таких x вычислять еще и значение f(x), получим алгоритм, перечисляющий  множествоF. Напротив, если имеется алгоритм, перечисляющий F, то функция f вычисляется таким  алгоритмом: имея на входе n, ждем появления в F пары, первый член которой равен n ;  как только такая пара появилась, печатаем ее второй член и кончаем работу. Пусть f частичная функция с натуральными аргументами и  значениями. Образ множества A при f определяется как множество всех чисел f(n), для  которых  множество всех тех n, при которых f(n) определено и принадлежит A.  и f(n) определено. Прообраз множества A при f определяется как  Теорема 5. Прообраз и образ перечислимого множества при вычислимой функции  перечислимы. В самом деле, прообраз перечислимого множества A при вычислимой функции f можно  получить так: взять график f, пересечь его с перечислимым множеством N x A и  спроектировать на первую координату. Рассуждение для образов аналогично,  толькокоординаты меняются местами.   7. Пусть F перечислимое множество пар натуральных чисел. Докажите. что существует  вычислимая функция f, определенная на тех и только тех x, для которых найдется y, при  котором  называют иногда теоремой об униформизации.) , причем значение f(x) является одним из таких y. (Это утверждение   8. Даны два пересекающихся перечислимых множества X и Y. Докажите, что найдутся  непересекающиеся перечислимыемножества  которых  , для  .  и 9. Диофантовым называется уравнение, имеющее вид P(x1,...,xn)=0, где P многочлен с  целыми коэффициентами. Докажите, что множество диофантовых уравнений, имеющих  целые решения, перечислимо. (Оно неразрешимо: в этом состоит известный результат  Ю.В.Матиясевича, явившийся решением знаменитой " 10­й проблемы Гильберта".)   10. Не ссылаясь на доказательство теоремы Ферма, покажите, что множество всех  показателей n, для которых существует решение уравнения xn + yn = zn в целых  положительных числах, перечислимо. (Как теперь известно, это множество содержит  лишь числа 1и 2.)   11. Покажите, что всякое бесконечное перечислимое множество можно записать в  виде {a(0), a(1), a(2),...}, где aвычислимая функция, все значения которой различны.  (Указание: в ходе перечисления удаляем повторения.)   12. Покажите, что всякое бесконечное перечислимое множество содержит бесконечное  разрешимое подмножество. (Указание: воспользуемся предыдущей задачей и выберем  возрастающую подпоследовательность.)   13. Покажите, что для всякой вычислимой функции f существует вычислимая функция,  являющаяся " псевдообратной " к f в следующем смысле: область  определения g совпадает с областью значений f, и при этом f(g(f(x)))=f(x) для всех x, при  которых f(x) определено.   14. Действительное число  вычислимая функция a, которая по любому рациональному   называется вычислимым, если существует   дает рациональное   для любого   с ошибкой не более  приближение к  рационального  понятие вычислимости не требует специального уточнения.)  т.е.  . (Рациональное число является конструктивным объектом, так что   Докажите, что число   вычислимо тогда и только тогда, когда множество  рациональных чисел, меньших   разрешимо.  Докажите, что число   вычислимо тогда и только тогда, когда последовательность  знаков представляющей его десятичной (или двоичной) дроби вычислима.  Докажите, что число   вычислимо тогда и только тогда, когда существует  вычислимая последовательность рациональных чисел, вычислимо сходящаяся к  (последнее означает, что можно алгоритмически указать N по   в стандартном  ­ N ­определении сходимости.)  Покажите, что сумма, произведение, разность и частное вычислимых  действительных чисел вычислимы. Покажите, что корень многочлена с  вычислимыми коэффициентами вычислим.  Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся  последовательности вычислимых действительных чисел вычислим.  Действительное число   называют перечислимым снизу, если множество всех  рациональных чисел, меньших  определяется аналогично.) Докажите, что число  только тогда, когда оно является пределом некоторой вычислимой возрастающей  последовательности рациональных чисел. перечислимо. (Перечислимость сверху   перечислимо снизу тогда и   Докажите, что действительное число вычислимо тогда и только тогда, когда оно  перечислимо снизу и сверху. Разрешимость и перечислимость множеств Теперь, когда мы достаточно подробно изучили три различных формализации понятия  алгоритма, установили их эквивалентность и сформулировали тезисы Тьюринга, Чёрча и  Маркова, можно сделать некоторые общие выводы. Из наших рассмотрений следует, что  любые утверждения о существовании или несуществовании алгоритмов, сделанные в  одной из трех формализации, верны и в Другой. Это означает, что возможно развитие и  изложение теории алгоритмов, инвариантное по отношению к способу формализации  понятия "алгоритм". Это своего рода общая теория алгоритмов. Основные ее понятия —  алгоритм и вычислимая функция. При интерпретировании этой общей теории, например, в теории рекурсивных функций  понятие алгоритм превращается в рекурсивное описание функции, понятие вычислимая  функция — в понятие частично рекурсивная (или общерекурсивная) функция. (При этом  следует всегда помнить, что алгоритм и вычисляемая им функция — это не одно и то же.  Одна и та же функция может вычисляться с помощью разных алгоритмов.) Будем рассматривать функции f от одного или нескольких аргументов, заданные на  множестве N=\{0,1,2,3,4,\ldots,n,\ldots\} всех натуральных чисел или на некоторых его  подмножествах (частичные функции) и принимающие значения в множестве N. Таким  образом, рассматриваются функции f, являющиеся отображениями декартовой n­й  степени N^n в множество N. Область определения Df функции f есть подмножество  множества N^n=N\times\ldots\times N\colon Df=\{(x_1,\ldots,x_n)\colon\, f(x_1,\ldots,x_n)  — определено}. Область изменения (значений) f есть подмножество множества N\colon If= \bigl\{y\in N\colon\, (\exists x_1,\ldots,x_n)(f(x_1,\ldots,x_n)=y)\bigr\}. Определение 35.1. Функция f(x_1,\ldots,x_n) называется вычислимой, если существует  алгоритм, позволяющий вычислять ее значения для тех наборов аргументов, для которых  она определена, и работающий вечно, если функция для данного набора значений  аргументов не определена. Пусть M\subseteq N^n=N\times\ldots\times N. Определение 35.2. Множество M называется разрешимым, если существует алгоритм  A_M, который по любому объекту a дает ответ, принадлежит a множеству Мили нет.  Алгоритм A_M называется разрешающим алгоритмом для M. Известно понятие характеристической функции множества M. Ею называется функция  \chi_M, заданная на множестве M, принимающая значения в двухэлементном множестве \ {0;1\} и определяемая следующим образом: \chi_M(x_1,\ldots,x_n)= \begin{cases}0,&\text{if}\quad (x_1,\ldots,x_n)\notin M;\\  1,&\text{if}\quad (x_1,\ldots,x_n)\in M. \end{cases} Отсюда ясно, что множество M разрешимо тогда и только тогда, когда его  характеристическая функция \chi_M вычислима. Примером разрешимого множества может служить множество всех тавтологий логики  высказываний. Разрешающий алгоритм состоит в прямом вычислении значений данной  формулы на всевозможных наборах значений ее пропозициональных переменных  (составление таблицы истинности формулы). Пусть теперь M\subseteq N. Определение 35.3. Множество M\subseteq N называется (рекурсивно, или эффективно,  или алгоритмически) перечислимым, если M либо пусто, либо есть область значений  некоторой вычислимой функции или, другими словами, если существует алгоритм для  последовательного порождения (перечисления) всех его элементов. Другими словами, M перечислимо, если существует такая вычислимая функция  \varphi_M(x), что a\in M \Leftrightarrow (\exists x)(a=\varphi_M(x)). Функция \varphi_M  называется перечисляющей множество M (или для множества M); соответственно  алгоритм, вычисляющий \varphi_M, называется перечисляющим или порождающим для M. Пример 35.4. Рассмотрим множество М=\{1,4,9,16,25,36, \ldots\} квадратов натуральных  чисел. Оно перечислимо: для получения его элементов нужно последовательно брать  числа 1,2,3,4,\ldots и возводить их в квадрат. Другими словами, M есть область значений  вычислимой функции f(x)=x^2\colon M=\{1^2,2^2, 3^2, 4^2, \ldots\}. Более того, это  множество является также и разрешимым: для проверки того, принадлежит или нет  некоторое число данному множеству, нужно разложить число на простые множители, что  позволит выяснить, является ли оно точным квадратом. Далее, в теореме 35.6 будет показано, что любое разрешимое множество перечислимо, а в  теореме 35.7 — что обратное утверждение неверно. Важность понятий разрешимости и перечислимости множеств для оснований математики  связана с тем, что язык теории множеств является в известном смысле универсальным  языком математики. Всякому математическому утверждению можно придать вид  утверждения о каких­либо множествах. В связи с этим к способам задания множеств  предъявляются повышенные требования. Необходимо точное понимание таких понятий,  как "конструктивный способ задания множества" и "множество, заданное эффективно".  Это и достигается благодаря понятиям разрешимости и перечислимости множества. Язык разрешимых и перечислимых множеств является универсальным языком для утверждений о существовании (или отсутствии) алгоритмов решения математических проблем. Теорема 35.5. Если множества M и L перечислимы, то перечислимы множества M\cup L и  M\cap L. Доказательство. Если имеются алгоритмы для порождения элементов множеств M и L, то алгоритм для порождения множества M\cup L получается из исходных путем их  одновременного применения. Следовательно, множество M\cup L перечислимо. Пусть теперь алгоритм \Omega_M последовательно порождает элементы  m_1,m_2,m_3,\ldots множества m, а алгоритм \Omega_L последовательно порождает  элементы l_1,l_2,l_3,\ldots множества L. Тогда алгоритм для перечисления элементов  множества M\cap L заключается в следующем. Поочередно с помощью алгоритмов \Omega_M и \Omega_L порождаются элементы  m_1,l_1,\, m_2,l_2,\, m_3,l_3 и т.д. Каждый вновь порожденный элемент m_i сравнивается  со всеми ранее порожденными элементами l_j. Если m_i совпадает с одним из них, то он  включается во множество M\cap L. В противном случае надо переходить к порождению  элемента l_i и сравнивать его со всеми ранее порожденными элементами m_j, и т.д.  Описанная процедура позволяет эффективно перечислить все элементы множества M\cap  L, что и требовалось доказать. Теорема 35.6. Пусть M\subseteq N. Множество M разрешимо тогда и только тогда, когда  оно само и его дополнение \overline{M} перечислимы. Доказательство. Необходимость. Пусть M — разрешимое множество. Можем считать, что M\ne \varnothing, т. е. имеется элемент a\in M. Тогда характеристическая функция \chi_M  множества M, как было отмечено выше, вычислима, т.е. имеется алгоритм для ее  вычисления. Строим алгоритм для перечисления множества M. Рассмотрим функцию f(x)= \begin{cases}x,&\text{if}\quad \chi_M(x)=1,\\ a,&\text{if}\quad \chi_M(x)=0.  \end{cases} Отсюда M=\{f(0), f(1), f(2), f(3),\ldots\}, то есть M есть множество значений функции f,  которая, очевидно, вычислима ввиду вычислимости функции \chi_M(x). Следовательно,  множество M перечислимо. Аналогично, выбрав элемент b\notin M, строим функцию: g(x)= \begin{cases}b,&\text{if}\quad \chi_M(x)=1,\\ x,&\text{if}\quad \chi_M(x)=0,  \end{cases} которая также вычислима ввиду вычислимости функции \chi_M(x). Кроме того,  \overline{M}=\{g(0), g(1), g(2), g(3),\ldots\}, т.е. \overline{M} есть множество значений  вычислимой функции g. Следовательно, множество \overline{M} также перечислимо. Достаточность. Пусть множества M и \overline{M} перечислимы, т. е. M=\{f(0), f(1), f(2),  f(3),\ldots\} и \overline{M}=\{g(0), g(1), g(2), g(3),\ldots\}, где f и g — некоторые  вычислимые функции. Тогда алгоритм, выясняющий, принадлежит или нет произвольное  число n множеству M, действует следующим образом. Последовательно порождаем  элементы f(0),g(0),\, f(1),g(1),\, f(2),g(2),\ldots и на каждом шаге получаемый элемент сравниваем с n. Поскольку n должно принадлежать либо M, либо \overline{M}, то на  конечном шаге получим f(k)=n или g(k)=n. Если f(k)=n, то n\in M, а если g(k)=n, то n\in  \overline{M} и, значит, n\notin M. Следовательно, множество M разрешимо. Прежде чем переходить к следующей теореме, отметим, что существует эффективное  перечисление всех упорядоченных пар натуральных чисел, которое называется  диагональным методом, или диагональным процессом: \begin{array}{lllllllllll}(0,0)& & (1,0)& & (2,0)& & (3,0)& & (4,0)& & \ldots\\  ~~\downarrow& \nearrow & & \nearrow & & \nearrow & & \nearrow & & \nearrow & \\  (0,1)& & (1,1)& & (2,1)& & (3,1)& & (4,1)& & \ldots\\ & \nearrow & & \nearrow & &  \nearrow & & \nearrow & & \nearrow & \\ (0,2)& & (1,2)& & (2,2)& & (3,2)& & (4,2)& &  \ldots\\ & \nearrow & & \nearrow & & \nearrow & & \nearrow & & \nearrow & \\  \multicolumn{11}{l}{\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots  \ldots\ldots \ldots\ldots \ldots\ldots \ldots\ldots \ldots} \end{array} Перечисление осуществляется последовательным прохождением по диагоналям, начиная  с левого верхнего угла. Первыми парами этого перечисления являются: (0,0),~ (0,1),~(1,0),~(0,2),~(1,1),~(2,0),~ (0,3),~ \ldots Можно доказать, что в данной последовательности пара (m,n) стоит на месте с номером C(m,n)= \frac{m^2+2mn+n^2+3m+n+2}{2}\,. Теорема 35.7. Существует перечислимое, но неразрешимое множество натуральных чисел. Доказательство. На основании предыдущей теоремы достаточно привести пример такого  множества {U} натуральных_чисел, которое само было бы перечислимо, а его дополнение \overline{U} перечислимым не было. Ясно, что перечислимых множеств натуральных чисел (как и алгоритмов) имеется лишь  счетное количество. Следовательно, все перечислимые множества можно расположить в  последовательность (перенумеровать): M_0,M_1,M_2,\ldots. Более того, можно считать,  что эта нумерация эффективна, т.е. по номеру множества можно восстановить само это  множество. Рассмотрим теперь алгоритм \Omega, который последовательно порождает все элементы  следующего множества {U}. На шаге с номером C(m,n) этот алгоритм вычисляет m­й  элемент множества M_n, и если элемент совпадает с n, то он относит его в множестве  {U}. Таким образом, n\in U\quad \Leftrightarrow\quad n\in M_n, Итак, {U} порождается алгоритмом \Omega, т.е. {U} перечислимо. Поскольку  дополнение \overline{U} множества {U} состоит из всех таких n, что n\notin M, то {U}  отличается от любого перечислимого множества хотя бы одним элементом. Поэтому  \overline{U} не является перечислимым. Следовательно, на основании теоремы 35.6  множество {U} неразрешимо, что и завершает доказательство. Доказанная теорема фактически включает в себя в неявном виде теорему Гёделя о  неполноте формальной арифметики, о которой мы подробно будем говорить в  заключительном параграфе этой главы. Подведем некоторые итоги. Итак, эффективно заданное множество — это множество,  обладающее разрешающей или перечисляющей функцией (алгоритмом). Объединение и  пересечение перечислимых множеств перечислимы. Непустое множество M\subseteq N  разрешимо тогда и только тогда, когда оно само и его дополнение перечислимы. В частности, отсюда следует, что всякое непустое разрешимое множество перечислимо. Тем не менее существует перечислимое, но неразрешимое множество натуральных чисел. В  теореме 35.7 такое множество описано. Другим примером такого множества является  множество M=\{x\colon\, A_x(x) определен}, т.е. множество номеров самоприменимых  алгоритмов. Таким образом, перечислимость — более слабый вид эффективности, нежели  разрешимость. Хотя перечисляющая процедура и задает эффективно список элементов  множества M, поиск данного элемента а в этом списке может оказаться неэффективным:  это неопределенно долгий процесс, который в конечном счете остановится, если a\in M,  но не остановится, если a\notin M. В случае же перечислимости и дополнения  \overline{M} перечисляющая процедура для M становится эффективной и гарантирует  разрешимость множества M.