Search code examples
uniqueisabelle

Proving intuitive statements about THE in Isabelle


I would like to prove something like this lemma in Isabelle

lemma assumes "y = (THE x. P x)" shows "P (THE x. P x)"

I imagine that the assumption implies that THE x. P x exists and is well-defined. So this lemma ought to be true too

lemma assumes "y = (THE x. P x)" shows "∃! x. P x"

I'm not sure how to prove this because I've looked through all the theorems that turn up when I type "name: the" into the query box in Isabelle and they don't seem useful. I can't find the definition of THE either and I am not sure how to define it although I have an intuitive idea of what it means. I tried something like this although I am sure this is wrong

"(∃!x. P x) ⟹ THE x. P x = (SOME x. P x)"

and maybe even useless because I don't know how to define SOME either!


Solution

  • Unfortunately, the assumption does not imply that THE x. P x ‘exists’, at least not in a sense that you would find satisfying. As HOL is a total logic, there is no notion of ‘well-definedness’ in the logic.

    If you write THE x. P x when there is no unique x that satisfies P, then THE x. P x is still a value that ‘exists’ in HOL, but one that you cannot prove anything meaningful about (much like the undefined constant) and certainly not one for which P holds. The same is true for SOME, which is basically the same as THE with the difference that for THE, there has to be a unique witness for the property and for SOME uniqueness is not required.

    The typical approach for showing something about SOME x. P x is that you first show that a witness exists (i.e. ∃x. P x) and then you plug that into a rule like someI_ex which then tells you that P (SOME x. P x) indeed holds.

    It's the same for THE, except that there you have to show that there is exactly one witness – which is what the ∃! means (cf. the theorem Ex1_def). Showing this unique existence can be done e.g. with the rules ex_ex1I or ex1I. Then you can plug that fact into theI' and the1_equality to get the results you want.

    By the way, the constant for SOME is called Eps (as in ‘Hilbert's ε operator’) and the others are The and Ex1. If you type e.g. term Eps, you can ctrl-click on the Eps and it takes you to its definition (or, in case of Eps and The rather their axiomatisations).

    There's also a LEAST combinator for natural numbers that is very similar to SOME and can be quite useful sometimes (it's called ‘Least’ and the lemmas are LeastI_ex and Least_le).

    Another side note: This idea that just because you can write down a term, it is not necessarily ‘well-defined’ in an intuitive sense is very common in Isabelle: you can divide by zero, you can write down the derivative of a non-differentiable function, the measure of a non-measurable set, the integral of a non-integrable function etc. You then get some kind of dummy value (e.g. 0 for division by zero or something completely absurd like THE x. False), but most of the theorems that talk about actual properties of derivatives, integrals, etc. do explicitly require that the thing is actually well-defined.