Is ∃x (∀y (A(x,y) → B(x,y)) → ∃z C(z)) equivalent to ∃x ∃y ∃z ((A(x,y) → B(x,y)) → ∃z C(z))?

Question

Consider the first-order sentence

∃x (∀y (A(x,y) → B(x,y)) → ∃z C(z))

Let's write this sentence in prenex form.

First let's write one of the conditionals using the equivalence: a → b ⟺ ~a | b

∃x (~(∀y (A(x,y) → B(x,y))) | ∃z C(z))

Now we pass the negation through the universal quantifier using one of DeMorgan's Laws:

∃x (∃y ~(A(x,y) → B(x,y)) | ∃z C(z))

We can now pull the existential quantifiers to the beginning of the sentence because of null quantification:

∃x ∃y ∃z (~(A(x,y) → B(x,y)) | C(z))

Using the material conditional equivalence mentioned previously, we get:

∃x ∃y ∃z ((A(x,y) → B(x,y)) → C(z))

In summary, we started with

∃x (∀y (A(x,y) → B(x,y)) → ∃z C(z))

and arrived at

∃x ∃y ∃z ((A(x,y) → B(x,y)) → ∃z C(z))

Are these two sentences equivalent?

It seems really strange that we essentially replaced a universal quantifier with an existential one. We started with

"there is an x with the property that if it is the case that for all y, when A(x,y) then B(x,y), then there is a z with property C"

and that became

"there are x, y, z with the property that if it is the case that when A(x,y) then B(x,y), then there is a z with property C.

Just looking at it, this seems incorrect to me.

In the first case, if for every y, A(x,y) → B(x,y) is true, then ∃z such that C(z). If this is the case, then there exists some y such that A(x,y) → B(x,y), and also ∃z such that C(z) for that y. If it is false that for every y, A(x,y) → B(x,y), then the entire sentence is true. In this case, there could still be some y such that A(x,y) → B(x,y), and it could be the case that there is no z such that C(z) for that y, which would make the sentence false.

Are the two sentences really equivalent?

Answer 1

∃x (∀y (A(x,y) → B(x,y)) → ∃z C(z))

When does a particular x make this true? Two cases:

• If ∀y (A(x,y) → B(x,y)) is false, this makes the whole proposition true. For ∀y (A(x,y) → B(x,y)) to be false, this means we must have a y for which A(x,y) → B(x,y) is false.
• If ∃z C(z) is true, this makes the whole proposition true.

∃x ∃y ∃z ((A(x,y) → B(x,y)) → C(z))

When does a particular x make this true? Two cases:

• If there is a y such that A(x,y) → B(x,y) is false, then the whole thing is true. This is the same as the first condition above.
• If there is a z such that C(z) is true, then the whole thing is true. This is the same as the second condition above.

So yes, they are the same.