Welcome to Abella 2.0.4-dev

Abella <Specification "breduce".Reading specification "breduce"

Abella <Close tm, p.

Abella <Define ctx2 : olist -> olist -> prop by ctx2 nil nil; nabla x p, ctx2 (bred x x :: G) (path x p :: D) := ctx2 G D; nabla x, ctx2 ((pi u\bred N u => bred x u) :: G) ((pi q\path N q => path x q) :: D) := ctx2 G D.

Abella <Define name : tm -> prop by nabla n, name n.

Abella <Define fresh : tm -> tm -> prop by nabla n, fresh n X.

Abella <Define pname : p -> prop by nabla p, pname p.

Abella <Theorem ctx2_mem_G : forall G D F, ctx2 G D -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N).

============================ forall G D F, ctx2 G D -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <induction on 1.

IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ============================ forall G D F, ctx2 G D @ -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <intros.

Variables: G D F IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H1 : ctx2 G D @ H2 : member F G ============================ (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H1.

Subgoal 1: Variables: F IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H2 : member F nil ============================ (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) Subgoal 2 is: (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H2.

Subgoal 2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H2 : member (F n1 n2) (bred n1 n1 :: G1) H3 : ctx2 G1 D1 * ============================ (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H2.

Subgoal 2.1: Variables: D1 G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * ============================ (exists x, bred n1 n1 = bred x x /\ name x) \/ (exists x N, bred n1 n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 2.2 is: (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <search.

Subgoal 2.2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1 n2) G1 ============================ (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <apply IH to H3 H4.

Subgoal 2.2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1 n2) G1 H5 : (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) ============================ (exists x, F n1 n2 = bred x x /\ name x) \/ (exists x N, F n1 n2 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H5.

Subgoal 2.2.1: Variables: D1 G1 x IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (bred (x n1) (x n1)) G1 H6 : name (x n1) ============================ (exists x1, bred (x n1) (x n1) = bred x1 x1 /\ name x1) \/ (exists x1 N, bred (x n1) (x n1) = pi u\bred N u => bred x1 u /\ fresh x1 N) Subgoal 2.2.2 is: (exists x1, pi u\bred (N n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N1, pi u\bred (N n1) u => bred (x n1) u = pi u\bred N1 u => bred x1 u /\ fresh x1 N1) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <search.

Subgoal 2.2.2: Variables: D1 G1 x N IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (pi u\bred (N n1) u => bred (x n1) u) G1 H6 : fresh (x n1) (N n1) ============================ (exists x1, pi u\bred (N n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N1, pi u\bred (N n1) u => bred (x n1) u = pi u\bred N1 u => bred x1 u /\ fresh x1 N1) Subgoal 3 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <search.

Subgoal 3: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H2 : member (F n1) ((pi u\bred N u => bred n1 u) :: G1) H3 : ctx2 G1 D1 * ============================ (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H2.

Subgoal 3.1: Variables: D1 N G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * ============================ (exists x, pi u\bred N u => bred n1 u = bred x x /\ name x) \/ (exists x N1, pi u\bred N u => bred n1 u = pi u\bred N1 u => bred x u /\ fresh x N1) Subgoal 3.2 is: (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <search.

Subgoal 3.2: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1) G1 ============================ (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <apply IH to H3 H4.

Subgoal 3.2: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1) G1 H5 : (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ============================ (exists x, F n1 = bred x x /\ name x) \/ (exists x N, F n1 = pi u\bred N u => bred x u /\ fresh x N) ctx2_mem_G <case H5.

Subgoal 3.2.1: Variables: D1 N G1 x IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (bred (x n1) (x n1)) G1 H6 : name (x n1) ============================ (exists x1, bred (x n1) (x n1) = bred x1 x1 /\ name x1) \/ (exists x1 N, bred (x n1) (x n1) = pi u\bred N u => bred x1 u /\ fresh x1 N) Subgoal 3.2.2 is: (exists x1, pi u\bred (N1 n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N, pi u\bred (N1 n1) u => bred (x n1) u = pi u\bred N u => bred x1 u /\ fresh x1 N) ctx2_mem_G <search.

Subgoal 3.2.2: Variables: D1 N G1 x N1 IH : forall G D F, ctx2 G D * -> member F G -> (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (pi u\bred (N1 n1) u => bred (x n1) u) G1 H6 : fresh (x n1) (N1 n1) ============================ (exists x1, pi u\bred (N1 n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N, pi u\bred (N1 n1) u => bred (x n1) u = pi u\bred N u => bred x1 u /\ fresh x1 N) ctx2_mem_G <search.Proof completed.

Abella <Theorem ctx2_mem_D : forall G D F, ctx2 G D -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N).

============================ forall G D F, ctx2 G D -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <induction on 1.

IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ forall G D F, ctx2 G D @ -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <intros.

Variables: G D F IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H1 : ctx2 G D @ H2 : member F D ============================ (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H1.

Subgoal 1: Variables: F IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H2 : member F nil ============================ (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) Subgoal 2 is: (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H2.

Subgoal 2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H2 : member (F n1 n2) (path n1 n2 :: D1) H3 : ctx2 G1 D1 * ============================ (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H2.

Subgoal 2.1: Variables: D1 G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * ============================ (exists x p, path n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, path n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 2.2 is: (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <search.

Subgoal 2.2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1 n2) D1 ============================ (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <apply IH to H3 H4.

Subgoal 2.2: Variables: F D1 G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1 n2) D1 H5 : (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) ============================ (exists x p, F n1 n2 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 n2 = pi q\path N q => path x q /\ fresh x N) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H5.

Subgoal 2.2.1: Variables: D1 G1 x p IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (path (x n1) (p n2)) D1 H6 : name (x n1) H7 : pname (p n2) ============================ (exists x1 p1, path (x n1) (p n2) = path x1 p1 /\ name x1 /\ pname p1) \/ (exists x1 N, path (x n1) (p n2) = pi q\path N q => path x1 q /\ fresh x1 N) Subgoal 2.2.2 is: (exists x1 p, pi q\path (N n1) q => path (x n1) q = path x1 p /\ name x1 /\ pname p) \/ (exists x1 N1, pi q\path (N n1) q => path (x n1) q = pi q\path N1 q => path x1 q /\ fresh x1 N1) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <search.

Subgoal 2.2.2: Variables: D1 G1 x N IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (pi q\path (N n1) q => path (x n1) q) D1 H6 : fresh (x n1) (N n1) ============================ (exists x1 p, pi q\path (N n1) q => path (x n1) q = path x1 p /\ name x1 /\ pname p) \/ (exists x1 N1, pi q\path (N n1) q => path (x n1) q = pi q\path N1 q => path x1 q /\ fresh x1 N1) Subgoal 3 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <search.

Subgoal 3: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H2 : member (F n1) ((pi q\path N q => path n1 q) :: D1) H3 : ctx2 G1 D1 * ============================ (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H2.

Subgoal 3.1: Variables: D1 N G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * ============================ (exists x p, pi q\path N q => path n1 q = path x p /\ name x /\ pname p) \/ (exists x N1, pi q\path N q => path n1 q = pi q\path N1 q => path x q /\ fresh x N1) Subgoal 3.2 is: (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <search.

Subgoal 3.2: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1) D1 ============================ (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <apply IH to H3 H4.

Subgoal 3.2: Variables: F D1 N G1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (F n1) D1 H5 : (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ============================ (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ctx2_mem_D <case H5.

Subgoal 3.2.1: Variables: D1 N G1 x p IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (path (x n1) p) D1 H6 : name (x n1) H7 : pname p ============================ (exists x1 p1, path (x n1) p = path x1 p1 /\ name x1 /\ pname p1) \/ (exists x1 N, path (x n1) p = pi q\path N q => path x1 q /\ fresh x1 N) Subgoal 3.2.2 is: (exists x1 p, pi q\path (N1 n1) q => path (x n1) q = path x1 p /\ name x1 /\ pname p) \/ (exists x1 N, pi q\path (N1 n1) q => path (x n1) q = pi q\path N q => path x1 q /\ fresh x1 N) ctx2_mem_D <search.

Subgoal 3.2.2: Variables: D1 N G1 x N1 IH : forall G D F, ctx2 G D * -> member F D -> (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) H3 : ctx2 G1 D1 * H4 : member (pi q\path (N1 n1) q => path (x n1) q) D1 H6 : fresh (x n1) (N1 n1) ============================ (exists x1 p, pi q\path (N1 n1) q => path (x n1) q = path x1 p /\ name x1 /\ pname p) \/ (exists x1 N, pi q\path (N1 n1) q => path (x n1) q = pi q\path N q => path x1 q /\ fresh x1 N) ctx2_mem_D <search.Proof completed.

Abella <Theorem ctx2_uniform : forall G D X, nabla n, ctx2 (G n) (D n) -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n).

============================ forall G D X, nabla n, ctx2 (G n) (D n) -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) ctx2_uniform <induction on 1.

IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) ============================ forall G D X, nabla n, ctx2 (G n) (D n) @ -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) ctx2_uniform <intros.

Variables: G D X IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H1 : ctx2 (G n1) (D n1) @ H2 : member (pi u\bred X u => bred n1 u) (G n1) ============================ member (pi q\path X q => path n1 q) (D n1) ctx2_uniform <case H1.

Subgoal 1: Variables: X IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H2 : member (pi u\bred X u => bred n1 u) nil ============================ member (pi q\path X q => path n1 q) nil Subgoal 2 is: member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) Subgoal 3 is: member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <case H2.

Subgoal 2: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H2 : member (pi u\bred (X n2) u => bred n1 u) (bred n2 n2 :: G1 n1) H3 : ctx2 (G1 n1) (D1 n1) * ============================ member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) Subgoal 3 is: member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <case H2.

Subgoal 2: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 (G1 n1) (D1 n1) * H4 : member (pi u\bred (X n2) u => bred n1 u) (G1 n1) ============================ member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) Subgoal 3 is: member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <apply IH to H3 H4.

Subgoal 2: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 (G1 n1) (D1 n1) * H4 : member (pi u\bred (X n2) u => bred n1 u) (G1 n1) H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) Subgoal 3 is: member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <search.

Subgoal 3: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H2 : member (pi u\bred X u => bred n1 u) (bred n1 n1 :: G1) H3 : ctx2 G1 D1 * ============================ member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <case H2.

Subgoal 3: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 G1 D1 * H4 : member (pi u\bred X u => bred n1 u) G1 ============================ member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <apply IH to H3 H4.

Subgoal 3: Variables: X D1 G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 G1 D1 * H4 : member (pi u\bred X u => bred n1 u) G1 H5 : member (pi q\path X q => path n1 q) D1 ============================ member (pi q\path X q => path n1 q) (path n1 n2 :: D1) Subgoal 4 is: member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <search.

Subgoal 4: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H2 : member (pi u\bred (X n2) u => bred n1 u) ((pi u\bred (N n1) u => bred n2 u) :: G1 n1) H3 : ctx2 (G1 n1) (D1 n1) * ============================ member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <case H2.

Subgoal 4: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 (G1 n1) (D1 n1) * H4 : member (pi u\bred (X n2) u => bred n1 u) (G1 n1) ============================ member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <apply IH to H3 H4.

Subgoal 4: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 (G1 n1) (D1 n1) * H4 : member (pi u\bred (X n2) u => bred n1 u) (G1 n1) H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) Subgoal 5 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <search.

Subgoal 5: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H2 : member (pi u\bred X u => bred n1 u) ((pi u\bred N u => bred n1 u) :: G1) H3 : ctx2 G1 D1 * ============================ member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <case H2.

Subgoal 5.1: Variables: D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 G1 D1 * ============================ member (pi q\path N q => path n1 q) ((pi q\path N q => path n1 q) :: D1) Subgoal 5.2 is: member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <search.

Subgoal 5.2: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 G1 D1 * H4 : member (pi u\bred X u => bred n1 u) G1 ============================ member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <apply IH to H3 H4.

Subgoal 5.2: Variables: X D1 N G1 IH : forall G D X, nabla n, ctx2 (G n) (D n) * -> member (pi u\bred X u => bred n u) (G n) -> member (pi q\path X q => path n q) (D n) H3 : ctx2 G1 D1 * H4 : member (pi u\bred X u => bred n1 u) G1 H5 : member (pi q\path X q => path n1 q) D1 ============================ member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) ctx2_uniform <search.Proof completed.

Abella <Theorem member_prune_D : forall G D E, nabla n, ctx2 G D -> member (E n) D -> (exists F, E = x\F).

============================ forall G D E, nabla n, ctx2 G D -> member (E n) D -> (exists F, E = x\F) member_prune_D <induction on 1.

IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) ============================ forall G D E, nabla n, ctx2 G D @ -> member (E n) D -> (exists F, E = x\F) member_prune_D <intros.

Variables: G D E IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H1 : ctx2 G D @ H2 : member (E n1) D ============================ exists F, E = x\F member_prune_D <case H1.

Subgoal 1: Variables: E IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H2 : member (E n1) nil ============================ exists F, E = x\F Subgoal 2 is: exists F, E n2 n3 = x\F Subgoal 3 is: exists F, E n2 = x\F member_prune_D <case H2.

Subgoal 2: Variables: E D1 G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H2 : member (E n2 n3 n1) (path n2 n3 :: D1) H3 : ctx2 G1 D1 * ============================ exists F, E n2 n3 = x\F Subgoal 3 is: exists F, E n2 = x\F member_prune_D <case H2.

Subgoal 2.1: Variables: D1 G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * ============================ exists F, z3\path n2 n3 = x\F Subgoal 2.2 is: exists F, E n2 n3 = x\F Subgoal 3 is: exists F, E n2 = x\F member_prune_D <search.

Subgoal 2.2: Variables: E D1 G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member (E n2 n3 n1) D1 ============================ exists F, E n2 n3 = x\F Subgoal 3 is: exists F, E n2 = x\F member_prune_D <apply IH to H3 H4.

Subgoal 2.2: Variables: D1 G1 F IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member (F n1 n3) D1 ============================ exists F1, z3\F z3 n3 = x\F1 Subgoal 3 is: exists F, E n2 = x\F member_prune_D <apply IH to H3 H4.

Subgoal 2.2: Variables: D1 G1 F1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member (F1 n3) D1 ============================ exists F2, z3\F1 n3 = x\F2 Subgoal 3 is: exists F, E n2 = x\F member_prune_D <search.

Subgoal 3: Variables: E D1 N G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H2 : member (E n2 n1) ((pi q\path N q => path n2 q) :: D1) H3 : ctx2 G1 D1 * ============================ exists F, E n2 = x\F member_prune_D <case H2.

Subgoal 3.1: Variables: D1 N G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * ============================ exists F, z2\pi q\path N q => path n2 q = x\F Subgoal 3.2 is: exists F, E n2 = x\F member_prune_D <search.

Subgoal 3.2: Variables: E D1 N G1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member (E n2 n1) D1 ============================ exists F, E n2 = x\F member_prune_D <apply IH to H3 H4.

Subgoal 3.2: Variables: D1 N G1 F IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member (F n1) D1 ============================ exists F1, z2\F z2 = x\F1 member_prune_D <apply IH to H3 H4.

Subgoal 3.2: Variables: D1 N G1 F1 IH : forall G D E, nabla n, ctx2 G D * -> member (E n) D -> (exists F, E = x\F) H3 : ctx2 G1 D1 * H4 : member F1 D1 ============================ exists F2, z2\F1 = x\F2 member_prune_D <search.Proof completed.

Abella <Theorem member_D_determinate : forall G D X Y, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y.

============================ forall G D X Y, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y member_D_determinate <induction on 1.

IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y ============================ forall G D X Y, nabla n, ctx2 (G n) (D n) @ -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y member_D_determinate <intros.

Variables: G D X Y IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H1 : ctx2 (G n1) (D n1) @ H2 : member (pi q\path X q => path n1 q) (D n1) H3 : member (pi q\path Y q => path n1 q) (D n1) ============================ X = Y member_D_determinate <case H1.

Subgoal 1: Variables: X Y IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H2 : member (pi q\path X q => path n1 q) nil H3 : member (pi q\path Y q => path n1 q) nil ============================ X = Y Subgoal 2 is: X n2 = Y n2 Subgoal 3 is: X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H2.

Subgoal 2: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H2 : member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) H3 : member (pi q\path (Y n2) q => path n1 q) (path n2 n3 :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * ============================ X n2 = Y n2 Subgoal 3 is: X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H2.

Subgoal 2: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H3 : member (pi q\path (Y n2) q => path n1 q) (path n2 n3 :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ X n2 = Y n2 Subgoal 3 is: X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H3.

Subgoal 2: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) H6 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) ============================ X n2 = Y n2 Subgoal 3 is: X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <apply IH to H4 H5 H6.

Subgoal 2: Variables: Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) H6 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) ============================ Y n2 = Y n2 Subgoal 3 is: X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <search.

Subgoal 3: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H2 : member (pi q\path X q => path n1 q) (path n1 n2 :: D1) H3 : member (pi q\path Y q => path n1 q) (path n1 n2 :: D1) H4 : ctx2 G1 D1 * ============================ X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H2.

Subgoal 3: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H3 : member (pi q\path Y q => path n1 q) (path n1 n2 :: D1) H4 : ctx2 G1 D1 * H5 : member (pi q\path X q => path n1 q) D1 ============================ X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H3.

Subgoal 3: Variables: X Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 G1 D1 * H5 : member (pi q\path X q => path n1 q) D1 H6 : member (pi q\path Y q => path n1 q) D1 ============================ X = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <apply IH to H4 H5 H6.

Subgoal 3: Variables: Y D1 G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 G1 D1 * H5 : member (pi q\path Y q => path n1 q) D1 H6 : member (pi q\path Y q => path n1 q) D1 ============================ Y = Y Subgoal 4 is: X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <search.

Subgoal 4: Variables: X Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H2 : member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H3 : member (pi q\path (Y n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * ============================ X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H2.

Subgoal 4: Variables: X Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H3 : member (pi q\path (Y n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <case H3.

Subgoal 4: Variables: X Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) H6 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) ============================ X n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <apply IH to H4 H5 H6.

Subgoal 4: Variables: Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) H6 : member (pi q\path (Y n2) q => path n1 q) (D1 n1) ============================ Y n2 = Y n2 Subgoal 5 is: X = Y member_D_determinate <search.

Subgoal 5: Variables: X Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H2 : member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H3 : member (pi q\path Y q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H4 : ctx2 G1 D1 * ============================ X = Y member_D_determinate <case H2.

Subgoal 5.1: Variables: Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H3 : member (pi q\path Y q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H4 : ctx2 G1 D1 * ============================ N = Y Subgoal 5.2 is: X = Y member_D_determinate <case H3.

Subgoal 5.1.1: Variables: D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 G1 D1 * ============================ N = N Subgoal 5.1.2 is: N = Y Subgoal 5.2 is: X = Y member_D_determinate <search.

Subgoal 5.1.2: Variables: Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H4 : ctx2 G1 D1 * H5 : member (pi q\path Y q => path n1 q) D1 ============================ N = Y Subgoal 5.2 is: X = Y member_D_determinate <apply member_prune_D to H4 H5.

Subgoal 5.2: Variables: X Y D1 N G1 IH : forall G D X Y, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (pi q\path Y q => path n q) (D n) -> X = Y H3 : member (pi q\path Y q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H4 : ctx2 G1 D1 * H5 : member (pi q\path X q => path n1 q) D1 ============================ X = Y member_D_determinate <apply member_prune_D to H4 H5.Proof completed.

Abella <Theorem member_D_discrim : forall G D X P, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false.

============================ forall G D X P, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false member_D_discrim <induction on 1.

IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false ============================ forall G D X P, nabla n, ctx2 (G n) (D n) @ -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false member_D_discrim <intros.

Variables: G D X P IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H1 : ctx2 (G n1) (D n1) @ H2 : member (pi q\path X q => path n1 q) (D n1) H3 : member (path n1 P) (D n1) ============================ false member_D_discrim <case H1.

Subgoal 1: Variables: X P IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path X q => path n1 q) nil H3 : member (path n1 P) nil ============================ false Subgoal 2 is: false Subgoal 3 is: false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <case H2.

Subgoal 2: Variables: X P D1 G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path (X n2) q => path n1 q) (path n2 n3 :: D1 n1) H3 : member (path n1 (P n3)) (path n2 n3 :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * ============================ false Subgoal 3 is: false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <case H2.

Subgoal 2: Variables: X P D1 G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H3 : member (path n1 (P n3)) (path n2 n3 :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ false Subgoal 3 is: false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <case H3.

Subgoal 2: Variables: X P D1 G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) H6 : member (path n1 (P n3)) (D1 n1) ============================ false Subgoal 3 is: false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <apply IH to H4 H5 H6.

Subgoal 3: Variables: X P D1 G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path X q => path n1 q) (path n1 n2 :: D1) H3 : member (path n1 (P n2)) (path n1 n2 :: D1) H4 : ctx2 G1 D1 * ============================ false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <case H2.

Subgoal 3: Variables: X P D1 G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H3 : member (path n1 (P n2)) (path n1 n2 :: D1) H4 : ctx2 G1 D1 * H5 : member (pi q\path X q => path n1 q) D1 ============================ false Subgoal 4 is: false Subgoal 5 is: false member_D_discrim <apply member_prune_D to H4 H5.

Subgoal 4: Variables: X P D1 N G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path (X n2) q => path n1 q) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H3 : member (path n1 P) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * ============================ false Subgoal 5 is: false member_D_discrim <case H2.

Subgoal 4: Variables: X P D1 N G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H3 : member (path n1 P) ((pi q\path (N n1) q => path n2 q) :: D1 n1) H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) ============================ false Subgoal 5 is: false member_D_discrim <case H3.

Subgoal 4: Variables: X P D1 N G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H4 : ctx2 (G1 n1) (D1 n1) * H5 : member (pi q\path (X n2) q => path n1 q) (D1 n1) H6 : member (path n1 P) (D1 n1) ============================ false Subgoal 5 is: false member_D_discrim <apply IH to H4 H5 H6.

Subgoal 5: Variables: X P D1 N G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H3 : member (path n1 P) ((pi q\path N q => path n1 q) :: D1) H4 : ctx2 G1 D1 * ============================ false member_D_discrim <case H3.

Subgoal 5: Variables: X P D1 N G1 IH : forall G D X P, nabla n, ctx2 (G n) (D n) * -> member (pi q\path X q => path n q) (D n) -> member (path n P) (D n) -> false H2 : member (pi q\path X q => path n1 q) ((pi q\path N q => path n1 q) :: D1) H4 : ctx2 G1 D1 * H5 : member (path n1 P) D1 ============================ false member_D_discrim <apply member_prune_D to H4 H5.Proof completed.

Abella <Theorem jump_D_invert : forall G D X P, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> {D n |- path n P} -> {D n |- path X P}.

============================ forall G D X P, nabla n, ctx2 (G n) (D n) -> member (pi q\path X q => path n q) (D n) -> {D n |- path n P} -> {D n |- path X P} jump_D_invert <intros.

Variables: G D X P H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H3 : {D n1 |- path n1 P} ============================ {D n1 |- path X P} jump_D_invert <case H3.

Variables: G D X P F H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H4 : {D n1, [F n1] |- path n1 P} H5 : member (F n1) (D n1) ============================ {D n1 |- path X P} jump_D_invert <apply ctx2_mem_D to H1 H5.

Variables: G D X P F H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H4 : {D n1, [F n1] |- path n1 P} H5 : member (F n1) (D n1) H6 : (exists x p, F n1 = path x p /\ name x /\ pname p) \/ (exists x N, F n1 = pi q\path N q => path x q /\ fresh x N) ============================ {D n1 |- path X P} jump_D_invert <case H6.

Subgoal 1: Variables: G D X P x p H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H4 : {D n1, [path (x n1) p] |- path n1 P} H5 : member (path (x n1) p) (D n1) H7 : name (x n1) H8 : pname p ============================ {D n1 |- path X P} Subgoal 2 is: {D n1 |- path X P} jump_D_invert <case H4.

Subgoal 1: Variables: G D X P H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H5 : member (path n1 P) (D n1) H7 : name n1 H8 : pname P ============================ {D n1 |- path X P} Subgoal 2 is: {D n1 |- path X P} jump_D_invert <apply member_D_discrim to H1 H2 H5.

Subgoal 2: Variables: G D X P x N H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H4 : {D n1, [pi q\path (N n1) q => path (x n1) q] |- path n1 P} H5 : member (pi q\path (N n1) q => path (x n1) q) (D n1) H7 : fresh (x n1) (N n1) ============================ {D n1 |- path X P} jump_D_invert <case H4.

Subgoal 2: Variables: G D X P N H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H5 : member (pi q\path (N n1) q => path n1 q) (D n1) H7 : fresh n1 (N n1) H8 : {D n1 |- path (N n1) P} ============================ {D n1 |- path X P} jump_D_invert <case H7.

Subgoal 2: Variables: G D X P X1 H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X q => path n1 q) (D n1) H5 : member (pi q\path X1 q => path n1 q) (D n1) H8 : {D n1 |- path X1 P} ============================ {D n1 |- path X P} jump_D_invert <apply member_D_determinate to H1 H2 H5.

Subgoal 2: Variables: G D P X1 H1 : ctx2 (G n1) (D n1) H2 : member (pi q\path X1 q => path n1 q) (D n1) H5 : member (pi q\path X1 q => path n1 q) (D n1) H8 : {D n1 |- path X1 P} ============================ {D n1 |- path X1 P} jump_D_invert <search.Proof completed.

Abella <Theorem bred_ltr : forall G D M N P, ctx2 G D -> {G |- bred M N} -> {D |- path M P} -> {D |- path N P}.

============================ forall G D M N P, ctx2 G D -> {G |- bred M N} -> {D |- path M P} -> {D |- path N P} bred_ltr <induction on 2.

IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} ============================ forall G D M N P, ctx2 G D -> {G |- bred M N}@ -> {D |- path M P} -> {D |- path N P} bred_ltr <intros.

Variables: G D M N P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path M P} ============================ {D |- path N P} bred_ltr <case H2 (keep).

Subgoal 1: Variables: G D P U M1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H3 : {D |- path (abs M1) P} H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* ============================ {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H3.

Subgoal 1.1: Variables: G D U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, path n1 n2 |- path (M1 n1) (P1 n2)} ============================ {D |- path (abs U) (bnd P1)} Subgoal 1.2 is: {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply IH to _ H4 H5.

Subgoal 1.1: Variables: G D U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, path n1 n2 |- path (M1 n1) (P1 n2)} H6 : {D, path n1 n2 |- path (U n1) (P1 n2)} ============================ {D |- path (abs U) (bnd P1)} Subgoal 1.2 is: {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <search.

Subgoal 1.2: Variables: G D P U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [F] |- path (abs M1) P} H6 : member F D ============================ {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply ctx2_mem_D to H1 H6.

Subgoal 1.2: Variables: G D P U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [F] |- path (abs M1) P} H6 : member F D H7 : (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H7.

Subgoal 1.2.1: Variables: G D P U M1 x p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [path x p] |- path (abs M1) P} H6 : member (path x p) D H8 : name x H9 : pname p ============================ {D |- path (abs U) P} Subgoal 1.2.2 is: {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H8.

Subgoal 1.2.1: Variables: G D P U M1 p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (abs (M1 n2)) (abs (U n2))}@ H4 : {G n2, bred n1 n1 |- bred (M1 n2 n1) (U n2 n1)}* H5 : {D n2, [path n2 p] |- path (abs (M1 n2)) P} H6 : member (path n2 p) (D n2) H9 : pname p ============================ {D n2 |- path (abs (U n2)) P} Subgoal 1.2.2 is: {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H5.

Subgoal 1.2.2: Variables: G D P U M1 x N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [pi q\path N1 q => path x q] |- path (abs M1) P} H6 : member (pi q\path N1 q => path x q) D H8 : fresh x N1 ============================ {D |- path (abs U) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H8.

Subgoal 1.2.2: Variables: G D P U M1 X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (abs (M1 n2)) (abs (U n2))}@ H4 : {G n2, bred n1 n1 |- bred (M1 n2 n1) (U n2 n1)}* H5 : {D n2, [pi q\path X q => path n2 q] |- path (abs (M1 n2)) P} H6 : member (pi q\path X q => path n2 q) (D n2) ============================ {D n2 |- path (abs (U n2)) P} Subgoal 2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H5.

Subgoal 2: Variables: G D P V N1 U M1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H3 : {D |- path (app M1 N1) P} H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* ============================ {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H3.

Subgoal 2.1: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path M1 P1} ============================ {D |- path (app U V) (left P1)} Subgoal 2.2 is: {D |- path (app U V) (right P1)} Subgoal 2.3 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply IH to _ H4 H6.

Subgoal 2.1: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path M1 P1} H7 : {D |- path U P1} ============================ {D |- path (app U V) (left P1)} Subgoal 2.2 is: {D |- path (app U V) (right P1)} Subgoal 2.3 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <search.

Subgoal 2.2: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path N1 P1} ============================ {D |- path (app U V) (right P1)} Subgoal 2.3 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply IH to _ H5 H6.

