Language Proof and logic Chapter 13 problem 31

Question

I have been working on this problem for over an hour and I think I have simply missed something. I need some help. I don't see how this is supposed to work out

Here are the premises:

• ∀x ∀y[Likes(x,y) → Likes(y,x)]
• ∃x ∀yLikes(x,y)

Here is the goal: ∀x ∃yLikes(x,y)

I can see we will need to use existential elimination and introduction, but I do not understand why these rules are the way they are.

Answer 1

I can see we will need to use existential elimination and introduction, but I do not understand why these rules are the way they are.

Existential Introduction is easy. [Just avoid scope collisions when binding a term to the existential quantifier.]

: | : :
7.| |  Q(b)
8.| |  ∃y Q(y)    ∃I, 7   as long as `y` does not already occur in `Q(b)`

If a predicate is true for a term that does exist in the context, then in that context there exists some term which makes the predicate true.

Thus we "introduce" an existential statement.

---

Existential Elimination is slightly more involved.

Having derived a predicate in a context that makes an assumption that is a witness for an existential statement (outside the context), and the predicate does not include the assumed term, then that assumption may be discharged to deduce the predicate outside that context.

1.|  ∃y P(y)                   an existential statement about a predicate
2.|  |_ [b] P(b)               an assumed witness for that predicate
: |  |  :
8.|  |  R                      R does not include b as a free term
9.|  R           ∃E, 1, 2-8

We "eliminate" the existential in line 1, to derive the conclusion of the sub-proof in lines 2-8.

---

These are often combined. Existential Introduction is used to derive a predicate that does not include the term for the witness, so that Existential Elimination may be employed.

1.|  ∃y P(y)
2.|  |_ [b] P(b)
: |  |  :
7.|  |  Q(b)
8.|  |  ∃x Q(x)    ∃I, 7       as long as `x` does not already occur in `Q(b)`  
9.|  ∃x Q(x)       ∃E, 1, 2-8

Note: we are not required to use the same bound variable, and may choose to use a different one; .

---

 1.|  ∀x ∀y [Likes(x,y) → Likes(y,x)]
 2.|_ ∃x ∀y Likes(x,y)
 3.|  |_ [a] ∀y Likes(a,y)               A          a is a witness for 2
 4.|  |  ∀y [Likes(a,y) → Likes(y,a)]    ∀E 1       [x\a]
 5.|  |  |_ [b]                          A          b is an arbitrary entity
 6.|  |  |  Likes(a,b)                   ∀E 3       [y\b]
 7.|  |  |  Likes(a,b) → Likes(b,a)      ∀E 4       [y\b]
 8.|  |  |  Likes(b,a)                   →E 6,7
 9.|  |  |  ∃y Likes(b,y)                ∃I 8       since a exists in context
10.|  |  ∀x ∃y Likes(x,y)                ∀I 5-9     since b is arbitrary
11.|  ∀x ∃y Likes(x,y)                   ∃E 2,3-10  since a does not occur in 10

Answer 2

The problem is to derive the following using natural deduction:

Here are the premises:

• ∀x ∀y[Likes(x,y) → Likes(y,x)]
• ∃x ∀yLikes(x,y)

Here is the goal: ∀x ∃yLikes(x,y)

Using Klement's proof checker associated with the forallx textbook referenced below, this can be completed in 10 lines. The proof checker associated with the textbook you are using may require different syntax although the basic idea would be to use existential elimination and introduction with modus ponens (conditional elimination).

The real problem is understanding why the existential elimination rules work the way they do. It is relatively easy to manipulate a proof checker (or manually follow steps) to reach the correct result. It is not easy to understand why those specific steps should lead to a valid derivation. This takes studying the logic textbook itself describing existential elimination.

In forallx, existential elimination is covered in section 32.5. Given the premise ‘∃xFx’ as their example, the authors make the observation: (page 246)

Suppose we know that something is F. The problem is that simply knowing this does not tell us which thing is F. So it would seem that from ‘∃xFx’ we cannot immediately conclude ‘Fa’, ‘Fe23’, or any other substitution instance of the sentence. What can we do?

Note that, unlike universal elimination where we can substitute any name for the variable 'x' since everything in the domain is that predicate, we don't know which thing actually is F. All we know by the premise is that something in the domain is F.

After providing a proof on page 247 which is a simplification of your exercise, they make the following observation about what they did:

Breaking this down: we started by writing down our assumptions. At line 3, we made an additional assumption: ‘Fo’. This was just a substitution instance of ‘∃xFx’. On this assumption, we established ‘∃xGx’. Note that we had made no special assumptions about the object named by ‘o’; we had only assumed that it satisfies ‘Fx’. So nothing depends upon which object it is. And line 1 told us that something satisfies ‘Fx’, so our reasoning pattern was perfectly general. We can discharge the specific assumption ‘Fo’, and simply infer ‘∃xGx’ on its own.

This leads to the rules.

We must pick a name, 'o' in the case of this example, that was not previously used in an undischarged assumption nor in the line containing the existential quantifier we are eliminating. This is to make sure there are "no special assumptions about the object named by ‘o’".

We can discharge the assumption closing the subproof if we can derive a line that does not use that name so we don't take the name outside the subproof. An easy way to do that is to use existential introduction, but we also want some line that will help us complete the proof. For this example, existential introduction is all we need.

---

References

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/