Qual é a relação entre a lógica de primeira ordem e a teoria de primeira ordem?

Eu pensei que qualquer FOT é um subconjunto de FOL, mas isso não parece ser o caso, porque FOL está completo (todas as fórmulas são válidas ou inválidas), enquanto alguns FOT (como aritmética inteira linear) não estão completos.

Então, o FOL é mais expressivo que o FOT? Ou incomparável?

Além disso, a afirmação "existem afirmações válidas no LIA, mas que não podem ser provadas usando axiomas do LIA" é estranha. Como a declaração pode ser válida se não podemos provar sua validade? Eu sempre pensei que, se você não pode provar a validade da declaração, não pode afirmar que é válida.

logic first-order-logic Ayrat
fonte

Penso que a afirmação "existem afirmações válidas no LIA, mas que não podem ser provadas usando axiomas do LIA", é falsa. O teorema da completude de godel garante que uma afirmação válida possa eventualmente ser provada em uma quantidade finita de tempo. Eu acho que você está confundindo validade lógica com verdade lógica. Essas são duas coisas diferentes. O significado de completude usado no teorema da completude de godel e o usado no teorema da incompletude não são os mesmos.

Rotia 26/04

Respostas:

Lógica de primeira ordem é um assunto matemática que define muitos conceitos diferentes, tais como fórmula de primeira ordem , a estrutura de primeira ordem , a teoria de primeira ordem , e muitos mais. Um desses conceitos é a teoria de primeira ordem : é um conjunto de fórmulas de primeira ordem. Muitas vezes, consideramos a teoria de primeira ordem gerada por um número finito de axiomas e esquemas de axiomas. Essa teoria é fechada com relação às derivações lógicas , e geralmente consideramos apenas as teorias que satisfazem essa condição.

Uma teoria de primeira ordem é completa se, para cada afirmação , contiver ou sua negação. Nem toda teoria está completa. De fato, o teorema da incompletude de Gödel destaca o fato de que muitas teorias interessantes de primeira ordem são necessariamente incompletas. $\sigma$ $\sigma$

Um modelo de uma teoria de primeira ordem é uma interpretação válida da teoria (deixamos a definição exata para os livros didáticos). Por exemplo, a teoria de primeira ordem dos grupos consiste em todas as afirmações que se seguem dos axiomas do grupo. Todo grupo é um modelo da teoria de primeira ordem dos grupos.

Para todo modelo, uma sentença muito determinada é verdadeira ou falsa. O teorema da completude de Gödel afirma que, se uma sentença de primeira ordem é verdadeira em todos os modelos de uma teoria de primeira ordem, é possível provar a partir de um número finito de sentenças na teoria. Por exemplo, toda declaração de primeira ordem no idioma dos grupos que é válida para todos os grupos é comprovável a partir dos axiomas do grupo.

A LIA é (presumivelmente) uma teoria de primeira ordem que é interessante o suficiente para ficar incompleta devido ao teorema da incompletude de Gödel. No entanto, no modelo padrão - os números inteiros "verdadeiros" - cada frase é verdadeira ou falsa. Em particular, se é uma afirmação tal que nem nem pertencem ao LIA, então ou vale para os inteiros verdadeiros, mas esse fato não é comprovável no LIA. $\sigma$ $\sigma$ $\lnot \sigma$ $\sigma$ $\lnot \sigma$

Yuval Filmus
fonte

o que há de especial nas teorias 'completas'? por que eles são interessantes? "é claro", muitas teorias são incompletas, porque a definição de completude pergunta se uma frase é verdadeira para todos os modelos. Sobre a incompletude: no "modelo inteiro padrão", não nos preocupamos com todos os modelos que satisfazem os axiomas, temos apenas um, "modelo inteiro padrão". O teorema da incompletude não sugere que a maneira como definimos validade (especialmente nossa consideração de todos os modelos que satisfazem os axiomas) é inadequada?

Ayrat

