Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 (yxP(x,y))(xyP(x,y)). We show that σ is valid.

So let A be any L-structure and let s:VarsA be any assignment function. We must show that

A[(yxP(x,y))(xyP(x,y))][s].

Assume that A(yxP(x,y))[s], we know that there is an element of the universe, A, such that AxP(x,y)[s[y|a]]. And so, again by the definition of satisfaction, we know that if b is any element of A, AP(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 bA.

We have to prove that A(xyP(x,y))[s]. As the statement of interest is universal, we must show that, if c is an arbitrary element of A, AyP(x,y)[s[x|c]], which means that we must produce an element of the universe, d, such that AP(x,y)[(s[x|c])[y|d]]. Again, from the definition of satisfaction this means that we must find a dA 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(xyP(x,y))[s], and we are finished.

Exercises

  1. Show that {α,αβ}β for any formulas α and β. 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 ¬x=y in terms of validity?
  3. 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 xyzϕ is valid. The sentence xyzϕ is called the universal closure of ϕ.
  4. (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 ψϕ.]

This page titled 1.10: Logical Implication is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Christopher Leary and Lars Kristiansen (OpenSUNY) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?