Questions: Natural Deduction for First-Order Logic

Question 1

You want to prove ∀x P(x) by deriving P(a) from your premises. The constant a already appears in one of your undischarged assumptions. Which rule is blocked?

• A. ∀E — universal elimination cannot be applied to premises containing a
• B. ∀I — universal introduction requires a fresh constant not appearing in any undischarged assumption
• C. ∃I — existential introduction requires the witness to be fresh
• D. ∃E — you must discharge a before generalizing

Answer: (B)

∀I (universal introduction) has a freshness condition: the constant a must not appear in any undischarged assumption. The reason is that if a already appears in an assumption, then P(a) was derived using some specific property of a — you cannot legitimately conclude that every object has property P. Only ∀I and ∃E have freshness conditions; ∀E and ∃I are unconstrained.

Question 2

In existential elimination (∃E), you derive conclusion C from ∃x φ(x) using a fresh constant a. Why must a not appear in C?

• A. Because fresh constants are automatically removed from all formulas when ∃E is applied
• B. Because C must hold regardless of which specific object witnesses the existential, and mentioning a would tie C to that particular witness
• C. Because ∃E discharges the assumption φ(a), which removes a from the proof's scope entirely
• D. Because first-order logic does not allow constants to appear in conclusions, only in premises

Answer: (B)

The whole point of ∃E is that you don't know which object witnesses ∃x φ(x) — you name it a and reason from φ(a). If your conclusion C mentioned a, it would assert something about that specific (unknown) witness, not about the world in general. The freshness condition ensures that C is a fact that follows from ∃x φ(x) alone, independent of which witness was chosen. The fresh constant is a proof artifact — a device for reasoning — not an object the theorem is about.

Question 3

Universal elimination (∀E) has no freshness condition: from ∀x φ(x), you may derive φ(t) for any term t already appearing in the proof.

• T. True
• F. False

Answer: True

True. ∀E is unconstrained — you may substitute any term t for x, including terms that already appear everywhere in your proof. This makes sense: if everything has property φ, then this particular thing (referred to by t) has it too. There is no freshness needed because you are instantiating a universal claim to a specific case, not generalizing from a specific case to all cases.

Question 4

The fresh constant a introduced by ∃E appears in the final theorem that is ultimately proved.

• T. True
• F. False

Answer: False

False. The fresh constant is a proof artifact — it is the name given to the unknown witness during the ∃E derivation, but it is discharged when ∃E concludes. The final conclusion C is required by the rule to not mention a at all. This mirrors the natural language phrasing: 'suppose the witness is called a; then... therefore C' — C is the conclusion, and the name a was just scaffolding.

Question 5

Explain why applying ∀I to a constant a that already appears in an undischarged assumption would make the proof unsound.

Model answer: If a appears in an undischarged assumption, then the derivation of φ(a) relied on some specific property of a that was assumed. Applying ∀I would claim that because φ(a) was proved, φ holds for all objects — but the proof only worked because a has whatever special property the assumption ascribed to it. Other objects may not have that property. The freshness condition ensures that a is genuinely arbitrary: if a appears nowhere in the undischarged assumptions, then nothing special was assumed about it, and the derivation of φ(a) must work for any object.

A concrete example: suppose you assume P(a) and then derive P(a) trivially. Applying ∀I would 'prove' ∀x P(x) — everything has property P — from a mere assumption that a does. This is clearly invalid. The freshness condition blocks exactly this inference by requiring that a was not assumed to have any properties.