Compreendendo a lógica do ponto menos fixo

Para entender melhor um artigo, estou tentando entender brevemente a lógica do ponto menos fixo. Existem alguns pontos em que estou preso.

Se é um gráfico e$G = (V,E)$

$$\Phi(P) = \{(a,b) \mid G \models E(a,b) \lor P(a,b) \lor \exists z (E(a,z) \land P(z,b)) \}$$

é um operador na relação binária . Eu não entendo por que o ponto menos fixo de é o fechamento transitivo de . O exemplo é retirado da Teoria dos Modelos Finitos e suas aplicações (p. 60).P ∗ P $P$$P^*$$P$$E$

Ao estender a lógica de primeira ordem com o operador ponteiro menos fixo, não entendo por que o símbolo de relação precisa ser positivo na fórmula. Positivo significa que toda ocorrência de na fórmula está dentro de um número par de símbolos de negação.$S_i$$S_i$

Alguém tem idéia do que é bom ler para entender intuitivamente a lógica dos ponteiros menos fixos e sua sintaxe e semântica?

Se você está tendo problemas com o conceito de ponto menos fixo, recomendo que dedique algum tempo para obter uma formação em teoria de ordem mais geral.

Davey e Priestley, Introdução às Malhas e Ordem é uma boa introdução.

Para ver por que o fechamento transitivo é o ponto menos fixo, imagine construir o fechamento a partir de um conjunto vazio, aplicando a fórmula lógica, uma etapa de cada vez. O ponto menos fixo chega quando você não pode adicionar nenhuma nova aresta usando a fórmula.

O requisito de que a fórmula seja positiva garante que o processo seja monotônico, ou seja, que cresça a cada etapa. Se você tivesse um sub-formulário negativo, poderia ter o caso em que em algumas etapas o conjunto de arestas diminuiria, e isso poderia levar a uma oscilação sem fim para cima e para baixo, em vez de uma convergência para o LFP.

Considere a álgebra booleana formada a partir do conjunto de potências de um conjunto finito , ordenado pela inclusão de conjuntos. Agora, considere o operador P definido por$S$$P$

$$P(X) = \lnot X$$

Claramente, é um operador não positivo.$P$

1. Mostram que não existem pontos fixos de modo a que P ( μ P ) = μ P . Como resultado, você pode concluir que μ X $\mu P$$P(\mu P) = \mu P$ não pode ser bem definido.$\mu X.\;P(X)$

2. Prove o teorema de Knaster-Tarksi por si mesmo. Ou seja, se você possui uma treliça completa e uma função monotônica f : L → L , o conjunto de pontos fixos de f forma uma treliça completa. (Como conseqüência, f tem um ponto fixo mínimo e maior.) Essa prova é muito curta, mas é um arranhão na cabeça na primeira vez que você a vê, e a monotonicidade de f é crítica para o argumento.$L$$f : L \to L$$f$$f$$f$

3. Prove você mesmo que qualquer operador definido por uma expressão com uma variável livre que ocorre apenas positivamente é monótono. Portanto, a ocorrência positiva é uma condição sintática suficiente para reforçar a monotonicidade.$X$

Acho que não há substituto para você fazer essas provas por realmente internalizar a intuição.

este é um post muito antigo, portanto você já deve ter encontrado a resposta desejada. Desde que estudei FO (LFP) nos últimos meses. Eu tenho alguma compreensão das respostas que você precisa.

$[\sigma$$\phi(\vec{x},X)$$|\vec{x}|=ar(X)$$f_\phi$$\mathcal{P}(A^{ar(X)}) \mapsto \mathcal{P}(A^{ar(x)})$$\sigma$a estrutura $\mathbb{A}$ e $\mathcal{P}(Z)$ é o conjunto de potência do conjunto Z. E $f_\phi(Z) = \{\ \vec{a} \in A^{ar(X)}\ |\ \mathbb{A},\vec{a},Z \models \phi\ \}$. Se esse operador for monótono, podemos capturar facilmente o ponto fixo na estrutura finita e infinita, seguindo o teorema do ponto fixo do knaster tarski mencionado nas respostas acima. Mas, o problema está testando se a fórmula escrita fora do formulário, como acima, codifica um operador monótono ou não, é indecidível; portanto, precisamos obter a melhor coisa a seguir. A positividade na variável livre de segunda ordem garante que o requisito de monotonicidade seja atendido, sendo uma indução estrutural padrão para provar esse fenômeno. A questão é, é suficiente?

Para isso, ainda não tenho uma resposta sólida, pois ainda estou lendo. Eu posso apontar para papéis nesta frente. Pelo menos as idéias explicativas que mencionei aqui são do artigo Monotone vs Positive - Ajtai, Gurevich. Ele também menciona outro artigo Extensões de ponto fixo da lógica de primeira ordem de Gurevich e Shelah, que afirmam que o operador de ponto fixo quando aplicado à fórmula positiva não perde poder expressivo quando comparado com o aplicativo sendo feito sobre fórmulas monótonas arbitrárias.