Ethical Realism

July 20, 2015

Predicate Logic 4: Natural Deduction

Filed under: philosophy — JW Gray @ 8:07 am

This is part 4. You should see part 1, part 2, and part 3 before reading this. This is also written with the assumption that you already know propositional logic.

Natural deduction is the use of rules of inference and assumptions in order to reach a conclusion, and they are used to prove argument forms to be logically valid. The entire reasoning process is made entirely explicit, and is known as a ‘proof’ or ‘derivation.’ I will assume here that you already know how to use natural deduction in propositional logic, and natural deduction in predicate logic is done in the same way as in propositional logic, except some additional rules of inference are needed.

1. The rules of inference of propositional logic

I already introduced the following rules if inference, which are used in propositional logic:

Rules of implication

Modus ponens (MP) Modus tollens (MT) Hypothetical syllogism (HS) Disjunctive syllogism (DS)
p → q p → q

p → q

p ∨ q
p

¬q

q → r

¬p

∴q

∴¬p

∴r → s ∴q
Constructive Dilemma (CD) Simplification (Simp) Conjunction (Conj) Addition (Add)
p → q p ∧ q p p
r → s ∴p q ∴p q
p ∨ r ∴p q
∴q s

Rules of replacement

DeMorgan’s Rule (DM) Commutativity (Com) Associativity (Assoc) Distribution (Dist) Double negation (DN)

¬(p ∧ q) :: (¬p ∨ ¬q)

(p q) :: (q p) [p (q r)] ::

[(p q) r]

[p (q r)] ::

[(p q) ∨ (p ∧ r)]

p :: ¬¬p

¬(p ∨ q) :: (¬p ∧ ¬q)

(p q) :: (q p) [p (q r)] ::

[(p q) r]

[p (q r)] ::

[(p q) ∧ (p ∨ r)]

Transposition (Trans) Material implication (Impl) Material equivalence (Equiv) Exportation (Exp) Tautology (Taut)
(p → q) :: (¬q → ¬p) (p → q) :: (¬p ∨ q) (p ↔ q) ::

(p → q) ∧ (q → p)

[(p q) r] ::

[p (q r)]

p :: (p p)
(p ↔ q) ::
(p ∧ q) ∨ (¬p ∧ ¬q)
p :: (p p)

In addition, there are two other strategies that use additional assumptions and sub-derivations: the conditional proof, and indirect proof. Sub-derivations are lines of a proof that use a temporary assumption, and those lines can’t be used outside the sub-derivation. Rules for using these sub-derivations can also be considered to be rules of inference.

I will not describe the conditional proof and indirect proof in detail, but they can be briefly described in the following way:

  1. Conditional proof (CP) – Provide a sub-derivation starting with the assumption of the antecedent (first part) of a conditional you would like to derive. Use that assumption to derive the consequent (second part) of the conditional. At that point the sub-derivation is complete and you have derived the conditional.
  2. Indirect proof (IP) – Provide a sub-derivation starting with the assumption of the negation of what you would like to derive. Use the assumption to derive a contradiction (a sentence and the negation of the sentence). At that point the sub-derivation is complete and you have derived the negation of what you would like to derive.

2. Predicate logic’s rules of inference

Predicate logic requires rules of implication for introducing and eliminated quantifiers, which are the following:

Universal Elimination (∀E) Existential Introduction (∃I)
(∀x)P P(a/x)
P(a/x) (∃x)P

‘P’, ‘a’, and ‘x’ are all meta-variables when shown in a rule of inference. ‘P’ stands for any formula, ‘a’ stands for any predicate constant (represented by a lower case letter between a and v), and ‘x’ stands for any variable (represented by the lower case letters x, y, or z).

a/x” refers to the necessity to replace the variable with a constant when a quantifier is eliminated, or to replace a variable with a constant when a quantifier is introduced. For example, we can use Universal Elimination to use “(∀y)Fy” as a premise to conclude “Fc.”

Universal Elimination and Existential Introduction are the more straightforward rules of implication. The more complicated rules are Universal Introduction and Existential Elimination:

Universal Introduction (∀I) Existential Elimination (∃E)
P(a/x) (x)P
(∀x)P

P(a/x)

Q

Q
additional restrictions additional restrictions
(i) a does not occur in an open assumption. (i) a does not occur in an open assumption
(ii) a does not occur in (∀x)P (ii) a does not occur in (x)P
(iii) a does not occur in Q.

Note that Existential Elimination requires a sub-derivation. The indented area is the sub-derivation, and it says you temporarily eliminate the existential quantifier in order to conclude something else, but you can’t actually conclude that the sentence without the existential quantifier is true.

