D45 Prover Enhancement

Objective

This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
This reasoner discharges sequent whose goal denotes a membership which can be inferred with hypotheses. Here an basic example of what it discharges :
$H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U$

Analysis

Such sequent are proved by PP and ML. But, these provers have both drawbacks :

• All the visible are added as needed hypotheses, which is most of the time not the case.
• They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
• If there are too many hypotheses, or if the expression of the $x$ is too complicated, they may not prove it.

This is particularly true when in the list of inclusion expressions of each side of the relation are not equal. For example : $H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq U\quad\vdash a\in U$

Such a reasoner contributes to prove more Proof Obligations automatically, faster and with fewer needed hypotheses which makes proof rule more legible and proof replay less sensitive to modifications.

Tactic

This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.

Goal

The tactic (as the reasoner) should works only on goals such as :

• $<goal>\quad:\quad expresion\quad\in\quad<set>$
• $<member>\quad:\quad expresion\quad\mid\quad FA$
• $<set>\quad:\quad expresion\otimes expresion\quad\mid\quad expresion\parallel expresion\quad\mid\quad <union>\quad\left[\cup <union>\right]$
• $<union>\quad:\quad<cprod>\quad\left[\cprod<cprod>\right]$
• $<cprod>\quad:\quad\left(<set>\right)\quad\mid\quad expresion$

For example those examples matches with the definition here above :

• $f(x)\in g\otimes h$
• $x\in A\cprod\left(B\cup C\right)$

Every other goals denoting a membership should be re-

Hypotheses

The hard part is to find the hypotheses leading to discharge the sequent. To do so, the tactic recovers three kinds of hypotheses :

1. the ones related to the left member of the goal $\left( x\in S\right)$ (this is the start point):
   • $x\in \cdots$
   • $\cdots\mapsto x\mapsto\cdots\in\cdots$
   • $\left\{\cdots, x,\cdots\right\}\subseteq\cdots$
2. the ones denoting inclusion (all but the ones matching the description of the first point) :
   • $\cdots\subset\cdots$
   • $\cdots\subseteq\cdots$
3. the one from which we can infer inclusion :
   • $f\in A\;op\;B \quad\vdash\quad f\subseteq A\cprod B\quad\bigl($ where $op$ is one of :$\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)$
   • $f\subseteq A\cprod B \quad\vdash\quad f\otimes f\subseteq A\cprod\left(B\cprod B\right)$

Then, it will search a link between those hypotheses so that the sequent can be discharged.

Find a path

Now that we recovered all the hypotheses that could be useful for the reasoner, it just remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. $f$ always represent an expression (may be a domain, a range, etc.).

1. The following sequent is provable because $f\subseteq \varphi (f)$.
   • $x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g$
   • $\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f$
2. The following sequent is provable because $\psi (f)\subseteq f$.
   • $x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g$
   • $\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f$
3. We can generalized the first two points. This is the Russian dolls system. We can easily prove a sequent with multiple inclusions by going from hypothesis to hypothesis.
   • $x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g$
4. For some relations, positions are needed to be known to continue to find hypotheses, but it is not always necessary.
   • $x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A$
   • $x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A$
   • $x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B$
   • $x\in f,\quad f\otimes g\subseteq A\cprod\left(B\cprod C\right)\quad\vdash\quad x\in A\cprod B$
   • $x\in f,\quad f\parallel g\subseteq \left(A\cprod C\right)\cprod\left(B\cprod D\right)\quad\vdash\quad x\in A\cprod B$
5. Those rewrites can be useful when the Russian dolls system does not succeed.
   • $dom(f)\cup dom(g) = dom(f\ovl g)$
   • $ran(f)\cup ran(g)\subseteq ran(f\ovl g)$
   • $dom(A\domres f) = dom(f)\cap A$
   • $ran(f\ranres A) = ran(f)\cap A$
   • $A\subseteq X\quad\land\quad B\subseteq Y\quad\vdash\quad A\cprod B\subseteq X\cprod Y$

   Be careful ! The previous one may appear as reciprocal, but it is not the case at all (just replace the set $B$ by $\varnothing$).

   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\subseteq A\cprod B$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f^{-1}\subseteq B\cprod A$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f[A]\subseteq B$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres prj1 = prj1\ranres f\subseteq A\cprod B\cprod A$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres prj2 = prj2\ranres f\subseteq A\cprod B\cprod B$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres id = id\ranres f\subseteq (A\cprod B)\cprod(A\cprod B)$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in B\;op_2\;C\;\lor\; g\subseteq B\cprod C \quad\vdash\quad f;g = g\circ f \subseteq A\cprod C$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in A\;op_2\;C\;\lor\; g\subseteq A\cprod C \quad\vdash\quad f\otimes g \subseteq A\cprod (B\cprod C)$
   • $f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in C\;op_2\;D\;\lor\; g\subseteq C\cprod D \quad\vdash\quad f\parallel g \subseteq (A\cprod C)\cprod (B\cprod D)$

   $\bigl($ where $op_1$ and $op_2$ are ones of :$\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)$

By using these inclusion and rewrites, it tries to find a path among the recovered hypotheses. Every hypotheses denoting an inclusion should be used only once. Every hypotheses from which new hypothesis can be inferred could be used as many times as wanted. Among all paths that lead to discharge the sequent, the tactic give the first it finds. Moreover, so that the reasoner does not do the same work as the tactic of writing new hypothesis, it gives all needed hypotheses and added hypotheses in the input.

Reasoner

This part describes how the reasoner works.

Goal

The goal must match the same kind of goal as describes in the tactic part.

Input

Because we do not want to do the job of re-writing, every added hypotheses used to discharge the sequent should be contained in the input (the reasoner must extend HypothesesReasoner) as well as hypotheses used to perform the re-writing and hypotheses used to discharge the sequent. Thus we get those obligations :

• Every added hypotheses must be re-writable with hypotheses contained in the sequent and in the input.
• Every added hypotheses should be used to discharge the sequent.
• Hypotheses used to perform re-writing could be also used to discharge a sequent and may be used several times to prove that added hypotheses are re-writable.
• Hypotheses used to discharge the sequent should be used only once in the path (no loop allowed).
• It checks that with all these hypotheses can actually discharge the sequent

If all those tests pass, then the sequent is discharged. The added hypotheses are set as AddedHyps, and all the other hypotheses of the input are set as NeededHps.