THE PREDICATE CALCULUS

 

TWO INFERENCE RULES FOR THE UNIVERSAL QUANTIFIER

Overview

Universal Elimination (E) and Universal Introduction (I) usually come in pairs in logical proofs like two bookends, where the one comes at the beginning of a proof, and the other at the end. The first removes the universal quantifier and essentially frees up propositions so that normal logical deductions can be performed on them. The second reintroduces the universal quantifier. The subject letter changes from “x” to some other arbitrarily designated letter such as “y” (for general variables) or s (for specific constants). These changed letters are called “instantial letters” since they designate instances of the original universal statement.

Example of E and I in a proof:

For all things, if that thing is a dog, then that thing is a mammal; for all things, if that thing is a mammal, then that thing is warm-blooded; therefore, for all things, if that thin is a dog, then that thing is warm-blooded.

1. x(Dx → Mx)

2. x(Mx → Wx) / ˫ x(Dx → Wx)

3. Dy → My (1 E)

4. My → Wy (2 E)

5. Dy → Wy (3, 4 HS)

6. ˫ x(Dx → Wx) (5. I)

In this example, note that premises 1 and 2 involve universal statements about all dogs and all mammals. Premises 3 and 4 (highlighted) remove the universal quantifiers and convert them to instances of the original statement, thus changing the “x” to the instantial letter “y”. Premise 5 is a normal deduction in propositional calculus using HS. The conclusion in 6 (highlighted) reintroduces the universal quantifier.

 

Universal Elimination (E – universal instantiation UI):

Explanation:

E eliminates the quantifier so rules and operations in propositional logic can be performed on the premises. The subject letter changes from “x” to some other arbitrarily designated instantial letter such as “y” (for general variables) or s (for specific constants). There are two forms of E, one involving variables and the other constants, and both of these forms are permissible.

Variable form (permissible): subject “y” refers to things in general, not specific things

x(Fx)

˫ Fy

Example: For all things in the universe, those things fluctuate; therefore things fluctuate.

Constant form (permissible): the subject “a” refers to specific thing (e.g., Socrates, tables), not things in general; this is a permissible

x(Fx)

˫ Fa

Example: For all things in the universe, those things fluctuate; therefore atoms fluctuate.

Example of constant form of E in a proof:

For all things, if that thing is human, then that thing is mortal; Socrates is human; therefore, Socrates is mortal.

1. x(Hx → Mx)

2. Hs / ˫ Ms

3. Hs → Ms (1 E)

4. ˫ Ms (3, 2 →E MP)

 

Universal Introduction (I – universal generalization UG): introduces the quantifier, and comes at the end of

Explanation:

I reintroduces the quantifier after normal logical operations have been performed. There are two forms of I, one involving variables and the other constants; only the variable form is permissible, while the constant form is impermissible.

Variable Form (permissible): only the variable form is permissible with I (unlike E where both the variable and constant forms were permissible)

Fy

˫ x(Fx)

e.g., things fluctuate; therefore, for all things in the universe, things fluctuate.

Constant Form (impermissible): the constant form is impermissible since, in the example below, you cannot move from a specific statement about “atoms fluctuating” to a general statement about “all things fluctuating”

Fa

˫ x(Fx)

e.g., atoms fluctuate; therefore, for all things in the universe, things fluctuate.

Example of variable form of I in a proof:

If things are material, then things take up space; things are material; therefore, for all things, things take up space.

1. My → Sy

2. My / ˫ (x)Sx

3. My (1, 2 MP)

4. ˫ (x)Sx (3 I)

 

TWO INFERENCE RULES FOR THE EXISTENTIAL QUANTIFIER

Overview:

Existential Elimination (ƎE) and Existential Introduction (ƎI) parallel E) and I), but are for particular statements (for some x) rather than general statements (for all x). They too function like bookends where ƎE eliminates the quantifier to enable normal logical operations, and ƎI reintroduces the quantifier. Again, once the quantifier is removed, the subject letter changes from “x” to some other arbitrarily designated letter such as “y” (for general variables) or s (for specific constants). Again, these changed letters are called “instantial letters” since they designate instances of the original universal statement.

Example in a proof:

For all things, if that thing is a guitarist, then that thing is a musician; there exists some thing such that it is a guitarist and is homeless; therefore, there exist some thing that is homeless and a musician.

1. x(Gx → Mx)

