# Prove that $\vdash \phi \land \psi \leftrightarrow \psi \land \phi$

I want to show that $$\vdash \phi \land \psi \leftrightarrow \psi \land \phi$$ for any two formulas $$\phi$$ and $$\psi$$. Before I write down my thoughts, I would like to mention that I am by no means experienced with logic, so if I should mention what axioms I am assuming or anything else, please let me know (I remember the prof only saying that we are using a Hilbert deduction system and the deduction rule is modus ponens; I will also mention that this is an introductory logic course).

The exercise previously asked me to show the following four facts:
$$\{\phi \land \psi\} \vdash \phi$$ $$\{\phi \land \psi\} \vdash \psi$$ $$\{\phi, \psi\} \vdash \phi \land \psi$$ $$\{\phi, \psi\} \vdash \chi \text{ iff } \{ \phi \land \psi\}\vdash \chi \text{ for any formula }\chi$$ This is why I thought that some of them may come in handy. If I write the definition of $$\leftrightarrow$$ in terms of $$\land$$ and $$\rightarrow$$, I will end up with a horrendous expression, so this doesn't look like the way to go. I thought that I might use the completeness theorem and this is a valid way to solve the problem, but I think that I am supposed to solve it using syntactic results only.

EDIT: As requested, the axioms are:
$$\bullet$$ $$\phi \rightarrow (\psi \rightarrow \phi)$$
$$\bullet$$ $$(\phi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\phi \rightarrow \psi)\rightarrow (\phi \rightarrow \chi))$$
$$\bullet$$ $$(\neg \psi \rightarrow \neg \phi) \rightarrow (\phi \rightarrow \psi)$$,
where $$\phi$$, $$\psi$$ and $$\chi$$ are formulas.

• You have to write the axioms of the system... In some cases $(A \land B) \to A$ is an axiom. Jun 12, 2021 at 15:38
• @MauroALLEGRANZA Ok, I will add the axioms right away Jun 12, 2021 at 15:44
• @MauroALLEGRANZA I have added the axioms of the system. If I should specify anything else, please let me know, thank you! Jun 12, 2021 at 15:49
• If those are the axioms, maybe $\land$ is an abbreviation... $\lnot (\phi \to \lnot \psi)$ Jun 12, 2021 at 16:18
• @MauroALLEGRANZA yes, this is how $\land$ is defined Jun 12, 2021 at 16:21

As you have proved, $$\{\phi,\psi\}\vdash\psi\land\phi$$ (since $$\{\phi,\psi\}=\{\psi,\phi\}$$ and according to point 3 of your exercise). And according to point 4 this means that $$\{\phi\land\psi\}\vdash\psi\land\phi$$. Using the deduction theorem we gain $$\vdash(\phi\land\psi)\rightarrow(\psi\land\phi).$$ Similarly, $$\vdash(\psi\land\phi)\rightarrow(\phi\land\psi)$$.
Now it's quite simple to conclude $$\vdash(\phi\land\psi)\leftrightarrow(\psi\land\phi).$$
• Niktin thank you! Could you tell me how I may conclude that $\vdash(\phi\land\psi)\leftrightarrow(\psi\land\phi)$? I mean, this is really intuitive, but I want to see what the formal reasoning would be. Jun 12, 2021 at 23:03
• The formal proof depends on the exact definition of equivalence in this axiomatization. For instance, if $\alpha\leftrightarrow\beta$ is an abbreviation for $(\alpha\rightarrow\beta)\land(\beta\rightarrow\alpha)$ then the desired formula is an immediate consequence of what we know and from point 3 from the exersize you've mentioned. Jun 12, 2021 at 23:27