12
$\begingroup$

In Practical Foundations for Programming Languages, Robert Harper says

If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a refutation of it, showing that it cannot be proved. That is, a proposition is false if we can show that the assumption that it is true (has a proof) contradicts known facts.

But then, this begs the question- what is a contradiction in constructive/intuitionistic logic?

Is this meant in the sense of deriving $(\bot\text{ true})$ somehow? How would this happen in a sensible way? Would a judgment of the form $(A \supset \bot \text{ true})$ need to be introduced?

Alternatively, is it perhaps meant in the sense of the reader using their discretion to informally label something as contradictory? For example, interpreting $a = b$ and $a \neq b$ as conflicting propositions.

$\endgroup$
15
$\begingroup$

It is immaterial whether we speak about constructive or classical logic in this situation. If you read your questions again, you will see that they apply to boths kinds. The only difference that we need to take notice of is the presentation of negation $\lnot A$. It can be presented in several ways classically, but intuitionistically it is best to use it as an abbreviation for $A \Rightarrow \bot$ (which is precisely what Bob Harper is hinting at in the quoted paragraph). But let us not confuse negations and contradictions.

In both cases, a contradiction is a situation in which we have managed to prove falsity $\bot$. How could we derive $\bot$ in a sensible way? Well, from an inconsistent set of hypotheses, that wold be a sensible way to do it.

You have no discretion to "declare" a contradiction. You must prove that a given set of hypotheses is contradictory by deriving $\bot$. For instance, if $a = b$ and $\lnot (a = b)$ then we may use the fact that $\lnot (a = b)$ is an abbreviation for $(a = b) \Rightarrow \bot$ and conclude $\bot$ by modus ponens.

$\endgroup$
  • $\begingroup$ I read again and it seems better, now. :-) I think I got it stuck in my head that you'd typoed "aloud" so I couldn't find anything else it might be. $\endgroup$ – David Richerby Dec 9 '16 at 16:41
  • $\begingroup$ Now, that's a great idea, reading out loud stackexchange questions! $\endgroup$ – Andrej Bauer Dec 10 '16 at 8:22
8
$\begingroup$

A contradiction is usually represented as $A \land \lnot A$. It's typical in intuitionistic logic to define $\lnot A$ as $A \Rightarrow \bot$. It's clear we can derive $\bot$ from $A \land \lnot A$. Ultimately, a contradiction will be a hypothetical derivation of $\bot$ as the very definition of $\lnot$ suggests. It will be hypothetical because otherwise your logic is inconsistent.

The point Harper is making is that to prove something is to have a proof and to refute something is to have a proof that it implies $\bot$. However, you can easily be in the situation that you can (meta-logically) prove that you are unable to provide either a proof or refutation. In such a situation, the proposition is neither constructively true nor false.

A way to understand classical logic and contrast it to the above is the following (essentially Kolmogorov's double negation interpretation): we say a proposition is false if it implies a contradiction, i.e. it implies $\bot$. A proposition is true if we can prove that it can't be contradicted, i.e. we can show assuming it is false leads to a contradiction. In symbols, $A$ is false in this sense if $A \Rightarrow \bot$, as usual. $A$ is true in this sense if $\lnot A \Rightarrow \bot$, i.e. $\lnot \lnot A$ is provable. You can show that the the Law of the Excluded Middle holds constructively if we interpret "true" and "false" in this sense. That is, you can prove that $\lnot \lnot (\lnot \lnot A \lor \lnot A)$ holds constructively. More compactly, you can show $\lnot \lnot \lnot A \Rightarrow \lnot A$. With this notion of "true" and "false", we can say that a proposition is true if we can prove that no refutation exists. By contrast, constructively a proposition can fail to be constructively true even if we can demonstrate within the system that no refutation can exist.

$\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.