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$

2 Answers 2

2
$\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$
1
  • $\begingroup$ Very nice explanation, thank you :) $\endgroup$ Commented Apr 4, 2017 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$

You must log in to answer this question.

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