These two rules of inference have additional restrictions, which were noted above, and they will be described in detail at a later point.

Finally, there is one additional rule of replacement needed in predicate logic:

Quantifier Negation (QN)

¬(∀x)P :: (∃x)¬P

¬(∃x)P :: (∀x)¬P

3. Explanations and examples

Universal Elimination

Universal Elimination (∀E)
(∀x)P
P(a/x)

Universal Elimination is based on the realization that saying everything has some characteristic automatically allows us to conclude that any particular thing has that characteristic as well.

For example:

  1. Everything is a living organism.

  2. Therefore, Socrates is a living organism.

We can use the following scheme of abbreviation:

UD: The set of all humans.

Lx: x is a living organism.

s: Socrates

The proof using natural deduction is then the following:

1. (∀x)Lx /Ls
2. Ls 1, ∀E

The actual rule is cited on the justification column on line 2.

In this case “P” is the sentence “Lx” and the constant is “s.”

Note that you can’t eliminate quantifiers without replacing variables with a constant. For example, “Lx” is not a sentence of predicate logic. It is unclear what exactly “x is a living organism” would mean, and there is the same type of problem for other unquantified sentences that use variables.

Existential Introduction (∃I)

Existential Introduction (∃I)
P(a/x)
(∃x)P

This rule is based on the realization that if some particular individual has a characteristic then there exists an individual that has the characteristic.

For example:

  1. Socrates is a living organism.

  2. Therefore, there is a living organism.

This argument can use the same scheme of abbreviation as the one before.

The proof using natural deduction is the following:

1. Ls /(∃x)Lx
2. (∃x)Lx 1, (∃I)

Universal Introduction

Universal Introduction (∀I)
P(a/x)
(∀x)P
additional restrictions
(i) a does not occur in an open assumption.
(ii) a does not occur in (∀x)P

An open assumption is any initial premise or assumption of a proof except those that are part of a completed sub-derivation. The initial assumptions used in a sub-derivation are also open assumptions while you are still working within that sub-derivation. Lines of sub-derivations can’t ordinarily be used by main lines of a proof, and it’s like they don’t exist after they are completed. An assumption is closed when it is an assumption of a completed sub-derivation.

Universal Introduction is based on the realization that it would be fallacious to conclude that everything has some characteristic just because some particular thing has that characteristic. For example, “Socrates is a human. Therefore, everything is a human” is a fallacious argument.

Instead, what this rule is mainly used for is just to change the variable letter of a sentence.

For example:

1. (∀x)Fx /(∀y)Fy
2. Fb 1, ∀E
3. (∀y)Fy 2, ∀I

This proof abides by the restrictions. The constant (in this case “b”) did not occur in the derived quantified sentence, and it didn’t occur in an assumption or premise.

These restrictions tell us that we can’t use the sentence “Faa” to conclude “(∀x)Fxa” because the same constant would then be in the original statement and the derived quantified sentence, and that we can’t use a premise to reach the conclusion (unless the premise is in a completed sub-derivation).

Existential Elimination

Existential Elimination (∃E)
(x)P

P(a/x)

Q

Q
additional restrictions
(i) a does not occur in an open assumption
(ii) a does not occur in (x)P
(iii) a does not occur in Q.

Existential Elimination is based on the realization that we can’t know any characteristics of a particular individual just because we know some individual has that characteristic. For example, “Something is a dog. Therefore, Joe is a dog” is a fallacious argument.

Existential Elimination uses an existentially quantified sentence to temporarily assume a sentence without the quantification, but the new conclusion reached will not be able to have any constants that were assumed when the quantifier was eliminated.

For example, consider the following argument:

  1. There is a human doctor.
  2. Let’s assume Socrates is a doctor.
  3. Therefore, Socrates is a doctor or a philosopher.
  4. Therefore, someone is a doctor or a philosopher.

We can use the following scheme of abbreviation:

UD: The set of all humans.

Dx: x is a doctor.

Px: x is a philosopher.

s: Socrates

The proof is then the following:

1. (∃x)Dx /(∃x)(Dx ∨ Px)
2.

Ds

A∃E
3.

Ds ∨ Ps

2, Add
4.

(∃x)(Dx ∨ Px)

3, ∃I
5. (∃x)(Dx ∨ Px) 2-4 ∃E

Notice that Existential Elimination requires a sub-derivation (the indented area), and multiple rules are used within that derivation. The sub-derivation starts of with “A∃E” in the justification column, which means “assumption for existential elimination.” It then ends whenever you derived what you want to prove. After the sub-derivation is finished, the next line is on the main line of the proof and cites all the lines of the existential elimination. In this case, lines 2-4 are all cited.

