I'm taking an introductory course in logic and have stumbled upon a question which to me seems more subtle than I first expected. I hope this is the correct place to ask.
The question is (true/false):
Can an arbitrary formula A be a logical consequence of any contradiction B? (*)
By logical consequence I mean that A is true whenever B is true.
By contradiction I mean any rule that always outputs false. An example is $\lnot ( p \rightarrow p) $, where $p$ can take the usual logic values $0$ or $1$. The expression always gives zero as the output, as can be seen by constructing the truth table. To specify: In this context a contradiction is often said to be the opposite of a tautology, where all outputs are true.
With the definition in mind my immediate answer is that the statement (*) is false since the contradiction never is true. However, I have some doubts because I'm vaguely aware of "the principle of explosion" that loosely states that anything can be proven if one starts from a contradiction. In addition, the contradiction is never actually true, so it seems unclear how the definition should be applied.
In short: I believe the statement (*) above is false, but I'm not entirely confident. Can anyone shed some light on the issue.
Best Answer
Thanks for taking so much trouble to ask your question so clearly and in detail. Yes, this is a correct place to ask it. Welcome to Math StackExchange.
It is pretty hard to get rid of the principle of explosion. Consider the following three principles and decide whether you believe them.
The prototypical contradiction is $$a \land \lnot a\tag{$\star$}$$
which says that $a$ is both true and false. (Your suggested contradiction, $\lnot(p\to p)$, can be used similarly, as I will explain at the bottom of this article.)
$(\star)$ is a conjunction. One consequence of it is $a$. By additivity, $a\lor b$ is a consequence also.
But another consequence of $(\star)$ is $\lnot a$. From this, and $a\lor b$, we have $b$, by disjunctive syllogism.
So, from just $a\land\lnot a$, we got $b$. But $b$ could be anything. This is the principle of explosion.
As you say, the contradiction is not actually true. The point is that if it were true, we could infer any $b$ at all from it. Or, viewed another way, if we could prove it, we could prove anything at all.
If you want to get rid of explosion, you have to decide which part of this proof you are willing to discard. Most mathematicians and logicians are unwilling to relinquish it.
That's not intended to shut down your question, but to point out the obstacles you'll face in eliminating the principle of explosion. If you're interested in the paths others have taken before you, you can read about paraconsistent logic, which rejects the principle of explosion.
Your suggested contradiction, $$\lnot (p\to p),\tag{$\heartsuit$}$$ does the same thing. In many systems of logic, we can infer $p\land\lnot p$ directly from $\heartsuit$, and then carry out the argument from the top half of this article. But even if we can't prove $p\land \lnot p$, it's certainly possible to prove $p \to p$ directly, and together with $\heartsuit$, we get $$(p\to p) \land \lnot(p\to p)$$ which is a contradiction, from which the earlier argument derives explosion anyway.
If you plan to look into this more, it may be helpful to know that the principle of explosion is also known as “ex falso quodlibet”, often abbreviated to “EFQ”, and as “ex contradictione quodlibet”, abbreviated “ECQ”. These are Latin phrases that mean “from (falsity / a contradiction), whatever you like”.