Why are 2 Constants introduced in proving: ∃y ∀x (x = y) ∴ ∀y ∀x (x = y)?

Question

_{Source: Sweet Reason: A Field Guide to Modern Logic (2010 2 ed) by Henle, Garfield, Tymoczko.}

[Question, p 330, Section 12.1.] [Justify:] 7. [Premise 1:] ∃y ∀x (x = y)
∴ ∀y ∀x (x = y)

[Answer: p 379, also online.]

I understand, and so ask not about, steps 1-3 and the justification for each step that is clearly stated. Instead, probably because I do not understand the intuition behind this argument, I do not understand the proof strategy, especially 4, 4.1-4.3.3. E.g.:

5. Why must we introduce b and c in 4.1 and 4.2 (as Assumptions for Conditional Proof)? Why not only one Constant? Why any at all?

6. Intuitively, how does ∃y expand and so universalise itself into ∀y?

Answer 1

The intuition is that if there is something (y) that is equal to everything (x), then everything must be equal to everything by transitivity of equality.

• a is the variable that is known to exist because of the ∃ quantifier in the premise.
• b and c are the x and y in the conclusion. a cannot be used here, because it is not 'clean' (it comes from 1.).

Both b and c are known to be equal to a by application of 3 (4.2 and 4.3.2). By transitivity of equality, then also c = b (4.3.3).

You could see 4.1 and 4.3.1 as eliminating the ∀ quantifiers in the conclusion. On both instantiations, 3 is applied to achieve equality with a. Then transitivity is applied in 4.3.3.

To concretely answer your questions:

5. We have to eliminate two universal quantifiers, so we need two clean variables. a is not clean, because it is introduced by ∃-elimination.

6. I'm not entirely sure what you mean here. The variable introduced from the ∃ quantifier is not universalised, because a clean variable is needed for that. a is used in the transitivity step (4.3.3.). This step basically says b = a = c.

Answer 2

Keelan's answer is perfectly good. Just to add my two cents to your question 6: there is one (and as far as I know only one) case where you may infer, from the premise that something is F, that everything is F, and that is when there's just one object! If there's only one thing, and it has a given property, then everything (i.e., that one thing) has that property!

Note that the premise says, essentially, "there is something such that everything is identical to it." Well, if everything is identical to a given thing, then everything is that (one!) thing, i.e., the premise is true if and only if there's only one object. That's the intuitive reason why the conclusion (the universal claim that everything is identical to everything) follows.

Answer 3

Why must we introduce b and c in 4.1 and 4.2 (as Assumptions for Conditional Proof)? Why not only one Constant? Why any at all?

To derive the conclusion, two universal quantifiers must be introduced. The rule of Universal Introduction requires a subproof that begins with the assumption of an arbitrary term, and concludes with a derivation about that term.

To derive ∀x∀y P(x,y) from a set of premises, assume two arbitrary terms that do not occur free within any premise, say b, c, and derive P(b,c), then discharge those assumptions.

Intuitively, how does ∃y expand and so universalise itself into ∀y?

It doesn't. They are different y. What the proof is saying is:

• ∃y∀x (x=y) is the premise. That is a promise that "There is something that is equal to everything".
• Let us use the label a for this thing that we are promised exists.
• Thus ∀x (x=a), which says "Anything equals a"
• Let us take two arbitrary things b and c.
• Since anything equals a, therefore b does. b=a.
• Since anything equals a, therefore c does. c=a.
• Well, since b=a and c=a, therefore they equal each other. c=b [by the rule of equality elimination]
• Since c is arbitrary, then we are saying "anything equals b", that is ∀x (x=b)
• Since b is arbitrary, then we are saying ∀z ∀x (x=z). Well actually, we can use any symbol not already in ∀x (x=b), so we may also reuse y and conclude ∀y ∀x (x=y).