Estrutura de interpretação (lógica)

Na lógica, uma estrutura (ou estrutura de interpretação) é um objeto que dá significado semântico ou interpretação aos símbolos definidos pela assinatura de uma linguagem. Uma estrutura possui diferentes configurações, seja em lógicas de primeira ordem, seja em linguagens lógicas poli-sortidas ou de ordem superior.

Estruturas de primeira ordem

Uma assinatura Σ de uma linguagem de primeira ordem consiste de um conjunto Cst de símbolos de constantes e de conjuntos Fun_n e Rel_n de símbolos de funções e relações n-árias, respectivamente. Uma Σ-estrutura ${\mathcal {M}}$ para tal linguagem consiste de um par ${\mathcal {M}}=\langle {\mathcal {D}}_{I},{\mathcal {I}}\rangle$, no qual D_I será o universo (ou domínio) de discurso, e I é uma intepretação para os símbolos da linguagem, na qual vale as definições:

• Os símbolos de constantes são interpretados como "nomes" que se referem a um objeto do universo, são funções 0-árias em D_I. Em outras palavras, para cada c ∈ Cst, há um objeto específico c^I ∈ D_I

• Cada símbolo de função n-ária f_n ∈ Fun_n é interpretado como uma função específica $f_{n}^{I}:{\mathcal {D}}_{I}^{n}\rightarrow {\mathcal {D}}_{I}$.

• Cada símbolo de relação n-ária R_n ∈ Rel_n é interpretado como um subconjunto do produto cartesiano ${\mathcal {D}}_{I}^{n}$, ou seja, o conjunto das n-uplas ordenadas que satisfazem R^I_n.

Exemplo

Na álgebra booleana binária uma assinatura é constituída por:

• $Cst=\lbrace 0,1\rbrace ,Fun_{1}=\lbrace \neg \rbrace ,Fun_{2}=\lbrace \lor ,\land \rbrace$

E uma estrutura para essa assinatura é:

• ${\mathcal {D}}_{I}=\lbrace 0,1\rbrace$

• O símbolo de constante 0 é interpretado como o próprio objeto 0 (valor de verdade falso) e o símbolo 1, como o próprio 1 (verdadeiro).

• $\neg (x)\quad {\mbox{ou}}\quad \neg x$ :     Negação de x;

• $\lor (x,y)\quad {\mbox{ou}}\quad x\lor y\quad$ :     X ou y é verdadeiro (1);

• $\land (x,y)\quad {\mbox{ou}}\quad x\land y\quad$ :     X e y são verdadeiros.

Assim, a sentença $(x\land \neg y)=1$ é verdadeira apenas para uma atribuição ρ tal que ρ(x)=1 e ρ(y)=0.

Algumas definições sobre estruturas

Subestrutura

Ver artigo principal: Subestrutura

Uma estrutura ${\mathcal {M}}$ é dita subestrutura de outra estrutura ${\mathcal {M'}}$ para a mesma assinatura, denotado por ${\mathcal {M}}\subseteq {\mathcal {M'}}$, se:

