About formula deducibility from theory

65 Views Asked by At

In the book "Model theory" of Mr.Chang and Mr.Keisler we have such definition: enter image description here

Issue is: what if we consider negation of $\varphi(v_0, \dots,v_n)$? Say we consider, that $\varphi$ isn't deducible from $Σ$ (i.e. it isn't consistent with $\Sigma$), then $\lnot \varphi$ does. But from that definition for $\varphi$, as for any other regular formula, we have $Σ ⊨ (∀ v_0 \dots v_n) ¬\varphi(v_0,\dots,v_n)$.

Am I right?

1

There are 1 best solutions below

9
On BEST ANSWER

The fact that $\varphi$ is not a consequence of $\Sigma$ implies (but it is not equivalent to say) that $\varphi$ is not consistent with $\Sigma$ (that is, no model of $\Sigma$ satifies $\varphi$), but it does not imply that $\lnot \varphi$ is a consequence of $\Sigma$.

For instance, let $\Sigma$ be the set of axioms for being a group (a model satisfies $\Sigma$ iff it is a group), and let $\varphi$ be the formula that expresses that the group is abelian. Now, $\varphi$ is not a consequence of $\Sigma$ because not every group is abelian, but it is not true that $\lnot\varphi$ is a consequence of $\Sigma$ because there are abelian groups.


More formally, the notion of (logical) consequence$-$aka deducibility$-$is a bit delicate. Moreover, pay attention to not confuse the operation of negating a formula with the operation of negating that a formula is a consequence of a set of sentences.

  1. First, let us see what negating a formula means with respect to the notion of consequence. That is, let us apply the definition of consequence you posted to a formula $\varphi(v_0, \dots, v_n) = \lnot \psi(v_0, \dots, v_n)$. A formula $\lnot \psi(v_0, \dots, v_n)$ is a consequence of $\Sigma$, noted $\Sigma \models \lnot \psi(v_0, \dots, v_n)$, iff for every model $\mathfrak{A}$ and every sequence $a_0, \dots, a_n \in A$, $a_0, \dots, a_n$ satisfies $\lnot \psi$, which is equivalent to say that for every model $\mathfrak{A}$ and every sequence $a_0, \dots, a_n \in A$, $a_0, \dots, a_n$ doeas not satisfy $\psi$.

  2. Negating that a formula is a consequence of a set of sentences amounts to negate the English sentence in the definition you posted: a formula $\varphi(v_0, \dots, v_n)$ is not a consequence of a set of sentences $\Sigma$, noted $\Sigma \not\models \varphi(v_0, \dots, v_n)$, iff there is a model $\mathfrak{A}$ and a sequence $a_0, \dots, a_n \in A$ such that $a_0, \dots, a_n$ does not satisfy $\varphi$.

Do you see the difference in quantifiers used for 1. and for 2.? This means that $\Sigma \not\models \varphi(v_0, \dots, v_n)$ does not imply $\Sigma \models \lnot\varphi(v_0, \dots, v_n)$. In other words, if a formula is not a consequence of a set of sentences, the negation of that formula need not be a consequence of that set of sentences. This is exactly what you are ignoring when you say:

$φ$ isn't deducible from $Σ$ (i.e. it isn't consistent with $\Sigma$), then $¬φ$ does.


There is a special case where the fact that $\varphi$ is not a consequence of $\Sigma$ implies (and actually is equivalent to say) that $\lnot \varphi$ is a consequence of $\Sigma$: this holds when the set of sentences $\Sigma$ is complete, that is, for every formula $\varphi$, either $\Sigma \models \varphi$ or $\Sigma \models \lnot\varphi$.

However, many important sets of sentences are not complete. For instance, first-order Peano arithmetic, the theory of groups, etc.