4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $p \rightarrow q = \neg p \vee q$ and $\neg q \rightarrow \neg p = q \vee \neg p$--so they are always equivalent. I'm not sure what your question is. $\endgroup$ – Jared May 31 '15 at 6:02
  • $\begingroup$ Suppose when one was happy they always smiled and never smiled when they were sad. Then the sentence "if I'm smiling then I'm happy" wouldn't need to be logically equivalent to "if I'm not happy then I'm not smiling" because it isn't necessarily true in the instance where you could be neutral feeling but still smiling. However if we stipulate that there is no third feeling like neutral that satisfies "not happy" and also "happy" (which could happen in multiple valued logic), then the sentences become equivalent. I'm wondering if there's any weaker way to do this in general. $\endgroup$ – aaron May 31 '15 at 6:13
  • $\begingroup$ The statement "If I'm smiling then I'm happy" is equivalent to "If I'm not happy then I'm not smiling" because if you were smiling then you'd be happy according to the original statement. You confused things by explaining them one way and then writing a non-equivalent "expression". If you meant that when one is happy they always smile then it should have been: "If I'm happy then I smile" and "If I'm not smiling then I'm not happy". Now you can absolutely smile when you are neutral because neutral is not happy and therefore you could smile or not smile and satisfy both expressions. $\endgroup$ – Jared May 31 '15 at 6:19
  • 3
    $\begingroup$ @Jared You need to learn about intuitionistic logic. $\endgroup$ – Zhen Lin May 31 '15 at 8:37
  • 1
    $\begingroup$ @TrevorWilson : I think your answer is good; the fact that contraposition and excluded middle are equivalent relative to intuitionistic logic is interesting, relevant to the OP's question, and well explained in your answer. I only wish to object to the assumption that when someone talks about omitting excluded middle, they're talking about intuitionistic logic (especially when they explicitly refer to other kinds of logic as well). I apologize for my brusqueness in making the objection. I've added an answer about two standard multi-valued logics to complement yours. $\endgroup$ – user21467 May 31 '15 at 17:22
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By the way, @aaron , it seems that when you say "first-order logic", you mean first-order classical logic. Is this the normal terminology in your area? (I ask because in this kind of context I'd always specify, and I think I might have misunderstood a question here a few days ago because I saw "first-order logic" and didn't think it implied "classical".) $\endgroup$ – user21467 May 31 '15 at 17:29
  • $\begingroup$ That's the way I learned it in undergrad. Your answer is really interesting, thank you! $\endgroup$ – aaron Jun 1 '15 at 12:12
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wolfram disagrees about the Law of Excluded Middle: "A law in (2-valued) logic which states there is no third alternative to truth or falsehood. In other words, for any statement A, either A or not-A must be true and the other must be false. This law no longer holds in three-valued logic or fuzzy logic." $\endgroup$ – Jared Jun 1 '15 at 7:00
  • $\begingroup$ @Jared I don't see any disagreement. I'm not claiming that intuitionistic logic is the only logic without LEM. However, it is a commonly studied one. Also, there are natural axiomatizations of classical logic such that, if you remove LEM, you get an axiomatization of intuitionistic logic. So it does seem like a natural setting for the OP's question. $\endgroup$ – Trevor Wilson Jun 1 '15 at 15:21

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.