1.10: Logical Implication
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 Δ and Γ are sets of L-formulas. We will say that Δ logically implies Γ and write Δ⊨Γ if for every L-structure A, if A⊨Δ, then A⊨Γ.
This definition is a little bit tricky. It says that if Δ is true in A, then Γ is true in A. Remember, for Δ to be true in A, it must be the case that A⊨Δ[s] for every assignment function s. See Exercise 4.
If Γ={γ} is a set consisting of a single formula, we will write Δ⊨γ rather than the official Δ⊨{γ}.
Definition 1.9.2. An L-formula ϕ is said to be valid if ∅⊨ϕ, in other words, if ϕ is true in every L-structure with every assignment function s. In this case, we will write ⊨ϕ.
Chaff: It doesn't seem like it would be easy to check whether Δ⊨Γ. To do so directly would mean that we would have to examine every possible 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, ⊨, is getting a lot of use. Just remember that if there is a structure on the left, A⊨σ, we are discussing truth in a single structure. If there is a set of sentences on the left, Γ⊨σ, then we are discussing logical implication.
Example 1.9.3. Let L be the language consisting of a single binary relation symbol, P, and let σ be the sentence (∃y∀xP(x,y))→(∀x∃yP(x,y)). We show that σ is valid.
So let A be any L-structure and let s:Vars→A be any assignment function. We must show that
A⊨[(∃y∀xP(x,y))→(∀x∃yP(x,y))][s].
Assume that A⊨(∃y∀xP(x,y))[s], we know that there is an element of the universe, A, such that A⊨∀xP(x,y)[s[y|a]]. And so, again by the definition of satisfaction, we know that if b is any element of A, A⊨P(x,y)[(s[y|a])[x|b]]. 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 (b,a)∈PA for any choice of b∈A.
We have to prove that A⊨(∀x∃yP(x,y))[s]. As the statement of interest is universal, we must show that, if c is an arbitrary element of A, A⊨∃yP(x,y)[s[x|c]], which means that we must produce an element of the universe, d, such that A⊨P(x,y)[(s[x|c])[y|d]]. Again, from the definition of satisfaction this means that we must find a d∈A such that (c,d)∈PA. Fortunately, we have such a d in hand, namely a. As we know, (c,a)∈PA, we have shown A⊨(∀x∃yP(x,y))[s], and we are finished.
Exercises
- Show that {α,α→β}⊨β for any formulas α and β. Translate this result into everyday English. Or Norwegian, if you prefer.
- Show that the formula x=x is valid. Show that the formula x=y is not valid. What can you prove about the formula ¬x=y in terms of validity?
- Suppose that ϕ is an L-formula and x is a variable. Prove that ϕ is valid if and only if (∀x)(ϕ) is valid. Thus, if ϕ has free variables x, y, and z, ϕ will be valid if and only if ∀x∀y∀zϕ is valid. The sentence ∀x∀y∀zϕ is called the universal closure of ϕ.
- (a) Assume that ⊨(ϕ→ψ). Show that ϕ⊨ψ.
(b) Suppose that ϕ is x<y and ψ is z<w. Show that ϕ⊨ψ but ⊭(ϕ→ψ). (The slash through ⊨ 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 ϕ and ψ are logically equivalent if ⊨(ϕ→ψ) and ⊨(ψ→ϕ). The weak form of the definition states that ϕ and ψ are logically equivalent if ϕ⊨ψ and ψ⊨ϕ.]