Фиксированные точки в вычислимости и логике

Этот вопрос также был размещен на Math.SE,

/math/1002540/fixed-points-in-computability-nd-logic

Я надеюсь, что это также хорошо, чтобы опубликовать это здесь. Если нет, или если это слишком просто для CS.SE, пожалуйста, сообщите мне, и я удалю его.

Я хотел бы лучше понять связь между теоремами о неподвижной точке в логике и -calculus.$\lambda$

Фон

1) Роль неподвижных точек в неполноте и неопределимости истины

Насколько я понимаю, помимо основной идеи интернализации логики, ключ к обеим доказательствам неопределимости Тарской истины и теорем о неполноте Гёделя является следующей теоремой логической фиксированной точки , живущей в конструктивной, finitistic метатеории (я надеюсь , что формулировка все в порядке, пожалуйста, исправьте меня, если что-то не так или неточно):

Наличие неподвижных точек в логике

Предположим, что - достаточно выразительная, рекурсивно перечислимая теория над языком , и пусть - кодировка -формул в , то есть алгоритм, преобразующий произвольные правильно сформированные -формулы в -формулы с одной свободной переменной , такой что для любого -формула у нас .L C L T L φ L C (φ)(v) L φ T ⊢∃! V: C (φ)(V${\mathscr T}$${\mathcal L}$${\mathbf C}$${\mathcal L}$${\mathscr T}$${\mathcal L}$$\varphi$${\mathcal L}$${\mathbf C}(\varphi)(v)$${\mathcal L}$$\varphi$${\mathscr T}\vdash \exists! v: {\mathbf C}(\varphi)(v)$

Тогда существует алгоритм превращающий правильно сформированные -формулы из одной свободной переменной в замкнутые правильно сформированные -формулы, такой, что для любой -формулы в у нас есть одна свободная переменная который, интерпретируя как определенный символ функции , также может быть записан более компактно какL L L ф Т ⊢ У (ф)⇔∃v: С ( У (ф))(v)∧ф(v), С ⌈-⌉ Т ⊢ У (ф)⇔ф(⌈ У (ф)⌉)${\mathbf Y}$${\mathcal L}$${\mathcal L}$${\mathcal L}$$\phi$

$${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \exists v: {\mathbf C}({\mathbf Y}(\phi))(v)\wedge \phi(v),$$ ${\mathbf C}$$\lceil -\rceil$ $${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \phi(\lceil{\mathbf Y}(\phi)\rceil).$$

Другими словами, является алгоритмом для построения неподвижных точек относительно -эквивалентности однопеременных -формул.T ${\mathbf Y}$${\mathscr T}$${\mathcal L}$

Это имеет как минимум два приложения:

• Применяя его к предикату выражающему « кодирует предложение, которое, когда создается его собственное кодирование, не доказуемо». дает формализацию «Это предложение не доказуемо», которое лежит в основе аргумента Геделя.$\phi(v)$$v$

• Применение его к для произвольного предложения дает Тарски неопределимость истины.$\neg\phi$$\phi$

2) Фиксированные точки в нетипизированном -calculus$\lambda$

В нетипизированном исчислении построение неподвижных точек важно для реализации рекурсивных функций.$\lambda$

Существование неподвижных точек в -calculus:$\lambda$

Существует комбинатор с фиксированной точкой , т. Е. -терм такой, что для любой -терм мы имеемY λ f f ( Y f ) ∼ α β Y f $\lambda$$Y$$\lambda$$f$

$$f(Y f)\sim_{\alpha\beta} Yf.$$

наблюдение

Что меня поразило, так это то, что комбинатор с фиксированной точкой в λ- калькуляторе очень чисто и нетехническим образом отражает обычное доказательство логической теоремы о неподвижной точке:$\lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$$\lambda$

Очень грубо , учитывая формулу , рассматривают формализацию φ ( v ) утверждения « v кодирует предложение, которое, когда создается его экземпляр, удовлетворяет ϕ », и ставит A ( ϕ ) : = φ ( ⌈ φ ⌉ ) . Предложение φ ( v ) похоже на λ x . f ( x x ) , а φ ( ⌈ φ ⌉ ) соответствует$\varphi$$\varphi(v)$$v$$\phi$${\mathbf A}(\phi) := \varphi(\lceil\varphi\rceil)$$\varphi(v)$$\lambda x. f(x x)$$\varphi(\lceil\varphi\rceil)$ .$(\lambda x. f(x x))(\lambda x. f(x x))$

Вопрос

Несмотря на быстро описанную идею, доказательство теоремы о фиксированной точке оказалось довольно техническим и трудным во всех деталях; Кунен делает это, например, в теореме 14.2 своей книги «Теория множеств». С другой стороны, комбинатор в λ- калькуляторе очень прост, и его свойства легко проверяются.$Y$$\lambda$

Строго ли вытекает теорема о неподвижной точке из логических комбинаторов с неподвижной точкой в вычислении?$\lambda$

Например, можно ли моделировать вычисление с помощью L- формул с точностью до логической эквивалентности, чтобы при интерпретации любого комбинатора с фиксированной точкой получался алгоритм, описанный в теореме о логической фиксированной точке?$\lambda$${\mathcal L}$

редактировать

Ввиду множества других примеров того же аргумента диагонализации, описанного в ответах Мартина и Коди, следует перефразировать вопрос:

Существует ли общее обобщение аргументов диагонализации в соответствии с принципом, выраженным в комбинаторе? λ ф . ( λ x . f ( x x ) ) ( λ x . f ( x x ) $Y$

$$\lambda f.(\lambda x. f(xx))(\lambda x.f(xx))$$

Если я правильно понимаю, одно предложение - это теорема Лоувера о неподвижной точке , см. Ниже. К сожалению, однако, я не могу следовать соответствующим специализациям ни в одной из статей, которые Мартин цитировал в своем ответе, и я был бы рад, если бы кто-то мог их объяснить. Во-первых, для полноты:

Теорема Лавре о неподвижной точке

Пусть - категория с конечными произведениями и φ : A × A → Y такая, что для любого морфизма f : A → Y в C найдется некоторая ⌈ f ⌉ : 1 → A такая, что для всех точек p : 1 → A имеется 1 р → е → Y = 1 р → ⟨ ⌈ е ⌉ , ${\mathscr C}$$\varphi: A\times A\to Y$$f: A\to Y$${\mathscr C}$$\lceil f\rceil: 1\to A$$p: 1\to A$

$$1\xrightarrow{p} A\xrightarrow{\ f\ } Y\ \ =\ \ 1\xrightarrow{p} A\xrightarrow{\langle \lceil f\rceil,\text{id}_A\rangle} A\times A\xrightarrow{\varphi} Y.$$

Тогда для любого эндоморфизма , положив ф : = Д → × ф → Y г → Y , любой выбор ⌈ е ⌉ приводит к фиксированной точке г , а именно : 1 ⟨ ⌈ е ⌉ , ⌈ е ⌉ ⟩ → × ф → Y $g: Y\to Y$

$$f\ :=\ A\xrightarrow{\Delta} A\times A\xrightarrow{\varphi} Y\xrightarrow{g} Y,$$ $\lceil f\rceil$$g$ $$1\xrightarrow{\langle\lceil f\rceil,\lceil f\rceil\rangle} A\times A\xrightarrow{\varphi} Y.$$

Это утверждение в (интуиционистской) теории первого порядка категорий с конечными произведениями и, следовательно, применимо к любой модели последнего.

Например , если взять теоретическую вселенную в качестве области дискурса, весь парадокс Рассела (возьмем гипотетический набор множеств, Y : = Ω : = { 0 , 1 } и ρ : A × A → Ω - ∈ -предикат) и теорема Кантора (возьмем A любое множество и ρ : A × A → Ω, соответствующее гипотетическому предположению A → Ω $A$$Y := \Omega := \{0,1\}$$\rho: A\times A\to\Omega$$\in$$A$$\rho: A\times A\to \Omega$$A\to\Omega^A$). Далее, перевод доказательства теоремы Лаврера дает обычные диагональные рассуждения.

Более конкретная проблема:

Может ли кто-нибудь подробно объяснить применение теоремы Лаврера к частичным рекурсивным функциям или теоремы о неподвижной точке? В частности, какие категории нам нужно рассмотреть там?

В D. Pavlovic, О структуре парадоксов , автор считает категорию, свободно порожденную с End ( N ) частичными рекурсивными функциями.${\mathbb N}$${\text{End}}({\mathbb N})$

К сожалению, я не понимаю, что это значит.

$\text{End}({\mathbb N})$$A=Y={\mathbb N}$${\mathbb N}\to{\mathbb N}$$1\to {\mathbb N}$$1\to {\mathbb N}$${\mathbb N}$$1\to {\mathbb N}$ тоже только частичная функция, следовательно, может быть неопределенной, теорема о неподвижной точке тривиальна.

Какую категорию вы действительно хотите рассмотреть?

Возможно, цель состоит в том, чтобы получить теорему Роджера о неподвижной точке, но тогда нужно как-то встроить кодирование частично рекурсивных функций натуральными числами в определение категории, и я не могу понять, как это сделать.

Я был бы очень рад, если бы кто-то мог объяснить конструкцию контекста, к которому применяется теорема Лаврэра о неподвижной точке, давая начало теореме о логической неподвижной точке или теореме о неподвижной точке для частично рекурсивных функций.

Спасибо!

Я, вероятно, не отвечаю прямо на ваш вопрос, но есть общее математическое обобщение многих парадоксов, включая теоремы Геделя и Y-комбинатор. Я думаю, что это было впервые исследовано Lawvere. Смотрите также [2, 3].

1. Ф. В. Лавре, Диагональные аргументы и декартовы замкнутые категории .

2. Д. Павлович, О структуре парадоксов .

3. Янофский Н.С. Универсальный подход к самореференциальным парадоксам, неполноте и неподвижным точкам .

У меня нет полного ответа на ваш вопрос, но у меня есть это:

Согласно Википедии говорит

$Q(x, y)$$p$

$$\varphi_p\simeq \lambda y.Q(p, y)$$ $\varphi$$\mathbb{N}$

$\lambda$

$\phi$${\mathscr T}$$n$

$${\mathscr T}\vdash \phi(\overline{n}) \Leftrightarrow {\mathscr T}\vdash \exists y, \varphi_n(y)=0$$

Это не совсем то, что вы хотите, но уловка интернализации может дать вам более сильное утверждение

${\mathscr T}\vdash \phi(\overline{n})\leftrightarrow \exists y, \varphi_n(y) = 0$

Опять же, это не совсем логическая теорема о неподвижной точке, но она может служить той же цели.

$Q(x,y)$

$$Q(x,y) = 0 \mbox{ iff }{\mathscr T}\vdash \phi(\overline{x})\mbox{ in at most $y$ steps}$$ $Q$$\exists y, Q(x, y)$${\mathscr T}$$\phi(\overline{x})$${\mathscr T}\vdash\exists y,Q(\overline{x}, y)$$\omega$$Q$$\square$

Немного подумав, вы, вероятно, сможете усилить этот аргумент, чтобы получить полную теорему напрямую без интернализации.