Also note that line 2 technically required the existentially quantified sentence from line 1, but it is not actually cited.

None of the restrictions were violated by this proof. The constant found in the sub-derivation’s premise is “s,” and it is not in an open assumption (or premise), or from the quantified sentence (which is the only premise in this case), and the constant is not in the conclusion of the sub-derivation.

We can interpret the proof as having the following line of reasoning:

  1. There is a doctor.
  2. Let’s assume that Socrates is a doctor.
  3. In that case Socrates is either a doctor or a philosopher.
  4. In that case there is someone who is either a doctor or a philosopher.
  5. Therefore, someone is either a doctor or a philosopher.

Quantifier Negation

Quantifier Negation (QN)

¬(∀x)P :: (∃x)¬P

¬(∃x)P :: (∀x)¬P

Negating a quantifier is the same thing as negating an entire quantified sentence. Quantifier Negation is a rule of replacement, and concern various types of logically equivalent sentences. There is a sense that the two different types of quantified sentences could be said in two different ways. “¬(∀x)P” and “(∃x)¬P” always have the same truth value, and “¬(∃x)P” and “(∀x)¬P” always have the same truth value.

The rule is based on the realization that the following types of sentences are equivalent:

  1. Not all things are P” is logically equivalent to “some things are not P.”
  2. No things are P” is logically equivalent to “All things are non-P.”

For example, consider the following argument:

  1. Not all humans are doctors.
  2. Therefore, some humans are not doctors.

This argument can use the following scheme of abbreviation:

UD: The set of all humans.

Dx: x is a doctor.

The argument could be expressed with the following proof:

1.

¬(∀x)Dx

/(∃x)¬Dx
2. (∃x)¬Dx 1, QN

Quantifier Negation is the easiest of the new rules to use. You can derive any of these types of logically equivalent quantified sentence from the other.

4. Three More examples

Note that there are sometimes multiple ways to prove an argument form to be logically valid by using natural deduction, but I will provide examples of how it could be done.

Example 1

Premises: (∀x)(Hx → Mx), Ha

Conclusion: Ma

  1. All humans are mammals.
  2. Obama is a human.
  3. Therefore, Obama is a mammal.

The proof that the argument has a logically valid form:

1.

(∀x)(Hx → Mx)

2.

Ha

/Ma
3.

Ha → Ma

1, ∀E
4.

Ma

2, 3 MP

An interpretation of the argument is the following:

  1. All humans are mammals.
  2. Something is a human.
  3. Assume that Obama is a human.
  4. If Obama is a human, Obama is a mammal.
  5. Then Obama is a mammal.
  6. In that case something is a mammal.
  7. Therefore, something is a mammal.

Line 3 of the proof could be read as an extra step that says, “If Obama is a human, then Obama is a Mammal.”

Example 2

Premises: (∀x)(Fx → Gx), (∃x)Fx

Conclusion: (∃x)Gx

An interpretation of the argument is the following:

  1. All humans are mammals.
  2. Something is a human.
  3. Therefore, something is a mammal.

We can prove the argument to have a valid logical form using the following proof:

1.

(∀x)(Fx → Gx)

2.

(∃x)Fx

/(∃x)Gx
3.

Fa

A∃E
4.

Fa → Ga

1, ∀E
5.

Ga

3, 4 MP
6.

(∃x)Gx

5, ∃I
7.

(∃x)Gx

3-6 ∃E

The proof can be interpreted as having the following line of reasoning:

  1. All humans are mammals.
  2. Something is a human.
  3. Assume that Obama is a human.
  4. If Obama is a human, Obama is a mammal.
  5. Then Obama is a mammal.
  6. In that case something is a mammal.
  7. Therefore, something is a mammal.

Note that the three restrictions of Existential Elimination were not violated. One, the constant (“a”) is not in an open assumption (a premise or an assumption in an open sub-derivation until it was introduced by Existential Elimination). Two, the constant is not in the Existentially quantified sentence that was eventually eliminated (which was also a premise in this case). Three, the constant is not in the conclusion of the sub-derivation.

Example 3

Premise: (∀x)(Ax → Bx), (Aa → Ba) ↔ (∃x)Cx

Conclusion: Cb → (Aa → Ba)

This argument can be interpreted as the following:

  1. All lawyers are human.
  2. Hillary Clinton is a human provided that she is a lawyer if and only if there is a law school.
  3. Therefore, if UC Berkeley is a law school, then Hillary Clinton is a human provided that she is a lawyer.

The proof:

1.

(∀x)(Ax → Bx)

2.

(Aa → Ba) ↔ (∃x)Cx

