Membership in Goal

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 from 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.

Design Decision

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 :

• $\cdots~\in~\cdots$

For examples :

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

In the latter case, the reasoner won't try to prove that x belongs to A and y belongs to B, but that the mapplet belong to the Cartesian product.

Hypotheses

Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic recovers two 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\}=/\subset/\subseteq\cdots$
   • $\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=/\subset/\subseteq\cdots$
   • $f\ovl\left\{\cdots, x, \cdots\right\}=/\subset/\subseteq\cdots$
2. the ones denoting inclusion (all but the ones matching the description of the first point) :
   • $\cdots\subset\cdots$
   • $\cdots\subseteq\cdots$
   • $\cdots=\cdots$

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 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$
   • $f=g\bunion h\quad\mid\quad \varphi(f)=g\bunion k\bunion h\bunion l$
   • $f=i\ovl j\quad\mid\quad\varphi(f)=g\ovl h\ovl i\ovl j$
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$
   • $\psi(f)=g\binter h\binter k\binter l\quad\mid\quad f=g\binter k$
3. By keeping the notation $\psi(f)\subseteq f\subseteq\varphi(f)$ we also deduce that :
   • $\psi(A)\domres\psi(f)\subseteq\varphi(A)\domres\varphi(f)$
   • $\psi(f)\ranres\psi(A)\subseteq\varphi(f)\ranres\varphi(A)$
   • $\varphi(A)\domsub\psi(f)\subseteq\psi(A)\domres\varphi(f)$
   • $\psi(f)\ransub\varphi(A)\subseteq\varphi(f)\ransub\psi(A)$
   • $\psi(f)\setminus\varphi(g)\subseteq\varphi(f)\setminus\psi(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$

By using these inclusions it tries to find a path among the recovered hypotheses. Every one of those should only be used once, avoiding possible infinite loop $\left(A\subseteq B,\quad B\subseteq A\right)$. Among all paths that lead to discharge the sequent, the tactic give the first it finds.

Reasoner

This part describe how the reasoner MembershipGoal works.

Goal

First, it checks that the goal matches the description made in the part tactic : $x\in S$. Thus, we record the member x as well as the set S

Input

Then, it checks that the input is a hypothesesReasonerInput (an input with an array of predicates). Every given predicates must be contained in the sequent. Only one must be related to the goal's member so that there are no ambiguity. All the other ones must denote inclusion.

Find a path

With the same reasoning as for the tactic, we try to find a path leading to discharge the goal.

Trusted Base

At that point, the reasoner performs the same jobs as the tactic which is quite complicated. That poses one problem : it is hard to proof the reasoner is safe (only doing what it was meant to, not discharging sequent that cannot be proofed). Because reasoners are in the trusted base, we should be absolutely sure of what they perform. How to validate the found path ?

As we know, the reasoner condense several inferences rules in only one proof rule. To validate the found path, we have to validate every single inference rule. To achieve it, we use the class created in that purpose : Rules. Each rules contain one predicate and an array of rules (its antecedents). When the path is searched, the rule corresponding is created. When the path is found, we test if the predicate of the rule is equal to the goal. If not, it means the path found was incorrect, so the reasoner fails, else the sequent is discharged.

Example of rules :

$name\;of\;the\;rule\quad\frac{predicate\;of\;first\;antecedent\cdots predicate\;of\;last\;antecedent}{consequent\;of\;that\;rule}\left[parameters\right]$

$Hypothesis\quad\frac{}{predicate}\left[predicate\right]$

$IncludBunion\quad\frac{A\bunion B\bunion C\bunion D\subseteq Z}{B\bunion C\subseteq Z}\left[B,~C\right]$

$Composition\quad\frac{x\in A,~A\subseteq B}{x\in B}\left[~\right]$

Implementation

This section explain how the tactic has bee implemented.

Positions

As it was said, we may sometimes need the position. It is represented by an array of integer. Here are the possible values the array contains (atomic positions) :

• kdom : it corresponds to the domain.
  • $\left[A\cprod B\right]_{pos\;=\;kdom} = A$
  • $\left[x\mapsto y\right]_{pos\;=\;kdom} = x$
  • $\left[g\right]_{pos\;=\;kdom} = dom(g)$
• kran : it corresponds to the domain.
  • $\left[A\cprod B\right]_{pos\;=\;kran} = B$
  • $\left[x\mapsto y\right]_{pos\;=\;kran} = y$
  • $\left[g\right]_{pos\;=\;kran} = ran(g)$
• converse : it corresponds to the child of an inverse
  • $\left[f^{-1}\right]_{pos\;=\;converse}=f$
  • $\left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A$

For example, the following expressions at the given positions are equivalent.

$\left[ran(dom(g))\right]_{pos\;=\;\left[\right]} = \left[dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[g\right]_{pos\;=\;\left[kdom,\; kran\right]}$

Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :

• $ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}$
• $dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}$
• $\left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}$

