MODULE: Predicate logic

TUTORIAL Q05: Validity in SPL

In SL, we can use truth-tables to check the validity of sequents, but this method is not applicable to many of the sentences in SPL, such as the quantified wffs. It is indeed possible to use other methods to prove the validity of a sequent in SPL, or PL, but we shall not discuss them in this introductory course. If you are interested you can look up the more advanced textbooks in the section on further readings.

Basically, we can divide all the valid sequents in SPL into three kinds :

Valid sequents of SL
Sequents not in SL, but are truth-functionally valid
All other valid sequents

Valid sequents of SL are still valid in SPL

Let us look at the first kind of valid sequents. Since SL is part of SPL, all the valid sequents of SL are also sequents in SPL. Of course these sequents remain valid in SPL. They include :

P P
(P&Q) P
P, (P→Q) Q
P, (~P∨Q) Q

Truth-functional validity in SPL

How about these sequents which can only be found in SPL?

∃zFz ∃zFz
(~Ca&Gb) ~Ca
Ka, (Ka→∀yDy) ∀yDy
∃xWx, (~∃xWx∨Fc) Fc

These sequents are actually all valid. Even though they are not sequents of SL, we can see that they are of the same form as the four valid sequents of SL above them. The third sequent, for example, is simply an application of modus ponens.

In other words, if any sequent of SPL has the same form as a valid sequent in PL, then it is also valid in SPL. What we need to do now is to give a more precise definition of this rule :

Definition of truth-functional validity in SPL
Suppose we have a valid sequent φ in SL.
Take any number N of distinct sentence letters α₁, α₂, ...α_N that appear in φ.
Take N WFFs of SPL β₁, β₂, ...β_N, none of which contain sentence letters that appear in φ.
Now replace all occurrences of α₁ by β₁, and replace all occurrences of α₂ by β₂, ... , and replace all occurrences of α_N by β_N.
If the original sequent φ is a valid sequent in SL, then the resulting new sequent after replacement is also a truth-functionally valid sequent in SPL.

So let us apply this rule once to see how it works :

We have a valid sequent φ in SL : (P→Q), (Q→R) (P→R)
Take 2 distinct sentence letters "P" and "R" that appear in the sequent.
Take 2 WFFs of SPL : "∀x(Fx&Gx)", "~S", none of which contain sentence letters that appear in φ.
Replace all occurrences of "P" in φ by "∀x(Fx&Gx)". Replace all occurrences of "R" by "~S".
We end up with a new valid sequent : (∀x(Fx&Gx)→Q), (Q→~S) (∀x(Fx&Gx)→~S)

Here are some more examples of truth-functionally valid sequents unique to SPL :

Example #1:
Replacement scheme : P ⇒ ∃xFx, Q ⇒ He
From this valid sequent in SL : (P∨Q), ~Q P, we obtain,
(∃xFx∨He), ~He ∃xFx
Example #2:
Replacement scheme : P ⇒ ∀x(Gx&Fx)
From this valid sequent in SL : (P&~Q) ~(P↔Q), we obtain,
(∀x(Gx&Fx)&~Q) ~(∀x(Gx&Fx)↔Q)

Exercises

Show that these sequents are truth-functionally valid by identifying the replacement schemes and the SL-valid sequents from which they can be derived :

(P↔∃xGx), ~~~∃xGx ~P
(∀xFx→S), (P→Gb) (~(∀xFx&P)∨(S&Gb))

Other valid sequents in SPL

However, not all valid sequents in SPL or PL can be identified using this method. Here is an example of a sequent in SPL that is valid, but which is not truth-functionally valid:

Every F is G. a is F. So, a is G.
∀x(Fx→Gx), Fa Ga

It should be intuitive that this is a valid sequent. But if you are not sure, perhaps this informal explanation might help. "∀x(Fx→Gx)" says that every F is a G. You can think of this wff as logically equivalent to an infinite conjunction "( (Fa→Ga) & (Fb→Gb) & (Fc→Gc) & ... )" where "a", "b", "c", etc. are names of all the objects in the domain. This infinite conjunction of course entails "(Fa→Ga)", which together with "Fa", entail "Ga" by modus ponens.

Now consider another example of a sequent in SPL that is valid but not truth-functionally valid :

a is F. a is G. So something is both F and G.
Fa, Ga ∃x(Fx&Gx)

Again we can offer an informal explanation as to why this sequent is valid. An existentially quantified wff says that there is at least one object that satisfies some condition. So we can think of "∃x(Fx&Gx)" as logically equivalent to the infinite disjunction "( (Fa&Ga) ∨ (Fb&Gb) ∨ (Fc&Gc) ∨ ... )". The first two premises of the sequent entail "(Fa&Ga)", and this conjunction in turn entails the infinite disjunction. So the sequent is indeed valid. It should be pointed out though that this argument is not very rigorous, and that a more precise justification can and should be given. But we shall not discuss the details here. What is important to remember is that an existentially quantified wff can be thought of as an infinite disjunction, and a universally quantified wff as an infinite conjunction. Bearing these two points in mind should help you understand why the following sequents are all valid sequents of SPL:

Every F is G. Everything is F. So, everything is G.
∀x(Fx→Gx), ∀xFx ∀xGx
Every F is G. Everything is not G. So, everything is not F.
∀x(Fx→Gx), ∀x~Gx ∀x~Fx
Every F is G. Something is F. So, something is G.
∀x(Fx→Gx), ∃xFx ∃xGx
Every F is G. Something is not G. So, something is not F.
∀x(Fx→Gx), ∃x~Gx, ∃x~Fx
Everything is F or G. Everything is not F. So, everything is G.
∀x(Fx∨Gx), ∀x~Fx ∀xGx
Everything is F or G. Something is not G. So, something is F.
∀x(Fx∨Gx), ∃x~Gx ∃xFx
Everything is F and G. So, everything is F.
∀x(Fx&Gx) So, ∀xFx
Something is F and G. So, something is F.
∃x(Fx&Gx) ∃xFx
Every F is G. Every G is H. So, every F is H.
∀x(Fx→Gx), ∀x(Gx→Hx) ∀x(Fx→Hx)
Every F is G. No G is H. So, no F is H.
∀x(Fx→Gx), ∀x(Gx→~Hx) ∀x(Fx→~Hx)
Every F is G. Some F is not H. So, some G is not H.
∀x(Fx→Gx), ∃x(Fx&~Hx) ∃x(Gx&~Hx)
Every F is G. Some H is not G. So, some H is not F.
∀x(Fx→Gx), ∃x(Hx&~Gx) ∃x(Hx&~Fx)
No F is G. Some F is H. So, some H is not G.
∀x(Fx→~Gx), ∃x(Fx&Hx) ∃x(Hx&~Gx)
No F is G. Some G is H. So, some H is not F.
∀x(Fx→~Gx), ∃x(Gx&Hx) ∃x(Hx&~Fx)