2. Ǝx(Gx & Hx) / ˫ Ǝx (Hx & Mx)

3. Ga & Ha (2 ƎE)

4. Ga → Ma (1 E)

5. Ga (3 SIMP)

6. Ma (4, 5 MP)

7. Ha & Ga (3 COM)

8. Ha (7 SIMP)

9. Ha & Ma ( CONJ)

10. ˫ Ǝx (Hx & Mx) (ƎI)

In this example, note that premises 1 and 2 involve universal and existential statements. Premises 3 and 4 (highlighted) remove the universal and existential quantifiers and convert them to instances of the original statement, thus changing the “x” to the instantial letter “a”. Premises 5-9 involve normal deductions in propositional calculus. The conclusion in 10 (highlighted) reintroduces the existential quantifier.

 

Existential Elimination (ƎE – existential instantiation EI)

Explanation:

ƎE eliminates the quantifier so rules and operations in propositional logic can be performed on the premises. The subject letter changes from “x” to some other arbitrarily designated instantial letter s (for specific constants). Only the constant form is permissible, while the variable form is impermissible.

Constant Form (permissible)

Ǝx(Fx)

˫ Fa

e.g.: There exists some thing such that this thing is a frog; therefore Alex (which we will call him) is a frog.

Restriction: the existential name “a” must be a new name that has not occurred in any previous line

Variable form (impermissible)

Ǝx(Fx)

˫ Fy

e.g. There exists some thing such that this thing is a frog; therefore things are frogs.

Existential Introduction (ƎI – existential generalization EG)

Explanation:

ƎI reintroduces the quantifier after normal logical operations have been performed. Both the constant and the variable form is permissible.

Constant Form (permissible)

Fa

˫ Ǝx(Fx)

e.g., atoms fluctuate; therefore, there exists some thing that fluctuates

Variable Form (permissible)

Fy

˫ Ǝx(Fx)

e.g., things fluctuate; therefore, there exists some thing that fluctuates

Example of both E and ƎI use in a proof:

For all things, if that thing is a frog then that thing is green; Alex is a frog; therefore, there exists some thing such that it is green.

1. x(Fx →  Gx)

2. Fa / ˫ Ǝx(Gx)

3. Fa →  Ga (1 E)

4. Ga (3, 2 MP)

5. ˫ Ǝx(Gx) (4 ƎI)

 

OTHER QUANTIFICATION RULES

Two-place relational predicate proofs

The above proofs involve premises that contained one-place predicates, such as Fa (Alex is a Frog), or Ǝx(Fx) (everything is a frog). Premises can also contain two-place predicates, such as Abc (Bob admires Claire), or Ǝx(Abx) (there is something that Bob admires), or x y(Fxy) (for all x and all y, x forgets y). Proofs with two-place predicates work the same way as proofs with one-place predicate, but with this additional requirement: when a single premise contains two quantifiers, such as x y(Fxy), removal of the two quantifiers through the universal elimination (E) requires two steps, one for the first quantifier (x) and one for the second quantifier (y). Reintroducing two quantifiers at the end of proofs similarly requires two steps. In the following example, the two steps of elimination are highlighted in yellow, and the two steps of introduction are highlighted in green:

1. x y(Fxy → Fyx)

2. Fab / ˫ Ǝx Ǝy (Fyx)

3. y (Fay → Fya) [1 E (UI)]

4. Fab → Fba [3 E (UI)]

5. Fba [4, 2 MP (→E)]

6. Ǝx (Fbx) [5 ƎI]

7. ˫ Ǝx Ǝy (Fyx) [6 ƎI]

Identity (ID)

The Identity (ID) rule allows exchanging one subject for another subject within a proposition. The form of the rule is this:

Fx, x=y / ˫ Fy

Example:

1. Ǝx(Fx & Gx)

2. a=b / ˫ Gb

3. Fa & Ga [1 ƎE (UI)]

4. Ga [3 SIMP (&E)]

5. ˫ Gb [2, 4 ID]

Quantifier Equivalence Rules (Quantifier Exchange QE)

Quantifier Equivalence rules allow for replacing statements containing universal quantifiers with statements containing existential quantifiers, and vice versa. There are four such rules:

x(Fx) :: ~Ǝx~(Fx)

~x(Fx) :: Ǝx~(Fx)

x~(Fx) :: ~Ǝx(Fx)

~x~(Fx) :: Ǝx(Fx)