All Rewrite Rules

From Event-B
Jump to navigationJump to search
CAUTION! Any modification to this page shall be announced on the User mailing list!

This page groups together all the rewrite rules implemented (or planned for implementation) in the Rodin prover. The rules themselves can be found in their respective location (for editing purposes):

Conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_rules

Set Rewrite Rules

Rules that are marked with a * in the first column are implemented in the latest version of Rodin. Rules without a * are planned to be implemented in future versions. Other conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_Rules.


  Name Rule Side Condition A/M
*
SIMP_SPECIAL_AND_BTRUE
  P \land  \ldots  \land  \btrue  \land  \ldots  \land  Q \;\;\defi\;\;  P \land  \ldots  \land  Q A
*
SIMP_SPECIAL_AND_BFALSE
  P \land  \ldots  \land  \bfalse  \land  \ldots  \land  Q \;\;\defi\;\;  \bfalse A
*
SIMP_MULTI_AND
  P \land  \ldots  \land  Q \land  \ldots  \land  Q \land  \ldots  \land  R \;\;\defi\;\;  P \land  \ldots  \land  Q \land  \ldots  \land  R A
*
SIMP_MULTI_AND_NOT
  P \land  \ldots  \land  Q \land  \ldots  \land  \lnot\, Q \land  \ldots  \land  R \;\;\defi\;\;  \bfalse A
*
SIMP_SPECIAL_OR_BTRUE
  P \lor  \ldots  \lor  \btrue  \lor  \ldots  \lor  Q \;\;\defi\;\;  \btrue A
*
SIMP_SPECIAL_OR_BFALSE
  P \lor  \ldots  \lor  \bfalse  \lor  \ldots  \lor  Q \;\;\defi\;\;  P \lor  \ldots  \lor  Q A
*
SIMP_MULTI_OR
  P \lor  \ldots  \lor  Q \lor  \ldots  \lor  Q \lor  \ldots  \lor  R \;\;\defi\;\;  P \lor  \ldots  \lor  Q \lor  \ldots  \lor  R A
*
SIMP_MULTI_OR_NOT
  P \lor  \ldots  \lor  Q \lor  \ldots  \lor  \lnot\, Q \land  \ldots  \land  R \;\;\defi\;\;  \btrue A
*
SIMP_SPECIAL_IMP_BTRUE_R
  P \limp  \btrue  \;\;\defi\;\;  \btrue A
*
SIMP_SPECIAL_IMP_BTRUE_L
  \btrue  \limp  P \;\;\defi\;\;  P A
*
SIMP_SPECIAL_IMP_BFALSE_R
  P \limp  \bfalse  \;\;\defi\;\;  \lnot\, P A
*
SIMP_SPECIAL_IMP_BFALSE_L
  \bfalse  \limp  P \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_IMP
  P \limp  P \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_IMP_NOT_L
\lnot P\limp P\;\;\defi\;\; P A
*
SIMP_MULTI_IMP_NOT_R
P\limp\lnot P\;\;\defi\;\;\lnot P A
*
SIMP_MULTI_IMP_AND
  P \land  \ldots  \land  Q \land  \ldots  \land  R \limp  Q \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_IMP_AND_NOT_R
  P \land  \ldots  \land  Q \land  \ldots  \land  R \limp  \lnot\, Q \;\;\defi\;\;  \lnot\,(P \land  \ldots  \land  Q \land  \ldots  \land  R) A
*
SIMP_MULTI_IMP_AND_NOT_L
  P \land  \ldots  \land  \lnot\, Q \land  \ldots  \land  R \limp  Q \;\;\defi\;\;  \lnot\,(P \land  \ldots  \land  \lnot\, Q \land  \ldots  \land  R) A
*
SIMP_MULTI_EQV
  P \leqv  P \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_EQV_NOT
  P \leqv  \lnot\, P \;\;\defi\;\;  \bfalse A
*
SIMP_SPECIAL_NOT_BTRUE
  \lnot\, \btrue  \;\;\defi\;\;  \bfalse A
*
SIMP_SPECIAL_NOT_BFALSE
  \lnot\, \bfalse  \;\;\defi\;\;  \btrue A
*
SIMP_NOT_NOT
  \lnot\, \lnot\, P \;\;\defi\;\;  P AM
*
SIMP_NOTEQUAL
  E \neq  F \;\;\defi\;\;  \lnot\, E = F A
*
SIMP_NOTIN
  E \notin  F \;\;\defi\;\;  \lnot\, E \in  F A
*
SIMP_NOTSUBSET
  E  \not\subset  F \;\;\defi\;\;  \lnot\, E  \subset  F A
*
SIMP_NOTSUBSETEQ
  E  \not\subseteq  F \;\;\defi\;\;  \lnot\, E \subseteq  F A
*
SIMP_NOT_LE
  \lnot\, a \leq  b \;\;\defi\;\;  a > b A
*
SIMP_NOT_GE
  \lnot\, a \geq  b \;\;\defi\;\;  a < b A
*
SIMP_NOT_LT
  \lnot\, a < b \;\;\defi\;\;  a \geq  b A
*
SIMP_NOT_GT
  \lnot\, a > b \;\;\defi\;\;  a \leq  b A
*
SIMP_SPECIAL_NOT_EQUAL_FALSE_R
  \lnot\, (E = \False ) \;\;\defi\;\;  (E = \True ) A
*
SIMP_SPECIAL_NOT_EQUAL_FALSE_L
  \lnot\, (\False  = E) \;\;\defi\;\;  (\True  = E) A
*
SIMP_SPECIAL_NOT_EQUAL_TRUE_R
  \lnot\, (E = \True ) \;\;\defi\;\;  (E = \False ) A
*
SIMP_SPECIAL_NOT_EQUAL_TRUE_L
  \lnot\, (\True  = E) \;\;\defi\;\;  (\False  = E) A
*
SIMP_FORALL_AND
  \forall x \qdot  P \land  Q \;\;\defi\;\;  (\forall x \qdot  P) \land  (\forall x \qdot  Q) A
*
SIMP_EXISTS_OR
  \exists x \qdot  P \lor  Q \;\;\defi\;\;  (\exists x \qdot  P) \lor  (\exists x \qdot  Q) A
*
SIMP_EXISTS_IMP
\exists x\qdot P\limp Q\;\;\defi\;\;(\forall x\qdot P)\limp(\exists x\qdot Q) A
*
SIMP_FORALL
  \forall \ldots ,z,\ldots  \qdot  P(z) \;\;\defi\;\;  \forall z \qdot  P(z) Quantified identifiers other than z do not occur in P A
*
SIMP_EXISTS
  \exists \ldots ,z,\ldots  \qdot  P(z) \;\;\defi\;\;  \exists z \qdot  P(z) Quantified identifiers other than z do not occur in P A
*
SIMP_MULTI_EQUAL
  E = E \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_NOTEQUAL
  E \neq  E \;\;\defi\;\;  \bfalse A
*
SIMP_EQUAL_MAPSTO
  E \mapsto  F = G \mapsto  H \;\;\defi\;\;  E = G \land  F = H A
*
SIMP_EQUAL_SING
  \{ E\}  = \{ F\}  \;\;\defi\;\;  E = F A
*
SIMP_SPECIAL_EQUAL_TRUE
  \True  = \False  \;\;\defi\;\;  \bfalse A
*
SIMP_TYPE_SUBSETEQ
  S \subseteq  \mathit{Ty} \;\;\defi\;\;  \btrue where \mathit{Ty} is a type expression A
*
SIMP_SUBSETEQ_SING
  \{ E\}  \subseteq  S \;\;\defi\;\;  E \in  S where E is a single expression A
*
SIMP_SPECIAL_SUBSETEQ
  \emptyset  \subseteq  S \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_SUBSETEQ
  S \subseteq  S \;\;\defi\;\;  \btrue A
*
SIMP_SUBSETEQ_BUNION
  S \subseteq  A \bunion  \ldots  \bunion  S \bunion  \ldots  \bunion  B \;\;\defi\;\;  \btrue A
*
SIMP_SUBSETEQ_BINTER
  A \binter  \ldots  \binter  S \binter  \ldots  \binter  B \subseteq  S \;\;\defi\;\;  \btrue A
*
DERIV_SUBSETEQ_BUNION
  A \bunion  \ldots  \bunion  B \subseteq  S \;\;\defi\;\;  A \subseteq  S \land  \ldots  \land  B \subseteq  S A
*
DERIV_SUBSETEQ_BINTER
  S \subseteq  A \binter  \ldots  \binter  B \;\;\defi\;\;  S \subseteq  A \land  \ldots  \land  S \subseteq  B A
*
SIMP_SPECIAL_IN
  E \in  \emptyset  \;\;\defi\;\;  \bfalse A
*
SIMP_MULTI_IN
  B \in  \{ A, \ldots , B, \ldots , C\}  \;\;\defi\;\;  \btrue A
*
SIMP_IN_SING
  E \in  \{ F\}  \;\;\defi\;\;  E = F A
*
SIMP_MULTI_SETENUM
  \{ A, \ldots , B, \ldots , B, \ldots , C\}  \;\;\defi\;\;  \{ A, \ldots , B, \ldots , C\} A
*
SIMP_SPECIAL_BINTER
  S \binter  \ldots  \binter  \emptyset  \binter  \ldots  \binter  T \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_BINTER
  S \binter  \ldots  \binter  \mathit{Ty} \binter  \ldots  \binter  T \;\;\defi\;\;  S \binter  \ldots  \binter  T where \mathit{Ty} is a type expression A
*
SIMP_MULTI_BINTER
  S \binter  \ldots  \binter  T \binter  \ldots  \binter  T \binter  \ldots  \binter  U \;\;\defi\;\;  S \binter  \ldots  \binter  T \binter  \ldots  \binter  U A
*
SIMP_MULTI_EQUAL_BINTER
  S \binter  \ldots  \binter  T \binter  \ldots  \binter  U = T \;\;\defi\;\;  T \subseteq  S \binter  \ldots  \binter  U A
*
SIMP_SPECIAL_BUNION
  S \bunion  \ldots  \bunion  \emptyset  \bunion  \ldots  \bunion  T \;\;\defi\;\;  S \bunion  \ldots  \bunion  T A
*
SIMP_TYPE_BUNION
  S \bunion  \ldots  \bunion  \mathit{Ty} \bunion  \ldots  \bunion  T \;\;\defi\;\;  \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_MULTI_BUNION
  S \bunion  \ldots  \bunion T \bunion  \ldots  \bunion T \bunion \ldots  \bunion  U \;\;\defi\;\;  S \bunion  \ldots  \bunion  T \bunion  \ldots  \bunion  U A
*
SIMP_MULTI_EQUAL_BUNION
  S \bunion  \ldots  \bunion  T \bunion  \ldots  \bunion  U = T \;\;\defi\;\;  S \bunion  \ldots  \bunion  U \subseteq  T A
*
SIMP_MULTI_SETMINUS
  S \setminus S \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_SETMINUS_R
  S \setminus \emptyset  \;\;\defi\;\;  S A
*
SIMP_SPECIAL_SETMINUS_L
  \emptyset  \setminus S \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_SETMINUS
  S \setminus \mathit{Ty} \;\;\defi\;\;  \emptyset where \mathit{Ty} is a type expression A
