Semântica categórica para lógicas não monotônicas?

8

Existe alguma semântica categórica para lógicas não monotônicas?

Parece que a resposta simples para isso é "Não", pois a noção óbvia de composição falha em qualquer modelo de lógica não monotônica. Mas existe um modelo que realmente funcione com uma noção de composição adequadamente definida?

ct.category-theory semantics denotational-semantics David Boshton
fonte

3

Você está perguntando se alguém já fez isso ou se pode ser feito? Certamente isso pode ser feito, mas não sei se foi feito. (Você simplesmente não deve modelar a relação de conseqüência como a relação subobject, mas passar para uma fibraç~ao mais extravagante.)

Andrej Bauer

1

Estou perguntando se isso pode ser feito. Você tem uma referência em um exemplo de fibração?

David Boshton

4

A lógica não monotônica é uma área ampla - você tem alguma lógica específica em mente? De qualquer forma, supondo que :) que

você está interessado em qualquer lógica na qual o princípio da monotonia falha, e
você deseja uma semântica categórica no sentido da teoria da prova categórica (em vez de, por exemplo, uma semântica de hiperdótrina),

Uma resposta é que você pode fornecer uma semântica categórica razoável para qualquer lógica pela qual um cálculo sequencial com eliminação de corte seja conhecido. Basicamente, os tipos são objetos, as formas normais do cálculo sequencial são morfismos e a eliminação de cortes informa como implementar a composição. Isso fornece a categoria inicial em qualquer categoria de modelo que você usar para provar a integridade e a integridade.

$A \multimap B$ $A$ $B$ $A$ $B$ $A$ $X$ $B$ ) No entanto, possui uma excelente teoria de prova e seus modelos categóricos estão intimamente ligados à teoria das categorias monoidais.

Neel Krishnaswami
fonte

Embora, pensando bem, não tenha ideia de por onde começar efetivamente. O que é uma categoria inicial?

David Boshton

1

Ao provar a integridade e a integridade, você considera uma coleção de modelos e mostra que o cálculo prova exatamente as vinculações prováveis em todos os modelos. Normalmente, você também deseja organizar sua coleção de modelos em uma categoria, com um morfismo entre modelos sendo uma noção adequada de homomorfismo de modelos. Então, mostrar solidez e completude significa essencialmente mostrar que o termo modelo do cálculo é o objeto inicial na categoria de modelos.

Neel Krishnaswami

4

[Minhas desculpas por escrever isso como resposta, apesar de ser basicamente apenas um comentário à resposta anterior. Mas não tenho permissão para postar um comentário lá em cima, pois não tenho "reputação" suficiente]

A resposta anterior não está correta. A lógica linear (assim como qualquer um de seus sistemas subestruturais: MLL, MALL, MELL, ALL, o que você quiser ...) é perfeitamente monótona .

A resposta de Neel confunde "relevância" e "não monotonicidade".

A relevância pode ser vista como não monotonicidade do conector de inferência do sistema . A lógica linear é relevante, na medida em que a possibilidade de $\;\vdash A \multimap B$ $\vdash X\otimes A \multimap B$

Por outro lado, o que as pessoas chamam de lógica não monotônica são sistemas em que a provabilidade do sistema não é monótona: adicionar um novo elemento ao conjunto de fórmulas altera o conjunto de fórmulas prováveis. É uma forma de meta não monotonicidade, porque diz respeito à provabilidade e não ao conector de inferência. A lógica linear é monótona: você pode adicionar o que quiser ao conjunto de fórmulas e qualquer novo axioma ou regra de inferência ao sistema, mas se você tiver uma prova do sequente $\;\Gamma \vdash M: A$

Até onde eu sei, é difícil definir lógicas não-monotônicas (reais) em uma forma de cálculo sequencial, com eliminação de corte ou qualquer outro tipo de sistema de prova com uma noção equivalente de terminar a redução de prova. É por isso que as abordagens semânticas categóricas da tradição dificilmente funcionariam para elas.

Domenico Ruoppolo
fonte

Semântica categórica para lógicas não monotônicas?

Respostas: