Playground Documentation Challenges Full Docs

notation("hint")

Facts of a relation as hints, through named theorems

Overview

notation("hint" | Rewrite, RewriteBack, Reflexive) lets a fact R(a, b) -> v of a relation R be a hint: a proof rewrites a to b by it, as if it called Rewrite[| F]. The relation and its value are read from the theorems themselves. Like every notation it states nothing: every step it allows is a call of one of the theorems it names, and the certificate says so. The other steps of a proof are named the same way — notation("apply" | A∀Apply), notation("generalize" | generalize), notation("deduce" | deduce), notation("witness" | witness), notation("obtain" | obtain, …) — see steps read through theorems.

notation("hint" | rewriteLabel)notation("hint" | rewriteLabel, rewriteBackLabel, reflexiveLabel)
rewriteLabel
Required: a -> b under one if(R(a, b) -> v), over the atoms a, b only. A fact R(l, r) -> v then rewrites l to r.
rewriteBackLabel
Optional: b -> a under the same condition. Without it a fact rewrites one way only.
reflexiveLabel
Optional: R(x, x) -> v over one atom. With it R(t, t) reduces to v by itself.

Basic examples

A relation of its own

▶ Run

Details

The three theorems are the axioms Reflexive, Rewrite and the lemma RewriteBack a file writes for its equality (Command Reducibility); here they are named: a fact, a quantified fact and a theorem whose conclusion is R(l, r) -> v rewrite by Rewrite and RewriteBack, a bracket without a hint uses the visible facts of the relation, R(t, t) is Reflexive. The library declares its equality this way: notation("hint" | A=Rewrite, L=RewriteBack, A=Reflexive) in logic/equality.fl, and equivalence the same way: notation("hint" | L⇔Rewrite, L⇔Back, L⇔Reflexive) in logic/propositional.fl, so a fact P ⇔ Q -> ✔ rewrites P to Q and back. Nothing about = or ⇔ is built into the language beyond what the theorems say.

Each theorem must hold one statement and be proved without locks or rules of its own, over atoms of one type; the theorems must be about one relation and one value. A theorem of another form is an error that names it.

One way only

Without RewriteBack the fact rewrites left to right only.

▶ Run

Expected error: No matching statement found for expression substitution