Subgoal 2.2: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path N1 P1} H7 : {D |- path V P1} ============================ {D |- path (app U V) (right P1)} Subgoal 2.3 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <search.

Subgoal 2.3: Variables: G D P V N1 U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [F] |- path (app M1 N1) P} H7 : member F D ============================ {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply ctx2_mem_D to H1 H7.

Subgoal 2.3: Variables: G D P V N1 U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [F] |- path (app M1 N1) P} H7 : member F D H8 : (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H8.

Subgoal 2.3.1: Variables: G D P V N1 U M1 x p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [path x p] |- path (app M1 N1) P} H7 : member (path x p) D H9 : name x H10 : pname p ============================ {D |- path (app U V) P} Subgoal 2.3.2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H9.

Subgoal 2.3.1: Variables: G D P V N1 U M1 p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (app (M1 n1) (N1 n1)) (app (U n1) (V n1))}@ H4 : {G n1 |- bred (M1 n1) (U n1)}* H5 : {G n1 |- bred (N1 n1) (V n1)}* H6 : {D n1, [path n1 p] |- path (app (M1 n1) (N1 n1)) P} H7 : member (path n1 p) (D n1) H10 : pname p ============================ {D n1 |- path (app (U n1) (V n1)) P} Subgoal 2.3.2 is: {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H6.

Subgoal 2.3.2: Variables: G D P V N1 U M1 x N2 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [pi q\path N2 q => path x q] |- path (app M1 N1) P} H7 : member (pi q\path N2 q => path x q) D H9 : fresh x N2 ============================ {D |- path (app U V) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H9.

Subgoal 2.3.2: Variables: G D P V N1 U M1 X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (app (M1 n1) (N1 n1)) (app (U n1) (V n1))}@ H4 : {G n1 |- bred (M1 n1) (U n1)}* H5 : {G n1 |- bred (N1 n1) (V n1)}* H6 : {D n1, [pi q\path X q => path n1 q] |- path (app (M1 n1) (N1 n1)) P} H7 : member (pi q\path X q => path n1 q) (D n1) ============================ {D n1 |- path (app (U n1) (V n1)) P} Subgoal 3 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H6.