Teorias completas são especiais, pois fornecem um valor de verdade definido para cada afirmação. Isso é algo que você gostaria de ter. O restante de suas perguntas pertence ao domínio da filosofia. Dito isto, o teorema da completude de Gödel iguala validade em todos os modelos com provabilidade.

Yuval Filmus

ainda não vê a utilidade - considere o FOL, que está completo: suponha que você queira verificar se F é válido ou não: 'completude' não ajuda muito se F for inválido, porque a validade do FOL é semi-decidível. Perco alguma coisa?

Ayrat

A afirmação "a lógica de primeira ordem está completa" é sem sentido ou falsa.

Yuval Filmus

Não é verdade que uma teoria de primeira ordem seja um conjunto consistente de sentenças de primeira ordem. A coisa correta a dizer é: uma teoria de primeira ordem é um conjunto de fórmulas de primeira ordem que são fechadas sob dedução. Posso perfeitamente formular uma teoria inconsistente. Pode levar anos até descobrirmos que é inconsistente. E uma teoria pode conter fórmulas, não apenas sentenças (que são fórmulas fechadas).

Andrej Bauer

A frase "lógica de primeira ordem" tem dois significados:

É um capítulo da lógica matemática em que estudamos certos tipos de sistemas formais e tudo relacionado a eles.
É um tipo especial de teoria de primeira ordem, a que é gerada por uma assinatura vazia e um conjunto vazio de axiomas.

Sua pergunta se refere ao segundo significado, mas para entender isso, precisamos construir as coisas:

Existe uma certa linguagem formal chamada linguagem da lógica de primeira ordem . Falando informalmente, é o material que você pode construir a partir de variáveis, igualdade, $\land$ , $\lor$ , $\lnot$ , $\Rightarrow$ , $\forall$ e $\exists$ . Esse material é conhecido como fórmulas de primeira ordem .
Existe um certo sistema formal chamado lógica de primeira ordem que nos diz o que significa provar uma fórmula de primeira ordem. O sistema é fornecido como um conjunto de regras de inferência.
Uma teoria de primeira ordem $\mathcal{T}$ É dado por:
- uma assinatura $\Sigma_{\mathcal{T}}$ que consiste em um conjunto de constantes, símbolos de função e símbolos de relação. Pense nelas como extensões da linguagem básica da lógica de primeira ordem. Nós chamamos isso de linguagem $\mathcal{T}$ .
- um conjunto dedutivamente fechado de fórmulas de primeira ordem escritas no idioma estendido pela assinatura.

Um conjunto $S$ Diz-se que as fórmulas são encerradas dedutivamente se qualquer aplicação de regras de inferência da lógica de primeira ordem a fórmulas em $S$ dá fórmulas que estão novamente em $S$ . Em outras palavras, $S$ contém todas as suas consequências lógicas. Uma maneira comum de criar esse conjunto $S$ é: comece com um conjunto escolhido de fórmulas $A$ e adicione todas as suas consequências lógicas e as consequências dessas conseqüências e assim por diante. Isso é chamado de fechamento dedutivo de $A$ . Costumamos chamar as fórmulas em $A$ axiomas .

Uma teoria pode ou não estar completa. Não é importante saber o que "completo" significa aqui, mas é importante saber que o seguinte pode acontecer: podemos ter dois conjuntos de fórmulas $A$ e $B$ , de tal modo que $A \subseteq B$ , o fechamento dedutivo de $A$ é uma teoria completa e o fechamento dedutivo de $B$ não é uma teoria completa.

Agora estamos prontos para responder à sua pergunta. Deixei $T$ seja a teoria cuja assinatura está vazia e cujo conjunto de fórmulas é o fechamento dedutivo do conjunto vazio. Deixei $P$ seja a teoria cuja assinatura é a da aritmética Peano (constante $0$ operação unária $S$ operações binárias $+$ e $\times$ ) e as fórmulas são o fechamento dedutivo dos axiomas Peano. É fato que

