1
$\begingroup$

This is my first week studying logic, and I am a bit stumped on the following problem:

Show $\alpha \leftrightarrow \psi$ is a tautology if and only if $\alpha \approx \psi$

Here's what I'm thinking:

Assume $\alpha\leftrightarrow\psi$ Is a tautology. Then \begin{align} (\alpha\rightarrow\psi)\wedge (\psi\rightarrow\alpha)\approx T\\ \implies (\neg \alpha \vee \psi)\wedge(\neg\psi\vee\alpha)\approx T \end{align}

And then I don't know where to go.

In the other direction, assume $\alpha\approx \psi$. Thus $[[ \alpha ]]=[[\psi]]$ is true in all interpretations. Then \begin{align} (\neg \alpha \vee \psi)&\wedge(\neg\psi\vee\alpha)&= \\ 1 &\wedge 1& = 1 \end{align} Since if (WLOG) $[[\alpha]]=1$, then $[[\neg \psi]]=0$, thus \begin{align} (\neg \alpha \vee \psi)&\wedge(\neg\psi\vee\alpha)&\approx T \end{align}

So i need help with the first part, and it would be nice to get comments on how sound my argument for the converse is. Thank you!

$\endgroup$
3
$\begingroup$

By def, if $\alpha \leftrightarrow \psi$ is a tautology, then it is true under every interpretation.

Assume by contradiction that not: $\alpha \approx \psi$.

This means that there is an int $v$ such that $[[ \alpha ]]_v= 1$ and $[[\psi]]_v= 0$ (the choice is immaterial).

Thus, $[[ \alpha \to \psi ]]_v=0$, contradicting the fact that $\alpha \leftrightarrow \psi$ is a tautology.


Also for the other "direction", it is enough to stop the analysis to: $\alpha \leftrightarrow \psi = (\alpha \to \psi) \land (\psi \to \alpha)$.

We have that: $[[α]]_v=[[ψ]]_v$ in every interpretation $v$.

This means that, either they are both true or both false in $v$, and so $[[α \to ψ]]_v=[[ψ \to α]]_v=1$ for every $v$.

$\endgroup$
  • $\begingroup$ Very nice explanation, thank you :) $\endgroup$ – jgcello Apr 4 '17 at 7:26
1
$\begingroup$

$\alpha \leftrightarrow \psi$ is a tautology iff (definition tautology)

$[[\alpha \leftrightarrow \psi]]$ is true under all interpretations iff (semantics $\leftrightarrow$)

$[[\alpha]]=[[\psi]]$ under all interpretations iff (definition $\approx$)

$\alpha \approx \psi$

$\endgroup$

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.