Subgoal 3: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H3 : {D |- path (beta R N1) P} H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* ============================ {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H3.

Subgoal 3.1: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} ============================ {D |- path N P} Subgoal 3.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply IH to _ H4 H5.

Subgoal 3.1: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} H6 : {D, pi q\path N1 q => path n1 q |- path N P} ============================ {D |- path N P} Subgoal 3.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <inst H6 with n1 = N1.

Subgoal 3.1: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} H6 : {D, pi q\path N1 q => path n1 q |- path N P} H7 : {D, pi q\path N1 q => path N1 q |- path N P} ============================ {D |- path N P} Subgoal 3.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <assert {D |- pi q\path N1 q => path N1 q}.

Subgoal 3.1: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} H6 : {D, pi q\path N1 q => path n1 q |- path N P} H7 : {D, pi q\path N1 q => path N1 q |- path N P} H8 : {D |- pi q\path N1 q => path N1 q} ============================ {D |- path N P} Subgoal 3.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <cut H7 with H8.

Subgoal 3.1: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} H6 : {D, pi q\path N1 q => path n1 q |- path N P} H7 : {D, pi q\path N1 q => path N1 q |- path N P} H8 : {D |- pi q\path N1 q => path N1 q} H9 : {D |- path N P} ============================ {D |- path N P} Subgoal 3.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <search.

Subgoal 3.2: Variables: G D N P R N1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, [F] |- path (beta R N1) P} H6 : member F D ============================ {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <apply ctx2_mem_D to H1 H6.

Subgoal 3.2: Variables: G D N P R N1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, [F] |- path (beta R N1) P} H6 : member F D H7 : (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H7.

Subgoal 3.2.1: Variables: G D N P R N1 x p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, [path x p] |- path (beta R N1) P} H6 : member (path x p) D H8 : name x H9 : pname p ============================ {D |- path N P} Subgoal 3.2.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H8.

Subgoal 3.2.1: Variables: G D N P R N1 p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (beta (R n2) (N1 n2)) (N n2)}@ H4 : {G n2, pi u\bred (N1 n2) u => bred n1 u |- bred (R n2 n1) (N n2)}* H5 : {D n2, [path n2 p] |- path (beta (R n2) (N1 n2)) P} H6 : member (path n2 p) (D n2) H9 : pname p ============================ {D n2 |- path (N n2) P} Subgoal 3.2.2 is: {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H5.

Subgoal 3.2.2: Variables: G D N P R N1 x N2 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, [pi q\path N2 q => path x q] |- path (beta R N1) P} H6 : member (pi q\path N2 q => path x q) D H8 : fresh x N2 ============================ {D |- path N P} Subgoal 4 is: {D |- path N P} bred_ltr <case H8.

Subgoal 3.2.2: Variables: G D N P R N1 X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (beta (R n2) (N1 n2)) (N n2)}@ H4 : {G n2, pi u\bred (N1 n2) u => bred n1 u |- bred (R n2 n1) (N n2)}* H5 : {D n2, [pi q\path X q => path n2 q] |- path (beta (R n2) (N1 n2)) P} H6 : member (pi q\path X q => path n2 q) (D n2) ============================ {D n2 |- path (N n2) P} Subgoal 4 is: {D |- path N P} bred_ltr <case H5.

Subgoal 4: Variables: G D M N P F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path M P} H4 : {G, [F] |- bred M N}* H5 : member F G ============================ {D |- path N P} bred_ltr <apply ctx2_mem_G to H1 H5.

Subgoal 4: Variables: G D M N P F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path M P} H4 : {G, [F] |- bred M N}* H5 : member F G H6 : (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ============================ {D |- path N P} bred_ltr <case H6.

Subgoal 4.1: Variables: G D M N P x IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path M P} H4 : {G, [bred x x] |- bred M N}* H5 : member (bred x x) G H7 : name x ============================ {D |- path N P} Subgoal 4.2 is: {D |- path N P} bred_ltr <case H7.

Subgoal 4.1: Variables: G D M N P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (M n1) (N n1)}@ H3 : {D n1 |- path (M n1) P} H4 : {G n1, [bred n1 n1] |- bred (M n1) (N n1)}* H5 : member (bred n1 n1) (G n1) ============================ {D n1 |- path (N n1) P} Subgoal 4.2 is: {D |- path N P} bred_ltr <case H4.

Subgoal 4.1: Variables: G D P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 n1}@ H3 : {D n1 |- path n1 P} H5 : member (bred n1 n1) (G n1) ============================ {D n1 |- path n1 P} Subgoal 4.2 is: {D |- path N P} bred_ltr <search.

Subgoal 4.2: Variables: G D M N P x N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path M P} H4 : {G, [pi u\bred N1 u => bred x u] |- bred M N}* H5 : member (pi u\bred N1 u => bred x u) G H7 : fresh x N1 ============================ {D |- path N P} bred_ltr <case H7.

Subgoal 4.2: Variables: G D M N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (M n1) (N n1)}@ H3 : {D n1 |- path (M n1) P} H4 : {G n1, [pi u\bred X u => bred n1 u] |- bred (M n1) (N n1)}* H5 : member (pi u\bred X u => bred n1 u) (G n1) ============================ {D n1 |- path (N n1) P} bred_ltr <case H4.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* ============================ {D n1 |- path (N n1) P} bred_ltr <assert {D n1 |- path X P}.

Subgoal 4.2.1: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* ============================ {D n1 |- path X P} Subgoal 4.2 is: {D n1 |- path (N n1) P} bred_ltr <apply ctx2_uniform to H1 H5.

Subgoal 4.2.1: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : member (pi q\path X q => path n1 q) (D n1) ============================ {D n1 |- path X P} Subgoal 4.2 is: {D n1 |- path (N n1) P} bred_ltr <apply jump_D_invert to H1 H9 H3.

Subgoal 4.2.1: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : member (pi q\path X q => path n1 q) (D n1) H10 : {D n1 |- path X P} ============================ {D n1 |- path X P} Subgoal 4.2 is: {D n1 |- path (N n1) P} bred_ltr <search.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : {D n1 |- path X P} ============================ {D n1 |- path (N n1) P} bred_ltr <apply IH to H1 H8 H9.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path M P} -> {D |- path N P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path n1 P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : {D n1 |- path X P} H10 : {D n1 |- path (N n1) P} ============================ {D n1 |- path (N n1) P} bred_ltr <search.Proof completed.

Abella <Theorem bred_rtl : forall G D M N P, ctx2 G D -> {G |- bred M N} -> {D |- path N P} -> {D |- path M P}.

============================ forall G D M N P, ctx2 G D -> {G |- bred M N} -> {D |- path N P} -> {D |- path M P} bred_rtl <induction on 2.

IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} ============================ forall G D M N P, ctx2 G D -> {G |- bred M N}@ -> {D |- path N P} -> {D |- path M P} bred_rtl <intros.

