# Showing $\vdash(\phi_1\wedge\phi_2)\rightarrow(\phi_2\wedge\phi_1)$

How to show $\vdash(\phi_1\wedge\phi_2)\rightarrow(\phi_2\wedge\phi_1)$

Am I allowed to replace $(\phi_1\wedge\phi_2)=(\phi_2\wedge\phi_1)=\phi$ then the problem is reduced to show $\phi\rightarrow\phi$ or do I have to use deduction theorem, assuming the $(\phi_1\wedge\phi_2)$ is true and using an axiom $(\phi_1\wedge\phi_2)\rightarrow\phi_2$ twice $(\phi_1\wedge\phi_1)\rightarrow \phi_2$ obtain $\phi_2\wedge\phi_1$

It is forbidden to apply completeness theorem (still cannot find this in my notes, we had only deduction theorem)

• What does $\vdash$ mean to you? What proof system are you working in? Without context, my best guess is: no, your first approach is not allowed, because $\phi_1 \land \phi_2 \neq \phi_2 \land \phi_1$ (unless $\phi_1 = \phi_2$ of course); and your second approach is probably fine, as long as you already know the deduction theorem holds. – Mees de Vries Oct 27 '16 at 15:15
• No, you cannot do that because asserting that those are equal is stronger than what you are trying to prove. – user247327 Oct 27 '16 at 15:17
• @MeesdeVries Basic propositional logic. $\vdash: consequence$. Does it have another meaning ? – user257 Oct 27 '16 at 15:17
• Typically, $\vdash$ means "provable". But then you need to have some type of proof system in place. This might be natural deduction, for instance. – Mees de Vries Oct 27 '16 at 15:18
• I'm going to use 'A' for $\phi$$_1, 'B' for \phi$$_2$, and 'C' for $\phi$$_3$. You've said that ((A$\land$B)->A) is an axiom and that ((A$\land$B)->B) is an axiom. Now, is (A->(B->A)) an axiom? Is ((A->(B->C))->((A->B)->(A->C)) an axiom? Is ((A->B)->((A->(B->C))->(A->C))) an axiom? Is (A->(B->(A$\land$B))) also an axiom? – Doug Spoonwood Oct 27 '16 at 18:47