Top.Util.FSetDecide

FSetDecide.v

Author: Aaron Bohannon

This file implements a decision procedure for a certain class of propositions involving finite sets.

Module Decide (Import M : S).

Overview

This functor defines the tactic fsetdec, which will solve any valid goal of the form

    forall s1 ... sn,
    forall x1 ... xm,
    P1 -> ... -> Pk -> P

where P's are defined by the grammar:

P ::=
| Q
| Empty F
| Subset F F'
| Equal F F'

Q ::=
| E.eq X X'
| In X F
| Q /\ Q'
| Q \/ Q'
| Q -> Q'
| Q <-> Q'
| ~ Q
| True
| False

F ::=
| S
| empty
| singleton X
| add X F
| remove X F
| union F F'
| inter F F'
| diff F F'

X ::= x1 | ... | xm
S ::= s1 | ... | sn

The tactic will also work on some goals that vary slightly from the above form:

• The variables and hypotheses may be mixed in any order and may have already been introduced into the context. Moreover, there may be additional, unrelated hypotheses mixed in (these will be ignored).
• A conjunction of hypotheses will be handled as easily as separate hypotheses, i.e., P1 ∧ P2 → P can be solved iff P1 → P2 → P can be solved.
• fsetdec should solve any goal if the FSet-related hypotheses are contradictory.
• fsetdec will first perform any necessary zeta and beta reductions and will invoke subst to eliminate any Coq equalities between finite sets or their elements.
• If E.eq is convertible with Coq's equality, it will not matter which one is used in the hypotheses or conclusion.
• The tactic can solve goals where the finite sets or set elements are expressed by Coq terms that are more complicated than variables. However, non-local definitions are not expanded, and Coq equalities between non-variable terms are not used. For example, this goal will be solved:

      forall (f : t -> t),
      forall (g : elt -> elt),
      forall (s1 s2 : t),
      forall (x1 x2 : elt),
      Equal s1 (f s2) ->
      E.eq x1 (g (g x2)) ->
      In x1 s1 ->
      In (g (g x2)) (f s2)
  

  This one will not be solved:

      forall (f : t -> t),
      forall (g : elt -> elt),
      forall (s1 s2 : t),
      forall (x1 x2 : elt),
      Equal s1 (f s2) ->
      E.eq x1 (g x2) ->
      In x1 s1 ->
      g x2 = g (g x2) ->
      In (g (g x2)) (f s2)
  

Facts and Tactics for Propositional Logic

These lemmas and tactics are in a module so that they do not affect the namespace if you import the enclosing module Decide.

  Module FSetLogicalFacts.

Lemmas and Tactics About Decidable Propositions

XXX: The lemma dec_iff should have been included in Decidable.v. Some form of the solve_decidable tactics below would also make sense in Decidable.v.

    Lemma dec_iff : ∀ P Q : Prop,
      decidable P →
      decidable Q →
      decidable (P ↔ Q).

With this hint database, we can leverage auto to check decidability of propositions.

solve_decidable using lib will solve goals about the decidability of a proposition, assisted by an auxiliary database of lemmas. The database is intended to contain lemmas stating the decidability of base propositions, (e.g., the decidability of equality on a particular inductive type).

    Tactic Notation "solve_decidable" "using" ident(db) :=
      match goal with
      | |- decidable ?P ⇒
        solve [ auto 100 with decidable_prop db ]
      end.

    Tactic Notation "solve_decidable" :=
      solve_decidable using core.

Propositional Equivalences Involving Negation

These are all written with the unfolded form of negation, since I am not sure if setoid rewriting will always perform conversion.

Eliminating Negations

We begin with lemmas that, when read from left to right, can be understood as ways to eliminate uses of not.

    Lemma not_true_iff :
      (True → False) ↔ False.

    Lemma not_false_iff :
      (False → False) ↔ True.

    Lemma not_not_iff : ∀ P : Prop,
      decidable P →
      (((P → False) → False) ↔ P).

    Lemma contrapositive : ∀ P Q : Prop,
      decidable P →
      (((P → False) → (Q → False)) ↔ (Q → P)).

    Lemma or_not_l_iff_1 : ∀ P Q : Prop,
      decidable P →
      ((P → False) ∨ Q ↔ (P → Q)).

    Lemma or_not_l_iff_2 : ∀ P Q : Prop,
      decidable Q →
      ((P → False) ∨ Q ↔ (P → Q)).

    Lemma or_not_r_iff_1 : ∀ P Q : Prop,
      decidable P →
      (P ∨ (Q → False) ↔ (Q → P)).

    Lemma or_not_r_iff_2 : ∀ P Q : Prop,
      decidable Q →
      (P ∨ (Q → False) ↔ (Q → P)).

    Lemma imp_not_l : ∀ P Q : Prop,
      decidable P →
      (((P → False) → Q) ↔ (P ∨ Q)).

