Pontos fixos em computabilidade e lógica

Esta pergunta também foi publicada em Math.SE,

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

Espero que seja bom postá-lo aqui também. Caso contrário, ou se for muito básico para o CS.SE, informe-me e eu o excluirei.

Gostaria de entender melhor a relação entre teoremas de pontos fixos em lógica e $\lambda$ cálculo.

fundo

1) O papel dos pontos fixos na incompletude e indefinibilidade da verdade

Tanto quanto eu entendo, além da idéia fundamental de internalizar a lógica, a chave para as provas da indefinibilidade da verdade de Tarski e do teorema da incompletude de Goedel é o seguinte teorema do ponto fixo lógico , vivendo em uma metateoria construtiva e finitística (espero que a formulação está ok, corrija-me se algo estiver incorreto ou impreciso):

Existência de pontos fixos na lógica

Suponha que seja uma teoria suficientemente expressiva e recursivamente enumerável sobre a linguagem e que seja uma codificação de fórmulas em , ou seja, um algoritmo que transforma fórmulas arbitrárias bem formadas em fórmulas com uma variável livre , de tal forma que para qualquer -Fórmula temos . ${\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)$

Em seguida, existe um algoritmo transformando bem formadas -formulas em uma variável livre em fechadas bem formadas -formulas, de tal modo que para qualquer -Fórmula em uma variável livre temos o qual, interpretando como uma função definida símbolo ${\mathbf Y}$ ${\mathcal L}$ ${\mathcal L}$ ${\mathcal L}$ $\phi$
$T ⊢ Y (ϕ) \Leftrightarrow \exists v : C (Y (ϕ)) (v) \land ϕ (v),$ ${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \exists v: {\mathbf C}({\mathbf Y}(\phi))(v)\wedge \phi(v),$ ${\mathbf C}$ $\lceil -\rceil$ , também pode ser escrito de forma mais compacta como $T ⊢ Y (ϕ) \Leftrightarrow ϕ (⌈ Y (ϕ) ⌉) .$ ${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \phi(\lceil{\mathbf Y}(\phi)\rceil).$
Em outras palavras, é um algoritmo para a construção de pontos fixos em relação à equivalência das fórmulas de uma variável . ${\mathbf Y}$ ${\mathscr T}$ ${\mathcal L}$

Isso tem pelo menos dois aplicativos:

A aplicação ao predicado expressa " codifica uma sentença que, quando instanciada com sua própria codificação, não é comprovável". produz a formalização de "Esta frase não é comprovável", que está no cerne do argumento de Goedel. $\phi(v)$ $v$
Aplicando-a para uma sentença arbitrária produz undefinability da verdade de Tarski. $\neg\phi$ $\phi$

2) Pontos fixos no cálcio não tipado $\lambda$

No cálcio não tipado, a construção de pontos fixos é importante na realização de funções recursivas. $\lambda$

Existência de pontos fixos no cálcio- : $\lambda$

Existe um combinador de pontos fixos , ou seja, um termo tal que para qualquer termo , temos $\lambda$ $Y$ $\lambda$ $f$
$f (Y f) \sim_{α β} Y f .$ $f(Y f)\sim_{\alpha\beta} Yf.$

Observação

O que me deixa atordoado é que o combinador de ponto fixo nocalculo reflete diretamente, de uma maneira muito limpa e não técnica, a prova usual do teorema lógico do ponto fixo: $\lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$ $\lambda$

Muito grosso modo , dada uma fórmula , considera-se a formalização da afirmação " codifica uma sentença que, quando instanciada consigo mesma, satisfaz ", e coloca . A sentença é como e corresponde a $\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))$

Questão

Apesar de sua rápida descrição, achei a prova do teorema do ponto fixo lógico bastante técnica e difícil de executar em todos os detalhes; Kunen faz isso, por exemplo, no Teorema 14.2 de seu livro "Teoria dos conjuntos". Por outro lado, o combinador no cálculo é muito simples e suas propriedades são facilmente verificadas. $Y$ $\lambda$

O teorema lógico do ponto fixo segue rigorosamente os combinadores de ponto fixo no cálculo? $\lambda$

Por exemplo, pode-se modelar o cálculo de por fórmulas em até equivalência lógica, de modo que a interpretação de qualquer combinador de ponto fixo forneça um algoritmo conforme descrito no teorema lógico de ponto fixo? $\lambda$ ${\mathcal L}$

Editar

Em vista de muitas outras instâncias do mesmo argumento de diagonalização descritas nas respostas de Martin e Cody, deve-se reformular a pergunta:

Existe uma generalização comum dos argumentos da diagonalização seguindo o princípio expresso no combinador ? $Y$
$λ f . (λ x . f (x x)) (λ x . f (x x))$ $\lambda f.(\lambda x. f(xx))(\lambda x.f(xx))$