Variables: G D M N P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path N P} ============================ {D |- path M P} bred_rtl <case H2 (keep).

Subgoal 1: Variables: G D P U M1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H3 : {D |- path (abs U) P} H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* ============================ {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H3.

Subgoal 1.1: Variables: G D U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, path n1 n2 |- path (U n1) (P1 n2)} ============================ {D |- path (abs M1) (bnd P1)} Subgoal 1.2 is: {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply IH to _ H4 H5.

Subgoal 1.1: Variables: G D U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, path n1 n2 |- path (U n1) (P1 n2)} H6 : {D, path n1 n2 |- path (M1 n1) (P1 n2)} ============================ {D |- path (abs M1) (bnd P1)} Subgoal 1.2 is: {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <search.

Subgoal 1.2: Variables: G D P U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [F] |- path (abs U) P} H6 : member F D ============================ {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply ctx2_mem_D to H1 H6.

Subgoal 1.2: Variables: G D P U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [F] |- path (abs U) P} H6 : member F D H7 : (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H7.

Subgoal 1.2.1: Variables: G D P U M1 x p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [path x p] |- path (abs U) P} H6 : member (path x p) D H8 : name x H9 : pname p ============================ {D |- path (abs M1) P} Subgoal 1.2.2 is: {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H8.

Subgoal 1.2.1: Variables: G D P U M1 p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (abs (M1 n2)) (abs (U n2))}@ H4 : {G n2, bred n1 n1 |- bred (M1 n2 n1) (U n2 n1)}* H5 : {D n2, [path n2 p] |- path (abs (U n2)) P} H6 : member (path n2 p) (D n2) H9 : pname p ============================ {D n2 |- path (abs (M1 n2)) P} Subgoal 1.2.2 is: {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H5.

Subgoal 1.2.2: Variables: G D P U M1 x N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (abs M1) (abs U)}@ H4 : {G, bred n1 n1 |- bred (M1 n1) (U n1)}* H5 : {D, [pi q\path N1 q => path x q] |- path (abs U) P} H6 : member (pi q\path N1 q => path x q) D H8 : fresh x N1 ============================ {D |- path (abs M1) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H8.

Subgoal 1.2.2: Variables: G D P U M1 X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n2) (D n2) H2 : {G n2 |- bred (abs (M1 n2)) (abs (U n2))}@ H4 : {G n2, bred n1 n1 |- bred (M1 n2 n1) (U n2 n1)}* H5 : {D n2, [pi q\path X q => path n2 q] |- path (abs (U n2)) P} H6 : member (pi q\path X q => path n2 q) (D n2) ============================ {D n2 |- path (abs (M1 n2)) P} Subgoal 2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H5.

Subgoal 2: Variables: G D P V N1 U M1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H3 : {D |- path (app U V) P} H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* ============================ {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H3.

Subgoal 2.1: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path U P1} ============================ {D |- path (app M1 N1) (left P1)} Subgoal 2.2 is: {D |- path (app M1 N1) (right P1)} Subgoal 2.3 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply IH to _ H4 H6.

Subgoal 2.1: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path U P1} H7 : {D |- path M1 P1} ============================ {D |- path (app M1 N1) (left P1)} Subgoal 2.2 is: {D |- path (app M1 N1) (right P1)} Subgoal 2.3 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <search.

Subgoal 2.2: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path V P1} ============================ {D |- path (app M1 N1) (right P1)} Subgoal 2.3 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply IH to _ H5 H6.

Subgoal 2.2: Variables: G D V N1 U M1 P1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D |- path V P1} H7 : {D |- path N1 P1} ============================ {D |- path (app M1 N1) (right P1)} Subgoal 2.3 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <search.

Subgoal 2.3: Variables: G D P V N1 U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [F] |- path (app U V) P} H7 : member F D ============================ {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply ctx2_mem_D to H1 H7.

Subgoal 2.3: Variables: G D P V N1 U M1 F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [F] |- path (app U V) P} H7 : member F D H8 : (exists x p, F = path x p /\ name x /\ pname p) \/ (exists x N, F = pi q\path N q => path x q /\ fresh x N) ============================ {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H8.

Subgoal 2.3.1: Variables: G D P V N1 U M1 x p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [path x p] |- path (app U V) P} H7 : member (path x p) D H9 : name x H10 : pname p ============================ {D |- path (app M1 N1) P} Subgoal 2.3.2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H9.

Subgoal 2.3.1: Variables: G D P V N1 U M1 p IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (app (M1 n1) (N1 n1)) (app (U n1) (V n1))}@ H4 : {G n1 |- bred (M1 n1) (U n1)}* H5 : {G n1 |- bred (N1 n1) (V n1)}* H6 : {D n1, [path n1 p] |- path (app (U n1) (V n1)) P} H7 : member (path n1 p) (D n1) H10 : pname p ============================ {D n1 |- path (app (M1 n1) (N1 n1)) P} Subgoal 2.3.2 is: {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H6.

Subgoal 2.3.2: Variables: G D P V N1 U M1 x N2 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (app M1 N1) (app U V)}@ H4 : {G |- bred M1 U}* H5 : {G |- bred N1 V}* H6 : {D, [pi q\path N2 q => path x q] |- path (app U V) P} H7 : member (pi q\path N2 q => path x q) D H9 : fresh x N2 ============================ {D |- path (app M1 N1) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H9.

Subgoal 2.3.2: Variables: G D P V N1 U M1 X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (app (M1 n1) (N1 n1)) (app (U n1) (V n1))}@ H4 : {G n1 |- bred (M1 n1) (U n1)}* H5 : {G n1 |- bred (N1 n1) (V n1)}* H6 : {D n1, [pi q\path X q => path n1 q] |- path (app (U n1) (V n1)) P} H7 : member (pi q\path X q => path n1 q) (D n1) ============================ {D n1 |- path (app (M1 n1) (N1 n1)) P} Subgoal 3 is: {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <case H6.

Subgoal 3: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H3 : {D |- path N P} H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* ============================ {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <assert {D, pi q\path N1 q => path n1 q |- path N P}.

Subgoal 3: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H3 : {D |- path N P} H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path N P} ============================ {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <apply IH to _ H4 H5.

Subgoal 3: Variables: G D N P R N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred (beta R N1) N}@ H3 : {D |- path N P} H4 : {G, pi u\bred N1 u => bred n1 u |- bred (R n1) N}* H5 : {D, pi q\path N1 q => path n1 q |- path N P} H6 : {D, pi q\path N1 q => path n1 q |- path (R n1) P} ============================ {D |- path (beta R N1) P} Subgoal 4 is: {D |- path M P} bred_rtl <search.

Subgoal 4: Variables: G D M N P F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path N P} H4 : {G, [F] |- bred M N}* H5 : member F G ============================ {D |- path M P} bred_rtl <apply ctx2_mem_G to H1 H5.

Subgoal 4: Variables: G D M N P F IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path N P} H4 : {G, [F] |- bred M N}* H5 : member F G H6 : (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ============================ {D |- path M P} bred_rtl <case H6.

Subgoal 4.1: Variables: G D M N P x IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path N P} H4 : {G, [bred x x] |- bred M N}* H5 : member (bred x x) G H7 : name x ============================ {D |- path M P} Subgoal 4.2 is: {D |- path M P} bred_rtl <case H7.

Subgoal 4.1: Variables: G D M N P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (M n1) (N n1)}@ H3 : {D n1 |- path (N n1) P} H4 : {G n1, [bred n1 n1] |- bred (M n1) (N n1)}* H5 : member (bred n1 n1) (G n1) ============================ {D n1 |- path (M n1) P} Subgoal 4.2 is: {D |- path M P} bred_rtl <case H4.

Subgoal 4.1: Variables: G D P IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 n1}@ H3 : {D n1 |- path n1 P} H5 : member (bred n1 n1) (G n1) ============================ {D n1 |- path n1 P} Subgoal 4.2 is: {D |- path M P} bred_rtl <search.

Subgoal 4.2: Variables: G D M N P x N1 IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 G D H2 : {G |- bred M N}@ H3 : {D |- path N P} H4 : {G, [pi u\bred N1 u => bred x u] |- bred M N}* H5 : member (pi u\bred N1 u => bred x u) G H7 : fresh x N1 ============================ {D |- path M P} bred_rtl <case H7.

Subgoal 4.2: Variables: G D M N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred (M n1) (N n1)}@ H3 : {D n1 |- path (N n1) P} H4 : {G n1, [pi u\bred X u => bred n1 u] |- bred (M n1) (N n1)}* H5 : member (pi u\bred X u => bred n1 u) (G n1) ============================ {D n1 |- path (M n1) P} bred_rtl <case H4.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path (N n1) P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* ============================ {D n1 |- path n1 P} bred_rtl <apply IH to H1 H8 H3.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path (N n1) P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : {D n1 |- path X P} ============================ {D n1 |- path n1 P} bred_rtl <apply ctx2_uniform to H1 H5.

Subgoal 4.2: Variables: G D N P X IH : forall G D M N P, ctx2 G D -> {G |- bred M N}* -> {D |- path N P} -> {D |- path M P} H1 : ctx2 (G n1) (D n1) H2 : {G n1 |- bred n1 (N n1)}@ H3 : {D n1 |- path (N n1) P} H5 : member (pi u\bred X u => bred n1 u) (G n1) H8 : {G n1 |- bred X (N n1)}* H9 : {D n1 |- path X P} H10 : member (pi q\path X q => path n1 q) (D n1) ============================ {D n1 |- path n1 P} bred_rtl <search.Proof completed.

Abella <Define bfctx : olist -> olist -> prop by bfctx nil nil; nabla n p, bfctx (bfree n :: L) (path n p :: K) := bfctx L K.

Abella <Theorem member_prune_path : forall E L, nabla x, member (E x) L -> (exists F, E = y\F).

============================ forall E L, nabla x, member (E x) L -> (exists F, E = y\F) member_prune_path <induction on 1.

IH : forall E L, nabla x, member (E x) L * -> (exists F, E = y\F) ============================ forall E L, nabla x, member (E x) L @ -> (exists F, E = y\F) member_prune_path <intros.

Variables: E L IH : forall E L, nabla x, member (E x) L * -> (exists F, E = y\F) H1 : member (E n1) L @ ============================ exists F, E = y\F member_prune_path <case H1.

Subgoal 1: Variables: L3 L2 IH : forall E L, nabla x, member (E x) L * -> (exists F, E = y\F) ============================ exists F, z1\L2 = y\F Subgoal 2 is: exists F, E = y\F member_prune_path <search.

Subgoal 2: Variables: E L3 L2 IH : forall E L, nabla x, member (E x) L * -> (exists F, E = y\F) H2 : member (E n1) L3 * ============================ exists F, E = y\F member_prune_path <apply IH to H2.

Subgoal 2: Variables: L3 L2 F IH : forall E L, nabla x, member (E x) L * -> (exists F, E = y\F) H2 : member F L3 * ============================ exists F1, z1\F = y\F1 member_prune_path <search.Proof completed.

Abella <Theorem bfctx_member1 : forall X L K, bfctx L K -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F).

============================ forall X L K, bfctx L K -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) bfctx_member1 <induction on 1.

IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) ============================ forall X L K, bfctx L K @ -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) bfctx_member1 <intros.

Variables: X L K IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H1 : bfctx L K @ H2 : member X L ============================ exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F bfctx_member1 <case H1.

Subgoal 1: Variables: X IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H2 : member X nil ============================ exists E F, X = bfree E /\ name E /\ member (path E F) nil /\ pname F Subgoal 2 is: exists E F, X n1 n2 = bfree E /\ name E /\ member (path E F) (path n1 n2 :: K1) /\ pname F bfctx_member1 <case H2.

Subgoal 2: Variables: X K1 L1 IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H2 : member (X n1 n2) (bfree n1 :: L1) H3 : bfctx L1 K1 * ============================ exists E F, X n1 n2 = bfree E /\ name E /\ member (path E F) (path n1 n2 :: K1) /\ pname F bfctx_member1 <case H2.

Subgoal 2.1: Variables: K1 L1 IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H3 : bfctx L1 K1 * ============================ exists E F, bfree n1 = bfree E /\ name E /\ member (path E F) (path n1 n2 :: K1) /\ pname F Subgoal 2.2 is: exists E F, X n1 n2 = bfree E /\ name E /\ member (path E F) (path n1 n2 :: K1) /\ pname F bfctx_member1 <search.

Subgoal 2.2: Variables: X K1 L1 IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H3 : bfctx L1 K1 * H4 : member (X n1 n2) L1 ============================ exists E F, X n1 n2 = bfree E /\ name E /\ member (path E F) (path n1 n2 :: K1) /\ pname F bfctx_member1 <apply IH to H3 H4.