Moving Negations Around

We have four lemmas that, when read from left to right, describe how to push negations toward the leaves of a proposition and, when read from right to left, describe how to pull negations toward the top of a proposition.

    Lemma not_or_iff : ∀ P Q : Prop,
      (P ∨ Q → False) ↔ (P → False) ∧ (Q → False).

    Lemma not_and_iff : ∀ P Q : Prop,
      (P ∧ Q → False) ↔ (P → Q → False).

    Lemma not_imp_iff : ∀ P Q : Prop,
      decidable P →
      (((P → Q) → False) ↔ P ∧ (Q → False)).

    Lemma not_imp_rev_iff : ∀ P Q : Prop,
      decidable P →
      (((P → Q) → False) ↔ (Q → False) ∧ P).

Tactics for Negations

    Tactic Notation "fold" "any" "not" :=
      repeat (
        match goal with
        | H: context [?P → False] |- _ ⇒
          fold (¬ P) in H
        | |- context [?P → False] ⇒
          fold (¬ P)
        end).

push not using db will pushes all negations to the leaves of propositions in the goal, using the lemmas in db to assist in checking the decidability of the propositions involved. If using db is omitted, then core will be used. Additional versions are provided to manipulate the hypotheses or the hypotheses and goal together.

XXX: This tactic and the similar subsequent ones should have been defined using autorewrite. However, there is a bug in the order that Coq generates subgoals when rewriting using a setoid. In order to work around this bug, these tactics had to be written out in an explicit way. When the bug is fixed these tactics will break!!

    Tactic Notation "push" "not" "using" ident(db) :=
      unfold not, iff;
      repeat (
        match goal with
        

simplification by not_true_iff

        | |- context [True → False] ⇒
          rewrite not_true_iff
        

simplification by not_false_iff

        | |- context [False → False] ⇒
          rewrite not_false_iff
        

simplification by not_not_iff

        | |- context [(?P → False) → False] ⇒
          rewrite (not_not_iff P);
            [ solve_decidable using db | ]
        

simplification by contrapositive

        | |- context [(?P → False) → (?Q → False)] ⇒
          rewrite (contrapositive P Q);
            [ solve_decidable using db | ]
        

simplification by or_not_l_iff_1/2

        | |- context [(?P → False) ∨ ?Q] ⇒
          (rewrite (or_not_l_iff_1 P Q);
            [ solve_decidable using db | ]) ||
          (rewrite (or_not_l_iff_2 P Q);
            [ solve_decidable using db | ])
        

simplification by or_not_r_iff_1/2

        | |- context [?P ∨ (?Q → False)] ⇒
          (rewrite (or_not_r_iff_1 P Q);
            [ solve_decidable using db | ]) ||
          (rewrite (or_not_r_iff_2 P Q);
            [ solve_decidable using db | ])
        

simplification by imp_not_l

        | |- context [(?P → False) → ?Q] ⇒
          rewrite (imp_not_l P Q);
            [ solve_decidable using db | ]
        

rewriting by not_or_iff

        | |- context [?P ∨ ?Q → False] ⇒
          rewrite (not_or_iff P Q)
        

rewriting by not_and_iff

        | |- context [?P ∧ ?Q → False] ⇒
          rewrite (not_and_iff P Q)
        

rewriting by not_imp_iff

        | |- context [(?P → ?Q) → False] ⇒
          rewrite (not_imp_iff P Q);
            [ solve_decidable using db | ]
        end);
      fold any not.

    Tactic Notation "push" "not" :=
      push not using core.

    Tactic Notation
      "push" "not" "in" "*" "|-" "using" ident(db) :=
      unfold not, iff in × |-;
      repeat (
        match goal with
        

simplification by not_true_iff

        | H: context [True → False] |- _ ⇒
          rewrite not_true_iff in H
        

simplification by not_false_iff

        | H: context [False → False] |- _ ⇒
          rewrite not_false_iff in H
        

simplification by not_not_iff

        | H: context [(?P → False) → False] |- _ ⇒
          rewrite (not_not_iff P) in H;
            [ | solve_decidable using db ]
        

simplification by contrapositive

        | H: context [(?P → False) → (?Q → False)] |- _ ⇒
          rewrite (contrapositive P Q) in H;
            [ | solve_decidable using db ]
        

simplification by or_not_l_iff_1/2

        | H: context [(?P → False) ∨ ?Q] |- _ ⇒
          (rewrite (or_not_l_iff_1 P Q) in H;
            [ | solve_decidable using db ]) ||
          (rewrite (or_not_l_iff_2 P Q) in H;
            [ | solve_decidable using db ])
        

simplification by or_not_r_iff_1/2

        | H: context [?P ∨ (?Q → False)] |- _ ⇒
          (rewrite (or_not_r_iff_1 P Q) in H;
            [ | solve_decidable using db ]) ||
          (rewrite (or_not_r_iff_2 P Q) in H;
            [ | solve_decidable using db ])
        

simplification by imp_not_l

        | H: context [(?P → False) → ?Q] |- _ ⇒
          rewrite (imp_not_l P Q) in H;
            [ | solve_decidable using db ]
        

rewriting by not_or_iff

        | H: context [?P ∨ ?Q → False] |- _ ⇒
          rewrite (not_or_iff P Q) in H
        

rewriting by not_and_iff

        | H: context [?P ∧ ?Q → False] |- _ ⇒
          rewrite (not_and_iff P Q) in H
        

rewriting by not_imp_iff

        | H: context [(?P → ?Q) → False] |- _ ⇒
          rewrite (not_imp_iff P Q) in H;
            [ | solve_decidable using db ]
        end);
      fold any not.

    Tactic Notation "push" "not" "in" "*" "|-" :=
      push not in × |- using core.

    Tactic Notation "push" "not" "in" "*" "using" ident(db) :=
      push not using db; push not in × |- using db.
    Tactic Notation "push" "not" "in" "*" :=
      push not in × using core.