Se entendi corretamente, uma proposta é o Teorema de Ponto Fixo de Lawvere , veja abaixo. Infelizmente, porém, não posso seguir as especializações relevantes em nenhum dos artigos que Martin citou em sua resposta, e ficaria feliz se alguém pudesse explicá-las. Primeiro, para ser completo:

Teorema do Ponto Fixo de Lawvere

Seja uma categoria com produtos finitos e tal que para qualquer morfismo em exista algum tal que para todos os pontos tenha ${\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 \overset{p}{\to} A \overset{f}{\to} Y = 1 \overset{p}{\to} A \overset{⟨ ⌈ f ⌉, {id}_{A} ⟩}{\to} A \times A \overset{φ}{\to} Y .$ $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.$
Então, para qualquer endomorfismo , colocando qualquer escolha de dá origem a um ponto fixo do , ou seja $g: Y\to Y$
$f := A \overset{Δ}{\to} A \times A \overset{φ}{\to} Y \overset{g}{\to} Y,$ $f\ :=\ A\xrightarrow{\Delta} A\times A\xrightarrow{\varphi} Y\xrightarrow{g} Y,$ $\lceil f\rceil$ $g$ $1 \overset{⟨ ⌈ f ⌉, ⌈ f ⌉ ⟩}{\to} A \times A \overset{φ}{\to} Y .$ $1\xrightarrow{\langle\lceil f\rceil,\lceil f\rceil\rangle} A\times A\xrightarrow{\varphi} Y.$

Esta é uma afirmação na teoria (intuicionista) de primeira ordem de categorias com produtos finitos e, portanto, aplica-se a qualquer modelo deste último.

Por exemplo , levando todo o conjunto universo teórico como o domínio de discurso dá paradoxo de Russel (tomar conjunto hipotético de conjuntos, e a -predicate) e o teorema de Cantor (pegue qualquer conjunto e correspondente à exceção hipotética $A$ $Y := \Omega := \{0,1\}$ $\rho: A\times A\to\Omega$ $\in$ $A$ $\rho: A\times A\to \Omega$ $A\to\Omega^A$ ) Além disso, a tradução da prova do Teorema de Lawvere fornece os argumentos diagonais usuais.

Problema mais concreto:

Alguém pode explicar em detalhes uma aplicação do Teorema de Lawvere para funções recursivas parciais ou para os teoremas lógicos do ponto fixo? Em particular, quais categorias precisamos considerar lá?

Em D. Pavlovic, Sobre a estrutura dos paradoxos , o autor considera a categoria gerada livremente por com as funções recursivas particulares. ${\mathbb N}$ ${\text{End}}({\mathbb N})$

Infelizmente, não entendo o que isso significa.

$\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}$ também é apenas uma função parcial, portanto, pode ser indefinida, o teorema do ponto fixo é trivial.

Qual é a categoria que você realmente deseja considerar?

Talvez o objetivo seja obter o teorema do ponto fixo de Roger, mas, de alguma forma, deve-se criar uma codificação de funções recursivas parciais por números naturais na definição da categoria, e não consigo descobrir como fazer isso.

Ficaria muito feliz se alguém pudesse explicar a construção de um contexto ao qual o Teorema de Ponto Fixo de Lawvere se aplica, dando origem a um teorema lógico de ponto fixo ou a um ponto fixo para funções recursivas parciais.

Obrigado!

lo.logic computability lambda-calculus Hanno Becker
fonte

Q

$Q$

λ

$\lambda$

@ EmilJeřábek: Obrigado pelo seu comentário! Entendo que não haverá como contornar uma codificação de funções recursivas, mas gostaria de separar claramente o que diz respeito à codificação e o que é formal posteriormente.

Hanno Becker

λ

$\lambda$

Y

$Y$

φ

$\varphi$

N \to (N \to N)

$\mathbb{N}\rightarrow(\mathbb{N}\rightarrow\mathbb{N})$

(N \to N) \to (N \to N)

$(\mathbb{N}\rightarrow\mathbb{N})\rightarrow(\mathbb{N}\rightarrow\mathbb{N})$

Y

$Y$

Cody, você poderia elaborar com precisão qual categoria está usando, porque esse é o ponto em que não posso seguir as outras fontes.

Hanno Becker 12/11

Respostas:

Provavelmente não estou respondendo diretamente à sua pergunta, mas há uma generalização matemática comum de muita paradoxa, incluindo os teoremas de Gödel e o combinador Y. Eu acho que isso foi explorado pela primeira vez por Lawvere. Veja também [2, 3].

FW Lawvere, argumentos diagonais e categorias fechadas cartesianas .
D. Pavlovic, Sobre a estrutura dos paradoxos .
NS Yanofsky, Uma Abordagem Universal aos Paradoxos Auto-Referenciais, Incompletude e Pontos Fixos .

Martin Berger
fonte