• ${\mathcal {D}}_{I}\subseteq {\mathcal {D}}_{I'}$ ;

• $c^{I}=c^{I'}$     para toda constante c ∈ Cst;

• $f^{I}=f^{I'}|_{D_{I}^{n}}$     para toda função f_n ∈ Fun_n. Assim sendo,     $f^{I'}|_{D_{I}^{n}}:{\mathcal {D}}_{I}^{n}\rightarrow {\mathcal {D}}_{I}$;

• $R^{I}=R^{I'}\cap {\mathcal {D}}_{I}$     para toda relação R_n ∈ Rel_n.

Homomorfismo e Isomorfismo

Dadas duas estruturas ${\mathcal {M}}$ e ${\mathcal {M'}}$ para uma mesma assinatura, um homomorfismo $h:{\mathcal {M}}\rightarrow {\mathcal {M'}}$ é uma função $h:{\mathcal {D}}_{I}\rightarrow {\mathcal {D}}_{I'}$ tal que:

• Para todo c ∈ Cst,

$h(c^{I})=c^{I'}$

• Para toda f_n ∈ Fun_n e {a₁,...,a_n} ⊆ D_I,

$h(f^{I}(a_{1},\dots ,a_{n}))=f^{I'}(h(a_{1}),\dots ,h(a_{n}))$

• Para toda R_n ∈ Rel_n e {a₁,...,a_n} ⊆ D_I,

$(a_{1},\dots ,a_{n})\in R^{I}\Longrightarrow (h(a_{1}),\dots ,h(a_{n}))\in R^{I'}$

Diz-se que h é isomorfismo se a função for bijetiva, ou seja, o homomorfismo $h:{\mathcal {M'}}\rightarrow {\mathcal {M}}$ também vale.

Relação de satisfação

Seja φ uma fórmula bem-formada, ${\mathcal {M}}$ uma estrutura, e ρ uma atribuição, a relação de satisfação ou consequência, na qual ρ satisfaz φ em M denotado por ${\mathcal {M}}\vDash _{\rho }\phi$, define-se através do esquema-T por:

• $\phi \quad {\acute {\mbox{e}}}\quad (t_{1}=t_{2}):\quad {\mathcal {M}}\vDash _{\rho }(t_{1}=t_{2})\quad {\mbox{sse}}\quad t_{1}=t_{2}$;

• $\phi \quad {\acute {\mbox{e}}}\quad R(t_{1},...,t_{n}):\quad {\mathcal {M}}\vDash _{\rho }R(t_{1},...,t_{n})\quad {\mbox{sse}}\quad (\rho (t_{1}),...,\rho (t_{n}))\in R^{I}$;

• $\phi \quad {\acute {\mbox{e}}}\quad (\alpha _{1}\lor \alpha _{2}):\quad {\mathcal {M}}\vDash _{\rho }\alpha _{1}\lor \alpha _{2}\quad {\mbox{sse}}\quad {\mathcal {M}}\vDash _{\rho }\alpha _{1}\quad {\mbox{ou}}\quad {\mathcal {M}}\vDash _{\rho }\alpha _{2}$;

• $\phi \quad {\acute {\mbox{e}}}\quad \neg \alpha :\quad {\mathcal {M}}\vDash _{\rho }\neg \alpha \quad {\mbox{sse}}\quad {\mathcal {M}}\nvDash _{\rho }\alpha$;

• $\phi \quad {\acute {\mbox{e}}}\quad \forall x\alpha :\quad {\mathcal {M}}\vDash _{\rho }\forall x\alpha \quad {\mbox{sse}}\quad {\mathcal {M}}\vDash _{\rho '}\alpha$    para toda atribuição ρ'=ρ[x:=k], para todo k ∈ D_I.

Modelo de teorias de primeira-ordem

Uma estrutura é dita um modelo de uma teoria quando ambas têm a mesma linguagem e toda sentença consistente da teoria é satisfeita por tal estrutura. Assim, por exemplo, um anel é uma estrutura que satisfaz todos os axiomas da teoria dos anéis, e um modelo para a teoria das ordens parciais é uma estrutura com apenas um símbolo ≤ e que deve satisfazer os axiomas das ordens parciais.

"M é modelo de φ" denota-se por $\vDash _{\mathcal {M}}\phi$.

Definibilidade em uma estrutura

Uma relação n-ária R em um universo D_I de uma estrutura M é dita definível (ou explicitamente definível) se há uma fórmula φ(x₁,...,x_n), onde x₁,...,x_n são as variáveis livres de φ, tal que:

$R=(a_{1},\dots ,a_{n})\in {\mathcal {D}}_{I}^{n}:{\mathcal {M}}\vDash _{\rho }\phi (x_{1},\dots ,x_{n});\quad \rho [x_{1}:=a_{1};\dots ;x_{n}:=a_{n}]$

Ou seja,

$(a_{1},\dots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \phi (x_{1},\dots ,x_{n})$.

Um caso especial importante é a definibilidade de elementos específicos. Um elemento a ∈ D_I é definível em M sse há uma fórmula φ(x) tal que

${\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \phi (x))$.

Definibilidade com parâmetros

Uma relação R é dita definível em parâmetros se há uma sentença φ com parâmetros de M tal que R é definível usando φ. Todo elemento da uma estrutura é definível usando ele próprio como parâmetro.

Definibilidade implícita

Provém das definições acima que a fórmula φ pode não mencionar R, já que o mesmo pode não estar na linguagem de M. Se há uma fórmula φ na linguagem estendida contendo M e o novo símbolo R, e R é a única relação tal que ${\mathcal {M}}\vDash \phi$, então R é dita implicitamente definível em M.

Generalizações

Estruturas poli-sortidas

Uma linguagem poli-sortida inclui mais de um domínio de discurso. Por exemplo, a axiomatização em primeira ordem da lógica de segunda ordem inclui um tipo para números naturais e um tipo para conjuntos de números naturais. A definição de uma estrutura poli-sortida é a convencional, porém ao invés de um único universo de discurso, há vários, um para cada tipo.

Linguagens de ordem superior

Há mais de uma semântica possível para lógicas de ordem superior. Uma vez usando a semântica de ordem superior completa, uma estrutura necessita apenas de um universo para predicados, e o Esquema T é expandido para um quantificador sobre um tipo de ordem superior.

Requerimento de domínio não-vazio

Afirma-se acima que uma interpretação deve especificar um domínio não-vazio para ser o universo de discurso. Uma razão importante para isto é assim de modo a equivalências como

$(\phi \lor \exists x\psi )\leftrightarrow \exists x(\phi \lor \psi )$,

onde x não é livre em φ, serem logicamente válidas. Esta equivalência não é logicamente válida quando estruturas vazias são permitidas (por exemplo, assuma que φ seja $\forall y(y=y)$ e ψ seja $x=x$). Portanto, a teoria da demonstração da lógica de primeira ordem torna-se muito mais complicada quando estruturas com domínio vazio são permitidas, enquanto que o ganho em permití-las é pequeno, já que tanto as interpretações pretendidas como as interpretações interessantes das teorias que as pessoas estudam possuem domínios não-vazios. A dificuldade com domínios vazios está em certas regras de inferência que permitem que quantificadores sejam externalizados sobre conectivos lógicos. Para um exemplo concreto, considere

$\forall y(y=y)\lor \exists x(x=x)$

Esta estrutura é satisfeita por um domínio vazio. Para colocá-la na forma normal prenex, queremos mover o quantificador existencial para obter

$\exists x(\forall y(y=y)\lor x=x)$

Mas esta nova fórmula não é satisfeita por um domínio vazio, já que não existe nenhum elemento com o qual o quantificador existencial possa ser instanciado. O problema subjacente é que o escopo do quantificador existencial foi modificado para incluir o disjunto mais à esquerda.

As relações vazias, entretanto, não causam este problema, uma vez que não existe um conceito semelhante de externalizar um símbolo de relação sobre um conectivo lógico, alargando seu escopo no processo.

Ver também

• Teoria dos Modelos

Ligações externas

• Um Curso de Teoria dos Modelos(arquivo em .pdf), por Marcelo E. Coniglio.