Subgoal 2.2: Variables: K1 L1 E F IH : forall X L K, bfctx L K * -> member X L -> (exists E F, X = bfree E /\ name E /\ member (path E F) K /\ pname F) H3 : bfctx L1 K1 * H4 : member (bfree (E n1)) L1 H5 : name (E n1) H6 : member (path (E n1) (F n2)) K1 H7 : pname (F n2) ============================ exists E1 F, bfree (E n1) = bfree E1 /\ name E1 /\ member (path E1 F) (path n1 n2 :: K1) /\ pname F bfctx_member1 <search.Proof completed.

Abella <Theorem bfctx_member2 : forall X L K, bfctx L K -> member X K -> (exists E F, X = path E F /\ name E /\ pname F).

============================ forall X L K, bfctx L K -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) bfctx_member2 <induction on 1.

IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) ============================ forall X L K, bfctx L K @ -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) bfctx_member2 <intros.

Variables: X L K IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H1 : bfctx L K @ H2 : member X K ============================ exists E F, X = path E F /\ name E /\ pname F bfctx_member2 <case H1.

Subgoal 1: Variables: X IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H2 : member X nil ============================ exists E F, X = path E F /\ name E /\ pname F Subgoal 2 is: exists E F, X n1 n2 = path E F /\ name E /\ pname F bfctx_member2 <case H2.

Subgoal 2: Variables: X K1 L1 IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H2 : member (X n1 n2) (path n1 n2 :: K1) H3 : bfctx L1 K1 * ============================ exists E F, X n1 n2 = path E F /\ name E /\ pname F bfctx_member2 <case H2.

Subgoal 2.1: Variables: K1 L1 IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H3 : bfctx L1 K1 * ============================ exists E F, path n1 n2 = path E F /\ name E /\ pname F Subgoal 2.2 is: exists E F, X n1 n2 = path E F /\ name E /\ pname F bfctx_member2 <search.

Subgoal 2.2: Variables: X K1 L1 IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H3 : bfctx L1 K1 * H4 : member (X n1 n2) K1 ============================ exists E F, X n1 n2 = path E F /\ name E /\ pname F bfctx_member2 <apply IH to H3 H4.

Subgoal 2.2: Variables: K1 L1 E F IH : forall X L K, bfctx L K * -> member X K -> (exists E F, X = path E F /\ name E /\ pname F) H3 : bfctx L1 K1 * H4 : member (path (E n1) (F n2)) K1 H5 : name (E n1) H6 : pname (F n2) ============================ exists E1 F1, path (E n1) (F n2) = path E1 F1 /\ name E1 /\ pname F1 bfctx_member2 <search.Proof completed.

Abella <Theorem member_path_unique : forall L K X Y F, bfctx L K -> member (path X F) K -> member (path Y F) K -> X = Y.

============================ forall L K X Y F, bfctx L K -> member (path X F) K -> member (path Y F) K -> X = Y member_path_unique <induction on 2.

IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y ============================ forall L K X Y F, bfctx L K -> member (path X F) K @ -> member (path Y F) K -> X = Y member_path_unique <intros.

Variables: L K X Y F IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L K H2 : member (path X F) K @ H3 : member (path Y F) K ============================ X = Y member_path_unique <case H2.

Subgoal 1: Variables: L X Y F L1 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (path X F :: L1) H3 : member (path Y F) (path X F :: L1) ============================ X = Y Subgoal 2 is: X = Y member_path_unique <case H3.

Subgoal 1.1: Variables: L X F L1 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (path X F :: L1) ============================ X = X Subgoal 1.2 is: X = Y Subgoal 2 is: X = Y member_path_unique <search.

Subgoal 1.2: Variables: L X Y F L1 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (path X F :: L1) H4 : member (path Y F) L1 ============================ X = Y Subgoal 2 is: X = Y member_path_unique <case H1.

Subgoal 1.2: Variables: Y K1 L2 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H4 : member (path (Y n1) n2) K1 H5 : bfctx L2 K1 ============================ n1 = Y n1 Subgoal 2 is: X = Y member_path_unique <apply member_prune_path to H4.

Subgoal 2: Variables: L X Y F L1 B IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (B :: L1) H3 : member (path Y F) (B :: L1) H4 : member (path X F) L1 * ============================ X = Y member_path_unique <case H3.

Subgoal 2.1: Variables: L X Y F L1 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (path Y F :: L1) H4 : member (path X F) L1 * ============================ X = Y Subgoal 2.2 is: X = Y member_path_unique <case H1.

Subgoal 2.1: Variables: X K1 L2 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H4 : member (path (X n1) n2) K1 * H5 : bfctx L2 K1 ============================ X n1 = n1 Subgoal 2.2 is: X = Y member_path_unique <apply member_prune_path to H4.

Subgoal 2.2: Variables: L X Y F L1 B IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H1 : bfctx L (B :: L1) H4 : member (path X F) L1 * H5 : member (path Y F) L1 ============================ X = Y member_path_unique <case H1.

Subgoal 2.2: Variables: X Y F K1 L2 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H4 : member (path (X n1) (F n2)) K1 * H5 : member (path (Y n1) (F n2)) K1 H6 : bfctx L2 K1 ============================ X n1 = Y n1 member_path_unique <apply IH to H6 H4 H5.

Subgoal 2.2: Variables: Y F K1 L2 IH : forall L K X Y F, bfctx L K -> member (path X F) K * -> member (path Y F) K -> X = Y H4 : member (path (Y n1) (F n2)) K1 * H5 : member (path (Y n1) (F n2)) K1 H6 : bfctx L2 K1 ============================ Y n1 = Y n1 member_path_unique <search.Proof completed.

Abella <Theorem path_exists : forall L K M, bfctx L K -> {L |- bfree M} -> (exists P, {K |- path M P}).

============================ forall L K M, bfctx L K -> {L |- bfree M} -> (exists P, {K |- path M P}) path_exists <induction on 2.

IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) ============================ forall L K M, bfctx L K -> {L |- bfree M}@ -> (exists P, {K |- path M P}) path_exists <intros.

Variables: L K M IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H2 : {L |- bfree M}@ ============================ exists P, {K |- path M P} path_exists <case H2.

Subgoal 1: Variables: L K M1 IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, bfree n1 |- bfree (M1 n1)}* ============================ exists P, {K |- path (abs M1) P} Subgoal 2 is: exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <assert bfctx (bfree n1 :: L) (path n1 n2 :: K).

Subgoal 1: Variables: L K M1 IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, bfree n1 |- bfree (M1 n1)}* H4 : bfctx (bfree n1 :: L) (path n1 n2 :: K) ============================ exists P, {K |- path (abs M1) P} Subgoal 2 is: exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <apply IH to H4 H3.

Subgoal 1: Variables: L K M1 P IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, bfree n1 |- bfree (M1 n1)}* H4 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H5 : {K, path n1 n2 |- path (M1 n1) (P n2)} ============================ exists P, {K |- path (abs M1) P} Subgoal 2 is: exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <exists bnd P.

Subgoal 1: Variables: L K M1 P IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, bfree n1 |- bfree (M1 n1)}* H4 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H5 : {K, path n1 n2 |- path (M1 n1) (P n2)} ============================ {K |- path (abs M1) (bnd P)} Subgoal 2 is: exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <search.

Subgoal 2: Variables: L K N M1 IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L |- bfree M1}* H4 : {L |- bfree N}* ============================ exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <apply IH to H1 H3.

Subgoal 2: Variables: L K N M1 P IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L |- bfree M1}* H4 : {L |- bfree N}* H5 : {K |- path M1 P} ============================ exists P, {K |- path (app M1 N) P} Subgoal 3 is: exists P, {K |- path M P} path_exists <search.

Subgoal 3: Variables: L K M F IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, [F] |- bfree M}* H4 : member F L ============================ exists P, {K |- path M P} path_exists <apply bfctx_member1 to H1 H4.

Subgoal 3: Variables: L K M E F1 IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H3 : {L, [bfree E] |- bfree M}* H4 : member (bfree E) L H5 : name E H6 : member (path E F1) K H7 : pname F1 ============================ exists P, {K |- path M P} path_exists <case H3.

Subgoal 3: Variables: L K M F1 IH : forall L K M, bfctx L K -> {L |- bfree M}* -> (exists P, {K |- path M P}) H1 : bfctx L K H4 : member (bfree M) L H5 : name M H6 : member (path M F1) K H7 : pname F1 ============================ exists P, {K |- path M P} path_exists <search.Proof completed.

Abella <Theorem bfree_beta_absurd : forall L K R N, bfctx L K -> {L |- bfree (beta R N)} -> false.

============================ forall L K R N, bfctx L K -> {L |- bfree (beta R N)} -> false bfree_beta_absurd <intros.

Variables: L K R N H1 : bfctx L K H2 : {L |- bfree (beta R N)} ============================ false bfree_beta_absurd <case H2.

Variables: L K R N F H1 : bfctx L K H3 : {L, [F] |- bfree (beta R N)} H4 : member F L ============================ false bfree_beta_absurd <apply bfctx_member1 to H1 H4.

Variables: L K R N E F1 H1 : bfctx L K H3 : {L, [bfree E] |- bfree (beta R N)} H4 : member (bfree E) L H5 : name E H6 : member (path E F1) K H7 : pname F1 ============================ false bfree_beta_absurd <case H5.

Variables: L K R N F1 H1 : bfctx (L n1) (K n1) H3 : {L n1, [bfree n1] |- bfree (beta (R n1) (N n1))} H4 : member (bfree n1) (L n1) H6 : member (path n1 F1) (K n1) H7 : pname F1 ============================ false bfree_beta_absurd <case H3.Proof completed.

Abella <Theorem path_app : forall L K M N Y, bfctx L K -> {L |- bfree (app M N)} -> {L |- bfree Y} -> (forall P, {K |- path (app M N) P} -> {K |- path Y P}) -> (exists YM YN, Y = app YM YN).

============================ forall L K M N Y, bfctx L K -> {L |- bfree (app M N)} -> {L |- bfree Y} -> (forall P, {K |- path (app M N) P} -> {K |- path Y P}) -> (exists YM YN, Y = app YM YN) path_app <intros.

Variables: L K M N Y H1 : bfctx L K H2 : {L |- bfree (app M N)} H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} ============================ exists YM YN, Y = app YM YN path_app <case H2.

Subgoal 1: Variables: L K M N Y H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <apply path_exists to H1 H5.

Subgoal 1: Variables: L K M N Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <assert {K |- path (app M N) (left P)}.

Subgoal 1: Variables: L K M N Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <apply H4 to H8.

Subgoal 1: Variables: L K M N Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} H9 : {K |- path Y (left P)} ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <case H9.

Subgoal 1.1: Variables: L K M N P M1 N1 H1 : bfctx L K H3 : {L |- bfree (app M1 N1)} H4 : forall P, {K |- path (app M N) P} -> {K |- path (app M1 N1) P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} H10 : {K |- path M1 P} ============================ exists YM YN, app M1 N1 = app YM YN Subgoal 1.2 is: exists YM YN, beta R N1 = app YM YN Subgoal 1.3 is: exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <search.

Subgoal 1.2: Variables: L K M N P R N1 H1 : bfctx L K H3 : {L |- bfree (beta R N1)} H4 : forall P, {K |- path (app M N) P} -> {K |- path (beta R N1) P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} H10 : {K, pi q\path N1 q => path n1 q |- path (R n1) (left P)} ============================ exists YM YN, beta R N1 = app YM YN Subgoal 1.3 is: exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <apply bfree_beta_absurd to H1 H3.

Subgoal 1.3: Variables: L K M N Y P F H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} H10 : {K, [F] |- path Y (left P)} H11 : member F K ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <apply bfctx_member2 to H1 H11.

Subgoal 1.3: Variables: L K M N Y P E F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L |- bfree M} H6 : {L |- bfree N} H7 : {K |- path M P} H8 : {K |- path (app M N) (left P)} H10 : {K, [path E F1] |- path Y (left P)} H11 : member (path E F1) K H12 : name E H13 : pname F1 ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <case H13.

Subgoal 1.3: Variables: L K M N Y P E H1 : bfctx (L n1) (K n1) H3 : {L n1 |- bfree Y} H4 : forall P, {K n1 |- path (app M N) P} -> {K n1 |- path Y P} H5 : {L n1 |- bfree M} H6 : {L n1 |- bfree N} H7 : {K n1 |- path M (P n1)} H8 : {K n1 |- path (app M N) (left (P n1))} H10 : {K n1, [path E n1] |- path Y (left (P n1))} H11 : member (path E n1) (K n1) H12 : name E ============================ exists YM YN, Y = app YM YN Subgoal 2 is: exists YM YN, Y = app YM YN path_app <case H10.