Obrigado, Martin, estas são referências muito interessantes! No entanto, estou tendo problemas para extrair da situação lógica um contexto categórico ao qual o teorema do ponto fixo lógico de Lawvere se aplica verbalmente. No artigo de Yanofsky, por exemplo, duvido que a operação de substituição

{Lind}^{1} \times {Lind}^{1} \to {Lind}^{0}

$\text{Lind}^1\times\text{Lind}^1\to\text{Lind}^0$ é bem definido se considerarmos termos com equivalência lógica. Você entende isso?

Hanno Becker

@ HannoBecker Isso pode ser bastante difícil e sensível à codificação.

Martin Berger

Não tenho uma resposta completa para sua pergunta, mas tenho o seguinte:

Conforme Wikipedia diz

Para cada função recursiva parcial $Q(x, y)$ existe um índice $p$ de tal modo que
$φ_{p} ≃ λ y . Q (p, y)$ $\varphi_p\simeq \lambda y.Q(p, y)$ Onde $\varphi$ é uma joia entre $\mathbb{N}$ e as funções recursivas parciais.

Agora está bem claro que esse teorema é uma conseqüência do teorema do ponto de correção no $\lambda$ -cálculo. Podemos usar isso para provar uma variante do teorema do ponto fixo lógico:

Para cada fórmula $\phi$ e re teoria ${\mathscr T}$ contendo aritmética, existe um índice $n$ de tal modo que
$T ⊢ ϕ (\bar{n}) \Leftrightarrow T ⊢ \exists y, φ_{n} (y) = 0 0$ ${\mathscr T}\vdash \phi(\overline{n}) \Leftrightarrow {\mathscr T}\vdash \exists y, \varphi_n(y)=0$

Isso não é exatamente o que você deseja, mas um truque de internalização pode lhe dar uma afirmação mais forte

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

Agora, novamente, esse não é exatamente o teorema lógico de ponto fixo, mas pode servir ao mesmo propósito.

Prova: Definir $Q(x,y)$ para ser a função recursiva definida por
$Q (x, y) = 0 0 iff T ⊢ ϕ (\bar{x}) no máximo y passos$ $Q(x,y) = 0 \mbox{ iff }{\mathscr T}\vdash \phi(\overline{x})\mbox{ in at most $y$ steps}$ É fácil ver que $Q$ é (total) recursivo. Observe que $\exists y, Q(x, y)$ expressa o fato " ${\mathscr T}$ prova $\phi(\overline{x})$ ", e isso é verdade se ${\mathscr T}\vdash\exists y,Q(\overline{x}, y)$ (estamos assumindo $\omega$ -consistência). Agora, uma aplicação simples do Teorema da Recursão Kleene em $Q$ nos dá a conclusão desejada. $\square$

Com um pouco de reflexão, você provavelmente pode fortalecer esse argumento para fornecer o teorema completo diretamente, sem a internalização.

cody
fonte

Obrigado pela sua resposta! Deixe-me ir devagar para ver se eu entendo você: em sua primeira declaração, pode

φ : N ≅ C (N, N)

$\varphi:{\mathbb N}\cong\text{C}({\mathbb N},{\mathbb N})$ seja completamente arbitrário ou você deseja pelo menos o mapa de caril induzido

C (N^{2}, N) \to Mapa (N, C (N, N)) ≅ Mapa (N, N)

$\text{C}({\mathbb N}^2,{\mathbb N})\to\text{Map}({\mathbb N},\text{C}({\mathbb N},{\mathbb N}))\cong\text{Map}({\mathbb N},{\mathbb N})$ ter imagem nas funções recursivas parciais

C (N, N)

$\text{C}({\mathbb N},{\mathbb N})$ , e que a avaliação induzida

N^{2} \to N

${\mathbb N}^2\to{\mathbb N}$ ,

(n, m) \mapsto φ (n) (m)

$(n,m)\mapsto\varphi(n)(m)$ ser computável?

Hanno Becker

Com essas suposições, entendo que a afirmação é verdadeira; No entanto, embora - como em muitos desses tipos de declarações - a semelhança com o

Y

$Y$ -combinador em

λ

$\lambda$ -cálculo é impressionante, não vejo como você faria disso uma conseqüência formal deste último. Você poderia elaborar?

Hanno Becker

Para o primeiro ponto: você está correto, deseja

φ

$\varphi$ ser "são" no sentido que você descreve. Para o segundo ponto: o

Y

$Y$ combinador expressa essencialmente

Y f ≃ f (Y f)

$Y\ f\simeq f(Y\ f)$ . O teorema da recursão diz essencialmente a mesma coisa:

p := Y Q

$p:= Y\ Q$ . No entanto, a teoria das funções recursivas parciais permite um pouco mais de generalidade: o código de uma função é distinto da própria função. O equivalente em

λ

$\lambda$ -calculus estaria tendo uma operação quotee evalcomo no Lisp. Nesse sentido, o teorema da recursão é mais geral do que a existência do

Y

$Y$ combinador.

Cody