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)

  • 2
    $\begingroup$ 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. $\endgroup$ – Mees de Vries Oct 27 '16 at 15:15
  • $\begingroup$ No, you cannot do that because asserting that those are equal is stronger than what you are trying to prove. $\endgroup$ – user247327 Oct 27 '16 at 15:17
  • $\begingroup$ @MeesdeVries Basic propositional logic. $\vdash: consequence$. Does it have another meaning ? $\endgroup$ – user257 Oct 27 '16 at 15:17
  • $\begingroup$ Typically, $\vdash$ means "provable". But then you need to have some type of proof system in place. This might be natural deduction, for instance. $\endgroup$ – Mees de Vries Oct 27 '16 at 15:18
  • $\begingroup$ 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? $\endgroup$ – Doug Spoonwood Oct 27 '16 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.