*
SIMP_TYPE_SETMINUS_SETMINUS
 \mathit{Ty} \setminus (\mathit{Ty} \setminus S) \;\;\defi\;\;  S where \mathit{Ty} is a type expression A
*
SIMP_KUNION_POW
  \union (\pow (S)) \;\;\defi\;\;  S A
*
SIMP_KUNION_POW1
  \union (\pown (S)) \;\;\defi\;\;  S A
*
SIMP_SPECIAL_KUNION
  \union (\{ \emptyset \} ) \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_QUNION
  \Union  x\qdot  \bfalse  \mid  E \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_KINTER
  \inter (\{ \emptyset \} ) \;\;\defi\;\;  \emptyset A
*
SIMP_KINTER_POW
  \inter (\pow (S)) \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_POW
  \pow (\emptyset ) \;\;\defi\;\;  \{ \emptyset \} A
*
SIMP_SPECIAL_POW1
  \pown (\emptyset ) \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_CPROD_R
  S \cprod  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_CPROD_L
  \emptyset  \cprod  S \;\;\defi\;\;  \emptyset A
SIMP_COMPSET_EQUAL
  \{ x, y \qdot x = E(y) \land P(y) \mid F(x, y) \}  \;\;\defi\;\;  \{ y \qdot P(y) \mid F(E(y), y) \} where x non free in E and non free in P A
*
SIMP_COMPSET_IN
  \{  x \qdot  x \in  S \mid  x \}  \;\;\defi\;\;  S where x non free in S A
*
SIMP_COMPSET_SUBSETEQ
  \{  x \qdot  x \subseteq  S \mid  x \}  \;\;\defi\;\;  \pow (S)  where x non free in S A
*
SIMP_SPECIAL_COMPSET_BFALSE
  \{  x \qdot  \bfalse  \mid  x \}  \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_COMPSET_BTRUE
  \{  x \qdot  \btrue  \mid  E \}  \;\;\defi\;\;  \mathit{Ty} where the type of E is \mathit{Ty} and E is a maplet combination of locally-bound, pairwise-distinct bound identifiers A
*
SIMP_SUBSETEQ_COMPSET_L
  \{  x \qdot  P(x) \mid  E(x) \}  \subseteq  S \;\;\defi\;\;  \forall y\qdot  P(y) \limp  E(y) \in  S where y is fresh A
*
SIMP_IN_COMPSET
  F \in  \{  x,y,\ldots \qdot  P(x,y,\ldots) \mid  E(x,y,\ldots) \}  \;\;\defi\;\;  \exists x,y,\ldots \qdot P(x,y,\ldots) \land E(x,y,\ldots) = F where x, y, \ldots are not free in F A
*
SIMP_IN_COMPSET_ONEPOINT
  E \in  \{  x \qdot  P(x) \mid  x \}  \;\;\defi\;\;  P(E) Equivalent to general simplification followed by One Point Rule application with the last conjunct predicate A
SIMP_SUBSETEQ_COMPSET_R
  S \subseteq  \{  x \qdot  P(x) \mid  x \}  \;\;\defi\;\;  \forall y\qdot  y \in  S \limp  P(y) where y non free in S, \{  x \qdot  P(x) \mid  x \} M
*
SIMP_SPECIAL_OVERL
  r \ovl  \ldots  \ovl  \emptyset  \ovl  \ldots  \ovl  s \;\;\defi\;\;  r \ovl  \ldots  \ovl  s A
*
SIMP_SPECIAL_KBOOL_BTRUE
  \bool (\btrue ) \;\;\defi\;\;  \True A
*
SIMP_SPECIAL_KBOOL_BFALSE
  \bool (\bfalse ) \;\;\defi\;\;  \False A
DISTRI_SUBSETEQ_BUNION_SING
  S \bunion  \{ F\}  \subseteq  T \;\;\defi\;\;  S \subseteq  T \land  F \in  T where F is a single expression M
*
DEF_FINITE
  \finite(S) \;\;\defi\;\;  \exists n,f\qdot f\in 1\upto n \tbij S M
*
SIMP_SPECIAL_FINITE
  \finite (\emptyset ) \;\;\defi\;\;  \btrue A
*
SIMP_FINITE_SETENUM
  \finite (\{ a, \ldots , b\} ) \;\;\defi\;\;  \btrue A
*
SIMP_FINITE_BUNION
  \finite (S \bunion  T) \;\;\defi\;\;  \finite (S) \land  \finite (T) A
*
SIMP_FINITE_POW
  \finite (\pow (S)) \;\;\defi\;\;  \finite (S) A
*
DERIV_FINITE_CPROD
  \finite (S \cprod  T) \;\;\defi\;\;  S = \emptyset  \lor  T = \emptyset  \lor  (\finite (S) \land  \finite (T)) A
*
SIMP_FINITE_CONVERSE
  \finite (r^{-1} ) \;\;\defi\;\;  \finite (r) A
*
SIMP_FINITE_UPTO
  \finite (a \upto  b) \;\;\defi\;\;  \btrue A
*
SIMP_FINITE_ID
  \finite (\id) \;\;\defi\;\;  \finite (S) where \id has type \pow(S \cprod S) A
*
SIMP_FINITE_ID_DOMRES
  \finite (E \domres \id) \;\;\defi\;\;  \finite (E) A
*
SIMP_FINITE_PRJ1
  \finite (\prjone) \;\;\defi\;\;  \finite (S \cprod T) where \prjone has type \pow(S \cprod T \cprod S) A
*
SIMP_FINITE_PRJ2
  \finite (\prjtwo) \;\;\defi\;\;  \finite (S \cprod T) where \prjtwo has type \pow(S \cprod T \cprod T) A
*
SIMP_FINITE_PRJ1_DOMRES
  \finite (E \domres \prjone) \;\;\defi\;\;  \finite (E) A
*
SIMP_FINITE_PRJ2_DOMRES
  \finite (E \domres \prjtwo) \;\;\defi\;\;  \finite (E) A
*
SIMP_FINITE_NATURAL
  \finite (\nat ) \;\;\defi\;\;  \bfalse A
*
SIMP_FINITE_NATURAL1
  \finite (\natn ) \;\;\defi\;\;  \bfalse A
*
SIMP_FINITE_INTEGER
  \finite (\intg ) \;\;\defi\;\;  \bfalse A
*
SIMP_FINITE_BOOL
  \finite (\Bool ) \;\;\defi\;\;  \btrue A
*
SIMP_FINITE_LAMBDA
  \finite(\{x\qdot P\mid E\mapsto F\}) \;\;\defi\;\;  \finite(\{x\qdot P\mid E\} ) where E is a maplet combination of bound identifiers and expressions that are not bound by the comprehension set (i.e., E is syntactically injective) and all identifiers bound by the comprehension set that occur in F also occur in E A
*
SIMP_TYPE_IN
  t \in  \mathit{Ty} \;\;\defi\;\;  \btrue where \mathit{Ty} is a type expression A
*
SIMP_SPECIAL_EQV_BTRUE
  P \leqv  \btrue  \;\;\defi\;\;  P A
*
SIMP_SPECIAL_EQV_BFALSE
  P \leqv  \bfalse  \;\;\defi\;\;  \lnot\, P A
*
DEF_SUBSET
  A  \subset  B  \;\;\defi\;\;  A \subseteq B \land \lnot A = B A
*
SIMP_SPECIAL_SUBSET_R
  S  \subset  \emptyset  \;\;\defi\;\;  \bfalse A
*
SIMP_SPECIAL_SUBSET_L
\emptyset\subset S \;\;\defi\;\;  \lnot\; S = \emptyset A
*
SIMP_TYPE_SUBSET_L
  S  \subset  \mathit{Ty} \;\;\defi\;\;  S \neq  \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_MULTI_SUBSET
  S  \subset  S \;\;\defi\;\;  \bfalse A
*
SIMP_EQUAL_CONSTR
  \operatorname{constr} (a_1, \ldots, a_n) = \operatorname{constr} (b_1, \ldots, b_n)  \;\;\defi\;\;  a_1 = b_1 \land \ldots \land  a_n = b_n  where \operatorname{constr} is a datatype constructor A
*
SIMP_EQUAL_CONSTR_DIFF
  \operatorname{constr_1} (\ldots) = \operatorname{constr_2} (\ldots)  \;\;\defi\;\;  \bfalse where \operatorname{constr_1} and \operatorname{constr_2} are different datatype constructors A
*
SIMP_DESTR_CONSTR
  \operatorname{destr} (\operatorname{constr} (a_1, \ldots, a_n))  \;\;\defi\;\;  a_i  where \operatorname{destr} is the datatype destructor for the i-th argument of datatype constructor \operatorname{constr} A
*
DISTRI_AND_OR
  P \land  (Q \lor  R) \;\;\defi\;\;  (P \land  Q) \lor  (P \land  R) M
*
DISTRI_OR_AND
  P \lor  (Q \land  R) \;\;\defi\;\;  (P \lor  Q) \land  (P \lor  R) M
*
DEF_OR
  P \lor  Q \lor  \ldots  \lor  R \;\;\defi\;\;  \lnot\, P \limp  (Q \lor  \ldots  \lor  R) M
*
DERIV_IMP
  P \limp  Q \;\;\defi\;\;  \lnot\, Q \limp  \lnot\, P M
*
DERIV_IMP_IMP
  P \limp  (Q \limp  R) \;\;\defi\;\;  P \land  Q \limp  R M
*
DISTRI_IMP_AND
  P \limp  (Q \land  R) \;\;\defi\;\;  (P \limp  Q) \land  (P \limp  R) M
*
DISTRI_IMP_OR
  (P \lor  Q) \limp  R \;\;\defi\;\;  (P \limp  R) \land  (Q \limp  R) M
*
DEF_EQV
  P \leqv  Q \;\;\defi\;\;  (P \limp  Q) \land  (Q \limp  P) M
*
DISTRI_NOT_AND
  \lnot\,(P \land  Q) \;\;\defi\;\;  \lnot\, P \lor  \lnot\, Q M
*
DISTRI_NOT_OR
  \lnot\,(P \lor  Q) \;\;\defi\;\;  \lnot\, P \land  \lnot\, Q M
*
DERIV_NOT_IMP
  \lnot\,(P \limp  Q) \;\;\defi\;\;  P \land  \lnot\, Q M
*
DERIV_NOT_FORALL
  \lnot\, \forall x \qdot  P \;\;\defi\;\;  \exists x \qdot  \lnot\, P M
*
DERIV_NOT_EXISTS
  \lnot\, \exists x \qdot  P \;\;\defi\;\;  \forall x \qdot  \lnot\, P M
*
DEF_IN_MAPSTO
  E \mapsto  F \in  S \cprod  T \;\;\defi\;\;  E \in  S \land  F \in  T AM
*
DEF_IN_POW
  E \in  \pow (S) \;\;\defi\;\;  E \subseteq  S M
*
DEF_IN_POW1
  E \in  \pown (S) \;\;\defi\;\; E \in  \pow (S) \land S \neq \emptyset M
*
DEF_SUBSETEQ
 S \subseteq T  \;\;\defi\;\;  \forall x \qdot  x \in  S \limp  x \in  T where x is not free in S or T M
*
DEF_IN_BUNION
  E \in  S \bunion  T \;\;\defi\;\;  E \in  S \lor  E \in  T M
*
DEF_IN_BINTER
  E \in  S \binter  T \;\;\defi\;\;  E \in  S \land  E \in  T M
