1.9: Logical Implication

At first glance it seems that a large portion of mathematics can be broken down into answering questions of the form: If I know this statement is true, is it necessarily the case that this other statement is true? In this section we will formalize that question.

Definition 1.9.1. Suppose that \(\Delta\) and \(\Gamma\) are sets of \(\mathcal{L}\)-formulas. We will say that \(\Delta\) logically implies \(\Gamma\) and write \(\Delta \models \Gamma\) if for every \(\mathcal{L}\)-structure \(\mathfrak{A}\), if \(\mathfrak{A} \models \Delta\), then \(\mathfrak{A} \models \Gamma\).

This definition is a little bit tricky. It says that if \(\Delta\) is true in \(\mathfrak{A}\), then \(\Gamma\) is true in \(\mathfrak{A}\). Remember, for \(\Delta\) to be true in \(\mathfrak{A}\), it must be the case that \(\mathfrak{A} \models \Delta \left[ s \right]\) for every assignment function \(s\). See Exercise 4.

If \(\Gamma = \{ \gamma \}\) is a set consisting of a single formula, we will write \(\Delta \models \gamma\) rather than the official \(\Delta \models \{ \gamma \}\).

Definition 1.9.2. An \(\mathcal{L}\)-formula \(\phi\) is said to be valid if \(\emptyset \models \phi\), in other words, if \(\phi\) is true in every \(\mathcal{L}\)-structure with every assignment function \(s\). In this case, we will write \(\models \phi\).

Chaff: It doesn't seem like it would be easy to check whether \(\Delta \models \Gamma\). To do so directly would mean that we would have to examine every possible \(\mathcal{L}\)-structure and every possible assignment function \(s\, of which there will be many.

I'm also sure that you've noticed that this double turnstyle symbol, \(\models\), is getting a lot of use. Just remember that if there is a structure on the left, \(\mathfrak{A} \models \sigma\), we are discussing truth in a single structure. If there is a set of sentences on the left, \(\Gamma \models \sigma\), then we are discussing logical implication.

Example 1.9.3. Let \(\mathcal{L}\) be the language consisting of a single binary relation symbol, \(P\), and let \(\sigma\) be the sentence \(\left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right)\). We show that \(\sigma\) is valid.

So let \(\mathfrak{A}\) be any \(\mathcal{L}\)-structure and let \(s : Vars \rightarrow A\) be any assignment function. We must show that 

\[\mathfrak{A} \models \left[ \left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right) \right] \left[ s \right].\]

Assume that \(\mathfrak{A} \models \left( \exists y \forall x P \left( x, y \right) \right) \left[ s \right]\), we know that there is an element of the universe, \(A\), such that \(\mathfrak{A} \models \forall x P \left( x, y \right) \left[s \left[ y | a \right] \right]\). And so, again by the definition of satisfaction, we know that if \(b\) is any element of \(A\), \(\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ y | a \right] \right) \left[ x | b \right] \right]\). If we chase through the definition of satisfaction (Definition 1.7.4) and of the various assignment functions, this means that for our one fixed \(a\), the ordered pair \(\left( b, a \right) \in P^\mathfrak{A}\) for any choice of \(b \in A\).

We have to prove that \(\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]\). As the statement of interest is universal, we must show that, if \(c\) is an arbitrary element of \(A\), \(\mathfrak{A} \models \exists y P \left( x, y \right) \left[ s \left[ x | c \right] \right]\), which means that we must produce an element of the universe, \(d\), such that \(\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ x | c \right] \right) \left[ y | d \right] \right]\). Again, from the definition of satisfaction this means that we must find a \(d \in A\) such that \(\left( c, d \right) \in P^\mathfrak{A}\). Fortunately, we have such a \(d\) in hand, namely \(a\). As we know, \(\left( c, a \right) \in P^\mathfrak{A}\), we have shown \(\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]\), and we are finished.

Exercises

1. Show that \(\{ \alpha, \alpha \rightarrow \beta \} \models \beta\) for any formulas \(\alpha\) and \(\beta\). Translate this result into everyday English. Or Norwegian, if you prefer.
2. Show that the formula \(x = x\) is valid. Show that the formula \(x = y\) is not valid. What can you prove about the formula \(\neg x = y\) in terms of validity?
3. Suppose that \(\phi\) is an \(\mathcal{L}\)-formula and \(x\) is a variable. Prove that \(\phi\) is valid if and only if \(\left( \forall x \right) \left( \phi \right)\) is valid. Thus, if \(\phi\) has free variables \(x\), \(y\), and \(z\), \(\phi\) will be valid if and only if \(\forall x \forall y \forall z \phi\) is valid. The sentence \(\forall x \forall y \forall z \phi\) is called the universal closure of \(\phi\).
4. (a) Assume that \(\models \left( \phi \rightarrow \psi \right)\). Show that \(\phi \models \psi\).
   (b) Suppose that \(\phi\) is \(x < y\) and \(\psi\) is \(z < w\). Show that \(\phi \models \psi\) but \(\not\models \left( \phi \rightarrow \psi \right)\). (The slash through \(\models\) means "does not logically imply.")
   
   [This exercise shows that the two possible ways to define logical equivalence are not equivalent. The strong form of the definition says that \(\phi\) and \(\psi\) are logically equivalent if \(\models \left( \phi \rightarrow \psi \right)\) and \(\models \left( \psi \rightarrow \phi \right)\). The weak form of the definition states that \(\phi\) and \(\psi\) are logically equivalent if \(\phi \models \psi\) and \(\psi \models \phi\).]