Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
7  
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
3  
@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
1  
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
1  
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
add comment

1 Answer

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.