/Cb → (Aa → Ba)
3.

((Aa → Ba) → (∃x)Cx) ∧ ((∃x)Cx → (Aa → Ba))

2, Equiv.
4.

(∃x)Cx → (Aa → Ba)

4, Simp.
5.

Cb

ACP
6.

(∃x)Cx

5, ∃I
7.

Aa → Ba

6, 4 MP
8.

Cb → (Aa → Ba)

5-7 CP

The proof can be interpreted as using the following reasoning:

  1. All lawyers are humans.
  2. Hillary Clinton is a human provided that she is a lawyer if and only if there is a law school.
  3. Thus, if Hillary Clinton is a human provided that she is a lawyer, then there is a law school; and if there is a law school, then Hillary Clinton is a human provided that she is a lawyer.
  4. Thus, if there is a law school, then Hillary Clinton is a human provided that she is a lawyer.
  5. Let’s assume UC Berkeley is a law school.
  6. In that case there is a law school.
  7. In that case if Hillary Clinton is a lawyer, then she is a human.
  8. Therefore, if UC Berkeley is a law school, Hillary Clinton is a human provided that she is a lawyer.

Example 4

Premises: (∀x)Ax ∨ (∃x)Cx, Aa → Ba, (∃x)Cx → Db

Conclusion: Ba ∨ (∃x)Dx

An interpretation of this argument is the following:

  1. Either everyone is a living organism or there is a sentient computer.
  2. If Alexander the great is a living organism, then he is made of carbon.
  3. If someone is a sentient robot, then Samantha is made out of silicon.
  4. Therefore, either Alexander the great is made of carbon, or someone is made of silicon.
1.

(∀x)Ax ∨ (∃x)Cx

2.

Aa → Ba

3.

(∃x)Cx → Db

/Ba ∨ (∃x)Dx
4.

(∀x)Ax

ACP
5.

Aa

4, ∀E
6.

Ba

2, 5 MP
7.

(∀x)Ax → Ba

4-6 CP
8.

(∃x)Cx

ACP
9.

Db

3, 8 MP
10.

(∃x)Dx

9, ∃I
11.

(∃x)Cx → (∃x)Dx

8-10 CP
12.

Ba ∨ (∃x)Dx

1, 7, 11 CD

This proof can be interpreted as using the following reasoning:

  1. Either everyone is a living organism or there is a sentient computer.
  2. If Alexander the great is a living organism, then he is made of carbon.
  3. If someone is a sentient robot, then Samantha is made out of silicon.
  4. Assume that everyone is a living organism.
  5. In that case Alexander the great is a living organism.
  6. In that case Alexander the great is made of carbon.
  7. Thus, if everyone is a living organism, then Alexander the great is made of carbon.
  8. Assume someone is a sentient computer.
  9. In that case Samantha is a made out of silicon.
  10. In that case someone is made out of silicon.
  11. Thus, if someone is a sentient computer, then Samantha is made out of silicon.
  12. Therefore, either Alexander the great is made of carbon, or someone is made of silicon.

Example 5

Premises: None

Conclusion: (∃x)Fxx → (∃x)(∃y)Fxy

This is asking us to provide a theorem—a proof that uses no initial premises, and requires us to use sub-derivations, such as an indirect proof or conditional proof.

We can interpret the conclusion as: If there is someone who loves herself, then there is someone who loves someone.

The proof:

1. /(∃x)Fxx → (∃x)(∃y)Fxy
2.

(∃x)Fxx

ACP
3.

Faa

A∃E
4.

(∃y)Fay

3, ∃I
5.

(∃x)(∃y)Fxy

4, ∃I
6.

(∃x)(∃y)Fxy

3-5, ∃E
7.

(∃x)Fxx → (∃x)(∃y)Fxy

2-6, CP

We can interpret this proof as using the following reasoning:

  1. Let’s assume that there is someone who loves herself.
  2. Let’s then assume that Alice loves herself.
  3. In that case Alice loves someone.
  4. In that case there is someone who loves someone.
  5. Thus, someone loves someone.
  6. Therefore, if someone loves herself, then there is someone who loves someone.

This proof requires two sub-derivations, and Existential Elimination provides a sub-derivation that’s already in the sub-derivation used for the Conditional Proof.

This proof also requires that we appreciate the flexibility of Existential Introduction. You can use it to introduce one variable by replacing one constant, even if the constant is used more than once in the sentence.

Existential Elimination is not that flexible, and every copy of the same variable must be replaced with the same constant. We could not have used Existential Elimination to provide the assumption “Fax” because variables can’t exist in a sentence without a corresponding quantifier.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: