What does `true = false` mean in Coq?

Question

[I am not sure this is appropriate for stack overflow, but there are many other Coq questions here so perhaps someone can help.]

I am working through the following from http://www.cis.upenn.edu/~bcpierce/sf/Basics.html#lab28 (just below where Case is introduced). Note that I am a complete beginner at this, and am working at home - I am not a student.

Theorem andb_true_elim1 : forall b c : bool,
  andb b c = true -> b = true.
Proof.
  intros b c H.
  destruct b.
  Case "b = true".
    reflexivity.
  Case "b = false".
    rewrite <- H. reflexivity.
Qed.

and I am looking at what the rewrite does:

  Case := "b = false" : String.string
  c : bool
  H : andb false c = true
  ============================
   false = true

then rewrite <- H. is applied:

  Case := "b = false" : String.string
  c : bool
  H : andb false c = true
  ============================
   false = andb false c

and it's clear how the proof will succeed.

I can see how in terms of manipulating symbols in a mechanical way I am arriving at a proof. That's fine. But I am disturbed by the "meaning". In particular, how can I have false = true in the middle of a proof?

It seems like I am making some kind of argument with contradictions, but I am not sure what. I feel like I have been blindly following rules and have somehow arrived at a point where I am typing nonsense.

What am I doing above?

I hope the question is clear.

Answer 1

Generally, when you do a case analysis in a theorem prover, a lot of the cases boil down to "cannot happen". For example, if you are proving some fact about the integers, you may need to do a case analysis of whether the integer i is positive, zero, or negative. But there may be other hypotheses lying around in your context, or perhaps some part of your goal, that is contradictory with one of the cases. You may know from a previous assertion, for example, that i can never be negative.

However Coq is not that smart. So you still have to go through the mechanics of actually showing that the two contradictory hypotheses can be glued together into a proof of absurdity and hence a proof of your theorem.

Think about it like in a computer program:

switch (k) {
  case X:
    /* do stuff */
    break;
  case Y:
    /* do other stuff */
    break;
  default:
    assert(false, "can't ever happen");
}

The false = true goal is the "can't ever happen". But you can't just assert your way out in Coq. You actually have to put down a proof term.

So above, you have to prove the absurd goal false = true. And the only thing you have to work with is the hyothesis H: andb false c = true. A moment's thought will show you that actually this is an absurd hypothesis (because andb false y reduces to false for any y and hence cannot possibly be true). So you bang on the goal with the only thing at your disposal (namely H) and your new goal is false = andb false c.

So you apply an absurd hypothesis trying to achive an absurd goal. And lo and behold you end up with something you can actually show by reflexivity. Qed.

UPDATE Formally, here's what's going on.

Recall that every inductive definition in Coq comes with an induction principle. Here are the types of the induction principles for equality and the False proposition (as opposed to the term false of type bool):

Check eq_ind.
eq_ind
  : forall (A : Type) (x : A) (P : A -> Prop),
    P x -> forall y : A, x = y -> P y
Check False_ind.
False_ind
 : forall P : Prop, False -> P

That induction principle for False says that if you give me a proof of False, I can give you a proof of any proposition P.

The induction principle for eq is more complicated. Let's consider it confined to bool. And specifically to false. It says:

Check eq_ind false.
eq_ind false
 : forall P : bool -> Prop, P false -> forall y : bool, false = y -> P y

So if you start with some proposition P(b) that depends on a boolean b, and you have a proof of P(false), then for any other boolean y that is equal to false, you have a proof of P(y).

This doesn't sound terribly exiciting, but we can apply it to any proposition P that we want. And we want a particularly nasty one.

Check eq_ind false (fun b : bool => if b then False else True).
eq_ind false (fun b : bool => if b then False else True)
 : (fun b : bool => if b then False else True) false ->
   forall y : bool,
   false = y -> (fun b : bool => if b then False else True) y

Simplifying a bit, what this says is True -> forall y : bool, false = y -> (if y then False else True).

So this wants a proof of True and then some boolean y that we get to pick. So let's do that.

Check eq_ind false (fun b : bool => if b then False else True) I true.
eq_ind false (fun b : bool => if b then False else True) I true
 : false = true -> (fun b : bool => if b then False else True) true

And here we are: false = true -> False.

Combining with what we know about the induction principle for False, we have: if you give me a proof of false = true, I can prove any proposition.

So back to andb_true_elim1. We have a hypothesis H that is false = true. And we want to prove some kind of goal. As I've shown above, there exists a proof term that turns proofs of false = true into proofs of anything you want. So in particular H is a proof of false = true, so you can now prove any goal you want.

The tactics are basically machinery that builds the proof term.

Answer 2

true = false is a statement equating two different boolean values. Since those values are different this statement is clearly not provable (in the empty context).

Considering your proof: you arrive at the stage where the goal is false = true, so clearly you won't be able to prove it... but the thing is that your context (assumptions) are also contradictory. This often happens for instance when you do case-analysis and one of the cases is contradictory with your other assumptions.

Answer 3

I realize this is old, but I want to clarify some of the intuition behind Lambdageek's answer (in case someone finds this)

I noticed that the key point seems to be that we define a function F:bool->Prop with different values at each point (ie. true => True and false => False). However it can easily be shown from the induction principle for equality eq_ind the intuitive idea (this is in fact the "Leibniz" way of defining equality) that

forall P:bool -> Prop, forall x,y:bool, (x = y) -> (P x) -> (P y),

But this would mean that from true=false and I:True, we can conclude False.

Another fundamental property we are using here is the ability to define F, which is given by the recursion principle for bool, bool_rect:

forall P:bool -> Type, P true -> P false -> (forall b:bool, P b)

by choosing P := (fun b:bool => Prop), then we get

(bool_rect P) : Prop -> Prop -> (bool -> Prop),

where we input True and False to get our function F.

If we put this all together, we would get

(eq_ind true (bool_rect (fun b => Prop) True False) I false) : true = false -> False

It is also worth pointing out that Coq takes induction/recursion principles like eq_ind or bool_rect as axioms that define the identity and boolean types.

Answer 4

The normal, human, way of proving this is to say that since the hypothesis is not matched in this case, we do not need to prove the sequel. And in Coq, there is a way for expressing that. This is through a tactic named inversion.

Here is an example:

Theorem absurd_implies_absurd : 
  true = false -> 1 = 2.
Proof.
  intros H.
  inversion H.
  Qed.

The first step let H be the hypothesis true = false, and therefore the goal to prove is 1 = 2.

The inversion H step will automatically prove the goal! Exactly what we wanted, magic!

To understand this magic, we turn to the documentation of what inversion means.

To a beginner (like me), the official documentation for inversion is terse and cryptic to read, here is a much better explanation of it. Search for the keyword inversion on the page and you will find this:

If c and d are different constructors, then the hypothesis H is contradictory. That is, a false assumption has crept into the context, and this means that any goal whatsoever is provable! In this case, inversion H marks the current goal as completed and pops it off the goal stack.

This expresses exactly what we wanted. The only issue is that this is ahead of the book's plan. Of course, rewriting true to false will work. The issue is not that it doesn't work, the issue is that it is just not what we wanted.