*
DEF_IN_SETMINUS
  E \in  S \setminus T \;\;\defi\;\;  E \in  S \land  \lnot\,(E \in  T) M
*
DEF_IN_SETENUM
  E \in  \{ A, \ldots , B\}  \;\;\defi\;\;  E = A \lor  \ldots  \lor  E = B M
*
DEF_IN_KUNION
  E \in  \union (S) \;\;\defi\;\;  \exists s \qdot  s \in  S \land  E \in  s where s is fresh M
*
DEF_IN_QUNION
  E \in  (\Union x \qdot P(x) \mid T(x)) \;\;\defi\;\;  \exists s \qdot P(s) \land E \in T(s) where s is fresh M
*
DEF_IN_KINTER
  E \in  \inter (S) \;\;\defi\;\;  \forall s \qdot  s \in  S \limp  E \in  s where s is fresh M
*
DEF_IN_QINTER
  E \in  (\Inter x \qdot P(x) \mid T(x)) \;\;\defi\;\;  \forall s \qdot P(s) \limp E \in T(s) where s is fresh M
*
DEF_IN_UPTO
  E \in  a \upto b \;\;\defi\;\; a \leq E \land E \leq b  M
*
DISTRI_BUNION_BINTER
  S \bunion  (T \binter  U) \;\;\defi\;\;  (S \bunion  T) \binter  (S \bunion  U) M
*
DISTRI_BINTER_BUNION
  S \binter  (T \bunion  U) \;\;\defi\;\;  (S \binter  T) \bunion  (S \binter  U) M
DISTRI_BINTER_SETMINUS
  S \binter  (T \setminus U) \;\;\defi\;\;  (S \binter  T) \setminus (S \binter  U) M
DISTRI_SETMINUS_BUNION
  S \setminus (T \bunion  U) \;\;\defi\;\;  S \setminus T \setminus U M
*
DERIV_TYPE_SETMINUS_BINTER
  \mathit{Ty} \setminus (S \binter  T) \;\;\defi\;\;  (\mathit{Ty} \setminus S) \bunion  (\mathit{Ty} \setminus T) where \mathit{Ty} is a type expression M
*
DERIV_TYPE_SETMINUS_BUNION
  \mathit{Ty} \setminus (S \bunion  T) \;\;\defi\;\;  (\mathit{Ty} \setminus S) \binter  (\mathit{Ty} \setminus T) where \mathit{Ty} is a type expression M
*
DERIV_TYPE_SETMINUS_SETMINUS
  \mathit{Ty} \setminus (S \setminus T) \;\;\defi\;\;  (\mathit{Ty} \setminus S) \bunion  T where \mathit{Ty} is a type expression M
DISTRI_CPROD_BINTER
  S \cprod  (T \binter  U) \;\;\defi\;\;  (S \cprod  T) \binter  (S \cprod  U) M
DISTRI_CPROD_BUNION
  S \cprod  (T \bunion  U) \;\;\defi\;\;  (S \cprod  T) \bunion  (S \cprod  U) M
DISTRI_CPROD_SETMINUS
  S \cprod  (T \setminus U) \;\;\defi\;\;  (S \cprod  T) \setminus (S \cprod  U) M
*
DERIV_SUBSETEQ
  S \subseteq  T \;\;\defi\;\;  (\mathit{Ty} \setminus T) \subseteq  (\mathit{Ty} \setminus S) where \pow (\mathit{Ty}) is the type of S and T M
*
DERIV_EQUAL
  S = T \;\;\defi\;\;  S \subseteq  T \land  T \subseteq  S where \pow (\mathit{Ty}) is the type of S and T M
*
DERIV_SUBSETEQ_SETMINUS_L
  A \setminus B \subseteq  S \;\;\defi\;\;  A \subseteq  B \bunion  S M
*
DERIV_SUBSETEQ_SETMINUS_R
  S \subseteq  A \setminus B \;\;\defi\;\;  S \subseteq  A \land  S \binter  B = \emptyset M
*
DEF_PARTITION
  \operatorname{partition} (s, s_1, s_2, \ldots, s_n) \;\;\defi\;\; 
 		  	\begin{array}{ll}
		  		& s = s_1\bunion s_2\bunion\cdots\bunion s_n\\
				\land& s_1\binter s_2 = \emptyset\\
				\vdots\\
				\land& s_1\binter s_n = \emptyset\\
				\vdots\\
				\land& s_{n-1}\binter s_n = \emptyset
			\end{array} AM
*
SIMP_EMPTY_PARTITION
\operatorname{partition}(S)  \;\;\defi\;\;  S = \emptyset A
*
SIMP_SINGLE_PARTITION
\operatorname{partition}(S, T)  \;\;\defi\;\;  S = T A
*
DEF_EQUAL_CARD
\operatorname{card}(S) = k \;\;\defi\;\; \exists f \qdot f \in 1..k \tbij S also works for k = \operatorname{card}(S) M
*
SIMP_EQUAL_CARD
\operatorname{card}(S) = \operatorname{card}(T) \;\;\defi\;\; \exists f \qdot f \in S \tbij T M

Relation Rewrite Rules

Rules that are marked with a * in the first column are implemented in the latest version of Rodin. Rules without a * are planned to be implemented in future versions. Other conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_Rules.


  Name Rule Side Condition A/M
*
SIMP_DOM_SETENUM
  \dom (\{ x \mapsto  a, \ldots , y \mapsto  b\} ) \;\;\defi\;\;  \{ x, \ldots , y\} A
*
SIMP_DOM_CONVERSE
  \dom (r^{-1} ) \;\;\defi\;\;  \ran (r) A
*
SIMP_RAN_SETENUM
  \ran (\{ x \mapsto  a, \ldots , y \mapsto  b\} ) \;\;\defi\;\;  \{ a, \ldots , b\} A
*
SIMP_RAN_CONVERSE
  \ran (r^{-1} ) \;\;\defi\;\;  \dom (r) A
*
SIMP_SPECIAL_OVERL
  r \ovl  \ldots  \ovl  \emptyset  \ovl  \ldots  \ovl  s \;\;\defi\;\;  r \ovl  \ldots  \ovl  s A
*
SIMP_MULTI_OVERL
r_1 \ovl  \cdots  \ovl r_n \defi r_1 \ovl \cdots \ovl r_{i-1} \ovl r_{i+1} \ovl \cdots \ovl r_n there is a j such that 1\leq i < j \leq n and r_i and r_j are syntactically equal. A
*
SIMP_TYPE_OVERL_CPROD
 r\ovl\cdots\ovl\mathit{Ty}\ovl\cdots\ovl s \;\defi\;\; \mathit{Ty}\ovl\cdots\ovl s where \mathit{Ty} is a type expression A
*
SIMP_SPECIAL_DOMRES_L
  \emptyset  \domres  r \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_DOMRES_R
  S \domres  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_DOMRES
 \mathit{Ty} \domres  r \;\;\defi\;\;  r where \mathit{Ty} is a type expression A
*
SIMP_MULTI_DOMRES_DOM
  \dom (r) \domres  r \;\;\defi\;\;  r A
*
SIMP_MULTI_DOMRES_RAN
  \ran (r) \domres  r^{-1}  \;\;\defi\;\;  r^{-1} A
*
SIMP_DOMRES_DOMRES_ID
  S \domres  (T \domres \id) \;\;\defi\;\;  (S \binter  T) \domres \id A
*
SIMP_DOMRES_DOMSUB_ID
  S \domres  (T \domsub \id) \;\;\defi\;\;  (S \setminus  T) \domres \id A
*
SIMP_SPECIAL_RANRES_R
  r \ranres  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_RANRES_L
  \emptyset  \ranres  S \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_RANRES
  r \ranres  \mathit{Ty} \;\;\defi\;\;  r where \mathit{Ty} is a type expression A
*
SIMP_MULTI_RANRES_RAN
  r \ranres  \ran (r) \;\;\defi\;\;  r A
*
SIMP_MULTI_RANRES_DOM
  r^{-1}  \ranres  \dom (r) \;\;\defi\;\;  r^{-1} A
*
SIMP_RANRES_ID
  \id  \ranres  S \;\;\defi\;\;  S  \domres \id A
*
SIMP_RANSUB_ID
  \id  \ransub  S \;\;\defi\;\;  S  \domsub \id A
*
SIMP_RANRES_DOMRES_ID
  (S \domres \id) \ranres  T \;\;\defi\;\;  (S \binter  T) \domres \id A
*
SIMP_RANRES_DOMSUB_ID
  (S \domsub \id) \ranres  T \;\;\defi\;\;  (T \setminus  S) \domres \id A
*
SIMP_SPECIAL_DOMSUB_L
  \emptyset  \domsub  r \;\;\defi\;\;  r A
*
SIMP_SPECIAL_DOMSUB_R
  S \domsub  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_DOMSUB
 \mathit{Ty} \domsub  r \;\;\defi\;\;  \emptyset where \mathit{Ty} is a type expression A
*
SIMP_MULTI_DOMSUB_DOM
  \dom (r) \domsub  r \;\;\defi\;\;  \emptyset A
*
SIMP_MULTI_DOMSUB_RAN
  \ran (r) \domsub  r^{-1} \;\;\defi\;\;  \emptyset A
*
SIMP_DOMSUB_DOMRES_ID
  S \domsub (T \domres \id ) \;\;\defi\;\;  (T \setminus S) \domres \id A
*
SIMP_DOMSUB_DOMSUB_ID
  S \domsub (T \domsub \id ) \;\;\defi\;\;  (S \bunion T) \domsub \id A
*
SIMP_SPECIAL_RANSUB_R
  r \ransub  \emptyset  \;\;\defi\;\;  r A
*
SIMP_SPECIAL_RANSUB_L
  \emptyset  \ransub  S \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_RANSUB
  r \ransub  \mathit{Ty} \;\;\defi\;\;  \emptyset where \mathit{Ty} is a type expression A
*
SIMP_MULTI_RANSUB_DOM
  r^{-1} \ransub  \dom (r) \;\;\defi\;\;  \emptyset A
*
SIMP_MULTI_RANSUB_RAN
  r \ransub  \ran (r) \;\;\defi\;\;  \emptyset A
*
SIMP_RANSUB_DOMRES_ID
  (S \domres \id) \ransub  T \;\;\defi\;\;  (S \setminus T) \domres \id A
*
SIMP_RANSUB_DOMSUB_ID
  (S \domsub \id) \ransub  T \;\;\defi\;\;  (S \bunion T) \domsub \id A
*
SIMP_SPECIAL_FCOMP
  r \fcomp \ldots  \fcomp \emptyset  \fcomp \ldots  \fcomp s \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_FCOMP_ID
  r \fcomp \ldots  \fcomp \id \fcomp \ldots  \fcomp s \;\;\defi\;\;  r \fcomp \ldots  \fcomp s A
*
SIMP_TYPE_FCOMP_R
  r \fcomp \mathit{Ty} \;\;\defi\;\;  \dom (r) \cprod  \mathit{Tb} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_TYPE_FCOMP_L
 \mathit{Ty} \fcomp r \;\;\defi\;\;  \mathit{Ta} \cprod  \ran (r) where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_FCOMP_ID
  r \fcomp \ldots  \fcomp S \domres \id \fcomp T \domres \id \fcomp \ldots  s \;\;\defi\;\;  r \fcomp \ldots  \fcomp (S \binter  T) \domres \id \fcomp \ldots  \fcomp s A