A simple test case to see how this works.

    Lemma test_push : ∀ P Q R : Prop,
      decidable P →
      decidable Q →
      (¬ True) →
      (¬ False) →
      (¬ ¬ P) →
      (¬ (P ∧ Q) → ¬ R) →
      ((P ∧ Q) ∨ ¬ R) →
      (¬ (P ∧ Q) ∨ R) →
      (R ∨ ¬ (P ∧ Q)) →
      (¬ R ∨ (P ∧ Q)) →
      (¬ P → R) →
      (¬ ((R → P) ∨ (R → Q))) →
      (¬ (P ∧ R)) →
      (¬ (P → R)) →
      True.

pull not using db will pull as many negations as possible toward the top of the propositions in the goal, using the lemmas in db to assist in checking the decidability of the propositions involved. If using db is omitted, then core will be used. Additional versions are provided to manipulate the hypotheses or the hypotheses and goal together.

    Tactic Notation "pull" "not" "using" ident(db) :=
      unfold not, iff;
      repeat (
        match goal with
        

simplification by not_true_iff

        | |- context [True → False] ⇒
          rewrite not_true_iff
        

simplification by not_false_iff

        | |- context [False → False] ⇒
          rewrite not_false_iff
        

simplification by not_not_iff

        | |- context [(?P → False) → False] ⇒
          rewrite (not_not_iff P);
            [ solve_decidable using db | ]
        

simplification by contrapositive

        | |- context [(?P → False) → (?Q → False)] ⇒
          rewrite (contrapositive P Q);
            [ solve_decidable using db | ]
        

simplification by or_not_l_iff_1/2

        | |- context [(?P → False) ∨ ?Q] ⇒
          (rewrite (or_not_l_iff_1 P Q);
            [ solve_decidable using db | ]) ||
          (rewrite (or_not_l_iff_2 P Q);
            [ solve_decidable using db | ])
        

simplification by or_not_r_iff_1/2

        | |- context [?P ∨ (?Q → False)] ⇒
          (rewrite (or_not_r_iff_1 P Q);
            [ solve_decidable using db | ]) ||
          (rewrite (or_not_r_iff_2 P Q);
            [ solve_decidable using db | ])
        

simplification by imp_not_l

        | |- context [(?P → False) → ?Q] ⇒
          rewrite (imp_not_l P Q);
            [ solve_decidable using db | ]
        

rewriting by not_or_iff

        | |- context [(?P → False) ∧ (?Q → False)] ⇒
          rewrite <- (not_or_iff P Q)
        

rewriting by not_and_iff

        | |- context [?P → ?Q → False] ⇒
          rewrite <- (not_and_iff P Q)
        

rewriting by not_imp_iff

        | |- context [?P ∧ (?Q → False)] ⇒
          rewrite <- (not_imp_iff P Q);
            [ solve_decidable using db | ]
        

rewriting by not_imp_rev_iff

        | |- context [(?Q → False) ∧ ?P] ⇒
          rewrite <- (not_imp_rev_iff P Q);
            [ solve_decidable using db | ]
        end);
      fold any not.

    Tactic Notation "pull" "not" :=
      pull not using core.

    Tactic Notation
      "pull" "not" "in" "*" "|-" "using" ident(db) :=
      unfold not, iff in × |-;
      repeat (
        match goal with
        

simplification by not_true_iff

        | H: context [True → False] |- _ ⇒
          rewrite not_true_iff in H
        

simplification by not_false_iff

        | H: context [False → False] |- _ ⇒
          rewrite not_false_iff in H
        

simplification by not_not_iff

        | H: context [(?P → False) → False] |- _ ⇒
          rewrite (not_not_iff P) in H;
            [ | solve_decidable using db ]
        

simplification by contrapositive

        | H: context [(?P → False) → (?Q → False)] |- _ ⇒
          rewrite (contrapositive P Q) in H;
            [ | solve_decidable using db ]
        

simplification by or_not_l_iff_1/2

        | H: context [(?P → False) ∨ ?Q] |- _ ⇒
          (rewrite (or_not_l_iff_1 P Q) in H;
            [ | solve_decidable using db ]) ||
          (rewrite (or_not_l_iff_2 P Q) in H;
            [ | solve_decidable using db ])
        

simplification by or_not_r_iff_1/2

        | H: context [?P ∨ (?Q → False)] |- _ ⇒
          (rewrite (or_not_r_iff_1 P Q) in H;
            [ | solve_decidable using db ]) ||
          (rewrite (or_not_r_iff_2 P Q) in H;
            [ | solve_decidable using db ])
        

simplification by imp_not_l

        | H: context [(?P → False) → ?Q] |- _ ⇒
          rewrite (imp_not_l P Q) in H;
            [ | solve_decidable using db ]
        

rewriting by not_or_iff

        | H: context [(?P → False) ∧ (?Q → False)] |- _ ⇒
          rewrite <- (not_or_iff P Q) in H
        

rewriting by not_and_iff

        | H: context [?P → ?Q → False] |- _ ⇒
          rewrite <- (not_and_iff P Q) in H
        

rewriting by not_imp_iff

        | H: context [?P ∧ (?Q → False)] |- _ ⇒
          rewrite <- (not_imp_iff P Q) in H;
            [ | solve_decidable using db ]
        

rewriting by not_imp_rev_iff

        | H: context [(?Q → False) ∧ ?P] |- _ ⇒
          rewrite <- (not_imp_rev_iff P Q) in H;
            [ | solve_decidable using db ]
        end);
      fold any not.

    Tactic Notation "pull" "not" "in" "*" "|-" :=
      pull not in × |- using core.

    Tactic Notation "pull" "not" "in" "*" "using" ident(db) :=
      pull not using db; pull not in × |- using db.
    Tactic Notation "pull" "not" "in" "*" :=
      pull not in × using core.