Goal

A pair (expression ; position) $\left(exp\mapsto pos\right)$ is said to be contained in the goal if and only if exp is contained in the goal, and if the position matched of exp in the goal is equal to pos. For examples, let's see the annexe

Hypotheses

As explained in the design decision part, there are two kinds of hypotheses which are recovered. But when hypotheses related to the left member of the goal $\left(x\in S\right)$ are stored, the position of x is also record. Then, if there is an hypothesis such as $\left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A$, then this hypothesis is mapped to the positions $\left\{\left[kdom,~kran\right],~\left[kran\right]\right\}$.

Find a path

Let's consider that following sequent : $x\in B,\quad dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\},\quad dom(p\ovl m)\subset g,\quad ran(g\bunion h)\bunion B\subseteq A\quad\vdash\quad x\in A$.

1. From the goal we get two informations : the member which is x as well as the set we try to prove it belongs to which is A.
2. By knowing x we recover hypothesis giving informations about it. In our study case, from the hypothesis $dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\}$ we infer that x belong to $\left(dom(m\setminus n)\binter f\right)$ at those possible positions $\left[\;\left[kran\right],~\left[kdom\right]\;\right]$
   • Tactic : record all these informations $\left\{x\in B\mapsto B\mapsto\left[\;\right]\;,\;\left(dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\}\right)\mapsto\left(dom(m\setminus n)\binter f\right)\mapsto\left[\;\left[kran\right],\;\left[kdom\right]\;\right]\right\}$
   • Reasoner : We consider that the tactic will found the most complicated path. For each positions, we make the associated rule, which give in our example $\left\{dom(m\setminus n)\binter f\;\mapsto\;\left[kdom\right]\;\mapsto\;x\in dom(dom(m\setminus n)\binter f),~~~dom(m\setminus n)\binter f\;\mapsto\;\left[kran\right]\;\mapsto\;x\in ran(dom(m\setminus n)\binter f)\right\}$.
3. Now, that we have a set to start the search of a path $\left(dom(m\setminus n)\binter f\right)$, we get all the expression containing it : $\left\{\;dom(m\setminus n)\binter f,~dom(m\setminus n),~ dom(m),~f\;\right\}$. As we don't want to have expression such as dom(...), we modify the position.
   • Tactic : Here, there are only the mapping between the positions and the expression : $\left\{\;dom(m\setminus n)\binter f\;\mapsto\;\left[kran\right],~~~f\;\mapsto\;\left[kran\right],~~~m\;\mapsto\;\left[kdom,\;kran\right],~~~m\setminus n\;\mapsto\;\left[kdom,\;kran\right]\;\right\}$
   • Reasoner : we generate the rule corresponding to the computed sets : $\left\{~\cdots~m\;\mapsto\;\left[kdom,\;kran\right]\;\mapsto\;x\in ran(dom(m))~\cdots~\right\}$
4. We test if one of these pair is contained in the goal. If so, we move to the step 5. But it clearly appears that it is not the case. So, we try to find hypotheses among the one denoting inclusion which are related to that pair. We clearly see that the expression $dom(m)\subseteq dom(p\ovl m)$. Actually, we search every expressions containing m using that mapping $m\;\mapsto\;\left[kdom,\;kran\right]$. From $dom(p\ovl m)$ we can say that only the domain of m is contained in it. Then it ensures this position is part of the position of m in which x belongs to. If so we remove that position and obtain a new mapping $g\;\mapsto\;\left[kran\right]$ (more details here) and we step back to 3 with that new pair.
   • Reasoner : the rule corresponding is generated $g\;\mapsto\;\left[kran\right]\;\mapsto\;x\in ran(g)$
5. We find a path, the works is done.
   • Tactic : If a path has been found, then we call the reasoner with all the used predicates as input.
   • Reasoner :At the end, we check that the generated rule is equal to the goal. If so, the sequent is discharged. Else, a failure is returned.

We see that the tactic may not find the most simple path to discharge the sequent. Moreover, there are some cases where the tactic is able to find a path but the reasoner is unable to prove it due to a weakness in the rules (see all the untreated cases). Example :

$x\in dom(f\bunion g)\binter A,~A\subseteq B,~dom(f)\bunion dom(g)\subseteq B~\vdash~x\in B$