Subgoal 2: Variables: L K M N Y F H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L, [F] |- bfree (app M N)} H6 : member F L ============================ exists YM YN, Y = app YM YN path_app <apply bfctx_member1 to H1 H6.

Subgoal 2: Variables: L K M N Y E F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H5 : {L, [bfree E] |- bfree (app M N)} H6 : member (bfree E) L H7 : name E H8 : member (path E F1) K H9 : pname F1 ============================ exists YM YN, Y = app YM YN path_app <case H5.

Subgoal 2: Variables: L K M N Y F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (app M N) P} -> {K |- path Y P} H6 : member (bfree (app M N)) L H7 : name (app M N) H8 : member (path (app M N) F1) K H9 : pname F1 ============================ exists YM YN, Y = app YM YN path_app <case H7.Proof completed.

Abella <Theorem path_abs : forall L K R Y, bfctx L K -> {L |- bfree (abs R)} -> {L |- bfree Y} -> (forall P, {K |- path (abs R) P} -> {K |- path Y P}) -> (exists YR, Y = abs YR).

============================ forall L K R Y, bfctx L K -> {L |- bfree (abs R)} -> {L |- bfree Y} -> (forall P, {K |- path (abs R) P} -> {K |- path Y P}) -> (exists YR, Y = abs YR) path_abs <intros.

Variables: L K R Y H1 : bfctx L K H2 : {L |- bfree (abs R)} H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} ============================ exists YR, Y = abs YR path_abs <case H2.

Subgoal 1: Variables: L K R Y H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <assert bfctx (bfree n1 :: L) (path n1 n2 :: K).

Subgoal 1: Variables: L K R Y H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <apply path_exists to H6 H5.

Subgoal 1: Variables: L K R Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <assert {K |- path (abs R) (bnd P)}.

Subgoal 1: Variables: L K R Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <apply H4 to H8.

Subgoal 1: Variables: L K R Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H9 : {K |- path Y (bnd P)} ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <case H9.

Subgoal 1.1: Variables: L K R P M H1 : bfctx L K H3 : {L |- bfree (abs M)} H4 : forall P, {K |- path (abs R) P} -> {K |- path (abs M) P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H10 : {K, path n1 n2 |- path (M n1) (P n2)} ============================ exists YR, abs M = abs YR Subgoal 1.2 is: exists YR, beta R1 N = abs YR Subgoal 1.3 is: exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <search.

Subgoal 1.2: Variables: L K R P R1 N H1 : bfctx L K H3 : {L |- bfree (beta R1 N)} H4 : forall P, {K |- path (abs R) P} -> {K |- path (beta R1 N) P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H10 : {K, pi q\path N q => path n1 q |- path (R1 n1) (bnd P)} ============================ exists YR, beta R1 N = abs YR Subgoal 1.3 is: exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <apply bfree_beta_absurd to H1 H3.

Subgoal 1.3: Variables: L K R Y P F H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H10 : {K, [F] |- path Y (bnd P)} H11 : member F K ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <apply bfctx_member2 to H1 H11.

Subgoal 1.3: Variables: L K R Y P E F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H10 : {K, [path E F1] |- path Y (bnd P)} H11 : member (path E F1) K H12 : name E H13 : pname F1 ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <case H10.

Subgoal 1.3: Variables: L K R Y P H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, bfree n1 |- bfree (R n1)} H6 : bfctx (bfree n1 :: L) (path n1 n2 :: K) H7 : {K, path n1 n2 |- path (R n1) (P n2)} H8 : {K |- path (abs R) (bnd P)} H11 : member (path Y (bnd P)) K H12 : name Y H13 : pname (bnd P) ============================ exists YR, Y = abs YR Subgoal 2 is: exists YR, Y = abs YR path_abs <case H13.

Subgoal 2: Variables: L K R Y F H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, [F] |- bfree (abs R)} H6 : member F L ============================ exists YR, Y = abs YR path_abs <apply bfctx_member1 to H1 H6.

Subgoal 2: Variables: L K R Y E F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H5 : {L, [bfree E] |- bfree (abs R)} H6 : member (bfree E) L H7 : name E H8 : member (path E F1) K H9 : pname F1 ============================ exists YR, Y = abs YR path_abs <case H5.

Subgoal 2: Variables: L K R Y F1 H1 : bfctx L K H3 : {L |- bfree Y} H4 : forall P, {K |- path (abs R) P} -> {K |- path Y P} H6 : member (bfree (abs R)) L H7 : name (abs R) H8 : member (path (abs R) F1) K H9 : pname F1 ============================ exists YR, Y = abs YR path_abs <case H7.Proof completed.

Abella <Theorem bfree_sames : forall L K M N, bfctx L K -> {L |- bfree M} -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N.

============================ forall L K M N, bfctx L K -> {L |- bfree M} -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N bfree_sames <induction on 2.

IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N ============================ forall L K M N, bfctx L K -> {L |- bfree M}@ -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N bfree_sames <intros.

Variables: L K M N IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} ============================ M = N bfree_sames <case H2 (keep).

Subgoal 1: Variables: L K N M1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H3 : {L |- bfree N} H4 : forall p, {K |- path (abs M1) p} -> {K |- path N p} H5 : {L, bfree n1 |- bfree (M1 n1)}* ============================ abs M1 = N Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply path_abs to H1 H2 H3 H4.

Subgoal 1: Variables: L K M1 YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H3 : {L |- bfree (abs YR)} H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* ============================ abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H3.

Subgoal 1.1: Variables: L K M1 YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} ============================ abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <assert forall p, {K, path n1 n2 |- path (M1 n1) p} -> {K, path n1 n2 |- path (YR n1) p}.

Subgoal 1.1.1: Variables: L K M1 YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} ============================ forall p, {K, path n1 n2 |- path (M1 n1) p} -> {K, path n1 n2 |- path (YR n1) p} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <intros.

Subgoal 1.1.1: Variables: L K M1 YR p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <assert {K |- path (abs M1) (bnd p)}.

Subgoal 1.1.1: Variables: L K M1 YR p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} H8 : {K |- path (abs M1) (bnd p)} ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply H4 to H8.

Subgoal 1.1.1: Variables: L K M1 YR p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} H8 : {K |- path (abs M1) (bnd p)} H9 : {K |- path (abs YR) (bnd p)} ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H9.

Subgoal 1.1.1.1: Variables: L K M1 YR p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} H8 : {K |- path (abs M1) (bnd p)} H10 : {K, path n1 n2 |- path (YR n1) (p n2)} ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1.1.2 is: {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <search.

Subgoal 1.1.1.2: Variables: L K M1 YR p F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} H8 : {K |- path (abs M1) (bnd p)} H10 : {K, [F] |- path (abs YR) (bnd p)} H11 : member F K ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply bfctx_member2 to H1 H11.

Subgoal 1.1.1.2: Variables: L K M1 YR p E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : {K, path n1 n2 |- path (M1 n1) (p n2)} H8 : {K |- path (abs M1) (bnd p)} H10 : {K, [path E F1] |- path (abs YR) (bnd p)} H11 : member (path E F1) K H12 : name E H13 : pname F1 ============================ {K, path n1 n2 |- path (YR n1) (p n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H13.

Subgoal 1.1.1.2: Variables: L K M1 YR p E IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n3) (K n3) H2 : {L n3 |- bfree (abs M1)}@ H4 : forall p, {K n3 |- path (abs M1) p} -> {K n3 |- path (abs YR) p} H5 : {L n3, bfree n1 |- bfree (M1 n1)}* H6 : {L n3, bfree n1 |- bfree (YR n1)} H7 : {K n3, path n1 n2 |- path (M1 n1) (p n3 n2)} H8 : {K n3 |- path (abs M1) (bnd (p n3))} H10 : {K n3, [path E n3] |- path (abs YR) (bnd (p n3))} H11 : member (path E n3) (K n3) H12 : name E ============================ {K n3, path n1 n2 |- path (YR n1) (p n3 n2)} Subgoal 1.1 is: abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H10.

Subgoal 1.1: Variables: L K M1 YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : forall p, {K, path n1 n2 |- path (M1 n1) p} -> {K, path n1 n2 |- path (YR n1) p} ============================ abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <assert bfctx (bfree n1 :: L) (path n1 n2 :: K).

Subgoal 1.1: Variables: L K M1 YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : forall p, {K, path n1 n2 |- path (M1 n1) p} -> {K, path n1 n2 |- path (YR n1) p} H8 : bfctx (bfree n1 :: L) (path n1 n2 :: K) ============================ abs M1 = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply IH to H8 H5 H6 H7.

Subgoal 1.1: Variables: L K YR IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs (z1\YR z1))}@ H4 : forall p, {K |- path (abs (z1\YR z1)) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (YR n1)}* H6 : {L, bfree n1 |- bfree (YR n1)} H7 : forall p, {K, path n1 n2 |- path (YR n1) p} -> {K, path n1 n2 |- path (YR n1) p} H8 : bfctx (bfree n1 :: L) (path n1 n2 :: K) ============================ abs (z1\YR z1) = abs YR Subgoal 1.2 is: abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <search.

Subgoal 1.2: Variables: L K M1 YR F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, [F] |- bfree (abs YR)} H7 : member F L ============================ abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply bfctx_member1 to H1 H7.

Subgoal 1.2: Variables: L K M1 YR E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (abs M1)}@ H4 : forall p, {K |- path (abs M1) p} -> {K |- path (abs YR) p} H5 : {L, bfree n1 |- bfree (M1 n1)}* H6 : {L, [bfree E] |- bfree (abs YR)} H7 : member (bfree E) L H8 : name E H9 : member (path E F1) K H10 : pname F1 ============================ abs M1 = abs YR Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H8.

Subgoal 1.2: Variables: L K M1 YR F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n2) (K n2) H2 : {L n2 |- bfree (abs (M1 n2))}@ H4 : forall p, {K n2 |- path (abs (M1 n2)) p} -> {K n2 |- path (abs (YR n2)) p} H5 : {L n2, bfree n1 |- bfree (M1 n2 n1)}* H6 : {L n2, [bfree n2] |- bfree (abs (YR n2))} H7 : member (bfree n2) (L n2) H9 : member (path n2 F1) (K n2) H10 : pname F1 ============================ abs (M1 n2) = abs (YR n2) Subgoal 2 is: app M1 N1 = N Subgoal 3 is: M = N bfree_sames <case H6.

Subgoal 2: Variables: L K N N1 M1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H3 : {L |- bfree N} H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path N p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* ============================ app M1 N1 = N Subgoal 3 is: M = N bfree_sames <apply path_app to H1 H2 H3 H4.

Subgoal 2: Variables: L K N1 M1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H3 : {L |- bfree (app YM YN)} H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* ============================ app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H3.

Subgoal 2.1: Variables: L K N1 M1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} ============================ app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <assert forall p, {K |- path M1 p} -> {K |- path YM p}.

Subgoal 2.1.1: Variables: L K N1 M1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} ============================ forall p, {K |- path M1 p} -> {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <intros.

Subgoal 2.1.1: Variables: L K N1 M1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} ============================ {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <assert {K |- path (app M1 N1) (left p)}.

Subgoal 2.1.1: Variables: L K N1 M1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} H10 : {K |- path (app M1 N1) (left p)} ============================ {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply H4 to H10.

Subgoal 2.1.1: Variables: L K N1 M1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} H10 : {K |- path (app M1 N1) (left p)} H11 : {K |- path (app YM YN) (left p)} ============================ {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H11.

Subgoal 2.1.1.1: Variables: L K N1 M1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} H10 : {K |- path (app M1 N1) (left p)} H12 : {K |- path YM p} ============================ {K |- path YM p} Subgoal 2.1.1.2 is: {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <search.

Subgoal 2.1.1.2: Variables: L K N1 M1 YM YN p F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} H10 : {K |- path (app M1 N1) (left p)} H12 : {K, [F] |- path (app YM YN) (left p)} H13 : member F K ============================ {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply bfctx_member2 to H1 H13.

Subgoal 2.1.1.2: Variables: L K N1 M1 YM YN p E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : {K |- path M1 p} H10 : {K |- path (app M1 N1) (left p)} H12 : {K, [path E F1] |- path (app YM YN) (left p)} H13 : member (path E F1) K H14 : name E H15 : pname F1 ============================ {K |- path YM p} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H15.

Subgoal 2.1.1.2: Variables: L K N1 M1 YM YN p E IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree (app M1 N1)}@ H4 : forall p, {K n1 |- path (app M1 N1) p} -> {K n1 |- path (app YM YN) p} H5 : {L n1 |- bfree M1}* H6 : {L n1 |- bfree N1}* H7 : {L n1 |- bfree YM} H8 : {L n1 |- bfree YN} H9 : {K n1 |- path M1 (p n1)} H10 : {K n1 |- path (app M1 N1) (left (p n1))} H12 : {K n1, [path E n1] |- path (app YM YN) (left (p n1))} H13 : member (path E n1) (K n1) H14 : name E ============================ {K n1 |- path YM (p n1)} Subgoal 2.1 is: app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H12.

