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.)