Logical Entailment with Different Signatures

62 Views Asked by At

Definitions:

A set of formulas $\Gamma$ entails a formula $\phi$ (symbolically, $\Gamma \models \phi$) iff for each interpretation that satisfies all formulas in $\Gamma$ also satisfies $\phi$. An interpretation of a propositional signature $\sigma$ is a function that maps $\sigma$ into $\{ T, F \}$.

Question:

How do you determine if $\Gamma \models \phi$ when the signatures of the formulas in $\Gamma$ are a proper subset of the signature of $\phi$? For example, does $\{ p \} \models p \land q$? There is one interpretation that satisfies $p$, which is ($p = T$). However, since $q$ is not in the signature of $p$, how can it be determined whether this interpretation also satisfies $p \land q$?

1

There are 1 best solutions below

0
On

An interpretation that assigns a value to both $p$ and $q$, clearly assigns a value to $p$. Alternatively, $p$ is a formula in terms of the propositional variables $p$ and $q$ that just happens not to use the propositional variable $q$. You could imagine decorating $\vDash$ with the set of propositional variables usable by the formula $\phi$ and the formulas in $\Gamma$ to be more explicit, e.g. $\{p\}\vDash_{\{p,q\}}p\land q$ or even $\{p\}\vDash_{\{p,q,r\}}p\land q$. $\{p\}\vDash_{\{p\}}p\land q$ would then just be nonsensical.

Set-theoretically/meta-logically this could be described as follows. Call the set of well-formed formulas with propositional variables in the set $\sigma$, $\mathsf{Form}(\sigma)$. Then $\vDash_\sigma$ is a relation on $\mathcal{P}_{fin}(\mathsf{Form}(\sigma))\times\mathsf{Form}(\sigma)$ where $\mathcal{P}_{fin}(\mathsf{Form}(\sigma))$ is the set of finite subsets of formulas with propositional variables from $\sigma$. (Or you can allow arbitrary subsets depending on what you're doing.)