Problem 12 Proof From Class

12. Give an example of an invalid deduction (i.e., the conclusion is not true even though the hypothesis is) using the ∃-introduction rule if we don't require y to be free in ϕ. (Hint: find a simple formula ϕ involving ∀y such that ϕ[y|x] is always true but ∃xϕ is not.)


Let's use the simple formula ϕ defined as ∀y (y = x), which is always true for ϕ[y|x] since replacing all free instances of x with y yields ∀y (y = y).

However, ∃xϕ is not true. That statement translates to ∃x ∀y (y = x), which is only true for sets containing one element. For all other cases, however, there is no possible x-value that equals all y-values.

This shows how although the hypothesis ϕ[y|x] is true, the conclusion ∃xϕ (even through proper ∃-introduction) does not have to be true, an example of an invalid deduction.

(Proof written by Anthony M.)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License