*
SIMP_SPECIAL_BCOMP
  r \bcomp  \ldots  \bcomp  \emptyset  \bcomp  \ldots  \bcomp  s \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_BCOMP_ID
  r \bcomp  \ldots  \bcomp  \id \bcomp  \ldots  \bcomp  s \;\;\defi\;\;  r \bcomp  \ldots  \bcomp  s A
*
SIMP_TYPE_BCOMP_L
 \mathit{Ty} \bcomp  r \;\;\defi\;\;  \dom (r) \cprod  \mathit{Tb} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_TYPE_BCOMP_R
  r \bcomp  \mathit{Ty} \;\;\defi\;\;  \mathit{Ta} \cprod  \ran (r) where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_BCOMP_ID
  r \bcomp  \ldots  \bcomp S \domres \id \bcomp T \domres \id \bcomp  \ldots  \bcomp  s \;\;\defi\;\;  r \bcomp  \ldots  \bcomp (S \binter  T) \domres \id \bcomp  \ldots  \bcomp  s A
*
SIMP_SPECIAL_DPROD_R
  r \dprod  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_DPROD_L
  \emptyset  \dprod  r \;\;\defi\;\;  \emptyset A
*
SIMP_DPROD_CPROD
  (\mathit{S} \cprod \mathit{T})  \dprod  (\mathit{U} \cprod \mathit{V})  \;\;\defi\;\;  \mathit{S}  \binter  \mathit{U}  \cprod  (\mathit{T}  \cprod  \mathit{V}) A
*
SIMP_SPECIAL_PPROD_R
  r \pprod  \emptyset  \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_PPROD_L
  \emptyset  \pprod  r \;\;\defi\;\;  \emptyset A
*
SIMP_PPROD_CPROD
  (\mathit{S} \cprod \mathit{T})  \pprod  (\mathit{U} \cprod \mathit{V}) \;\;\defi\;\;  (\mathit{S} \cprod \mathit{U}) \cprod (\mathit{T} \cprod \mathit{V}) A
*
SIMP_SPECIAL_RELIMAGE_R
  r[\emptyset ] \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_RELIMAGE_L
  \emptyset [S] \;\;\defi\;\;  \emptyset A
*
SIMP_TYPE_RELIMAGE
  r[Ty] \;\;\defi\;\;  \ran (r) where \mathit{Ty} is a type expression A
*
SIMP_MULTI_RELIMAGE_DOM
  r[\dom (r)] \;\;\defi\;\;  \ran (r) A
*
SIMP_RELIMAGE_ID
  \id[T] \;\;\defi\;\;  T A
*
SIMP_RELIMAGE_DOMRES_ID
  (S \domres \id)[T] \;\;\defi\;\;  S \binter  T A
*
SIMP_RELIMAGE_DOMSUB_ID
  (S \domsub \id)[T] \;\;\defi\;\;  T \setminus S A
*
SIMP_MULTI_RELIMAGE_CPROD_SING
  (\{ E\}  \cprod  S)[\{ E\} ] \;\;\defi\;\;  S where E is a single expression A
*
SIMP_MULTI_RELIMAGE_SING_MAPSTO
  \{ E \mapsto  F\} [\{ E\} ] \;\;\defi\;\;  \{ F\} where E is a single expression A
*
SIMP_MULTI_RELIMAGE_CONVERSE_RANSUB
  (r \ransub  S)^{-1} [S] \;\;\defi\;\;  \emptyset A
*
SIMP_MULTI_RELIMAGE_CONVERSE_RANRES
  (r \ranres  S)^{-1} [S] \;\;\defi\;\;  r^{-1} [S] A
*
SIMP_RELIMAGE_CONVERSE_DOMSUB
  (S \domsub  r)^{-1} [T] \;\;\defi\;\;  r^{-1} [T] \setminus S A
DERIV_RELIMAGE_RANSUB
  (r \ransub  S)[T] \;\;\defi\;\;  r[T] \setminus S M
DERIV_RELIMAGE_RANRES
  (r \ranres  S)[T] \;\;\defi\;\;  r[T] \binter  S M
*
SIMP_MULTI_RELIMAGE_DOMSUB
  (S \domsub  r)[S] \;\;\defi\;\;  \emptyset A
DERIV_RELIMAGE_DOMSUB
  (S \domsub  r)[T] \;\;\defi\;\;  r[T \setminus S] M
DERIV_RELIMAGE_DOMRES
  (S \domres  r)[T] \;\;\defi\;\;  r[S \binter  T] M
*
SIMP_SPECIAL_CONVERSE
  \emptyset ^{-1}  \;\;\defi\;\;  \emptyset A
*
SIMP_CONVERSE_ID
  \id^{-1}  \;\;\defi\;\;  \id A
*
SIMP_CONVERSE_CPROD
  (\mathit{S} \cprod \mathit{T})^{-1}  \;\;\defi\;\;  \mathit{T} \cprod \mathit{S} A
*
SIMP_CONVERSE_SETENUM
  \{ x \mapsto  a, \ldots , y \mapsto  b\} ^{-1}  \;\;\defi\;\;  \{ a \mapsto  x, \ldots , b \mapsto  y\} A
*
SIMP_CONVERSE_COMPSET
  \{ X \qdot  P \mid  x\mapsto y\} ^{-1}  \;\;\defi\;\;  \{ X \qdot  P \mid  y\mapsto x\} A
*
SIMP_DOM_ID
  \dom (\id) \;\;\defi\;\;  S where \id has type \pow(S \cprod S) A
*
SIMP_RAN_ID
  \ran (\id) \;\;\defi\;\;  S where \id has type \pow(S \cprod S) A
*
SIMP_FCOMP_ID_L
  (S \domres \id) \fcomp r \;\;\defi\;\;  S \domres  r A
*
SIMP_FCOMP_ID_R
  r \fcomp (S \domres \id) \;\;\defi\;\;  r \ranres  S A
*
SIMP_SPECIAL_REL_R
  S \rel  \emptyset  \;\;\defi\;\;  \{ \emptyset \} idem for operators \srel  \pfun  \pinj  \psur A
*
SIMP_SPECIAL_REL_L
  \emptyset  \rel  S \;\;\defi\;\;  \{ \emptyset \} idem for operators \trel  \pfun  \tfun  \pinj  \tinj A
*
SIMP_FUNIMAGE_PRJ1
  \prjone (E \mapsto  F) \;\;\defi\;\;  E A
*
SIMP_FUNIMAGE_PRJ2
  \prjtwo (E \mapsto  F) \;\;\defi\;\;  F A
*
SIMP_DOM_PRJ1
  \dom (\prjone) \;\;\defi\;\;  S \cprod T where \prjone has type \pow(S \cprod T \cprod S) A
*
SIMP_DOM_PRJ2
  \dom (\prjtwo) \;\;\defi\;\; S \cprod T where \prjtwo has type \pow(S \cprod T \cprod T) A
*
SIMP_RAN_PRJ1
  \ran (\prjone) \;\;\defi\;\;  S where \prjone has type \pow(S \cprod T \cprod S) A
*
SIMP_RAN_PRJ2
  \ran (\prjtwo) \;\;\defi\;\;  T where \prjtwo has type \pow(S \cprod T \cprod T) A
*
SIMP_FUNIMAGE_LAMBDA
  (\lambda x \qdot  P(x) \mid  E(x))(y) \;\;\defi\;\;  E(y) A