$T$ está contido em $P$ (de fato $T$ está contido em toda teoria),
$T$ está completo,
$P$ não está completo.

A teoria $T$ é popularmente chamado de "lógica de primeira ordem", mas isso realmente é um nome impróprio. Algumas pessoas são um pouco mais precisas e chamam de "a pura teoria da lógica de primeira ordem".

Em resumo, sua pergunta revelou o seguinte:

Você não sabia que "lógica de primeira ordem" pode se referir à teoria com assinatura vazia gerada pelos axiomas vazios.
Uma teoria completa pode se tornar incompleta quando a estendermos.
Você usou a definição errada de integridade. A definição correta é: uma teoria está completa se, toda sentença ou sua negação é um teorema da teoria.

Nota: uma frase é uma fórmula fechada (que não contém variáveis livres).

Por fim, deixe-me responder à sua pergunta sobre validade:

uma fórmula é comprovável se houver uma prova disso
uma fórmula é válida se for verdadeira em todos os modelos

Um meta-teorema básico sobre lógica de primeira ordem é que toda fórmula comprovável é válida. O inverso também se aplica e é conhecido como o teorema da completude de Gödel .

No entanto, muitas vezes acontece que, em alguma situação específica, alguém propositalmente faz uma incompatibilidade entre validade e provabilidade por um bom motivo. Por exemplo, se limitarmos a atenção apenas a modelos finitos , pode facilmente acontecer que haja declarações válidas que não tenham provas. Por que alguém faria isso? Na ciência da computação, isso pode ser por razões algorítmicas ou porque se interessa apenas por uma determinada classe de modelos.

HVocê diz "a única maneira de saber se uma sentença é válida é prová-la". Este pode ser o caso em algum nível informal (acho que Deus discordaria de você), mas observe que qualquer prova de validade desse tipo acontece fora da teoria, no nível meta. De fato, como estabelecer validade requer que se fale de todos os modelos, isso certamente não é algo que esperamos realizar dentro da teoria.

Andrej Bauer
fonte

Você parece ter se confundido com o teorema da completude de Godel e com os teoremas da incompletude de Godel. O que você chama de "teorema da incompletude de Godel" parece ser uma negação direta do teorema da completude de Godel. O primeiro teorema da incompletude de Godel é sobre sentenças que não podem ser provadas nem refutadas, não sentenças válidas, mas não prováveis.

User2357112 suporta Monica

Obrigado, acabei de excluir esse bit porque ele não adiciona nada à explicação.

Andrej Bauer

@AndrejBauer você poderia esclarecer o seguinte 'paradoxo' com "1.

T

$T$ está contido em

P

$P$ " ? : Desde a

P

$P$ está incompleto, então existe

s

$s$ de tal modo que

s \notin P

$s \not\in P$ e

\neg s \notin P

$\neg s \not\in P$ . Agora pergunte "

s \in T

$s \in T$ "? Desde a

T \subset P

$T \subset P$ (fechamentos dedutivos de seus axiomas), deve haver

s \in T

$s \in T$ ou

\neg s \in T

$\neg s \in T$ , mas ambos violam a suposição de existência de tais

s

$s$ !

Ayrat

outra pergunta: você tem um exemplo de declaração válida que não possui uma prova?

Ayrat

Um pequeno esclarecimento:

Você pode estar pensando que a teoria com assinatura vazia é uma teoria vazia, ou seja, não contém fórmulas fechadas. Isso está incorreto. A lógica de primeira ordem permite provar - sem apelo aos axiomas - certas fórmulas fechadas conhecidas como tautologias. Estes são "verdadeiros" devido unicamente à sua forma; eles não têm conteúdo significativo como tal. O Teorema da Completude de Godel diz então que a coleção de tautologias está completa - ou seja, todas as fórmulas fechadas válidas (ou seja, 'verdade em todos os modelos') são realmente deriváveis na lógica de primeira ordem. [A prova é interessante e decididamente não trivial.]

PMar
fonte