How to prove that we can switch two $\forall$?

Question

1. This is true?

2. See a simple proof (High-school level)

Thanks

e.g:

$$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$

Answer 1

$$\DeclareMathOperator{\and}{~And~} \DeclareMathOperator{\inn}{~In~}$$

Here is an informal proof directed at high school level. First of all, $\forall$ serves the same purpose as $\and$. To understand, consider the example:

$$\forall x \inn \{1 \dots 10\} ~:~ P(x)$$

Is the same truth as :

$$P(1) \and P(2) \and P(3) \dots \and P(10)$$

To understand your question, consider another example using natural numbers, which are written as $\mathbb{N}$. Your expression with naturals is:

$$\forall x \inn \mathbb{N} ~:~ \forall y \inn \mathbb{N} ~:~ P(x,y)$$

So expand the above expression using the idea "$\forall$ means and" to get:

$$\begin{array} {ccccccccc} \bigg(P(0,0) & \and & P(0,1) & \and & P(0,2) & \and & P(0,3) & \and & \dots\bigg) \\ & & & & \and & & & & \\ \bigg(P(1,0) & \and & P(1,1) & \and & P(1,2) & \and & P(1,3) & \and & \dots\bigg) \\ & & & & \and & & & & \\ \bigg(P(2,0) & \and & P(2,1) & \and & P(2,2) & \and & P(2,3) & \and & \dots\bigg) \\ & & & & \vdots & & & & \\ \end{array}$$

You can regroup the parenthesis to get:

$$ \left(\begin{array} {c} P(0,0) \\ \\ \and \\ \\ P(1,0) \\ \\ \and \\ \\ P(2,0) \\ \\ \vdots \end{array}\right) \and \left(\begin{array} {c} P(0,1) \\ \\ \and \\ \\ P(1,1) \\ \\ \and \\ \\ P(2,1) \\ \\ \vdots \end{array}\right) \and \left(\begin{array} {c} P(0,2) \\ \\ \and \\ \\ P(1,2) \\ \\ \and \\ \\ P(2,2) \\ \\ \vdots \end{array}\right) \and \left(\begin{array} {c} P(0,3) \\ \\ \and \\ \\ P(1,3) \\ \\ \and \\ \\ P(2,3) \\ \\ \vdots \end{array}\right) \dots $$

which is the same as

$$\forall y \inn \mathbb{N} ~:~ \forall x \inn \mathbb{N} ~:~ P(x,y)$$

So you are just rearranging the order of a gigantic $\and$ expression.

Answer 2

HINT

Suggested first 2 lines of a proof by contradiction:

1. Suppose $\forall x: \forall y: P(x,y)$

2. Suppose to the contrary that $\neg\forall y: \forall x: P(x,y)$, or equivalently $\exists y: \exists x: \neg P(x,y)$