Subgoal 2.1: Variables: L K N1 M1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path M1 p} -> {K |- path YM p} ============================ app M1 N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply IH to H1 H5 H7 H9.

Subgoal 2.1: Variables: L K N1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} ============================ app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <assert forall p, {K |- path N1 p} -> {K |- path YN p}.

Subgoal 2.1.2: Variables: L K N1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} ============================ forall p, {K |- path N1 p} -> {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <intros.

Subgoal 2.1.2: Variables: L K N1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} ============================ {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <assert {K |- path (app M1 N1) (right p)}.

Subgoal 2.1.2: Variables: L K N1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} H11 : {K |- path (app YM N1) (right p)} ============================ {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply H4 to H11.

Subgoal 2.1.2: Variables: L K N1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} H11 : {K |- path (app YM N1) (right p)} H12 : {K |- path (app YM YN) (right p)} ============================ {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H12.

Subgoal 2.1.2.1: Variables: L K N1 YM YN p IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} H11 : {K |- path (app YM N1) (right p)} H13 : {K |- path YN p} ============================ {K |- path YN p} Subgoal 2.1.2.2 is: {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <search.

Subgoal 2.1.2.2: Variables: L K N1 YM YN p F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} H11 : {K |- path (app YM N1) (right p)} H13 : {K, [F] |- path (app YM YN) (right p)} H14 : member F K ============================ {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply bfctx_member2 to H1 H14.

Subgoal 2.1.2.2: Variables: L K N1 YM YN p E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : {K |- path N1 p} H11 : {K |- path (app YM N1) (right p)} H13 : {K, [path E F1] |- path (app YM YN) (right p)} H14 : member (path E F1) K H15 : name E H16 : pname F1 ============================ {K |- path YN p} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H16.

Subgoal 2.1.2.2: Variables: L K N1 YM YN p E IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree (app YM N1)}@ H4 : forall p, {K n1 |- path (app YM N1) p} -> {K n1 |- path (app YM YN) p} H5 : {L n1 |- bfree YM}* H6 : {L n1 |- bfree N1}* H7 : {L n1 |- bfree YM} H8 : {L n1 |- bfree YN} H9 : forall p, {K n1 |- path YM p} -> {K n1 |- path YM p} H10 : {K n1 |- path N1 (p n1)} H11 : {K n1 |- path (app YM N1) (right (p n1))} H13 : {K n1, [path E n1] |- path (app YM YN) (right (p n1))} H14 : member (path E n1) (K n1) H15 : name E ============================ {K n1 |- path YN (p n1)} Subgoal 2.1 is: app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H13.

Subgoal 2.1: Variables: L K N1 YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM N1)}@ H4 : forall p, {K |- path (app YM N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree N1}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : forall p, {K |- path N1 p} -> {K |- path YN p} ============================ app YM N1 = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply IH to H1 H6 H8 H10.

Subgoal 2.1: Variables: L K YM YN IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app YM YN)}@ H4 : forall p, {K |- path (app YM YN) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree YM}* H6 : {L |- bfree YN}* H7 : {L |- bfree YM} H8 : {L |- bfree YN} H9 : forall p, {K |- path YM p} -> {K |- path YM p} H10 : forall p, {K |- path YN p} -> {K |- path YN p} ============================ app YM YN = app YM YN Subgoal 2.2 is: app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <search.

Subgoal 2.2: Variables: L K N1 M1 YM YN F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L, [F] |- bfree (app YM YN)} H8 : member F L ============================ app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <apply bfctx_member1 to H1 H8.

Subgoal 2.2: Variables: L K N1 M1 YM YN E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree (app M1 N1)}@ H4 : forall p, {K |- path (app M1 N1) p} -> {K |- path (app YM YN) p} H5 : {L |- bfree M1}* H6 : {L |- bfree N1}* H7 : {L, [bfree E] |- bfree (app YM YN)} H8 : member (bfree E) L H9 : name E H10 : member (path E F1) K H11 : pname F1 ============================ app M1 N1 = app YM YN Subgoal 3 is: M = N bfree_sames <case H9.

Subgoal 2.2: Variables: L K N1 M1 YM YN F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree (app (M1 n1) (N1 n1))}@ H4 : forall p, {K n1 |- path (app (M1 n1) (N1 n1)) p} -> {K n1 |- path (app (YM n1) (YN n1)) p} H5 : {L n1 |- bfree (M1 n1)}* H6 : {L n1 |- bfree (N1 n1)}* H7 : {L n1, [bfree n1] |- bfree (app (YM n1) (YN n1))} H8 : member (bfree n1) (L n1) H10 : member (path n1 F1) (K n1) H11 : pname F1 ============================ app (M1 n1) (N1 n1) = app (YM n1) (YN n1) Subgoal 3 is: M = N bfree_sames <case H7.

Subgoal 3: Variables: L K M N F IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} H5 : {L, [F] |- bfree M}* H6 : member F L ============================ M = N bfree_sames <apply bfctx_member1 to H1 H6.

Subgoal 3: Variables: L K M N E F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} H5 : {L, [bfree E] |- bfree M}* H6 : member (bfree E) L H7 : name E H8 : member (path E F1) K H9 : pname F1 ============================ M = N bfree_sames <case H5.

Subgoal 3: Variables: L K M N F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} H6 : member (bfree M) L H7 : name M H8 : member (path M F1) K H9 : pname F1 ============================ M = N bfree_sames <assert {K |- path M F1}.

Subgoal 3: Variables: L K M N F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} H6 : member (bfree M) L H7 : name M H8 : member (path M F1) K H9 : pname F1 H10 : {K |- path M F1} ============================ M = N bfree_sames <apply H4 to H10.

Subgoal 3: Variables: L K M N F1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx L K H2 : {L |- bfree M}@ H3 : {L |- bfree N} H4 : forall p, {K |- path M p} -> {K |- path N p} H6 : member (bfree M) L H7 : name M H8 : member (path M F1) K H9 : pname F1 H10 : {K |- path M F1} H11 : {K |- path N F1} ============================ M = N bfree_sames <case H9.

Subgoal 3: Variables: L K M N IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree M}@ H3 : {L n1 |- bfree N} H4 : forall p, {K n1 |- path M p} -> {K n1 |- path N p} H6 : member (bfree M) (L n1) H7 : name M H8 : member (path M n1) (K n1) H10 : {K n1 |- path M n1} H11 : {K n1 |- path N n1} ============================ M = N bfree_sames <case H11.

Subgoal 3.1: Variables: L K M R N1 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree M}@ H3 : {L n1 |- bfree (beta R N1)} H4 : forall p, {K n1 |- path M p} -> {K n1 |- path (beta R N1) p} H6 : member (bfree M) (L n1) H7 : name M H8 : member (path M n1) (K n1) H10 : {K n1 |- path M n1} H12 : {K n1, pi q\path N1 q => path n2 q |- path (R n2) n1} ============================ M = beta R N1 Subgoal 3.2 is: M = N bfree_sames <apply bfree_beta_absurd to H1 H3.

Subgoal 3.2: Variables: L K M N F2 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree M}@ H3 : {L n1 |- bfree N} H4 : forall p, {K n1 |- path M p} -> {K n1 |- path N p} H6 : member (bfree M) (L n1) H7 : name M H8 : member (path M n1) (K n1) H10 : {K n1 |- path M n1} H12 : {K n1, [F2 n1] |- path N n1} H13 : member (F2 n1) (K n1) ============================ M = N bfree_sames <apply bfctx_member2 to H1 H13.

Subgoal 3.2: Variables: L K M N E1 F3 IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree M}@ H3 : {L n1 |- bfree N} H4 : forall p, {K n1 |- path M p} -> {K n1 |- path N p} H6 : member (bfree M) (L n1) H7 : name M H8 : member (path M n1) (K n1) H10 : {K n1 |- path M n1} H12 : {K n1, [path E1 (F3 n1)] |- path N n1} H13 : member (path E1 (F3 n1)) (K n1) H14 : name E1 H15 : pname (F3 n1) ============================ M = N bfree_sames <case H12.

Subgoal 3.2: Variables: L K M N IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree M}@ H3 : {L n1 |- bfree N} H4 : forall p, {K n1 |- path M p} -> {K n1 |- path N p} H6 : member (bfree M) (L n1) H7 : name M H8 : member (path M n1) (K n1) H10 : {K n1 |- path M n1} H13 : member (path N n1) (K n1) H14 : name N H15 : pname n1 ============================ M = N bfree_sames <apply member_path_unique to H1 H8 H13.

Subgoal 3.2: Variables: L K N IH : forall L K M N, bfctx L K -> {L |- bfree M}* -> {L |- bfree N} -> (forall p, {K |- path M p} -> {K |- path N p}) -> M = N H1 : bfctx (L n1) (K n1) H2 : {L n1 |- bfree N}@ H3 : {L n1 |- bfree N} H4 : forall p, {K n1 |- path N p} -> {K n1 |- path N p} H6 : member (bfree N) (L n1) H7 : name N H8 : member (path N n1) (K n1) H10 : {K n1 |- path N n1} H13 : member (path N n1) (K n1) H14 : name N H15 : pname n1 ============================ N = N bfree_sames <search.Proof completed.

Abella <Define brctx : olist -> olist -> prop by brctx nil nil; nabla x, brctx (bred x x :: L) (bfree x :: K) := brctx L K; nabla x, brctx ((pi u\bred N u => bred x u) :: L) K := brctx L K.

Abella <Theorem brctx_mem_1 : forall L K E, brctx L K -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N).

============================ forall L K E, brctx L K -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <induction on 1.

IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) ============================ forall L K E, brctx L K @ -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <intros.