A simple test case to see how this works.

    Lemma test_pull : ∀ P Q R : Prop,
      decidable P →
      decidable Q →
      (¬ True) →
      (¬ False) →
      (¬ ¬ P) →
      (¬ (P ∧ Q) → ¬ R) →
      ((P ∧ Q) ∨ ¬ R) →
      (¬ (P ∧ Q) ∨ R) →
      (R ∨ ¬ (P ∧ Q)) →
      (¬ R ∨ (P ∧ Q)) →
      (¬ P → R) →
      (¬ (R → P) ∧ ¬ (R → Q)) →
      (¬ P ∨ ¬ R) →
      (P ∧ ¬ R) →
      (¬ R ∧ P) →
      True.

  End FSetLogicalFacts.

Auxiliary Tactics

Again, these lemmas and tactics are in a module so that they do not affect the namespace if you import the enclosing module Decide.

  Module FSetDecideAuxiliary.

Generic Tactics

We begin by defining a few generic, useful tactics.

if t then t1 else t2 executes t and, if it does not fail, then t1 will be applied to all subgoals produced. If t fails, then t2 is executed.

    Tactic Notation
      "if" tactic(t)
      "then" tactic(t1)
      "else" tactic(t2) :=
      first [ t; first [ t1 | fail 2 ] | t2 ].