Depending on whether the tactic returns $\left\{x\in dom(f\bunion g)\binter A,~dom(f)\bunion dom(g)\subseteq B\right\}$ or $\left\{x\in dom(f\bunion g)\binter A,~A\subseteq B\right\}$, the reasoner will fail or succeed. To prevent such hazardous behavior, re-writing should be proceeded.

Annexe

Examples. All the following positions are contained in this one $\left[kdom,\;kdom,\;kran\right]$ $\left(x\in ran(dom(dom(g)))\right)$

Predicate	Position of g matched	Inferred predicate	Position in h
$g\subseteq h$	$\left[\;\right]$	$x\in ran(dom(dom(h)))$	$\left[kdom,\;kdom,\;kran\right]$
$dom(g)\subseteq h$	$\left[kdom\right]$	$x\in ran(dom(h))$	$\left[kdom,\;kran\right]$
$dom(dom(g))\subseteq h$	$\left[kdom,\;kdom\right]$	$x\in ran(h)$	$\left[kran\right]$
$ran(dom(dom(g)))\subseteq h$	$\left[kdom,\;kdom,\;kran\right]$	$x\in h$	$\left[~\right]$
$g^{-1}\subseteq h$	$\left[conv\right]$	$x\in ran(dom(ran(h)))$	$\left[kran,\;kdom,\;kran\right]$
$dom(g)^{-1}\subseteq h$	$\left[kdom,\;conv\right]$	$x\in ran(ran(h))$	$\left[kran,\;kran\right]$
$dom(dom(g))^{-1}\subseteq h$	$\left[kdom,\;kdom,\;conv\right]$	$x\in dom(h)$	$\left[kdom\right]$
$ran(dom(dom(g)))^{-1}\subseteq h$	$\left[kdom,\;kdom,\;kran,\;conv\right]$	$x\in h^{-1}$	$\left[conv\right]$

In the case a converse appears at the end of the position of g matched, it is removed, then, we test if the position is part of the position. If so, it is removed and converse is added at the beginning of the array (which is automatically normalized).

Untreated cases

Some cases are not treated. Further enhancement may be provided for some.

• $x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B$
• $x\in f\otimes g,\quad f\subseteq A\cprod B,\quad g\subseteq C\cprod D\quad\vdash\quad x\in (A\cprod C)\cprod(B\cprod D)$ as well as all the possibles re-writing.
• $x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g$
• $x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D$
• $x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B$
• $x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)$
• $x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)$
• $x\in dom(A\domres f)\quad\vdash\quad x\in dom(f)\cap A$
• $x\in ran(f\ranres A)\quad\vdash\quad x\in ran(f)\cap A$
• $x\in dom(f\bunion g)\quad\vdash\quad x\in dom(f)\bunion dom(g)$
• $x\in dom(f)\bunion dom(g)\quad\vdash\quad x\in dom(f\bunion g)$
• $x\in dom(f\binter g)\quad\vdash\quad x\in dom(f)\binter dom(g)$
• $x\in dom(f)\binter dom(g)\quad\vdash\quad x\in dom(f\binter g)$
• $x\in ran(f\bunion g)\quad\vdash\quad x\in ran(f)\bunion ran(g)$
• $x\in ran(f)\bunion ran(g)\quad\vdash\quad x\in ran(f\bunion g)$
• $x\in ran(f\binter g)\quad\vdash\quad x\in ran(f)\binter ran(g)$
• $x\in ran(f)\binter ran(g)\quad\vdash\quad x\in ran(f\binter g)$
• $x\in (f\bunion g)^{-1}\quad\vdash\quad x\in f^{-1}\bunion g^{-1}$
• $x\in f^{-1}\bunion g^{-1}\quad\vdash\quad x\in (f\bunion g)^{-1}$
• $x\in (f\binter g)^{-1}\quad\vdash\quad x\in f^{-1}\binter g^{-1}$
• $x\in f^{-1}\binter g^{-1}\quad\vdash\quad x\in (f\binter g)^{-1}$

  the last 12 examples fails because the Rules have some weakness. This show that some re-writing should be performed.

• $x\in A\bunion dom(f\binter g),A\bunion dom(f)\subseteq B\quad\vdash\quad x\in B$
• $x\in A\binter dom(f),A\binter dom(f\bunion g)\subseteq B\quad\vdash\quad x\in B$

  the reason for the failure of the two last examples is that when union or intersection are compared, we should take all the expression containing each member, but we don't.

• $x\in A\cprod dom(B\cprod C)\quad\vdash\quad x\in A\cprod B$

  it fails because when we get equivalent expression of the Cartesian product, we don't go further enough.

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