Variables: L K E IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx L K @ H2 : member E L ============================ (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H1 (keep).

Subgoal 1: Variables: E IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx nil nil @ H2 : member E nil ============================ (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) Subgoal 2 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H2.

Subgoal 2: Variables: E K1 L1 IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H2 : member (E n1) (bred n1 n1 :: L1) H3 : brctx L1 K1 * ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H2.

Subgoal 2.1: Variables: K1 L1 IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H3 : brctx L1 K1 * ============================ (exists x, bred n1 n1 = bred x x /\ name x) \/ (exists x N, bred n1 n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 2.2 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <search.

Subgoal 2.2: Variables: E K1 L1 IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H3 : brctx L1 K1 * H4 : member (E n1) L1 ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <apply IH to H3 H4.

Subgoal 2.2: Variables: E K1 L1 IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H3 : brctx L1 K1 * H4 : member (E n1) L1 H5 : (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H5.

Subgoal 2.2.1: Variables: K1 L1 x IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H3 : brctx L1 K1 * H4 : member (bred (x n1) (x n1)) L1 H6 : name (x n1) ============================ (exists x1, bred (x n1) (x n1) = bred x1 x1 /\ name x1) \/ (exists x1 N, bred (x n1) (x n1) = pi u\bred N u => bred x1 u /\ fresh x1 N) Subgoal 2.2.2 is: (exists x1, pi u\bred (N n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N1, pi u\bred (N n1) u => bred (x n1) u = pi u\bred N1 u => bred x1 u /\ fresh x1 N1) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <search.

Subgoal 2.2.2: Variables: K1 L1 x N IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx (bred n1 n1 :: L1) (bfree n1 :: K1) @ H3 : brctx L1 K1 * H4 : member (pi u\bred (N n1) u => bred (x n1) u) L1 H6 : fresh (x n1) (N n1) ============================ (exists x1, pi u\bred (N n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N1, pi u\bred (N n1) u => bred (x n1) u = pi u\bred N1 u => bred x1 u /\ fresh x1 N1) Subgoal 3 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <search.

Subgoal 3: Variables: E K1 L1 N IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H2 : member (E n1) ((pi u\bred N u => bred n1 u) :: L1) H3 : brctx L1 K1 * ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H2.

Subgoal 3.1: Variables: K1 L1 N IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H3 : brctx L1 K1 * ============================ (exists x, pi u\bred N u => bred n1 u = bred x x /\ name x) \/ (exists x N1, pi u\bred N u => bred n1 u = pi u\bred N1 u => bred x u /\ fresh x N1) Subgoal 3.2 is: (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <search.

Subgoal 3.2: Variables: E K1 L1 N IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H3 : brctx L1 K1 * H4 : member (E n1) L1 ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <apply IH to H3 H4.

Subgoal 3.2: Variables: E K1 L1 N IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H3 : brctx L1 K1 * H4 : member (E n1) L1 H5 : (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) ============================ (exists x, E n1 = bred x x /\ name x) \/ (exists x N, E n1 = pi u\bred N u => bred x u /\ fresh x N) brctx_mem_1 <case H5.

Subgoal 3.2.1: Variables: K1 L1 N x IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H3 : brctx L1 K1 * H4 : member (bred (x n1) (x n1)) L1 H6 : name (x n1) ============================ (exists x1, bred (x n1) (x n1) = bred x1 x1 /\ name x1) \/ (exists x1 N, bred (x n1) (x n1) = pi u\bred N u => bred x1 u /\ fresh x1 N) Subgoal 3.2.2 is: (exists x1, pi u\bred (N1 n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N, pi u\bred (N1 n1) u => bred (x n1) u = pi u\bred N u => bred x1 u /\ fresh x1 N) brctx_mem_1 <search.

Subgoal 3.2.2: Variables: K1 L1 N x N1 IH : forall L K E, brctx L K * -> member E L -> (exists x, E = bred x x /\ name x) \/ (exists x N, E = pi u\bred N u => bred x u /\ fresh x N) H1 : brctx ((pi u\bred N u => bred n1 u) :: L1) K1 @ H3 : brctx L1 K1 * H4 : member (pi u\bred (N1 n1) u => bred (x n1) u) L1 H6 : fresh (x n1) (N1 n1) ============================ (exists x1, pi u\bred (N1 n1) u => bred (x n1) u = bred x1 x1 /\ name x1) \/ (exists x1 N, pi u\bred (N1 n1) u => bred (x n1) u = pi u\bred N u => bred x1 u /\ fresh x1 N) brctx_mem_1 <search.Proof completed.

Abella <Theorem brctx_sync : forall L K, nabla x, brctx (L x) (K x) -> member (bred x x) (L x) -> member (bfree x) (K x).

============================ forall L K, nabla x, brctx (L x) (K x) -> member (bred x x) (L x) -> member (bfree x) (K x) brctx_sync <induction on 1.

IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) ============================ forall L K, nabla x, brctx (L x) (K x) @ -> member (bred x x) (L x) -> member (bfree x) (K x) brctx_sync <intros.

Variables: L K IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H1 : brctx (L n1) (K n1) @ H2 : member (bred n1 n1) (L n1) ============================ member (bfree n1) (K n1) brctx_sync <case H1.

Subgoal 1: IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H2 : member (bred n1 n1) nil ============================ member (bfree n1) nil Subgoal 2 is: member (bfree n1) (bfree n2 :: K1 n1) Subgoal 3 is: member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <case H2.

Subgoal 2: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H2 : member (bred n1 n1) (bred n2 n2 :: L1 n1) H3 : brctx (L1 n1) (K1 n1) * ============================ member (bfree n1) (bfree n2 :: K1 n1) Subgoal 3 is: member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <case H2.

Subgoal 2: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx (L1 n1) (K1 n1) * H4 : member (bred n1 n1) (L1 n1) ============================ member (bfree n1) (bfree n2 :: K1 n1) Subgoal 3 is: member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <apply IH to H3 H4.

Subgoal 2: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx (L1 n1) (K1 n1) * H4 : member (bred n1 n1) (L1 n1) H5 : member (bfree n1) (K1 n1) ============================ member (bfree n1) (bfree n2 :: K1 n1) Subgoal 3 is: member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <search.

Subgoal 3: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H2 : member (bred n1 n1) (bred n1 n1 :: L1) H3 : brctx L1 K1 * ============================ member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <case H2.

Subgoal 3.1: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx L1 K1 * ============================ member (bfree n1) (bfree n1 :: K1) Subgoal 3.2 is: member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <search.

Subgoal 3.2: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx L1 K1 * H4 : member (bred n1 n1) L1 ============================ member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <apply IH to H3 H4.

Subgoal 3.2: Variables: K1 L1 IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx L1 K1 * H4 : member (bred n1 n1) L1 H5 : member (bfree n1) K1 ============================ member (bfree n1) (bfree n1 :: K1) Subgoal 4 is: member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <search.

Subgoal 4: Variables: K2 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H2 : member (bred n1 n1) ((pi u\bred (N n1) u => bred n2 u) :: L1 n1) H3 : brctx (L1 n1) (K2 n1) * ============================ member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <case H2.

Subgoal 4: Variables: K2 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx (L1 n1) (K2 n1) * H4 : member (bred n1 n1) (L1 n1) ============================ member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <apply IH to H3 H4.

Subgoal 4: Variables: K2 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx (L1 n1) (K2 n1) * H4 : member (bred n1 n1) (L1 n1) H5 : member (bfree n1) (K2 n1) ============================ member (bfree n1) (K2 n1) Subgoal 5 is: member (bfree n1) K1 brctx_sync <search.

Subgoal 5: Variables: K1 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H2 : member (bred n1 n1) ((pi u\bred N u => bred n1 u) :: L1) H3 : brctx L1 K1 * ============================ member (bfree n1) K1 brctx_sync <case H2.

Subgoal 5: Variables: K1 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx L1 K1 * H4 : member (bred n1 n1) L1 ============================ member (bfree n1) K1 brctx_sync <apply IH to H3 H4.

Subgoal 5: Variables: K1 L1 N IH : forall L K, nabla x, brctx (L x) (K x) * -> member (bred x x) (L x) -> member (bfree x) (K x) H3 : brctx L1 K1 * H4 : member (bred n1 n1) L1 H5 : member (bfree n1) K1 ============================ member (bfree n1) K1 brctx_sync <search.Proof completed.

Abella <Theorem bred_makes_bfree : forall L K M U, brctx L K -> {L |- bred M U} -> {K |- bfree U}.

============================ forall L K M U, brctx L K -> {L |- bred M U} -> {K |- bfree U} bred_makes_bfree <induction on 2.

IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} ============================ forall L K M U, brctx L K -> {L |- bred M U}@ -> {K |- bfree U} bred_makes_bfree <intros.

Variables: L K M U IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ ============================ {K |- bfree U} bred_makes_bfree <case H2 (keep).

Subgoal 1: Variables: L K U1 M1 IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (abs M1) (abs U1)}@ H3 : {L, bred n1 n1 |- bred (M1 n1) (U1 n1)}* ============================ {K |- bfree (abs U1)} Subgoal 2 is: {K |- bfree (app U1 V)} Subgoal 3 is: {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <apply IH to _ H3.

Subgoal 1: Variables: L K U1 M1 IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (abs M1) (abs U1)}@ H3 : {L, bred n1 n1 |- bred (M1 n1) (U1 n1)}* H4 : {K, bfree n1 |- bfree (U1 n1)} ============================ {K |- bfree (abs U1)} Subgoal 2 is: {K |- bfree (app U1 V)} Subgoal 3 is: {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <search.

Subgoal 2: Variables: L K V N U1 M1 IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (app M1 N) (app U1 V)}@ H3 : {L |- bred M1 U1}* H4 : {L |- bred N V}* ============================ {K |- bfree (app U1 V)} Subgoal 3 is: {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <apply IH to _ H3.

Subgoal 2: Variables: L K V N U1 M1 IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (app M1 N) (app U1 V)}@ H3 : {L |- bred M1 U1}* H4 : {L |- bred N V}* H5 : {K |- bfree U1} ============================ {K |- bfree (app U1 V)} Subgoal 3 is: {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <apply IH to _ H4.

Subgoal 2: Variables: L K V N U1 M1 IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (app M1 N) (app U1 V)}@ H3 : {L |- bred M1 U1}* H4 : {L |- bred N V}* H5 : {K |- bfree U1} H6 : {K |- bfree V} ============================ {K |- bfree (app U1 V)} Subgoal 3 is: {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <search.

Subgoal 3: Variables: L K U R N IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (beta R N) U}@ H3 : {L, pi u\bred N u => bred n1 u |- bred (R n1) U}* ============================ {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <apply IH to _ H3.

Subgoal 3: Variables: L K U R N IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred (beta R N) U}@ H3 : {L, pi u\bred N u => bred n1 u |- bred (R n1) U}* H4 : {K |- bfree U} ============================ {K |- bfree U} Subgoal 4 is: {K |- bfree U} bred_makes_bfree <search.

Subgoal 4: Variables: L K M U F IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ H3 : {L, [F] |- bred M U}* H4 : member F L ============================ {K |- bfree U} bred_makes_bfree <apply brctx_mem_1 to H1 H4.

Subgoal 4: Variables: L K M U F IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ H3 : {L, [F] |- bred M U}* H4 : member F L H5 : (exists x, F = bred x x /\ name x) \/ (exists x N, F = pi u\bred N u => bred x u /\ fresh x N) ============================ {K |- bfree U} bred_makes_bfree <case H5.

Subgoal 4.1: Variables: L K M U x IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ H3 : {L, [bred x x] |- bred M U}* H4 : member (bred x x) L H6 : name x ============================ {K |- bfree U} Subgoal 4.2 is: {K |- bfree U} bred_makes_bfree <case H3.

Subgoal 4.1: Variables: L K U IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred U U}@ H4 : member (bred U U) L H6 : name U ============================ {K |- bfree U} Subgoal 4.2 is: {K |- bfree U} bred_makes_bfree <case H6.

Subgoal 4.1: Variables: L K IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx (L n1) (K n1) H2 : {L n1 |- bred n1 n1}@ H4 : member (bred n1 n1) (L n1) ============================ {K n1 |- bfree n1} Subgoal 4.2 is: {K |- bfree U} bred_makes_bfree <apply brctx_sync to H1 H4.

Subgoal 4.1: Variables: L K IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx (L n1) (K n1) H2 : {L n1 |- bred n1 n1}@ H4 : member (bred n1 n1) (L n1) H7 : member (bfree n1) (K n1) ============================ {K n1 |- bfree n1} Subgoal 4.2 is: {K |- bfree U} bred_makes_bfree <search.

Subgoal 4.2: Variables: L K M U x N IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ H3 : {L, [pi u\bred N u => bred x u] |- bred M U}* H4 : member (pi u\bred N u => bred x u) L H6 : fresh x N ============================ {K |- bfree U} bred_makes_bfree <case H3.

Subgoal 4.2: Variables: L K M U N IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx L K H2 : {L |- bred M U}@ H4 : member (pi u\bred N u => bred M u) L H6 : fresh M N H7 : {L |- bred N U}* ============================ {K |- bfree U} bred_makes_bfree <case H6.

Subgoal 4.2: Variables: L K U X IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx (L n1) (K n1) H2 : {L n1 |- bred n1 (U n1)}@ H4 : member (pi u\bred X u => bred n1 u) (L n1) H7 : {L n1 |- bred X (U n1)}* ============================ {K n1 |- bfree (U n1)} bred_makes_bfree <apply IH to H1 H7.

Subgoal 4.2: Variables: L K U X IH : forall L K M U, brctx L K -> {L |- bred M U}* -> {K |- bfree U} H1 : brctx (L n1) (K n1) H2 : {L n1 |- bred n1 (U n1)}@ H4 : member (pi u\bred X u => bred n1 u) (L n1) H7 : {L n1 |- bred X (U n1)}* H8 : {K n1 |- bfree (U n1)} ============================ {K n1 |- bfree (U n1)} bred_makes_bfree <search.Proof completed.

Abella <Theorem same_paths_bred_same : forall M N U V, (forall P, {path M P} -> {path N P}) -> {bred M U} -> {bred N V} -> U = V.

============================ forall M N U V, (forall P, {path M P} -> {path N P}) -> {bred M U} -> {bred N V} -> U = V same_paths_bred_same <intros.

Variables: M N U V H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} ============================ U = V same_paths_bred_same <apply bred_makes_bfree to _ H2.

Variables: M N U V H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} ============================ U = V same_paths_bred_same <apply bred_makes_bfree to _ H3.

Variables: M N U V H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} ============================ U = V same_paths_bred_same <backchain bfree_sames.

Variables: M N U V H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} ============================ forall p, {path U p} -> {path V p} same_paths_bred_same <intros.

Variables: M N U V p H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} H6 : {path U p} ============================ {path V p} same_paths_bred_same <apply bred_rtl to _ H2 H6.

Variables: M N U V p H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} H6 : {path U p} H7 : {path M p} ============================ {path V p} same_paths_bred_same <apply H1 to H7.

Variables: M N U V p H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} H6 : {path U p} H7 : {path M p} H8 : {path N p} ============================ {path V p} same_paths_bred_same <apply bred_ltr to _ H3 H8.

Variables: M N U V p H1 : forall P, {path M P} -> {path N P} H2 : {bred M U} H3 : {bred N V} H4 : {bfree U} H5 : {bfree V} H6 : {path U p} H7 : {path M p} H8 : {path N p} H9 : {path V p} ============================ {path V p} same_paths_bred_same <search.Proof completed.

Abella <