1
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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).$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – TheZone
    Jun 12, 2021 at 23:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 12, 2021 at 23:27
  • $\begingroup$ Yes, this is the case. Thank you! $\endgroup$
    – TheZone
    Jun 12, 2021 at 23:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .