The contrapositive

Question

Considering an arbitrary model, is law of the excluded middle the weakest axiom needed to make the contrapositive of a statement logically equivalent to the statement? I've seen and done the first order logic proof of it, but what about other kinds of logics like multiple valued logic. I'm not sure whether one needs a stronger or weaker axiom to make use of the contrapositive.

Answer 1

When you talk about logic without the law of excluded middle, I assume that you are talking about intuitionistic logic. In this context, the axiom $(p \to q) \leftrightarrow (\neg q \to \neg p)$ is equivalent to the law of excluded middle, so the answer to your question is yes.

To see this, note that $(p \to q) \to (\neg q \to \neg p)$ is a theorem of intuitionistic logic, so the useful direction will be $(\neg q \to \neg p) \to (p \to q)$. Plugging in $\neg \neg q$ for $p$, we get $(\neg q \to \neg\neg\neg q) \to (\neg \neg q \to q)$. Because $\neg q \to \neg\neg\neg q$ is a theorem of intuitionistic logic (and more generally so is $r \to \neg \neg r$) we get $\neg \neg q \to q$, the law of double negation elimination, which is well-known to be equivalent to the law of excluded middle.

You might be interested in reading about intermediate logics.

Answer 2

In the (strong) Kleene three-valued logic $K_3$, \begin{align*} p\to q &\vDash \neg q\to\neg p \\ \neg q\to\neg p &\vDash p\to q \\ &\not\vDash p\vee\neg p \end{align*} which strictly speaking is what you asked for. This is kind of cheating, though, since $K_3$ has no logical truths at all. For such a logic, maybe a more satisfying candidate for the title "law of the excluded middle" is something like $$ p\to q,\neg p\to q\vDash q $$ which $K_3$ validates (even though a tertium is certainly datur!).

---

In the Łukasiewicz three-valued logic $\textit{Ł}_3$, though, \begin{align*} p\to q &\vDash \neg q\to\neg p \\ \neg q\to\neg p &\vDash p\to q \\ &\not\vDash p\vee\neg p \\ p\to q,\neg p\to q &\not\vDash q \end{align*} (The key difference being that $i\to i = 1$ in $\textit{Ł}_3$, but $i\to i = i$ in $K_3$.) According to the SEP, Wajsberg (partially) axiomatized $\textit{Ł}_3$ thus:

1. $p\to (q\to p)$
2. $(p\to q)\to (q\to r)\to (p\to r)$
3. $(\neg p\to\neg q)\to (q\to p)$
4. $((p\to\neg p)\to p)\to p$

Half of contraposition is right there as (3); I guess the other half arises by taking $r=\bot$ in (2). (I suppose $\bot$ can be defined as $\neg(p\to p)$.) So it seems that, no, excluded middle is stronger in this context than contraposition.

---

I think I computed the truth tables correctly, but I'd recommend that you check them yourself. My computations are not completely reliable.