9. THE PREDICATE CALCULUS
Outline
James Fieser, UT Martin
updated 11/1/2023
A. INTRODUCTION
Predicate calculus is built upon the system of propositional calculus, with the rules of predicate logic added to it. Predicate calculus deals principally with how to introduce and remove universal and existential quantifiers when performing logical operations. There are four main rules titled as follows, with their abbreviations color coded for easier identification:
• Universal Elimination (∀E)
• Universal Introduction (∀I)
• Existential Elimination (ƎE)
• Existential Introduction (ƎI)
The four rules themselves are straight forward, and we will consider these in detail below. For more context, here is a typical argument in propositional calculus:
1. P → Q
2. P & P / ˫ Q
3. P [2 SIMP &E]
4. ˫ Q [1, 3 MP → E]
Next, here is a typical statement in predicate logic:
(∀x)Fx → Gx [for all x, if x has the property F, then x also has the property G]
Here, then, is how the symbols of predicate logic can be added into propositional calculus:
1. (∀x)Fx → Gx
2. (∀x)Fx & Fx / ˫ (∀x)Gx
3. Fy → Gy [1 ∀E]
4. Fy & Fy [2 ∀E]
5. Fy [4 SIMP &E]
6. Gy [2, 5 MP → E]
7. ˫ (∀x)Gx [5 ∀I]
This argument in predicate calculus parallels the previous one in propositional calculus, but with these three main differences.
1. Remove quantifiers to perform logical operations: Before any of the rules of propositional calculus can be used beneath line two, the universal quantifier "(∀x)" must be removed from the statements in both line 1 and 2. Think of quantifiers like "(∀x)" as being padlocks that prevent you from applying rules of inference and equivalence. Lines 3 and 4 remove those padlocks and in essence frees up those statements for performing normal deductions using rules in lines 5 and 6. In the above, think of lines 3-6 (shaded in gray) as a work area where the quantifiers are removed.
2. Quantifiers are paired for elimination and reintroduction. Quantifier rules in predicate calculus often come in pairs in logical proofs like two bookends, where the one appears at the beginning of a proof, and the other at the end. The first removes the quantifier and frees up propositions so that normal logical deductions can be performed on them. The second reintroduces the quantifier. In the above example, the rule ∀E (universal elimination) removes the quantifiers in lines 3 and 4, and the rule ∀I (universal introduction) restores the quantifier in the conclusion in line 7. With existential quantifiers, the rule ƎE (existential elimination) removes the quantifier, and the rule ƎI (existential introduction) restores the existential quantifier.
3. Temporarily change subject letter. Subject letters such as "x" should be changed to some other letter such as "y". In the above example, note that Fx → Gx in line 1 is changed to Fy → Gy in line 3 within the gray work area. In the conclusion in line 7, the y is changed back to x. The reason for the change is to avoid confusing general subjects (such as dogs in general) with particular subjects (such as the specific dog Fido). The letter change can be done in two ways, one for variables, and another for constants. As in math, a "variable" is a symbol representing an unknown or changing quantity (e.g., dogs in general), while a "constant" is a symbol representing a fixed and unchanging value (e.g., the specific dog Fido). Accordingly, for variables (things in general), the subject letters temporarily change from “x” to some other letter near the end of the alphabet such as “y”. However, for constants (specific things), subject letters temporarily change from “x” to some other letter near the beginning of the alphabet such as "a". In both cases, the changed letter is called an “instantial letter” since it designates an "instance" of the original subject "x".
All three of these issues will be explained in more detail below.
B. TWO INFERENCE RULES FOR THE UNIVERSAL QUANTIFIER
1. Overview
Again, the two quantification rules of Universal Elimination (∀E) and Universal Introduction (∀I) often come in pairs. In the example below, ∀E appears at the beginning of the work area in gray, and ∀I at the end. The first removes the universal quantifier and frees up propositions so that normal logical deductions can be performed on them. The second reintroduces the universal quantifier.
In English:
1. For all things, if a thing is a dog, then that thing is a mammal.
2. For all things, if a thing is a mammal, then that thing is warm-blooded.
3. Therefore, for all things, if a thing is a dog, then that thing is warm-blooded.
Use of ∀E and ∀I in a proof:
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]
Again, in the above, the subject letter temporarily changes from “x” to “y”, since it involves a discussion of dogs in general (i.e., a general variable) rather than a specific dog such as Fido (a particular constant).
2. Universal Elimination ∀E (sometimes called "universal instantiation"):
Two forms of the rule
There are two forms of ∀E, one involving variables and the other constants, and both of these forms are permissible with the ∀E rule.
• 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 this atom fluctuates.
Example of a variable form of ∀E in a proof (changing x to y):
The earlier hypothetical syllogism about dogs being warm blooded is such an example. The x was turned to a y since it was talking about dogs in general, and not some specific dog like Fido.
Example of constant form of ∀E in a proof (changing x to a):
For all things, if that thing is human, then that thing is mortal; Socrates is human; therefore, Socrates is mortal. (Note: the default symbol "a" is used to designate the individual constant "Socrates", although "s" or some other letter could also be used as long as it's not "x" or "y".)
1. ∀x(Hx → Mx)
2. Ha / ˫ Ma
3. Ha → Ma [1 ∀E constant form]
4. ˫ Ma [3, 2 →E MP]
3. Universal Introduction ∀I (sometimes called universal generalization UG): introduces the quantifier, and often comes at the end of a proof.
Two forms of the rule: 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. This is unlike ∀E where both the variable and constant forms were permissible. The issue of permissibility hinges on determining when we can or can't move back and forth between universal and particular statements. Take the following two statements:
1. All frogs are green, therefore this frog is green (this is permissible since you can move from a general to a particular)
2. This frog is green, therefore all frogs are green (this is impermissible, since you can't move from a particular to a general)
These two statements parallel the permissible and impermissible forms of ∀I.
• Variable Form (permissible): only the variable form is permissible with ∀I s
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 “this atom fluctuates” to a general statement about “all things fluctuating”. (Note: the constant form below is crossed out to make if visually clear that it is impermissible)
Fa
˫ ∀x(Fx)
e.g., this atom fluctuates; 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. Sy [1, 2 MP]
4. ˫ (∀x)Sx [3 ∀I variable form]
4. Use of both ∀E and ∀I in a proof:
For all x, if x is a dog then x is a mammal; for all x, if x is a mammal then x is warm blooded; therefore, for all x, if x is a dog, then x is warm blooded.
1. ∀x(Dx → Mx)
2. ∀x(Mx → Wx) / ˫ ∀x(Dx → Wx)
3. Dy → My [1 ∀E variable form]
4. My → Wy [2 ∀E variable form]
5. Dy → Wy [3, 4 HS]
6. ˫ ∀x(Dx → Wx) [5, ∀I variable form]
C. TWO INFERENCE RULES FOR THE EXISTENTIAL QUANTIFIER
1. 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).
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 constant form]
4. Ga → Ma [1 ∀E constant form]
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 constant form]
In this example, note that premises 1 and 2 involve universal and existential statements. Premises 3 and 4 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.
2. Existential Elimination ƎE (sometimes called "existential instantiation")
Two forms of the rule: 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) (Note: the variable form below is crossed out to make if visually clear that it is impermissible)
Ǝx(Fx)
˫ Fy
e.g. There exists some thing such that this thing is a frog; therefore things are frogs.
3. Existential Introduction ƎI (sometimes called "existential generalization")
Two forms of the rule: Both the constant and the variable form is permissible.
• Constant Form (permissible)
Fa
˫ Ǝx(Fx)
e.g., this atom fluctuates; therefore, there exists some thing that fluctuates
• Variable Form (permissible)
Fy
˫ Ǝx(Fx)
e.g., things fluctuate; therefore, there exists some thing that fluctuates
4. 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 constant form]
4. Ga [3, 2 MP]
5. ˫ Ǝx(Gx) [4 ƎI constant form]
D. OTHER QUANTIFICATION RULES
1. 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.
1. ∀x ∀y(Fxy → Fyx)
2. Fab / ˫ Ǝx Ǝy (Fyx)
3. ∀y (Fay → Fya) [1 ∀E]
4. Fab → Fba [3 ∀E]
5. Fba [4, 2 MP (→E)]
6. Ǝx (Fbx) [5 ƎI]
7. ˫ Ǝx Ǝy (Fyx) [6 ƎI]
2. 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]
4. Ga [3 SIMP (&E)]
5. ˫ Gb [2, 4 ID]
3. 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)
For all x, x is F :: it is not the case that there exist some x, such that no x is F
• ~∀x(Fx) :: Ǝx~(Fx)
It is not the case that, for all x, x is F :: there exists some x, such that it is not the case that x is F
• ∀x~(Fx) :: ~Ǝx(Fx)
For all x, it is not the case that x is F :: it is not the case that, there exists some x such that x is F
• ~∀x~(Fx) :: Ǝx(Fx)
It is not the case that, for all x, no x is F :: there exists some x such that x is F