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

Your Answer

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

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