2

Question

Is it the case that the statement $ \forall x \forall y P(x, y)$ is equivalent to the statement $\forall y \forall x P(x, y)$ ?

Thoughts

I know that if one of the quantifiers in the original statement was $\exists$, then it wouldn't be equivalent, but if both quantifiers were $\forall$ would this change whether or not the equivalence holds?

FD_bfa
  • 3,989
ripull
  • 21
  • Hello, it means the same thing. – Mateo_13 Oct 14 '22 at 03:47
  • Yes. In fact, some people write this as $\forall x,y P(x,y)$. And you can also condense together adjacent $\exists$s regardless of order. But as you note, you can't switch the order of any $\forall$ and $\exists$. – JonathanZ Oct 14 '22 at 04:42
  • @Mateo_13 thanks for responding. Can you just explain why? Or is there a way to show that? thanks. – ripull Oct 14 '22 at 13:24
  • I don't know how to prove it, but if you understand why you can't permute "There exists" and "For all", you should understand why permuting two "For all" doesn't matter. – Mateo_13 Oct 14 '22 at 18:37

3 Answers3

3

Informal Explanation

Yes, they can be used interchangeably.

The easiest way to see this, is to think about everyday examples in English and to see how the quantifiers behave here.

For example: “for every apple and for every orange, if I pick an apple and an orange, I will prefer the apple”

In regular English, this just says that I always prefer apples to oranges.

This is even easier to see in the special case where two distinct claims are made about the two items. This is the case because we are making two distinct claims that do not interact with one another.

For example: ”for all apples and for all oranges, it is the case that apples can be eaten and oranges are not purple.”

Your question is even true for $n$ variables. So it would apply if we introduced a third object, or a fourth, etc. Again, it is usually fairly intuitive to work out once you set aside the logic and think about constructing English sentences from a given sentence written using FO-Logic / Predicate Logic.

Informal Proof

I'm not sure whether or not you are interested in a proof, but I'll write an informal one based loosely on the principles used in the Fitch Proof System. The reason I am not doing this rigorously is to make it clear exactly what every step means in case you aren't familiar with the system.

Statement: $\forall x \forall y P(x,y)$

  • Step 1: As this applies for all x, the sentence is true for an arbitrary constant which I will call $\lambda$.

  • Step 2: So we know $\forall y P(\lambda, y)$ is true. Because, it's true for any value of x, it must be true when x is lambda.

  • Step 3: This statement is true for any value of y, so I can just replace y with an arbitrary constant. Let's call this $\phi$.

  • Step 4: Therefore, we now have the statement $P(\lambda, \phi)$. It should make sense that this is true, because we know already that $P(x,y)$ is true for any values of $x$ and $y$.

  • Step 5: Since, the choice of $\lambda$ was arbitrary and we could've chosen any value of $x$. Then we know $\forall P(x,\phi)$ is true.

  • Step 6: Since $\phi$ was also arbitrary and we could have chosen any value of $y$ instead, the statement in step 5 is true for any $y$. Hence, it is true that $\forall y \forall x P(x,y)$

And then we are done.

FD_bfa
  • 3,989
1

An intuitive account of this equivalence can be given over a sample domain (a set of numbers, for instance), while we ought to rely first and foremost on derivations. Here is one in axiomatic (Hilbert) style:

$1.\qquad\forall x\forall yP(x, y)\qquad\qquad\qquad\qquad\text{hypothesis}$

$2.\qquad\forall x\forall yP(x, y)\rightarrow\forall yP(x, y)\qquad\,\text{Axiom 4}$

$3.\qquad\forall yP(x, y)\qquad\qquad\qquad\qquad\quad\text{Modus ponens 1, 2}$

$4.\qquad\forall xP(x, y)\rightarrow P(x, y)\qquad\qquad\;\text{Axiom 4}$

$5.\qquad P(x, y)\qquad\qquad\qquad\qquad\qquad\text{Modus ponens 3, 4}$

$6.\qquad\forall xP(x, y)\qquad\qquad\qquad\qquad\quad\text{Generalisation from 5}$

$7.\qquad\forall y\forall xP(x, y)\qquad\qquad\qquad\qquad\text{Generalisation from 6}$

By symmetry, $\forall x\forall yP(x, y)$ is derived from $\forall y\forall xP(x, y)$ as well and we conclude

