Proof that the order of quantifiers doesn't matter (what went wrong)?

Question

I believe the order of quantifiers in a sentence matters, but I made this proof that basically says it doesn't, what am I doing wrong?

PROOF
$$\forall x\exists y(\phi(x,y))$$ $$\iff$$ $$\exists y\forall x(\phi(x,y))$$

1. $\forall x\exists y(\phi(x,y))$
   assumption
2. $\exists y(\phi(a,y))$
   universal instantiation 1 $a$/$x$
3. $\phi(a,b)$
   existential instantiation 2 $b$/$y$
4. $\forall x(\phi(x,b))$
   universal generalization 3 $x$/$a$
5. $\exists y\forall x(\phi(x,y))$
   existential generalization 4 $y$/$b$
6. $\forall x\exists y(\phi(x,y))\implies\exists y\forall x(\phi(x,y))$
   conditional proof 1,5
7. $\exists y\forall x(\phi(x,y))$
   assumption
8. $\forall x(\phi(x,d))$
   existential instantiation 7 $d$/$y$
9. $\phi(c,d)$
   universal instantiation 8 $c$/$x$
10. $\exists y(\phi(c,y))$
    existential generalization 9 $y$/$d$
11. $\forall x\exists y(\phi(x,y))$
    universal generalization 10 $x$/$c$
12. $\exists y\forall x(\phi(x,y))\implies\forall x\exists y(\phi(x,y))$
    conditional proof 7,11
13. $\forall x\exists y(\phi(x,y))\iff\exists y\forall x(\phi(x,y))$
    biconditional introduction 6,12

What am I doing wrong? Which step is invalid?

Answer 1

You don't say what version of the predicate calculus you are using. Different authors use different combinations of logical axioms and rules of inference. In every version though there are restrictions to prevent this sort of false conclusion.

Note first that the implication $$\exists y\forall x\;\phi(x,y)\to\forall x\exists y\;\phi(x,y)$$ is valid. So we need to look at only the first part of your "proof".

Intuitively it is clear what is wrong. Let me give a concrete example. If $\phi(x,y)$ means "$y$ is the mother of $x$", then the invalid argument claims that

If everyone has a mother, then someone is everyone's mother.

Going through the steps, the invalid inference is clearly $3\Rightarrow 4$: $b$ is $a$'s mother, but that doesn't mean $b$ is everyone's mother.

Now let's delve deeper to see exactly why $3\Rightarrow 4$ is invalid. In step 2, we chose $a$ as "someone, anyone". At this point, $a$ is essentially a free variable; it carries no specific assumptions. But in the next step, we let $b$ be $a$'s mother. This "attaches" $a$ to $b$, in a sense. In any formulas involving both $a$ and $b$, $a$ is not unrestricted, and so Universal Generalization cannot be applied. So the context matters.

This Wikipedia page puts it like this: $$\begin{align*}&\varphi(\beta/\alpha)\\ \hline &\forall\alpha\varphi\end{align*}$$ provided:

1. $\beta$ is a variable which does not occur in $\varphi$.
2. $\beta$ is not mentioned in any hypothesis or undischarged assumptions.

In your case, this would read:

1. $x$ does not occur in $\phi(a,b)$.
2. $x$ is not mentioned in any hypothesis or undischarged assumptions.

However, $x$ is mentioned in the "undischarged assumption" (1). So Universal Generalization is not permitted.

(The way you "discharge" an assumption is to make it the antecedent in an implication. That is, if $A,B,\ldots,G$ is a chain of inferences, with $A$ being an assumption, then we can add $A\to G$ to the end. The assumption $A$ has now been discharged. This is what you called "conditional proof".)

As I said, different versions of deductive systems vary in how they "police" the inference rules. Your example highlights a dangerous interaction between Universal Generalization (UG) and Existential Instantiation (EI). The collection of restrictions must be crafted as a whole. EI introduces "context" for the new constant.

So-called sequent systems make context explicit. Here's how Ebbinghaus and Flum put it in their textbook:

[we can] describe a stage in a proof by listing the corresponding assumptions and the respective claim. If we call a nonempty list (sequence) of formulas a sequent, then we can use sequents to describe "stages in a proof". For instance, the "stage" with assumptions $\varphi_1,\ldots,\varphi_n$ and claim $\varphi$ is rendered by the sequent $\varphi_1,\ldots,\varphi_n\vdash\varphi$.

In a sequent system, you could derive $$\forall x\exists y\;\phi(x,y)\vdash\exists y\;\phi(a,y)$$ But the next step, $\forall x\exists y\;\phi(x,y)\vdash\phi(a,b)$, is invalid.

The justification for something like step 3 comes from a metatheorem. Here is how it appears in Enderton's A Mathematical Introduction to Logic:

If there is a constant symbol $b$ not occurring in $\Gamma$, $\varphi(x)$, or $\psi$, and $\Gamma,\varphi(b)\vdash\psi$, then $\Gamma,\exists x\varphi(x)\vdash\psi$.

Because $b$ doesn't occur except in $\varphi(b)$, nothing occurring in $\Gamma$ or $\psi$ can have any "attachments" to $b$. So this does capture the usual mode of reasoning, "there exists an $x$ such that foobar, let's call it $b$". But if you try to use this in your case to justify step 5, you'll find that the pieces don't fit.

Similarly, Mileti's textbook has this rule of inference: $$\begin{align*}&\Gamma,\varphi(y)\vdash\psi\\ \hline &\Gamma,\exists x\varphi(x)\vdash\psi\end{align*}$$ provided $y$ is not free in $\Gamma$, $\exists x\varphi(x)$, or $\psi$.

Sequent systems typically do not have a rule of inference inferring $\Gamma\vdash\varphi(b)$ from $\Gamma\vdash\exists x\varphi(x)$, precisely because of the issue you noticed. The new constant $b$ may introduce context not captured by $\Gamma$. By putting the existential statement to the left of the $\vdash$ symbol, this problem is avoided.

With Hilbert-style deductive systems, the restrictions are more complicated to describe. Usually the approach taken is to phrase things in terms of implications. For example, here's a logical axiom taken from Mendelson's An Introduction to Mathematical Logic: $$\forall x(A\to B(x))\to(A\to\forall x B(x))$$ provided that $A$ contains no free occurrences of $x$. This is used, indirectly, to justify "let $b$ be the mother of $a$" type arguments. Another approach is to look at the whole preceding chain of statements (as in the Wikipedia page I referenced).

Hope this helps.