*
SIMP_DOM_LAMBDA
\dom(\{x\qdot P\mid E\mapsto F) \;\;\defi\;\; \{x\qdot P\mid E\} A
*
SIMP_RAN_LAMBDA
\ran(\{x\qdot P\mid E\mapsto F) \;\;\defi\;\; \{x\qdot P\mid F\} A
*
SIMP_IN_FUNIMAGE
E\mapsto F(E)\in F \;\;\defi\;\; \btrue A
*
SIMP_IN_FUNIMAGE_CONVERSE_L
F^{-1}(E)\mapsto E\in F \;\;\defi\;\; \btrue A
*
SIMP_IN_FUNIMAGE_CONVERSE_R
F(E)\mapsto E\in F^{-1} \;\;\defi\;\; \btrue A
*
SIMP_MULTI_FUNIMAGE_SETENUM_LL
  \{ A \mapsto  E, \ldots  , B \mapsto  E\} (x) \;\;\defi\;\;  E A
*
SIMP_MULTI_FUNIMAGE_SETENUM_LR
  \{ E, \ldots  , x \mapsto  y, \ldots  , F\} (x) \;\;\defi\;\;  y A
*
SIMP_MULTI_FUNIMAGE_OVERL_SETENUM
  (r \ovl  \ldots  \ovl  \{ E, \ldots  , x \mapsto  y, \ldots  , F\} )(x) \;\;\defi\;\;  y A
*
SIMP_MULTI_FUNIMAGE_BUNION_SETENUM
  (r \bunion  \ldots  \bunion  \{ E, \ldots  , x \mapsto  y, \ldots  , F\} )(x) \;\;\defi\;\;  y A
*
SIMP_FUNIMAGE_CPROD
  (S \cprod  \{ F\} )(x) \;\;\defi\;\;  F A
*
SIMP_FUNIMAGE_ID
  \id (x) \;\;\defi\;\;  x A
*
SIMP_FUNIMAGE_FUNIMAGE_CONVERSE
  f(f^{-1} (E)) \;\;\defi\;\;  E A
*
SIMP_FUNIMAGE_CONVERSE_FUNIMAGE
  f^{-1}(f(E)) \;\;\defi\;\;  E A
*
SIMP_FUNIMAGE_FUNIMAGE_CONVERSE_SETENUM
  \{x \mapsto a, \ldots, y \mapsto b\}(\{a \mapsto x, \ldots, b \mapsto y\}(E)) \;\;\defi\;\;  E A
*
SIMP_FUNIMAGE_DOMRES
(E \domres F)(G)\;\;\defi\;\;F(G) with hypothesis F \in \mathit{A} \ \mathit{op}\  \mathit{B} where \mathit{op} is one of \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij. AM
*
SIMP_FUNIMAGE_DOMSUB
(E \domsub F)(G)\;\;\defi\;\;F(G) with hypothesis F \in \mathit{A} \ \mathit{op}\  \mathit{B} where \mathit{op} is one of \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij. AM
*
SIMP_FUNIMAGE_RANRES
(F\ranres E)(G)\;\;\defi\;\;F(G) with hypothesis F \in \mathit{A} \ \mathit{op}\  \mathit{B} where \mathit{op} is one of \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij. AM
*
SIMP_FUNIMAGE_RANSUB
(F \ransub E)(G)\;\;\defi\;\;F(G) with hypothesis F \in \mathit{A} \ \mathit{op}\  \mathit{B} where \mathit{op} is one of \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij. AM
*
SIMP_FUNIMAGE_SETMINUS
(F \setminus E)(G)\;\;\defi\;\;F(G) with hypothesis F \in \mathit{A} \ \mathit{op}\  \mathit{B} where \mathit{op} is one of \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij. AM
*
DEF_EQUAL_FUNIMAGE
 f(x) = y \;\;\defi\;\; x \mapsto y \in f M
*
DEF_BCOMP
  r \bcomp  \ldots  \bcomp  s \;\;\defi\;\;  s \fcomp \ldots  \fcomp r M
DERIV_ID_SING
  \{ E\} \domres \id \;\;\defi\;\;  \{ E \mapsto  E\} where E is a single expression M
*
SIMP_SPECIAL_DOM
  \dom (\emptyset ) \;\;\defi\;\;  \emptyset A
*
SIMP_SPECIAL_RAN
  \ran (\emptyset ) \;\;\defi\;\;  \emptyset A
*
SIMP_CONVERSE_CONVERSE
  r^{-1-1}  \;\;\defi\;\;  r A
*
DERIV_RELIMAGE_FCOMP
  (p \fcomp q)[s] \;\;\defi\;\;  q[p[s]] M
*
DERIV_FCOMP_DOMRES
  (s \domres  p) \fcomp q \;\;\defi\;\;  s \domres  (p \fcomp q) M
*
DERIV_FCOMP_DOMSUB
  (s \domsub  p) \fcomp q \;\;\defi\;\;  s \domsub  (p \fcomp q) M
*
DERIV_FCOMP_RANRES
  p \fcomp (q \ranres  s) \;\;\defi\;\;  (p \fcomp q) \ranres  s M
*
DERIV_FCOMP_RANSUB
  p \fcomp (q \ransub  s) \;\;\defi\;\;  (p \fcomp q) \ransub  s M
DERIV_FCOMP_SING
  \{E\mapsto F\}\fcomp\{F\mapsto G\} \;\;\defi\;\;  \{E\mapsto G\} A
*
SIMP_SPECIAL_EQUAL_RELDOMRAN
  \emptyset  \strel  \emptyset  \;\;\defi\;\;  \{ \emptyset \} idem for operators \tsur  \tbij A
*
SIMP_TYPE_DOM
  \dom (\mathit{Ty}) \;\;\defi\;\;  \mathit{Ta} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_TYPE_RAN
  \ran (\mathit{Ty}) \;\;\defi\;\;  \mathit{Tb} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_MULTI_DOM_CPROD
  \dom (E \cprod  E) \;\;\defi\;\;  E A
*
SIMP_MULTI_RAN_CPROD
  \ran (E \cprod  E) \;\;\defi\;\;  E A
*
SIMP_MULTI_DOM_DOMRES
\dom(A\domres f) \;\;\defi\;\; \dom(f)\binter A A
*
SIMP_MULTI_DOM_DOMSUB
\dom(A\domsub f) \;\;\defi\;\; \dom(f)\setminus A A
*
SIMP_MULTI_RAN_RANRES
\ran(f\ranres A) \;\;\defi\;\; \ran(f)\binter A A
*
SIMP_MULTI_RAN_RANSUB
\ran(f\ransub A) \;\;\defi\;\; \ran(f)\setminus A A
*
DEF_IN_DOM
  E \in  \dom (r) \;\;\defi\;\;  \exists y \qdot  E \mapsto  y \in  r M
*
DEF_IN_RAN
  F \in  \ran (r) \;\;\defi\;\;  \exists x \qdot  x \mapsto  F  \in  r M
*
DEF_IN_CONVERSE
  E \mapsto  F \in  r^{-1}  \;\;\defi\;\;  F \mapsto  E \in  r M
*
DEF_IN_DOMRES
  E \mapsto  F \in  S \domres  r \;\;\defi\;\;  E \in  S \land  E \mapsto  F \in  r M
*
DEF_IN_RANRES
  E \mapsto  F \in  r \ranres  T \;\;\defi\;\;  E \mapsto  F \in  r \land  F \in  T M
*
DEF_IN_DOMSUB
  E \mapsto  F \in  S \domsub  r \;\;\defi\;\;  E \notin  S \land  E \mapsto  F \in  r M
*
DEF_IN_RANSUB
  E \mapsto  F \in  r \ranres  T \;\;\defi\;\;  E \mapsto  F \in  r \land  F \notin  T M
*
DEF_IN_RELIMAGE
  F \in  r[w] \;\;\defi\;\;  \exists x \qdot  x \in  w \land  x \mapsto  F \in  r M
*
DEF_IN_FCOMP
  E \mapsto  F \in  (p \fcomp q) \;\;\defi\;\;  \exists x \qdot  E \mapsto  x \in  p \land  x \mapsto  F \in  q M
*
DEF_OVERL
  p \ovl  q \;\;\defi\;\;  (\dom (q) \domsub  p) \bunion  q M
*
DEF_IN_ID
  E \mapsto  F \in  \id \;\;\defi\;\;  E = F M
*
DEF_IN_DPROD
  E \mapsto  (F \mapsto  G) \in  p \dprod  q \;\;\defi\;\;  E \mapsto  F \in  p \land  E \mapsto  G \in  q M
*
DEF_IN_PPROD
  (E \mapsto  G) \mapsto  (F \mapsto  H) \in  p \pprod  q \;\;\defi\;\;  E \mapsto  F \in  p \land  G \mapsto  H \in  q M
*
DEF_IN_REL
  r \in  S \rel  T \;\;\defi\;\;  r\subseteq S\cprod T M
*
DEF_IN_RELDOM
  r \in  S \trel  T \;\;\defi\;\;  r \in  S \rel  T \land  \dom (r) = S M
*
DEF_IN_RELRAN
  r \in  S \srel  T \;\;\defi\;\;  r \in  S \rel  T \land  \ran (r) = T M
*
DEF_IN_RELDOMRAN
  r \in  S \strel  T \;\;\defi\;\;  r \in  S \rel  T \land  \dom (r) = S \land  \ran (r) = T M
*
DEF_IN_FCT
\begin{array}{rcl}
 f \in  S \pfun  T & \defi & f \in  S \rel  T  \\  & \land & (\forall x,y,z \qdot  x \mapsto  y \in  f \land  x \mapsto  z \in  f \limp  y = z) \\ \end{array} M
*
DEF_IN_TFCT
  f \in  S \tfun  T \;\;\defi\;\;  f \in  S \pfun  T \land  \dom (f) = S M
*
DEF_IN_INJ
  f \in  S \pinj  T \;\;\defi\;\;  f \in  S \pfun  T \land  f^{-1}  \in  T \pfun  S M
*
DEF_IN_TINJ
  f \in  S \tinj  T \;\;\defi\;\;  f \in  S \pinj  T \land  \dom (f) = S M
*
DEF_IN_SURJ
  f \in  S \psur  T \;\;\defi\;\;  f \in  S \pfun  T \land  \ran (f) = T M
*
DEF_IN_TSURJ
  f \in  S \tsur  T \;\;\defi\;\;  f \in  S \psur  T \land  \dom (f) = S M
*
DEF_IN_BIJ
  f \in  S \tbij  T \;\;\defi\;\;  f \in  S \tinj  T \land  \ran (f) = T M
DISTRI_BCOMP_BUNION
  r \bcomp  (s \bunion  t) \;\;\defi\;\;  (r \bcomp  s) \bunion  (r \bcomp  t) M
*
DISTRI_FCOMP_BUNION_R
  p \fcomp (q \bunion  r) \;\;\defi\;\;  (p \fcomp q) \bunion  (p \fcomp r) M
*
DISTRI_FCOMP_BUNION_L
  (q \bunion  r) \fcomp p \;\;\defi\;\;  (q \fcomp p) \bunion  (r \fcomp p) M
DISTRI_DPROD_BUNION
  r \dprod  (s \bunion  t) \;\;\defi\;\;  (r \dprod  s) \bunion  (r \dprod  t) M
DISTRI_DPROD_BINTER
  r \dprod  (s \binter  t) \;\;\defi\;\;  (r \dprod  s) \binter  (r \dprod  t) M
DISTRI_DPROD_SETMINUS
  r \dprod  (s \setminus t) \;\;\defi\;\;  (r \dprod  s) \setminus (r \dprod  t) M
DISTRI_DPROD_OVERL
  r \dprod  (s \ovl  t) \;\;\defi\;\;  (r \dprod  s) \ovl  (r \dprod  t) M
DISTRI_PPROD_BUNION
  r \pprod  (s \bunion  t) \;\;\defi\;\;  (r \pprod  s) \bunion  (r \pprod  t) M
DISTRI_PPROD_BINTER
  r \pprod  (s \binter  t) \;\;\defi\;\;  (r \pprod  s) \binter  (r \pprod  t) M
DISTRI_PPROD_SETMINUS
  r \pprod  (s \setminus t) \;\;\defi\;\;  (r \pprod  s) \setminus (r \pprod  t) M
DISTRI_PPROD_OVERL
  r \pprod  (s \ovl  t) \;\;\defi\;\;  (r \pprod  s) \ovl  (r \pprod  t) M
DISTRI_OVERL_BUNION_L
  (p \bunion  q) \ovl  r \;\;\defi\;\;  (p \ovl  r) \bunion  (q \ovl  r) M
DISTRI_OVERL_BINTER_L
  (p \binter  q) \ovl  r \;\;\defi\;\;  (p \ovl  r) \binter  (q \ovl  r) M
*
DISTRI_DOMRES_BUNION_R
  s \domres  (p \bunion  q) \;\;\defi\;\;  (s \domres  p) \bunion  (s \domres  q) M
*
DISTRI_DOMRES_BUNION_L
  (s \bunion  t) \domres  r \;\;\defi\;\;  (s \domres  r) \bunion  (t \domres  r) M
*
DISTRI_DOMRES_BINTER_R
  s \domres  (p \binter  q) \;\;\defi\;\;  (s \domres  p) \binter  (s \domres  q) M
*
DISTRI_DOMRES_BINTER_L
  (s \binter  t) \domres  r \;\;\defi\;\;  (s \domres  r) \binter  (t \domres  r) M
DISTRI_DOMRES_SETMINUS_R
  s \domres  (p \setminus q) \;\;\defi\;\;  (s \domres  p) \setminus (s \domres  q) M
DISTRI_DOMRES_SETMINUS_L
  (s \setminus t) \domres  r \;\;\defi\;\;  (s \domres  r) \setminus (t \domres  r) M
DISTRI_DOMRES_DPROD
  s \domres  (p \dprod  q) \;\;\defi\;\;  (s \domres  p) \dprod  (s \domres  q) M
DISTRI_DOMRES_OVERL
  s \domres  (r \ovl  q) \;\;\defi\;\;  (s \domres  r) \ovl  (s \domres  q) M
*
DISTRI_DOMSUB_BUNION_R
  s \domsub  (p \bunion  q) \;\;\defi\;\;  (s \domsub  p) \bunion  (s \domsub  q) M
*
DISTRI_DOMSUB_BUNION_L
  (s \bunion  t) \domsub  r \;\;\defi\;\;  (s \domsub  r) \binter  (t \domsub  r) M
*
DISTRI_DOMSUB_BINTER_R
  s \domsub  (p \binter  q) \;\;\defi\;\;  (s \domsub  p) \binter  (s \domsub  q) M
*
DISTRI_DOMSUB_BINTER_L
  (s \binter  t) \domsub  r \;\;\defi\;\;  (s \domsub  r) \bunion  (t \domsub  r) M
DISTRI_DOMSUB_DPROD
  A \domsub  (r \dprod  s) \;\;\defi\;\;  (A \domsub  r) \dprod  (A \domsub  s) M
DISTRI_DOMSUB_OVERL
  A \domsub  (r \ovl  s) \;\;\defi\;\;  (A \domsub  r) \ovl  (A \domsub  s) M
*
DISTRI_RANRES_BUNION_R
  r \ranres (s \bunion t) \;\;\defi\;\;  (r \ranres  s) \bunion  (r \ranres  t) M
*
DISTRI_RANRES_BUNION_L
  (p \bunion  q) \ranres  s \;\;\defi\;\;  (p \ranres  s) \bunion  (q \ranres  s) M
*
DISTRI_RANRES_BINTER_R
  r \ranres (s \binter t) \;\;\defi\;\;  (r \ranres  s) \binter  (r \ranres  t) M
*
DISTRI_RANRES_BINTER_L
  (p \binter  q) \ranres  s \;\;\defi\;\;  (p \ranres  s) \binter  (q \ranres  s) M
DISTRI_RANRES_SETMINUS_R
  r \ranres  (s \setminus t) \;\;\defi\;\;  (r \ranres  s) \setminus (r \ranres  t) M
DISTRI_RANRES_SETMINUS_L
  (p \setminus q) \ranres  s \;\;\defi\;\;  (p \ranres  s) \setminus (q \ranres  s) M
*
DISTRI_RANSUB_BUNION_R
  r \ransub (s\bunion t) \;\;\defi\;\;  (r \ransub  s) \binter  (r \ransub  t) M
*
DISTRI_RANSUB_BUNION_L
  (p \bunion  q) \ransub  s \;\;\defi\;\;  (p \ransub  s) \bunion  (q \ransub  s) M
*
DISTRI_RANSUB_BINTER_R
  r \ransub (s \binter t) \;\;\defi\;\;  (r \ransub  s) \bunion  (r \ransub  t) M
*
DISTRI_RANSUB_BINTER_L
  (p \binter  q) \ransub  s \;\;\defi\;\;  (p \ransub  s) \binter  (q \ransub  s) M
*
DISTRI_CONVERSE_BUNION
  (p \bunion  q)^{-1}  \;\;\defi\;\;  p^{-1}  \bunion  q^{-1} M
DISTRI_CONVERSE_BINTER
  (p \binter  q)^{-1}  \;\;\defi\;\;  p^{-1}  \binter  q^{-1} M
DISTRI_CONVERSE_SETMINUS
  (r \setminus s)^{-1}  \;\;\defi\;\;  r^{-1}  \setminus s^{-1} M
DISTRI_CONVERSE_BCOMP
  (r \bcomp  s)^{-1}  \;\;\defi\;\;  (s^{-1}  \bcomp  r^{-1} ) M
DISTRI_CONVERSE_FCOMP
  (p \fcomp q)^{-1}  \;\;\defi\;\;  (q^{-1}  \fcomp p^{-1} ) M
DISTRI_CONVERSE_PPROD
  (r \pprod  s)^{-1}  \;\;\defi\;\;  r^{-1}  \pprod  s^{-1} M
DISTRI_CONVERSE_DOMRES
  (s \domres  r)^{-1}  \;\;\defi\;\;  r^{-1}  \ranres  s M
DISTRI_CONVERSE_DOMSUB
  (s \domsub  r)^{-1}  \;\;\defi\;\;  r^{-1}  \ransub  s M
DISTRI_CONVERSE_RANRES
  (r \ranres  s)^{-1}  \;\;\defi\;\;  s \domres  r^{-1} M
DISTRI_CONVERSE_RANSUB
  (r \ransub  s)^{-1}  \;\;\defi\;\;  s \domsub  r^{-1} M
*
DISTRI_DOM_BUNION
  \dom (r \bunion  s) \;\;\defi\;\;  \dom (r) \bunion  \dom (s) M
*
DISTRI_RAN_BUNION
  \ran (r \bunion  s) \;\;\defi\;\;  \ran (r) \bunion  \ran (s) M
*
DISTRI_RELIMAGE_BUNION_R
  r[S \bunion  T] \;\;\defi\;\;  r[S] \bunion  r[T] M
*
DISTRI_RELIMAGE_BUNION_L
  (p \bunion  q)[S] \;\;\defi\;\;  p[S] \bunion  q[S] M
*
DERIV_DOM_TOTALREL
  \dom (r) \;\;\defi\;\;  E with hypothesis r \in E \ \mathit{op}\  F, where \mathit{op} is one of \trel, \strel, \tfun, \tinj, \tsur, \tbij M
DERIV_RAN_SURJREL
  \ran (r) \;\;\defi\;\;  F with hypothesis r \in E \ \mathit{op}\  F, where \mathit{op} is one of \srel,\strel, \psur, \tsur, \tbij M
*
DERIV_PRJ1_SURJ
\prjone \in\mathit{Ty}_1\ \mathit{op}\ \mathit{Ty}_2\;\;\defi\;\; \btrue where \mathit{Ty}_1 and \mathit{Ty}_2 are types and \mathit{op} is one of \rel, \trel, \srel, \strel, \pfun, \tfun, \psur, \tsur A
*
DERIV_PRJ2_SURJ
\prjtwo \in\mathit{Ty}_1\ \mathit{op}\ \mathit{Ty}_2\;\;\defi\;\; \btrue where \mathit{Ty}_1 and \mathit{Ty}_2 are types and \mathit{op} is one of \rel, \trel, \srel, \strel, \pfun, \tfun, \psur, \tsur A
*
DERIV_ID_BIJ
\id \in\mathit{Ty}\ \mathit{op}\ \mathit{Ty}\;\;\defi\;\; \btrue where \mathit{Ty} is a type and \mathit{op} is any arrow A
*
SIMP_MAPSTO_PRJ1_PRJ2
\prjone(E)\mapsto\prjtwo(E)\;\;\defi\;\; E A
DERIV_EXPAND_PRJS
 E \;\;\defi\;\; \prjone(E) \mapsto \prjtwo(E) M
*
SIMP_DOM_SUCC
\dom(\usucc) \;\;\defi\;\; \intg A
*
SIMP_RAN_SUCC
\ran(\usucc) \;\;\defi\;\; \intg A
*
DERIV_MULTI_IN_BUNION
 E\in A\bunion\cdots\bunion\left\{\cdots, E,\cdots\right\}\bunion\cdots\bunion B\;\;\defi\;\; \btrue A
*
DERIV_MULTI_IN_SETMINUS
 E\in S\setminus\left\{\cdots, E,\cdots\right\} \;\;\defi\;\; \bfalse A
*
DEF_PRED
 \upred\;\;\defi\;\; \usucc^{-1} A
*
SIMP_SPECIAL_IN_ID
 E \mapsto E \in \id \;\;\defi\;\; \btrue A
*
SIMP_SPECIAL_IN_SETMINUS_ID
E \mapsto E \in r \setminus \id \;\;\defi\;\; \bfalse A
*
SIMP_SPECIAL_IN_DOMRES_ID
E \mapsto E \in S \domres \id \;\;\defi\;\; E \in S A
*
SIMP_SPECIAL_IN_SETMINUS_DOMRES_ID
E \mapsto E \in r \setminus (S \domres \id) \;\;\defi\;\; E \mapsto E \in S \domsub r A

Empty Set Rewrite Rules

Rules that are marked with a * in the first column are implemented in the latest version of Rodin. Rules without a * are planned to be implemented in future versions. Other conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_Rules.

All rewrite rules that match the pattern \textbf{P}=\emptyset are also applicable to predicates of the form \textbf{P}\subseteq\emptyset and \emptyset=\textbf{P}, as these predicates are equivalent. All rewrite rules that match the pattern \textbf{P}=\mathit{Ty} are also applicable to predicates of the form \mathit{Ty}\subseteq\textbf{P} and \mathit{Ty}=\textbf{P}, as these predicates are equivalent.


  Name Rule Side Condition A/M
*
DEF_SPECIAL_NOT_EQUAL
  \lnot\, S = \emptyset  \;\;\defi\;\;  \exists x \qdot  x \in  S where x is not free in S M
*
SIMP_SETENUM_EQUAL_EMPTY
  \{ A, \ldots , B\}  = \emptyset \;\;\defi\;\;  \bfalse A
*
SIMP_SPECIAL_EQUAL_COMPSET
  \{  x \qdot  P(x) \mid  E \}  = \emptyset  \;\;\defi\;\;  \forall x\qdot  \lnot\, P(x) A
*
SIMP_BINTER_EQUAL_TYPE
  A \binter \cdots \binter B = \mathit{Ty} \;\;\defi\;\;  A = \mathit{Ty} \land \cdots \land B  = \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_BINTER_SING_EQUAL_EMPTY
A\binter\cdots\binter\{a\}\binter\cdots\binter B  = \emptyset  \;\;\defi\;\;  \lnot\, a \in A\binter\cdots\binter B A
*
SIMP_BINTER_SETMINUS_EQUAL_EMPTY
A\binter\cdots\binter(B\setminus C)\binter\cdots\binter D  = \emptyset  \;\;\defi\;\;  (A\binter\cdots\binter B\binter\cdots\binter D) \setminus C = \emptyset A
*
SIMP_BUNION_EQUAL_EMPTY
  A \bunion \cdots \bunion B = \emptyset \;\;\defi\;\;  A = \emptyset \land \cdots \land B  = \emptyset A
*
SIMP_SETMINUS_EQUAL_EMPTY
  A \setminus  B = \emptyset \;\;\defi\;\;  A \subseteq  B  A
*
SIMP_SETMINUS_EQUAL_TYPE
  A \setminus  B = \mathit{Ty} \;\;\defi\;\;  A = \mathit{Ty} \land B = \emptyset where \mathit{Ty} is a type expression A
*
SIMP_POW_EQUAL_EMPTY
  \pow (S) = \emptyset \;\;\defi\;\;  \bfalse  A
*
SIMP_POW1_EQUAL_EMPTY
  \pown (S) = \emptyset \;\;\defi\;\;  S = \emptyset  A
*
SIMP_KINTER_EQUAL_TYPE
   \inter (S) = \mathit{Ty} \;\;\defi\;\;  S = \{ \mathit{Ty} \}  where \mathit{Ty} is a type expression A
*
SIMP_KUNION_EQUAL_EMPTY
   \union (S) = \emptyset \;\;\defi\;\;  S \subseteq \{ \emptyset \}  A
*
SIMP_QINTER_EQUAL_TYPE
  (\Inter  x\qdot P(x)  \mid  E(x)) = \mathit{Ty} \;\;\defi\;\;  \forall x\qdot  P(x) \limp E(x) = \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_QUNION_EQUAL_EMPTY
  (\Union  x\qdot P(x)  \mid  E(x)) = \emptyset \;\;\defi\;\;  \forall x\qdot  P(x) \limp E(x) = \emptyset A
*
SIMP_NATURAL_EQUAL_EMPTY
  \nat = \emptyset \;\;\defi\;\;  \bfalse A
*
SIMP_NATURAL1_EQUAL_EMPTY
  \natn = \emptyset \;\;\defi\;\;  \bfalse A
*
SIMP_TYPE_EQUAL_EMPTY
 \mathit{Ty} = \emptyset  \;\;\defi\;\;  \bfalse where \mathit{Ty} is a type expression A
*
SIMP_CPROD_EQUAL_EMPTY
  S \cprod T = \emptyset \;\;\defi\;\; S = \emptyset \lor T = \emptyset A
*
SIMP_CPROD_EQUAL_TYPE
  S \cprod T = \mathit{Ty} \;\;\defi\;\; S = \mathit{Ta} \land T = \mathit{Tb} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_UPTO_EQUAL_EMPTY
  i \upto j = \emptyset \;\;\defi\;\; i > j A
*
SIMP_UPTO_EQUAL_INTEGER
  i \upto j = \intg \;\;\defi\;\; \bfalse A
*
SIMP_UPTO_EQUAL_NATURAL
  i \upto j = \nat \;\;\defi\;\; \bfalse A
*
SIMP_UPTO_EQUAL_NATURAL1
  i \upto j = \natn \;\;\defi\;\; \bfalse A
*
SIMP_SPECIAL_EQUAL_REL
  A \rel  B = \emptyset  \;\;\defi\;\;  \bfalse idem for operators \pfun  \pinj A
SIMP_TYPE_EQUAL_REL
  A \rel  B = \mathit{Ty}  \;\;\defi\;\;  A = \mathit{Ta} \land B = \mathit{Tb} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_SPECIAL_EQUAL_RELDOM
  A \trel  B = \emptyset  \;\;\defi\;\;  \lnot\, A = \emptyset  \land  B = \emptyset idem for operator \tfun A
SIMP_TYPE_EQUAL_RELDOMRAN
  A \trel  B = \mathit{Ty}  \;\;\defi\;\;  \bfalse where \mathit{Ty} is a type expression, idem for operator \srel, \strel, \tfun, \tinj, \psur, \tsur, \tbij A
*
SIMP_SREL_EQUAL_EMPTY
  A \srel B = \emptyset \;\;\defi\;\; A = \emptyset \land  \lnot\,B = \emptyset A
*
SIMP_STREL_EQUAL_EMPTY
  A \strel B = \emptyset \;\;\defi\;\; (A = \emptyset \leqv  \lnot\,B = \emptyset) A
*
SIMP_DOM_EQUAL_EMPTY
  \dom (r) = \emptyset \;\;\defi\;\; r = \emptyset  A
*
SIMP_RAN_EQUAL_EMPTY
  \ran (r) = \emptyset \;\;\defi\;\; r = \emptyset  A
*
SIMP_FCOMP_EQUAL_EMPTY
 p \fcomp q = \emptyset \;\;\defi\;\; \ran (p) \binter \dom (q) = \emptyset  A
*
SIMP_BCOMP_EQUAL_EMPTY
 p \bcomp q = \emptyset \;\;\defi\;\; \ran (q) \binter \dom (p) = \emptyset  A
*
SIMP_DOMRES_EQUAL_EMPTY
 S \domres r = \emptyset \;\;\defi\;\; \dom (r) \binter S = \emptyset  A
*
SIMP_DOMRES_EQUAL_TYPE
 S \domres r = \mathit{Ty} \;\;\defi\;\; S = \mathit{Ta} \land r = \mathit{Ty}  where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_DOMSUB_EQUAL_EMPTY
 S \domsub r = \emptyset \;\;\defi\;\; \dom (r) \subseteq S A
*
SIMP_DOMSUB_EQUAL_TYPE
 S \domsub r = \mathit{Ty} \;\;\defi\;\; S = \emptyset \land r = \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_RANRES_EQUAL_EMPTY
 r \ranres S = \emptyset \;\;\defi\;\; \ran (r) \binter S = \emptyset A
*
SIMP_RANRES_EQUAL_TYPE
 r \ranres S = \mathit{Ty} \;\;\defi\;\; S = \mathit{Tb} \land r = \mathit{Ty} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod \mathit{Tb} A
*
SIMP_RANSUB_EQUAL_EMPTY
 r \ransub S = \emptyset \;\;\defi\;\; \ran (r) \subseteq S A
*
SIMP_RANSUB_EQUAL_TYPE
 r \ransub S = \mathit{Ty} \;\;\defi\;\; S = \emptyset \land r = \mathit{Ty} where \mathit{Ty} is a type expression A
*
SIMP_CONVERSE_EQUAL_EMPTY
 r^{-1} = \emptyset \;\;\defi\;\; r = \emptyset A
*
SIMP_CONVERSE_EQUAL_TYPE
 r^{-1} = \mathit{Ty} \;\;\defi\;\; r = \mathit{Ty}^{-1} where \mathit{Ty} is a type expression A
*
SIMP_RELIMAGE_EQUAL_EMPTY
 r[S] = \emptyset \;\;\defi\;\; S \domres r = \emptyset A
*
SIMP_OVERL_EQUAL_EMPTY
  r \ovl \cdots \ovl s = \emptyset \;\;\defi\;\; r = \emptyset \land \cdots \land s =  \emptyset A
*
SIMP_DPROD_EQUAL_EMPTY
  p \dprod q = \emptyset \;\;\defi\;\; \dom (p) \binter \dom (q) = \emptyset A
*
SIMP_DPROD_EQUAL_TYPE
  p \dprod q = \mathit{Ty} \;\;\defi\;\; p = \mathit{Ta} \cprod \mathit{Tb} \land q = \mathit{Ta} \cprod \mathit{Tc} where \mathit{Ty} is a type expression equal to \mathit{Ta} \cprod (\mathit{Tb} \cprod \mathit{Tc}) A
*
SIMP_PPROD_EQUAL_EMPTY
  p \pprod q = \emptyset \;\;\defi\;\; p = \emptyset \lor q = \emptyset A
*
SIMP_PPROD_EQUAL_TYPE
  p \pprod q = \mathit{Ty} \;\;\defi\;\;  p = \mathit{Ta} \cprod \mathit{Tc} \land q = \mathit{Tb} \cprod \mathit{Td} where \mathit{Ty} is a type expression equal to (\mathit{Ta} \cprod \mathit{Tb}) \cprod (\mathit{Tc} \cprod \mathit{Td}) A
*
SIMP_ID_EQUAL_EMPTY
  \id = \emptyset \;\;\defi\;\; \bfalse A
*
SIMP_PRJ1_EQUAL_EMPTY
  \prjone = \emptyset \;\;\defi\;\; \bfalse A
*
SIMP_PRJ2_EQUAL_EMPTY
  \prjtwo = \emptyset \;\;\defi\;\; \bfalse A

Arithmetic Rewrite Rules

Rules that are marked with a * in the first column are implemented in the latest version of Rodin. Rules without a * are planned to be implemented in future versions. Other conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_Rules.


  Name Rule Side Condition A/M
*
SIMP_SPECIAL_MOD_0
  0 \,\bmod\,  E \;\;\defi\;\;  0 A
*
SIMP_SPECIAL_MOD_1
  E \,\bmod\,  1 \;\;\defi\;\;  0 A
*
SIMP_MIN_SING
  \min (\{ E\} ) \;\;\defi\;\;  E where E is a single expression A
*
SIMP_MAX_SING
  \max (\{ E\} ) \;\;\defi\;\;  E where E is a single expression A
*
SIMP_MIN_NATURAL
  \min (\nat ) \;\;\defi\;\;  0 A
*
SIMP_MIN_NATURAL1
  \min (\natn ) \;\;\defi\;\;  1 A
*
SIMP_MIN_BUNION_SING
  \begin{array}{cl} & \min (S \bunion  \ldots  \bunion  \{ \min (T)\}  \bunion  \ldots  \bunion  U) \\ \defi & \min (S \bunion  \ldots  \bunion  T \bunion  \ldots  \bunion  U) \\ \end{array} A
*
SIMP_MAX_BUNION_SING
  \begin{array}{cl} & \max (S \bunion  \ldots  \bunion  \{ \max (T)\}  \bunion  \ldots  \bunion  U) \\ \defi &  \max (S \bunion  \ldots  \bunion  T \bunion  \ldots  \bunion  U) \\  \end{array} A
*
SIMP_MIN_UPTO
  \min (E \upto  F) \;\;\defi\;\;  E A
*
SIMP_MAX_UPTO
  \max (E \upto  F) \;\;\defi\;\;  F A
*
SIMP_MIN_IN
  \min (S) \in S \;\;\defi\;\;  \btrue A
*
SIMP_MAX_IN
  \max (S) \in S \;\;\defi\;\;  \btrue A
*
SIMP_LIT_MIN
  \min (\{ E, \ldots  , i, \ldots  , j, \ldots , H\} ) \;\;\defi\;\;  \min (\{ E, \ldots  , i, \ldots , H\} ) where i and j are literals and i \leq j A
*
SIMP_LIT_MAX
  \max (\{ E, \ldots  , i, \ldots  , j, \ldots , H\} ) \;\;\defi\;\;  \max (\{ E, \ldots  , i, \ldots , H\} ) where i and j are literals and i \geq j A
*
SIMP_SPECIAL_CARD
  \card (\emptyset ) \;\;\defi\;\;  0 A
*
SIMP_CARD_SING
  \card (\{ E\} ) \;\;\defi\;\;  1 where E is a single expression A
*
SIMP_SPECIAL_EQUAL_CARD
  \card (S) = 0 \;\;\defi\;\;  S = \emptyset A
*
SIMP_CARD_POW
  \card (\pow (S)) \;\;\defi\;\;  2\expn{\card(S)} A
*
SIMP_CARD_BUNION
  \card (S \bunion  T) \;\;\defi\;\;  \card (S) + \card (T) - \card (S \binter  T) A
SIMP_CARD_SETMINUS
\card(S\setminus T)\;\;\defi\;\;\card(S) - \card(T) with hypotheses T\subseteq S and either \finite(S) or \finite(T) A
SIMP_CARD_SETMINUS_SETENUM
\card(S\setminus\{E_1,\ldots,E_n\})\;\;\defi\;\;\card(S) - \card(\{E_1,\ldots,E_n\}) with hypotheses E_i\in S for all i\in 1\upto n A
*
SIMP_CARD_CONVERSE
  \card (r^{-1} ) \;\;\defi\;\;  \card (r) A
*
SIMP_CARD_ID
  \card (\id) \;\;\defi\;\;  \card (S) where \id has type \pow (S \cprod S) A
*
SIMP_CARD_ID_DOMRES
  \card (S\domres\id) \;\;\defi\;\;  \card (S) A
*
SIMP_CARD_PRJ1
  \card (\prjone) \;\;\defi\;\;  \card (S \cprod T) where \prjone has type \pow(S \cprod T \cprod S) A
*
SIMP_CARD_PRJ2
  \card (\prjtwo) \;\;\defi\;\;  \card (S \cprod T) where \prjtwo has type \pow(S \cprod T \cprod T) A
*
SIMP_CARD_PRJ1_DOMRES
  \card (E \domres \prjone) \;\;\defi\;\;  \card (E) A
*
SIMP_CARD_PRJ2_DOMRES
  \card (E \domres \prjtwo) \;\;\defi\;\;  \card (E) A
*
SIMP_CARD_LAMBDA
 \card(\{x\qdot P\mid E\mapsto F\}) \;\;\defi\;\; \card(\{x\qdot P\mid E\} ) where E is a maplet combination of bound identifiers and expressions that are not bound by the comprehension set (i.e., E is syntactically injective) and all identifiers bound by the comprehension set that occur in F also occur in E A
*
SIMP_LIT_CARD_UPTO
  \card (i \upto  j) \;\;\defi\;\;  j-i+1 where i and j are literals and i \leq j A
SIMP_TYPE_CARD
  \card (\mathit{Tenum}) \;\;\defi\;\;  N where \mathit{Tenum} is a carrier set containing N elements A
*
SIMP_LIT_GE_CARD_1
  \card (S) \geq  1 \;\;\defi\;\;  \lnot\, S = \emptyset A
*
SIMP_LIT_LE_CARD_1
  1 \leq  \card (S) \;\;\defi\;\;  \lnot\, S = \emptyset A
*
SIMP_LIT_LE_CARD_0
  0 \leq  \card (S) \;\;\defi\;\;  \btrue A
*
SIMP_LIT_GE_CARD_0
  \card (S) \geq  0 \;\;\defi\;\;  \btrue A
*
SIMP_LIT_GT_CARD_0
  \card (S) > 0 \;\;\defi\;\;  \lnot\, S = \emptyset A
*
SIMP_LIT_LT_CARD_0
  0 < \card (S) \;\;\defi\;\;  \lnot\, S = \emptyset A
*
SIMP_LIT_EQUAL_CARD_1
  \card (S) = 1 \;\;\defi\;\;  \exists x \qdot  S = \{ x\} A
*
SIMP_CARD_NATURAL
  \card (S) \in  \nat  \;\;\defi\;\;  \btrue A
*
SIMP_CARD_NATURAL1
  \card (S) \in  \natn  \;\;\defi\;\;  \lnot\, S = \emptyset A
*
SIMP_LIT_IN_NATURAL
  i \in  \nat  \;\;\defi\;\;  \btrue where i is a non-negative literal A
*
SIMP_SPECIAL_IN_NATURAL1
  0 \in  \natn  \;\;\defi\;\;  \bfalse A
*
SIMP_LIT_IN_NATURAL1
  i \in  \natn  \;\;\defi\;\;  \btrue where i is a positive literal A
*
SIMP_LIT_UPTO
  i \upto  j \;\;\defi\;\;  \emptyset where i and j are literals and j < i A
*
SIMP_LIT_IN_MINUS_NATURAL
  -i \in  \nat  \;\;\defi\;\;  \bfalse where i is a positive literal A
*
SIMP_LIT_IN_MINUS_NATURAL1
  -i \in  \natn  \;\;\defi\;\;  \bfalse where i is a non-negative literal A
*
DEF_IN_NATURAL
x \in \nat  \;\;\defi\;\;  0 \leq x M
*
DEF_IN_NATURAL1
x \in \natn  \;\;\defi\;\;  1 \leq x M
*
SIMP_LIT_EQUAL_KBOOL_TRUE
  \bool (P) = \True  \;\;\defi\;\;  P A
*
SIMP_LIT_EQUAL_KBOOL_FALSE
  \bool (P) = \False  \;\;\defi\;\;  \lnot\, P A
*
SIMP_KBOOL_LIT_EQUAL_TRUE
 \bool (B = \True) \;\;\defi\;\; B A
*
DEF_EQUAL_MIN
  E = \min (S) \;\;\defi\;\;  E \in  S \land  (\forall x \qdot  x \in  S \limp  E \leq  x) where x non free in S, E M
*
DEF_EQUAL_MAX
  E = \max (S) \;\;\defi\;\;  E \in  S \land  (\forall x \qdot  x \in  S \limp  E \geq  x) where x non free in S, E M
*
SIMP_SPECIAL_PLUS
  E + \ldots  + 0 + \ldots  + F \;\;\defi\;\;  E + \ldots  + F A
*
SIMP_SPECIAL_MINUS_R
  E - 0 \;\;\defi\;\;  E A
*
SIMP_SPECIAL_MINUS_L
  0 - E \;\;\defi\;\;  -E A
*
SIMP_MINUS_MINUS
   - (- E) \;\;\defi\;\;  E A
*
SIMP_MINUS_UNMINUS
 E  - (- F) \;\;\defi\;\;  E + F where (-F) is a unary minus expression or a negative literal M
*
SIMP_MULTI_MINUS
  E - E \;\;\defi\;\;  0 A
*
SIMP_MULTI_MINUS_PLUS_L
 (A + \ldots + C + \ldots + B) - C \;\;\defi\;\; A + \ldots + B M
*
SIMP_MULTI_MINUS_PLUS_R
 C - (A + \ldots + C + \ldots + B)  \;\;\defi\;\;  -(A + \ldots + B) M
*
SIMP_MULTI_MINUS_PLUS_PLUS
 (A + \ldots + E + \ldots + B) - (C + \ldots + E + \ldots + D)  \;\;\defi\;\; (A + \ldots + B) - (C + \ldots + D) M
*
SIMP_MULTI_PLUS_MINUS
(A + \ldots + D + \ldots + (C - D) + \ldots + B) \;\;\defi\;\; A + \ldots + C + \ldots + B  M
*
SIMP_MULTI_ARITHREL_PLUS_PLUS
 A + \ldots + E + \ldots + B  < C + \ldots + E + \ldots + D   \;\;\defi\;\; A + \ldots + B < C + \ldots + D where the root relation (< here) is one of \{=, <, \leq, >, \geq\} M
*
SIMP_MULTI_ARITHREL_PLUS_R
 C < A + \ldots + C \ldots + B   \;\;\defi\;\;   0 < A + \ldots + B where the root relation (< here) is one of \{=, <, \leq, >, \geq\} M
*
SIMP_MULTI_ARITHREL_PLUS_L
 A + \ldots + C \ldots + B < C   \;\;\defi\;\;   A + \ldots + B < 0 where the root relation (< here) is one of \{=, <, \leq, >, \geq\} M
*
SIMP_MULTI_ARITHREL_MINUS_MINUS_R
 A - C < B - C  \;\;\defi\;\; A < B where the root relation (< here) is one of \{=, <, \leq, >, \geq\} M
*
SIMP_MULTI_ARITHREL_MINUS_MINUS_L
 C - A < C - B  \;\;\defi\;\; B < A where the root relation (< here) is one of \{=, <, \leq, >, \geq\} M
*
SIMP_SPECIAL_PROD_0
  E * \ldots  * 0 * \ldots  * F \;\;\defi\;\;  0 A
*
SIMP_SPECIAL_PROD_1
  E * \ldots  * 1 * \ldots  * F \;\;\defi\;\;  E * \ldots  * F A
*
SIMP_SPECIAL_PROD_MINUS_EVEN
  (-E) * \ldots  * (-F) \;\;\defi\;\;  E * \ldots  * F if an even number of - A
*
SIMP_SPECIAL_PROD_MINUS_ODD
  (-E) * \ldots  * (-F) \;\;\defi\;\;  -(E * \ldots  * F) if an odd number of - A
*
SIMP_LIT_MINUS
   - (i) \;\;\defi\;\;  (-i) where i is a literal A
*
SIMP_LIT_EQUAL
  i = j \;\;\defi\;\;  \btrue  \;or\; \bfalse  \;\;(computation) where i and j are literals A
*
SIMP_LIT_LE
  i \leq  j \;\;\defi\;\;  \btrue  \;or\; \bfalse  \;\;(computation) where i and j are literals A
*
SIMP_LIT_LT
  i < j \;\;\defi\;\;  \btrue  \;or\; \bfalse  \;\;(computation) where i and j are literals A
*
SIMP_LIT_GE
  i \geq  j \;\;\defi\;\;  \btrue  \;or\; \bfalse  \;\;(computation) where i and j are literals A
*
SIMP_LIT_GT
  i > j \;\;\defi\;\;  \btrue  \;or\; \bfalse  \;\;(computation) where i and j are literals A
*
SIMP_DIV_MINUS
  (- E) \div  (-F) \;\;\defi\;\;  E \div  F A
*
SIMP_SPECIAL_DIV_1
  E \div  1 \;\;\defi\;\;  E A
*
SIMP_SPECIAL_DIV_0
  0 \div  E \;\;\defi\;\;  0 A
*
SIMP_SPECIAL_EXPN_1_R
  E ^ 1 \;\;\defi\;\;  E A
*
SIMP_SPECIAL_EXPN_1_L
  1 ^ E \;\;\defi\;\;  1 A
*
SIMP_SPECIAL_EXPN_0
  E ^ 0 \;\;\defi\;\;  1 A
*
DEF_EXPN_STEP
 E ^ P \;\;\defi\;\; E * E ^{(P - 1)} with an additional PO \lnot\, P = 0 M
*
SIMP_MULTI_LE
  E \leq  E \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_LT
  E < E \;\;\defi\;\;  \bfalse A
*
SIMP_MULTI_GE
  E \geq  E \;\;\defi\;\;  \btrue A
*
SIMP_MULTI_GT
  E > E \;\;\defi\;\;  \bfalse A
*
SIMP_MULTI_DIV
  E \div  E \;\;\defi\;\;  1 A
*
SIMP_MULTI_DIV_PROD
  (X * \ldots * E * \ldots * Y) \div  E \;\;\defi\;\;  X * \ldots * Y A
*
SIMP_MULTI_MOD
  E \,\bmod\,  E \;\;\defi\;\;  0 A
DISTRI_PROD_PLUS
  a * (b + c) \;\;\defi\;\;  (a * b) + (a * c) M
DISTRI_PROD_MINUS
  a * (b - c) \;\;\defi\;\;  (a * b) - (a * c) M
DERIV_NOT_EQUAL
    \lnot E = F \;\;\defi\;\;  E < F \lor E > F  E and F must be of Integer type M

Extension Proof Rules

Rules that are marked with a * in the first column are implemented in the latest version of Rodin. Rules without a * are planned to be implemented in future versions. Other conventions used in these tables are described in The_Proving_Perspective_(Rodin_User_Manual)#Rewrite_Rules.

Rewrite Rules

  Name Rule Side Condition A/M
*
SIMP_SPECIAL_COND_BTRUE
  \operatorname{COND}(\btrue, E_1, E_2)  \;\;\defi\;\;  E_1 A
*
SIMP_SPECIAL_COND_BFALSE
  \operatorname{COND}(\bfalse, E_1, E_2)  \;\;\defi\;\;  E_2 A
*
SIMP_MULTI_COND
  \operatorname{COND}(C, E, E)  \;\;\defi\;\;  E A

Inference Rules

  Name Rule Side Condition A/M
*
DATATYPE_DISTINCT_CASE
\frac{\textbf{H}, x=c_1(p_{11}, \ldots, p_{1k}) \;\;\vdash \;\; \textbf{G} \qquad \ldots \qquad \textbf{H}, x=c_n(p_{n1}, \ldots, p_{nl}) \;\;\vdash \;\; \textbf{G} }{ \textbf{H}  \;\;\vdash\;\;  \textbf{G} } where x has a datatype DT as type and appears free in \textbf{G}, DT has constructors c_1, \ldots, c_n, parameters p_{ij} are introduced as fresh identifiers M


*
DATATYPE_INDUCTION
\frac{ \textbf{H}, x=c_1(p_1, \ldots, p_k),\textbf{P}(p_{I_1}), \ldots, \textbf{P}(p_{I_l})  \;\;\vdash \;\; \textbf{P}(x)  \qquad \ldots \qquad}{ \textbf{H}  \;\;\vdash\;\;  \textbf{P}(x) } where x has inductive datatype DT as type and appears free in \textbf{P}; \{p_{I_1}, \ldots, p_{I_l}\} \subseteq \{p_1, \ldots, p_k\} are the inductive parameters (if any); an antecedent is created for every constructor c_i of DT; all parameters are introduced as fresh identifiers; examples here M