Take the 2-minute tour ×

Let $x,y$ be variables, $A(x,y)$ a formula in which both $x$ and $y$ occur free.

Show that

$$\forall x \Big(\forall y\big(A(x,y)\big)\Big) \to \forall y \Big(\forall x\big(A(x,y)\big)\Big)$$

is logically valid

share|improve this question
In what sense: Any model for the left is also a model for the right? Or do you have some deduction rules you are supposed to use for this proof? (We have no way of guessing them...) –  GEdgar Apr 12 '12 at 1:11
@GEdgar: You want to tell me that you're not a psychic?! I demand to talk to your supervisor! This is an outrage!! Professional mathematicians that cannot read minds?! Wait until the press hears about this! –  Asaf Karagila Apr 12 '12 at 1:13
You need to state what formal proof system you're using or this question will be closed; cf. this post on meta. –  jwodder Apr 12 '12 at 1:30
Mark13426, before the comments of others you may not have known that how you prove this depends on what formal proof system you use. Please don't feel discouraged that you didn't realize this. We all didn't know this at some point. That said, the very nature of a formal proof system requires that proofs in the object language stick rigorously to the rules and/or axioms of the system, or that slightly informal proofs can very easily get made into formal proofs (conversion of abbreviated wffs to actual wffs). Otherwise, the purported formal proof system is simply not formal. –  Doug Spoonwood Apr 12 '12 at 2:00

1 Answer 1

In any structure $M$, both formulas hold if and only if $M \models A(x,y)$ for all $x,y \in |M|$. Thus $M \models (\forall x)(\forall y)[A(x,y)] \leftrightarrow (\forall y)(\forall x)[A(x,y)]$. Because that last formula is satisfied by every structure, by definition it is logically valid.

share|improve this answer

Your Answer