prop P holds by t succeeds (but does not modify the goal or context) if the proposition P can be proved by t in the current context. Otherwise, the tactic fails.

    Tactic Notation "prop" constr(P) "holds" "by" tactic(t) :=
      let H := fresh in
      assert P as H by t;
      clear H.

This tactic acts just like assert ... by ... but will fail if the context already contains the proposition.

    Tactic Notation "assert" "new" constr(e) "by" tactic(t) :=
      match goal with
      | H: e |- _ ⇒ fail 1
      | _ ⇒ assert e by t
      end.

subst++ is similar to subst except that

• it never fails (as subst does on recursive equations),
• it substitutes locally defined variable for their definitions,
• it performs beta reductions everywhere, which may arise after substituting a locally defined function for its definition.

    Tactic Notation "subst" "++" :=
      repeat (
        match goal with
        | x : _ |- _ ⇒ subst x
        end);
      cbv zeta beta in ×.

If you have a negated goal and H is a negated hypothesis, then contra H exchanges your goal and H, removing the negations. (Just like swap but reuses the same name.

decompose records calls decompose record H on every relevant hypothesis H.

    Tactic Notation "decompose" "records" :=
      repeat (
        match goal with
        | H: _ |- _ ⇒ progress (decompose record H); clear H
        end).

Discarding Irrelevant Hypotheses

We will want to clear the context of any non-FSet-related hypotheses in order to increase the speed of the tactic. To do this, we will need to be able to decide which are relevant. We do this by making a simple inductive definition classifying the propositions of interest.

    Inductive FSet_elt_Prop : Prop → Prop :=
    | eq_Prop : ∀ (S : Set) (x y : S),
        FSet_elt_Prop (x = y)
    | eq_elt_prop : ∀ x y,
        FSet_elt_Prop (E.eq x y)
    | In_elt_prop : ∀ x s,
        FSet_elt_Prop (In x s)
    | True_elt_prop :
        FSet_elt_Prop True
    | False_elt_prop :
        FSet_elt_Prop False
    | conj_elt_prop : ∀ P Q,
        FSet_elt_Prop P →
        FSet_elt_Prop Q →
        FSet_elt_Prop (P ∧ Q)
    | disj_elt_prop : ∀ P Q,
        FSet_elt_Prop P →
        FSet_elt_Prop Q →
        FSet_elt_Prop (P ∨ Q)
    | impl_elt_prop : ∀ P Q,
        FSet_elt_Prop P →
        FSet_elt_Prop Q →
        FSet_elt_Prop (P → Q)
    | not_elt_prop : ∀ P,
        FSet_elt_Prop P →
        FSet_elt_Prop (¬ P).

    Inductive FSet_Prop : Prop → Prop :=
    | elt_FSet_Prop : ∀ P,
        FSet_elt_Prop P →
        FSet_Prop P
    | Empty_FSet_Prop : ∀ s,
        FSet_Prop (Empty s)
    | Subset_FSet_Prop : ∀ s1 s2,
        FSet_Prop (Subset s1 s2)
    | Equal_FSet_Prop : ∀ s1 s2,
        FSet_Prop (Equal s1 s2).

Here is the tactic that will throw away hypotheses that are not useful (for the intended scope of the fsetdec tactic).

Turning Set Operators into Propositional Connectives

The lemmas from FSetFacts will be used to break down set operations into propositional formulas built over the predicates In and E.eq applied only to variables. We are going to use them with autorewrite.

    Module F := FSetFacts.Facts M.

Decidability of FSet Propositions

In is decidable.

    Module D := DepOfNodep M.
    Lemma dec_In : ∀ x s,
      decidable (In x s).

E.eq is decidable.

    Module OTE := MOT_to_OT E.
    Lemma dec_eq : ∀ (x y : E.t),
      decidable (E.eq x y).

The hint database FSet_decidability will be given to the push_neg tactic from the module Negation.

Normalizing Propositions About Equality

We have to deal with the fact that E.eq may be convertible with Coq's equality. Thus, we will find the following tactics useful to replace one form with the other everywhere.

The next tactic, Logic_eq_to_E_eq, mentions the term E.t; thus, we must ensure that E.t is used in favor of any other convertible but syntactically distinct term.

These two tactics take us from Coq's built-in equality to E.eq (and vice versa) when possible.

This tactic works like the built-in tactic subst, but at the level of set element equality (which may not be the convertible with Coq's equality).

Considering Decidability of Base Propositions

This tactic adds assertions about the decidability of E.eq and In to the context. This is necessary for the completeness of the fsetdec tactic. However, in order to minimize the cost of proof search, we should be careful to not add more than we need. Once negations have been pushed to the leaves of the propositions, we only need to worry about decidability for those base propositions that appear in a negated form.

Handling Empty, Subset, and Equal

This tactic instantiates universally quantified hypotheses (which arise from the unfolding of Empty, Subset, and Equal) for each of the set element expressions that is involved in some membership or equality fact. Then it throws away those hypotheses, which should no longer be needed.

The Core fsetdec Auxiliary Tactics

Here is the crux of the proof search. Recursion through intuition! (This will terminate if I correctly understand the behavior of intuition.)

If we add unfold Empty, Subset, Equal in *; intros; to the beginning of this tactic, it will satisfy the same specification as the fsetdec tactic; however, it will be much slower than necessary without the pre-processing done by the wrapper tactic fsetdec.

  End FSetDecideAuxiliary.

The fsetdec Tactic

Here is the top-level tactic (the only one intended for clients of this library). It's specification is given at the top of the file.

Examples

  Module FSetDecideTestCases.

    Lemma test_eq_trans_1 : ∀ x y z s,
      E.eq x y →
      ¬ ¬ E.eq z y →
      In x s →
      In z s.

    Lemma test_eq_trans_2 : ∀ x y z r s,
      In x (singleton y) →
      ¬ In z r →
      ¬ ¬ In z (add y r) →
      In x s →
      In z s.

    Lemma test_eq_neq_trans_1 : ∀ w x y z s,
      E.eq x w →
      ¬ ¬ E.eq x y →
      ¬ E.eq y z →
      In w s →
      In w (remove z s).

    Lemma test_eq_neq_trans_2 : ∀ w x y z r1 r2 s,
      In x (singleton w) →
      ¬ In x r1 →
      In x (add y r1) →
      In y r2 →
      In y (remove z r2) →
      In w s →
      In w (remove z s).

    Lemma test_In_singleton : ∀ x,
      In x (singleton x).

    Lemma test_Subset_add_remove : ∀ x s,
      s [<=] (add x (remove x s)).

    Lemma test_eq_disjunction : ∀ w x y z,
      In w (add x (add y (singleton z))) →
      E.eq w x ∨ E.eq w y ∨ E.eq w z.

    Lemma test_not_In_disj : ∀ x y s1 s2 s3 s4,
      ¬ In x (union s1 (union s2 (union s3 (add y s4)))) →
      ¬ (In x s1 ∨ In x s4 ∨ E.eq y x).

    Lemma test_not_In_conj : ∀ x y s1 s2 s3 s4,
      ¬ In x (union s1 (union s2 (union s3 (add y s4)))) →
      ¬ In x s1 ∧ ¬ In x s4 ∧ ¬ E.eq y x.

    Lemma test_iff_conj : ∀ a x s s',
    (In a s' ↔ E.eq x a ∨ In a s) →
    (In a s' ↔ In a (add x s)).

    Lemma test_set_ops_1 : ∀ x q r s,
      (singleton x) [<=] s →
      Empty (union q r) →
      Empty (inter (diff s q) (diff s r)) →
      ¬ In x s.

    Lemma eq_chain_test : ∀ x1 x2 x3 x4 s1 s2 s3 s4,
      Empty s1 →
      In x2 (add x1 s1) →
      In x3 s2 →
      ¬ In x3 (remove x2 s2) →
      ¬ In x4 s3 →
      In x4 (add x3 s3) →
      In x1 s4 →
      Subset (add x4 s4) s4.

    Lemma test_too_complex : ∀ x y z r s,
      E.eq x y →
      (In x (singleton y) → r [<=] s) →
      In z r →
      In z s.

fsetdec is not intended to solve this directly.

    Lemma function_test_1 :
      ∀ (f : t → t),
      ∀ (g : elt → elt),
      ∀ (s1 s2 : t),
      ∀ (x1 x2 : elt),
      Equal s1 (f s2) →
      E.eq x1 (g (g x2)) →
      In x1 s1 →
      In (g (g x2)) (f s2).

    Lemma function_test_2 :
      ∀ (f : t → t),
      ∀ (g : elt → elt),
      ∀ (s1 s2 : t),
      ∀ (x1 x2 : elt),
      Equal s1 (f s2) →
      E.eq x1 (g x2) →
      In x1 s1 →
      g x2 = g (g x2) →
      In (g (g x2)) (f s2).

fsetdec is not intended to solve this directly.

  End FSetDecideTestCases.

End Decide.