$$\forall x\forall yP(x, y)\leftrightarrow\forall y\forall xP(x, y)$$

Remark. Each axiomatic system with its axioms and inference rules just as stated should be applied in its entirety; nothing more and nothing less. In the system I've used here, each line (including hypothesis) is accepted as tautology. Thus, line 5 states that $P(x, y)$ is true for arbitrary $x$ and $y$. Hence, generalisation is not an illegitimate binding of a variable.

Axiom 4 of this system is $\forall x\phi(x)\rightarrow\phi(t)$ where $t$ is free for $x$ in $\phi$. Clearly, each variable is free for itself.

Tankut Beygu
  • 2,331
-3

The informal proof by @FD_bfa is a bit confusing, because it introduces $\lambda$ and $\phi$ in the wrong order. Here is a version of the proof that I think is clearer.

Suppose that $\forall x\forall yP(x,y)$ is true. We want to prove that $\forall y\forall xP(x,y)$ is true, so let $\phi$ be an arbitrary object. If we can prove $\forall xP(x,\phi)$, then, since $\phi$ is arbitrary, we will be able to conclude $\forall y \forall xP(x,y)$. To prove $\forall xP(x,\phi)$, let $\lambda$ be an arbitrary object. If we can prove $P(\lambda, \phi)$, then, since $\lambda$ is arbitrary, we will be able to conclude $\forall xP(x,\phi)$. So our goal now is to prove $P(\lambda,\phi)$.

We started by assuming $\forall x\forall yP(x,y)$. Since this statement starts with $\forall x$, we can plug in anything we want for $x$. Plugging in $\lambda$ for $x$, we can conclude that $\forall yP(\lambda, y)$. Similarly, we can now plug in $\phi$ for $y$ to get $P(\lambda, \phi)$. Since this was our goal, we are done.

Of course, the proof of the implication in the other direction is similar.

Dan Velleman
  • 2,746
  • 2
    @FD_bfa's proof has the right order, not wrong. You can de-instantiate only the outermost quantifier – whoisit Oct 19 '22 at 15:41
  • No, the order is wrong. The variables $\lambda$ and $\phi$ are not introduced by instantiating in the hypothesis $\forall x\forall yP(x,y)$. Rather, they are introduced as arbitrary objects to prove the goal $\forall y\forall xP(x,y)$. Since $\forall y$ is the outermost quantifier in the goal, the arbitrary object for $y$ is the one that should be introduced first. It is only after the arbitrary objects are introduced that they can be used to instantiate $x$ and $y$ in the hypothesis. – Dan Velleman Oct 19 '22 at 21:16
  • In my version of the proof I am following the convention, common in mathematical writing, of beginning a proof of a universally quantified statement with a sentence of the form "Let _ be an arbitrary object." It seems to me that is the clearest way to explain the answer to the OP's question. If you follow that convention, then $\phi$ must be introduced first. – Dan Velleman Oct 19 '22 at 21:38
  • 1
    You cannot use arbitrary conventions like that. You cannot make changes to the "internal" statement without removing the outermost quantifier. – whoisit Oct 20 '22 at 00:51
  • 1
    If I go by your rule, $\forall x \exists y \Phi(x, y)$ could let me write $\forall x \Phi(x, \beta)$ for some $\beta$. That is obviously not correct. – whoisit Oct 20 '22 at 00:52
  • I didn't make changes to the "internal" statement. Go back and read my version of the proof more carefully. Once both arbitrary objects $\phi$ and $\lambda$ had been introduced, I first plugged in $\lambda$ for $x$ in $\forall x\forall y P(x,y)$ (the outermost quantifier) to get $\forall yP(\lambda, y)$, and then plugged in $\phi$ for $y$. I always worked with the outermost quantifier. – Dan Velleman Oct 20 '22 at 18:17
  • The conventions I used were not arbitrary. They are the conventions used in all mathematical writing--see my book How To Prove It. For the purpose of answering the OP's original question, I think it is helpful to follow those conventions. OP wanted to know: if $\forall x\forall yP(x,y)$ is true, how do we know $\forall y\forall xP(x,y)$ is true? To answer that, you have to explain why, if $\phi$ is an arbitrary object, the statement $\forall xP(x,\phi)$ is true. My version of the proof addresses that directly. – Dan Velleman Oct 20 '22 at 18:25