< Module nonExtensible:lists.
< Theorem perm_mem [Item] :
forall (L : list Item) (M : list Item) I, perm L M -> mem I L -> mem I M.
============================
forall L M I, perm L M -> mem I L -> mem I M
< induction on 2.
IH : forall L M I, perm L M -> mem I L * -> mem I M
============================
forall L M I, perm L M -> mem I L @ -> mem I M
< intros P M.
Variables: L M I
IH : forall L M I, perm L M -> mem I L * -> mem I M
P : perm L M
M : mem I L @
============================
mem I M
< M: case M.
Subgoal 1:
Variables: M I Rest
IH : forall L M I, perm L M -> mem I L * -> mem I M
P : perm (I::Rest) M
============================
mem I M
< P: case P.
Subgoal 1:
Variables: M I Rest L2
IH : forall L M I, perm L M -> mem I L * -> mem I M
P : select I L2 M
P1 : perm Rest L2
============================
mem I M
< apply select_mem to P.
Subgoal 1:
Variables: M I Rest L2
IH : forall L M I, perm L M -> mem I L * -> mem I M
P : select I L2 M
P1 : perm Rest L2
H1 : mem I M
============================
mem I M
< search.
Subgoal 2:
Variables: M I Rest I1
IH : forall L M I, perm L M -> mem I L * -> mem I M
P : perm (I1::Rest) M
M : mem I Rest *
============================
mem I M
< P: case P.
Subgoal 2:
Variables: M I Rest I1 L2
IH : forall L M I, perm L M -> mem I L * -> mem I M
M : mem I Rest *
P : select I1 L2 M
P1 : perm Rest L2
============================
mem I M
< M': apply IH to P1 M.
Subgoal 2:
Variables: M I Rest I1 L2
IH : forall L M I, perm L M -> mem I L * -> mem I M
M : mem I Rest *
P : select I1 L2 M
P1 : perm Rest L2
M' : mem I L2
============================
mem I M
< apply mem_after_select_before to _ M'.
Subgoal 2:
Variables: M I Rest I1 L2
IH : forall L M I, perm L M -> mem I L * -> mem I M
M : mem I Rest *
P : select I1 L2 M
P1 : perm Rest L2
M' : mem I L2
H1 : mem I M
============================
mem I M
< search.
Proof completed.
< Theorem prm_lemma [Item] :
forall A B B' (X : Item), perm B' A -> select X B' B -> perm B (X::A).
============================
forall A B B' X, perm B' A -> select X B' B -> perm B (X::A)
< induction on 2.
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
============================
forall A B B' X, perm B' A -> select X B' B @ -> perm B (X::A)
< intros P S.
Variables: A B B' X
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
P : perm B' A
S : select X B' B @
============================
perm B (X::A)
< S: case S.
Subgoal 1:
Variables: A B' X
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
P : perm B' A
============================
perm (X::B') (X::A)
< search.
Subgoal 2:
Variables: A X L2 I L1
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
P : perm (I::L1) A
S : select X L1 L2 *
============================
perm (I::L2) (X::A)
< P: case P.
Subgoal 2:
Variables: A X L2 I L1 L3
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
S : select X L1 L2 *
P : select I L3 A
P1 : perm L1 L3
============================
perm (I::L2) (X::A)
< apply IH to P1 S.
Subgoal 2:
Variables: A X L2 I L1 L3
IH : forall A B B' X, perm B' A -> select X B' B * -> perm B (X::A)
S : select X L1 L2 *
P : select I L3 A
P1 : perm L1 L3
H1 : perm L2 (X::L3)
============================
perm (I::L2) (X::A)
< search.
Proof completed.
< Theorem perm_symmetric [Item] :
forall (M : list Item) (L : list Item), perm L M -> perm M L.
============================
forall M L, perm L M -> perm M L
< induction on 1.
IH : forall M L, perm L M * -> perm M L
============================
forall M L, perm L M @ -> perm M L
< intros P.
Variables: M L
IH : forall M L, perm L M * -> perm M L
P : perm L M @
============================
perm M L
< P: case P.
Subgoal 1:
IH : forall M L, perm L M * -> perm M L
============================
perm [] []
< search.
Subgoal 2:
Variables: M L2 Rest A
IH : forall M L, perm L M * -> perm M L
P : select A L2 M
P1 : perm Rest L2 *
============================
perm M (A::Rest)
< PSub: apply IH to P1.
Subgoal 2:
Variables: M L2 Rest A
IH : forall M L, perm L M * -> perm M L
P : select A L2 M
P1 : perm Rest L2 *
PSub : perm L2 Rest
============================
perm M (A::Rest)
< apply prm_lemma to PSub P.
Subgoal 2:
Variables: M L2 Rest A
IH : forall M L, perm L M * -> perm M L
P : select A L2 M
P1 : perm Rest L2 *
PSub : perm L2 Rest
H1 : perm M (A::Rest)
============================
perm M (A::Rest)
< search.
Proof completed.
< Theorem no_lookup_perm [Key, Value] :
forall (L : list (pair Key Value)) (P : list (pair Key Value)) (Key : Key),
no_lookup L Key -> perm L P -> no_lookup P Key.
============================
forall L P Key, no_lookup L Key -> perm L P -> no_lookup P Key
< induction on 1.
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
============================
forall L P Key, no_lookup L Key @ -> perm L P -> no_lookup P Key
< intros NLkp P.
Variables: L P Key
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
NLkp : no_lookup L Key @
P : perm L P
============================
no_lookup P Key
< NLkp: case NLkp.
Subgoal 1:
Variables: P Key
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
P : perm [] P
============================
no_lookup P Key
< case P.
Subgoal 1:
Variables: Key
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
============================
no_lookup [] Key
< search.
Subgoal 2:
Variables: P Key Rest V K
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
P : perm ((K, V)::Rest) P
NLkp : K = Key -> false
NLkp1 : no_lookup Rest Key *
============================
no_lookup P Key
< P: case P.
Subgoal 2:
Variables: P Key Rest V K L2
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
NLkp : K = Key -> false
NLkp1 : no_lookup Rest Key *
P : select (K, V) L2 P
P1 : perm Rest L2
============================
no_lookup P Key
< NLkp': apply IH to NLkp1 P1.
Subgoal 2:
Variables: P Key Rest V K L2
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
NLkp : K = Key -> false
NLkp1 : no_lookup Rest Key *
P : select (K, V) L2 P
P1 : perm Rest L2
NLkp' : no_lookup L2 Key
============================
no_lookup P Key
< apply no_lookup_after_select_before to NLkp' P NLkp.
Subgoal 2:
Variables: P Key Rest V K L2
IH : forall L P Key, no_lookup L Key * -> perm L P -> no_lookup P Key
NLkp : K = Key -> false
NLkp1 : no_lookup Rest Key *
P : select (K, V) L2 P
P1 : perm Rest L2
NLkp' : no_lookup L2 Key
H1 : no_lookup P Key
============================
no_lookup P Key
< search.
Proof completed.
< Theorem countItem_is_integer [Item] :
forall (I : Item) L N, countItem I L N -> is_integer N.
============================
forall I L N, countItem I L N -> is_integer N
< induction on 1.
IH : forall I L N, countItem I L N * -> is_integer N
============================
forall I L N, countItem I L N @ -> is_integer N
< intros C.
Variables: I L N
IH : forall I L N, countItem I L N * -> is_integer N
C : countItem I L N @
============================
is_integer N
< C: case C.
Subgoal 1:
Variables: I
IH : forall I L N, countItem I L N * -> is_integer N
============================
is_integer 0
< search.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> is_integer N
C : countItem I Rest N1 *
C1 : 1 + N1 = N
============================
is_integer N
< apply IH to C.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> is_integer N
C : countItem I Rest N1 *
C1 : 1 + N1 = N
H1 : is_integer N1
============================
is_integer N
< apply plus_integer_is_integer to _ _ C1.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> is_integer N
C : countItem I Rest N1 *
C1 : 1 + N1 = N
H1 : is_integer N1
H2 : is_integer N
============================
is_integer N
< search.
Subgoal 3:
Variables: I N Rest Y
IH : forall I L N, countItem I L N * -> is_integer N
C : I = Y -> false
C1 : countItem I Rest N *
============================
is_integer N
< apply IH to C1.
Subgoal 3:
Variables: I N Rest Y
IH : forall I L N, countItem I L N * -> is_integer N
C : I = Y -> false
C1 : countItem I Rest N *
H1 : is_integer N
============================
is_integer N
< search.
Proof completed.
< Theorem countItem_geq_0 [Item] :
forall (I : Item) L N, countItem I L N -> N >= 0.
============================
forall I L N, countItem I L N -> N >= 0
< induction on 1.
IH : forall I L N, countItem I L N * -> N >= 0
============================
forall I L N, countItem I L N @ -> N >= 0
< intros C.
Variables: I L N
IH : forall I L N, countItem I L N * -> N >= 0
C : countItem I L N @
============================
N >= 0
< C: case C.
Subgoal 1:
Variables: I
IH : forall I L N, countItem I L N * -> N >= 0
============================
0 >= 0
< search.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> N >= 0
C : countItem I Rest N1 *
C1 : 1 + N1 = N
============================
N >= 0
< GEq: apply IH to C.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> N >= 0
C : countItem I Rest N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
============================
N >= 0
< apply greatereq_integer__add_positive to _ GEq C1.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I L N, countItem I L N * -> N >= 0
C : countItem I Rest N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
H1 : N >= 0
============================
N >= 0
< search.
Subgoal 3:
Variables: I N Rest Y
IH : forall I L N, countItem I L N * -> N >= 0
C : I = Y -> false
C1 : countItem I Rest N *
============================
N >= 0
< apply IH to C1.
Subgoal 3:
Variables: I N Rest Y
IH : forall I L N, countItem I L N * -> N >= 0
C : I = Y -> false
C1 : countItem I Rest N *
H1 : N >= 0
============================
N >= 0
< search.
Proof completed.
< Theorem select_countItem [Item] :
forall (I : Item) L Rest N N',
countItem I L N -> select I Rest L -> N - 1 = N' -> countItem I Rest N'.
============================
forall I L Rest N N',
countItem I L N -> select I Rest L -> N - 1 = N' -> countItem I Rest N'
< induction on 2.
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
============================
forall I L Rest N N',
countItem I L N -> select I Rest L @ -> N - 1 = N' -> countItem I Rest N'
< intros C S Minus.
Variables: I L Rest N N'
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
C : countItem I L N
S : select I Rest L @
Minus : N - 1 = N'
============================
countItem I Rest N'
< S: case S.
Subgoal 1:
Variables: I Rest N N'
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
C : countItem I (I::Rest) N
Minus : N - 1 = N'
============================
countItem I Rest N'
< IsN: apply countItem_is_integer to C.
Subgoal 1:
Variables: I Rest N N'
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
C : countItem I (I::Rest) N
Minus : N - 1 = N'
IsN : is_integer N
============================
countItem I Rest N'
< C: case C.
Subgoal 1.1:
Variables: I Rest N N' N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
IsN : is_integer N
C : countItem I Rest N1
C1 : 1 + N1 = N
============================
countItem I Rest N'
< IsN1: apply countItem_is_integer to C.
Subgoal 1.1:
Variables: I Rest N N' N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
IsN : is_integer N
C : countItem I Rest N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
============================
countItem I Rest N'
< P: apply plus_integer_comm to _ _ C1.
Subgoal 1.1:
Variables: I Rest N N' N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
IsN : is_integer N
C : countItem I Rest N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
============================
countItem I Rest N'
< M2: apply plus_minus_same_integer to _ _ P.
Subgoal 1.1:
Variables: I Rest N N' N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
IsN : is_integer N
C : countItem I Rest N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
============================
countItem I Rest N'
< apply minus_integer_unique to Minus M2.
Subgoal 1.1:
Variables: I Rest N N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
IsN : is_integer N
C : countItem I Rest N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
============================
countItem I Rest N1
< search.
Subgoal 1.2:
Variables: I Rest N N'
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
IsN : is_integer N
C : I = I -> false
C1 : countItem I Rest N
============================
countItem I Rest N'
< apply C to _.
Subgoal 2:
Variables: I N N' L2 I1 L1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
C : countItem I (I1::L2) N
Minus : N - 1 = N'
S : select I L1 L2 *
============================
countItem I (I1::L1) N'
< IsN: apply countItem_is_integer to C.
Subgoal 2:
Variables: I N N' L2 I1 L1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
C : countItem I (I1::L2) N
Minus : N - 1 = N'
S : select I L1 L2 *
IsN : is_integer N
============================
countItem I (I1::L1) N'
< C: case C.
Subgoal 2.1:
Variables: N N' L2 I1 L1 N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
============================
countItem I1 (I1::L1) N'
< IsN1: apply countItem_is_integer to C.
Subgoal 2.1:
Variables: N N' L2 I1 L1 N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
============================
countItem I1 (I1::L1) N'
< P: apply plus_integer_comm to _ _ C1.
Subgoal 2.1:
Variables: N N' L2 I1 L1 N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
============================
countItem I1 (I1::L1) N'
< M2: apply plus_minus_same_integer to _ _ P.
Subgoal 2.1:
Variables: N N' L2 I1 L1 N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
============================
countItem I1 (I1::L1) N'
< apply minus_integer_unique to Minus M2.
Subgoal 2.1:
Variables: N L2 I1 L1 N1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
============================
countItem I1 (I1::L1) N1
< Sub: apply minus_integer_total to IsN1 _ with
N2 = 1.
Subgoal 2.1:
Variables: N L2 I1 L1 N1 N3
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
Sub : N1 - 1 = N3
============================
countItem I1 (I1::L1) N1
< C': apply IH to C S Sub.
Subgoal 2.1:
Variables: N L2 I1 L1 N1 N3
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
Sub : N1 - 1 = N3
C' : countItem I1 L1 N3
============================
countItem I1 (I1::L1) N1
< P': apply minus_plus_same_integer to _ _ Sub.
Subgoal 2.1:
Variables: N L2 I1 L1 N1 N3
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
Sub : N1 - 1 = N3
C' : countItem I1 L1 N3
P' : N3 + 1 = N1
============================
countItem I1 (I1::L1) N1
< apply countItem_is_integer to C'.
Subgoal 2.1:
Variables: N L2 I1 L1 N1 N3
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
Sub : N1 - 1 = N3
C' : countItem I1 L1 N3
P' : N3 + 1 = N1
H1 : is_integer N3
============================
countItem I1 (I1::L1) N1
< apply plus_integer_comm to _ _ P'.
Subgoal 2.1:
Variables: N L2 I1 L1 N1 N3
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N1
S : select I1 L1 L2 *
IsN : is_integer N
C : countItem I1 L2 N1
C1 : 1 + N1 = N
IsN1 : is_integer N1
P : N1 + 1 = N
M2 : N - 1 = N1
Sub : N1 - 1 = N3
C' : countItem I1 L1 N3
P' : N3 + 1 = N1
H1 : is_integer N3
H2 : 1 + N3 = N1
============================
countItem I1 (I1::L1) N1
< search.
Subgoal 2.2:
Variables: I N N' L2 I1 L1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I L1 L2 *
IsN : is_integer N
C : I = I1 -> false
C1 : countItem I L2 N
============================
countItem I (I1::L1) N'
< apply IH to C1 S _.
Subgoal 2.2:
Variables: I N N' L2 I1 L1
IH : forall I L Rest N N',
countItem I L N -> select I Rest L * -> N - 1 = N' -> countItem I Rest N'
Minus : N - 1 = N'
S : select I L1 L2 *
IsN : is_integer N
C : I = I1 -> false
C1 : countItem I L2 N
H1 : countItem I L1 N'
============================
countItem I (I1::L1) N'
< search.
Proof completed.
< Theorem countItem_select [Item] :
forall (I : Item) L Rest N' N,
countItem I Rest N' -> select I Rest L -> 1 + N' = N -> countItem I L N.
============================
forall I L Rest N' N,
countItem I Rest N' -> select I Rest L -> 1 + N' = N -> countItem I L N
< induction on 2.
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
============================
forall I L Rest N' N,
countItem I Rest N' -> select I Rest L @ -> 1 + N' = N -> countItem I L N
< intros C S P.
Variables: I L Rest N' N
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
C : countItem I Rest N'
S : select I Rest L @
P : 1 + N' = N
============================
countItem I L N
< S: case S.
Subgoal 1:
Variables: I Rest N' N
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
C : countItem I Rest N'
P : 1 + N' = N
============================
countItem I (I::Rest) N
< search.
Subgoal 2:
Variables: I N' N L2 I1 L1
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
C : countItem I (I1::L1) N'
P : 1 + N' = N
S : select I L1 L2 *
============================
countItem I (I1::L2) N
< C: case C.
Subgoal 2.1:
Variables: N' N L2 I1 L1 N1
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
P : 1 + N' = N
S : select I1 L1 L2 *
C : countItem I1 L1 N1
C1 : 1 + N1 = N'
============================
countItem I1 (I1::L2) N
< apply IH to C S _.
Subgoal 2.1:
Variables: N' N L2 I1 L1 N1
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
P : 1 + N' = N
S : select I1 L1 L2 *
C : countItem I1 L1 N1
C1 : 1 + N1 = N'
H1 : countItem I1 L2 N'
============================
countItem I1 (I1::L2) N
< search.
Subgoal 2.2:
Variables: I N' N L2 I1 L1
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
P : 1 + N' = N
S : select I L1 L2 *
C : I = I1 -> false
C1 : countItem I L1 N'
============================
countItem I (I1::L2) N
< apply IH to C1 S _.
Subgoal 2.2:
Variables: I N' N L2 I1 L1
IH : forall I L Rest N' N,
countItem I Rest N' -> select I Rest L * -> 1 + N' = N -> countItem I L N
P : 1 + N' = N
S : select I L1 L2 *
C : I = I1 -> false
C1 : countItem I L1 N'
H1 : countItem I L2 N
============================
countItem I (I1::L2) N
< search.
Proof completed.
< Theorem select_countItem_neq [Item] :
forall (I : Item) (J : Item) L Rest N,
countItem I L N -> select J Rest L -> (I = J -> false) -> countItem I Rest N.
============================
forall I J L Rest N,
countItem I L N -> select J Rest L -> (I = J -> false) -> countItem I Rest N
< induction on 2.
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
============================
forall I J L Rest N,
countItem I L N -> select J Rest L @ -> (I = J -> false) -> countItem I Rest N
< intros C S NEq.
Variables: I J L Rest N
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
C : countItem I L N
S : select J Rest L @
NEq : I = J -> false
============================
countItem I Rest N
< S: case S.
Subgoal 1:
Variables: I J Rest N
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
C : countItem I (J::Rest) N
NEq : I = J -> false
============================
countItem I Rest N
< C: case C.
Subgoal 1.1:
Variables: J Rest N N1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : J = J -> false
C : countItem J Rest N1
C1 : 1 + N1 = N
============================
countItem J Rest N
< apply NEq to _.
Subgoal 1.2:
Variables: I J Rest N
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : I = J -> false
C : I = J -> false
C1 : countItem I Rest N
============================
countItem I Rest N
< search.
Subgoal 2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
C : countItem I (I1::L2) N
NEq : I = J -> false
S : select J L1 L2 *
============================
countItem I (I1::L1) N
< C: case C.
Subgoal 2.1:
Variables: J N L2 I1 L1 N1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : I1 = J -> false
S : select J L1 L2 *
C : countItem I1 L2 N1
C1 : 1 + N1 = N
============================
countItem I1 (I1::L1) N
< apply IH to C S _.
Subgoal 2.1:
Variables: J N L2 I1 L1 N1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : I1 = J -> false
S : select J L1 L2 *
C : countItem I1 L2 N1
C1 : 1 + N1 = N
H1 : countItem I1 L1 N1
============================
countItem I1 (I1::L1) N
< search.
Subgoal 2.2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : I = J -> false
S : select J L1 L2 *
C : I = I1 -> false
C1 : countItem I L2 N
============================
countItem I (I1::L1) N
< apply IH to C1 S _.
Subgoal 2.2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I L N -> select J Rest L * -> (I = J -> false) -> countItem I Rest N
NEq : I = J -> false
S : select J L1 L2 *
C : I = I1 -> false
C1 : countItem I L2 N
H1 : countItem I L1 N
============================
countItem I (I1::L1) N
< search.
Proof completed.
< Theorem countItem_select_neq [Item] :
forall (I : Item) (J : Item) L Rest N,
countItem I Rest N -> select J Rest L -> (I = J -> false) -> countItem I L N.
============================
forall I J L Rest N,
countItem I Rest N -> select J Rest L -> (I = J -> false) -> countItem I L N
< induction on 2.
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
============================
forall I J L Rest N,
countItem I Rest N -> select J Rest L @ -> (I = J -> false) -> countItem I L N
< intros C S NEq.
Variables: I J L Rest N
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
C : countItem I Rest N
S : select J Rest L @
NEq : I = J -> false
============================
countItem I L N
< S: case S.
Subgoal 1:
Variables: I J Rest N
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
C : countItem I Rest N
NEq : I = J -> false
============================
countItem I (J::Rest) N
< search.
Subgoal 2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
C : countItem I (I1::L1) N
NEq : I = J -> false
S : select J L1 L2 *
============================
countItem I (I1::L2) N
< C: case C.
Subgoal 2.1:
Variables: J N L2 I1 L1 N1
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
NEq : I1 = J -> false
S : select J L1 L2 *
C : countItem I1 L1 N1
C1 : 1 + N1 = N
============================
countItem I1 (I1::L2) N
< apply IH to C S _.
Subgoal 2.1:
Variables: J N L2 I1 L1 N1
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
NEq : I1 = J -> false
S : select J L1 L2 *
C : countItem I1 L1 N1
C1 : 1 + N1 = N
H1 : countItem I1 L2 N1
============================
countItem I1 (I1::L2) N
< search.
Subgoal 2.2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
NEq : I = J -> false
S : select J L1 L2 *
C : I = I1 -> false
C1 : countItem I L1 N
============================
countItem I (I1::L2) N
< apply IH to C1 S _.
Subgoal 2.2:
Variables: I J N L2 I1 L1
IH : forall I J L Rest N,
countItem I Rest N -> select J Rest L * -> (I = J -> false) -> countItem I L N
NEq : I = J -> false
S : select J L1 L2 *
C : I = I1 -> false
C1 : countItem I L1 N
H1 : countItem I L2 N
============================
countItem I (I1::L2) N
< search.
Proof completed.
< Theorem countItem_unique [Item] :
forall (I : Item) NA NB L, countItem I L NA -> countItem I L NB -> NA = NB.
============================
forall I NA NB L, countItem I L NA -> countItem I L NB -> NA = NB
< induction on 1.
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
============================
forall I NA NB L, countItem I L NA @ -> countItem I L NB -> NA = NB
< intros CA CB.
Variables: I NA NB L
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : countItem I L NA @
CB : countItem I L NB
============================
NA = NB
< CA: case CA.
Subgoal 1:
Variables: I NB
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CB : countItem I [] NB
============================
0 = NB
< case CB.
Subgoal 1:
Variables: I
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
============================
0 = 0
< search.
Subgoal 2:
Variables: I NA NB N Rest
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CB : countItem I (I::Rest) NB
CA : countItem I Rest N *
CA1 : 1 + N = NA
============================
NA = NB
< CB: case CB.
Subgoal 2.1:
Variables: I NA NB N Rest N1
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : countItem I Rest N *
CA1 : 1 + N = NA
CB : countItem I Rest N1
CB1 : 1 + N1 = NB
============================
NA = NB
< apply IH to CA CB.
Subgoal 2.1:
Variables: I NA NB Rest N1
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : countItem I Rest N1 *
CA1 : 1 + N1 = NA
CB : countItem I Rest N1
CB1 : 1 + N1 = NB
============================
NA = NB
< apply plus_integer_unique to CA1 CB1.
Subgoal 2.1:
Variables: I NB Rest N1
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : countItem I Rest N1 *
CA1 : 1 + N1 = NB
CB : countItem I Rest N1
CB1 : 1 + N1 = NB
============================
NB = NB
< search.
Subgoal 2.2:
Variables: I NA NB N Rest
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : countItem I Rest N *
CA1 : 1 + N = NA
CB : I = I -> false
CB1 : countItem I Rest NB
============================
NA = NB
< apply CB to _.
Subgoal 3:
Variables: I NA NB Rest Y
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CB : countItem I (Y::Rest) NB
CA : I = Y -> false
CA1 : countItem I Rest NA *
============================
NA = NB
< CB: case CB.
Subgoal 3.1:
Variables: NA NB Rest Y N
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : Y = Y -> false
CA1 : countItem Y Rest NA *
CB : countItem Y Rest N
CB1 : 1 + N = NB
============================
NA = NB
< apply CA to _.
Subgoal 3.2:
Variables: I NA NB Rest Y
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : I = Y -> false
CA1 : countItem I Rest NA *
CB : I = Y -> false
CB1 : countItem I Rest NB
============================
NA = NB
< apply IH to CA1 CB1.
Subgoal 3.2:
Variables: I NB Rest Y
IH : forall I NA NB L, countItem I L NA * -> countItem I L NB -> NA = NB
CA : I = Y -> false
CA1 : countItem I Rest NB *
CB : I = Y -> false
CB1 : countItem I Rest NB
============================
NB = NB
< search.
Proof completed.
< Theorem countItem_mem [Item] :
forall (I : Item) N L, countItem I L N -> N > 0 -> mem I L.
============================
forall I N L, countItem I L N -> N > 0 -> mem I L
< induction on 1.
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
============================
forall I N L, countItem I L N @ -> N > 0 -> mem I L
< intros C G.
Variables: I N L
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
C : countItem I L N @
G : N > 0
============================
mem I L
< C: case C.
Subgoal 1:
Variables: I
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
G : 0 > 0
============================
mem I []
< L: apply greater_integer_flip_less to G.
Subgoal 1:
Variables: I
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
G : 0 > 0
L : 0 < 0
============================
mem I []
< apply less_integer_not_eq to L.
Subgoal 2:
Variables: I N N1 Rest
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
G : N > 0
C : countItem I Rest N1 *
C1 : 1 + N1 = N
============================
mem I (I::Rest)
< search.
Subgoal 3:
Variables: I N Rest Y
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
G : N > 0
C : I = Y -> false
C1 : countItem I Rest N *
============================
mem I (Y::Rest)
< apply IH to C1 _.
Subgoal 3:
Variables: I N Rest Y
IH : forall I N L, countItem I L N * -> N > 0 -> mem I L
G : N > 0
C : I = Y -> false
C1 : countItem I Rest N *
H1 : mem I Rest
============================
mem I (Y::Rest)
< search.
Proof completed.
< Theorem countItem_not_mem [Item] :
forall (I : Item) L, countItem I L 0 -> mem I L -> false.
============================
forall I L, countItem I L 0 -> mem I L -> false
< induction on 1.
IH : forall I L, countItem I L 0 * -> mem I L -> false
============================
forall I L, countItem I L 0 @ -> mem I L -> false
< intros C Mem.
Variables: I L
IH : forall I L, countItem I L 0 * -> mem I L -> false
C : countItem I L 0 @
Mem : mem I L
============================
false
< C: case C.
Subgoal 1:
Variables: I
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I []
============================
false
< case Mem.
Subgoal 2:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
============================
false
< G: apply countItem_geq_0 to C.
Subgoal 2:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
============================
false
< IsN: apply countItem_is_integer to C.
Subgoal 2:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
============================
false
< P: apply plus_integer_comm to _ _ C1.
Subgoal 2:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
P : N + 1 = 0
============================
false
< Or: apply greatereq_integer_greater_or_eq to G.
Subgoal 2:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
P : N + 1 = 0
Or : N > 0 \/ N = 0
============================
false
< G': case Or.
Subgoal 2.1:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
P : N + 1 = 0
G' : N > 0
============================
false
< G'': apply greater_plus_positive to _ _ C1 _.
Subgoal 2.1:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
P : N + 1 = 0
G' : N > 0
G'' : 0 > 1
============================
false
< case G''.
Subgoal 2.1:
Variables: I N Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest N *
C1 : 1 + N = 0
G : N >= 0
IsN : is_integer N
P : N + 1 = 0
G' : N > 0
H1 : 1 < 0
============================
false
< case H1.
Subgoal 2.2:
Variables: I Rest
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (I::Rest)
C : countItem I Rest 0 *
C1 : 1 + 0 = 0
G : 0 >= 0
IsN : is_integer 0
P : 0 + 1 = 0
============================
false
< case P.
Subgoal 3:
Variables: I Rest Y
IH : forall I L, countItem I L 0 * -> mem I L -> false
Mem : mem I (Y::Rest)
C : I = Y -> false
C1 : countItem I Rest 0 *
============================
false
< Mem: case Mem.
Subgoal 3.1:
Variables: Rest Y
IH : forall I L, countItem I L 0 * -> mem I L -> false
C : Y = Y -> false
C1 : countItem Y Rest 0 *
============================
false
< backchain C.
Subgoal 3.2:
Variables: I Rest Y
IH : forall I L, countItem I L 0 * -> mem I L -> false
C : I = Y -> false
C1 : countItem I Rest 0 *
Mem : mem I Rest
============================
false
< apply IH to C1 Mem.
Proof completed.
< Theorem countItem_greater_0 [Item] :
forall (I : Item) L N, countItem I (I::L) N -> N > 0.
============================
forall I L N, countItem I (I::L) N -> N > 0
< induction on 1.
IH : forall I L N, countItem I (I::L) N * -> N > 0
============================
forall I L N, countItem I (I::L) N @ -> N > 0
< intros C.
Variables: I L N
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I (I::L) N @
============================
N > 0
< C: case C.
Subgoal 1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
============================
N > 0
< GEq: apply countItem_geq_0 to C.
Subgoal 1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
============================
N > 0
< Or: apply greatereq_integer_greater_or_eq to GEq.
Subgoal 1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
Or : N1 > 0 \/ N1 = 0
============================
N > 0
< G: case Or.
Subgoal 1.1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
G : N1 > 0
============================
N > 0
< IsN1: apply countItem_is_integer to C.
Subgoal 1.1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
G : N1 > 0
IsN1 : is_integer N1
============================
N > 0
< P: apply plus_integer_comm to _ _ C1.
Subgoal 1.1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
G : N1 > 0
IsN1 : is_integer N1
P : N1 + 1 = N
============================
N > 0
< G': apply greater_plus_positive to _ _ P _.
Subgoal 1.1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
G : N1 > 0
IsN1 : is_integer N1
P : N1 + 1 = N
G' : N > N1
============================
N > 0
< apply greater_integer_transitive to G' G.
Subgoal 1.1:
Variables: I L N N1
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L N1 *
C1 : 1 + N1 = N
GEq : N1 >= 0
G : N1 > 0
IsN1 : is_integer N1
P : N1 + 1 = N
G' : N > N1
H1 : N > 0
============================
N > 0
< search.
Subgoal 1.2:
Variables: I L N
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L 0 *
C1 : 1 + 0 = N
GEq : 0 >= 0
============================
N > 0
< P: apply plus_integer_comm to _ _ C1.
Subgoal 1.2:
Variables: I L N
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L 0 *
C1 : 1 + 0 = N
GEq : 0 >= 0
P : 0 + 1 = N
============================
N > 0
< case P.
Subgoal 1.2:
Variables: I L
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : countItem I L 0 *
C1 : 1 + 0 = 1
GEq : 0 >= 0
============================
1 > 0
< search.
Subgoal 2:
Variables: I L N
IH : forall I L N, countItem I (I::L) N * -> N > 0
C : I = I -> false
C1 : countItem I L N *
============================
N > 0
< apply C to _.
Proof completed.
< Theorem perm_countItems [Item] :
forall L P (I : Item) NL NP,
perm L P -> countItem I L NL -> countItem I P NP -> NL = NP.
============================
forall L P I NL NP, perm L P -> countItem I L NL -> countItem I P NP -> NL = NP
< induction on 2.
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
============================
forall L P I NL NP,
perm L P -> countItem I L NL @ -> countItem I P NP -> NL = NP
< intros P CL CP.
Variables: L P I NL NP
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
P : perm L P
CL : countItem I L NL @
CP : countItem I P NP
============================
NL = NP
< CL: case CL.
Subgoal 1:
Variables: P I NP
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
P : perm [] P
CP : countItem I P NP
============================
0 = NP
< case P.
Subgoal 1:
Variables: I NP
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I [] NP
============================
0 = NP
< case CP.
Subgoal 1:
Variables: I
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
============================
0 = 0
< search.
Subgoal 2:
Variables: P I NL NP N Rest
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
P : perm (I::Rest) P
CP : countItem I P NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
============================
NL = NP
< P: case P.
Subgoal 2:
Variables: P I NL NP N Rest L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I P NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I L2 P
P1 : perm Rest L2
============================
NL = NP
< S: case P (keep).
Subgoal 2.1:
Variables: I NL NP N Rest L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I::L2) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I L2 (I::L2)
P1 : perm Rest L2
============================
NL = NP
< CP: case CP.
Subgoal 2.1.1:
Variables: I NL NP N Rest L2 N1
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I L2 (I::L2)
P1 : perm Rest L2
CP : countItem I L2 N1
CP1 : 1 + N1 = NP
============================
NL = NP
< apply IH to P1 CL CP.
Subgoal 2.1.1:
Variables: I NL NP Rest L2 N1
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CL : countItem I Rest N1 *
CL1 : 1 + N1 = NL
P : select I L2 (I::L2)
P1 : perm Rest L2
CP : countItem I L2 N1
CP1 : 1 + N1 = NP
============================
NL = NP
< apply plus_integer_unique to CL1 CP1.
Subgoal 2.1.1:
Variables: I NP Rest L2 N1
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CL : countItem I Rest N1 *
CL1 : 1 + N1 = NP
P : select I L2 (I::L2)
P1 : perm Rest L2
CP : countItem I L2 N1
CP1 : 1 + N1 = NP
============================
NP = NP
< search.
Subgoal 2.1.2:
Variables: I NL NP N Rest L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I L2 (I::L2)
P1 : perm Rest L2
CP : I = I -> false
CP1 : countItem I L2 NP
============================
NL = NP
< apply CP to _.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
============================
NL = NP
< IsNP: apply countItem_is_integer to CP.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
============================
NL = NP
< Minus: apply minus_integer_total to IsNP _ with
N2 = 1.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
============================
NL = NP
< C': apply select_countItem to CP P Minus.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
============================
NL = NP
< P': apply minus_plus_same_integer to _ _ Minus.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
P' : N3 + 1 = NP
============================
NL = NP
< IsN3: apply minus_integer_is_integer to _ _ Minus.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
P' : N3 + 1 = NP
IsN3 : is_integer N3
============================
NL = NP
< Plus: apply plus_integer_comm to _ _ P'.
Subgoal 2.2:
Variables: I NL NP N Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N *
CL1 : 1 + N = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
P' : N3 + 1 = NP
IsN3 : is_integer N3
Plus : 1 + N3 = NP
============================
NL = NP
< apply IH to P1 CL _.
Subgoal 2.2:
Variables: I NL NP Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N3 *
CL1 : 1 + N3 = NL
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
P' : N3 + 1 = NP
IsN3 : is_integer N3
Plus : 1 + N3 = NP
============================
NL = NP
< apply plus_integer_unique to CL1 Plus.
Subgoal 2.2:
Variables: I NP Rest L3 I1 L1 N3
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I (I1::L3) NP
CL : countItem I Rest N3 *
CL1 : 1 + N3 = NP
P : select I (I1::L1) (I1::L3)
P1 : perm Rest (I1::L1)
S : select I L1 L3
IsNP : is_integer NP
Minus : NP - 1 = N3
C' : countItem I (I1::L1) N3
P' : N3 + 1 = NP
IsN3 : is_integer N3
Plus : 1 + N3 = NP
============================
NP = NP
< search.
Subgoal 3:
Variables: P I NL NP Rest Y
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
P : perm (Y::Rest) P
CP : countItem I P NP
CL : I = Y -> false
CL1 : countItem I Rest NL *
============================
NL = NP
< P: case P.
Subgoal 3:
Variables: P I NL NP Rest Y L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I P NP
CL : I = Y -> false
CL1 : countItem I Rest NL *
P : select Y L2 P
P1 : perm Rest L2
============================
NL = NP
< C: apply select_countItem_neq to CP P CL.
Subgoal 3:
Variables: P I NL NP Rest Y L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I P NP
CL : I = Y -> false
CL1 : countItem I Rest NL *
P : select Y L2 P
P1 : perm Rest L2
C : countItem I L2 NP
============================
NL = NP
< apply IH to P1 CL1 C.
Subgoal 3:
Variables: P I NP Rest Y L2
IH : forall L P I NL NP,
perm L P -> countItem I L NL * -> countItem I P NP -> NL = NP
CP : countItem I P NP
CL : I = Y -> false
CL1 : countItem I Rest NP *
P : select Y L2 P
P1 : perm Rest L2
C : countItem I L2 NP
============================
NP = NP
< search.
Proof completed.
< Theorem intRange_is :
forall Low High R,
is_integer Low -> intRange Low High R -> is_list is_integer R.
============================
forall Low High R,
is_integer Low -> intRange Low High R -> is_list is_integer R
< induction on 2.
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
============================
forall Low High R,
is_integer Low -> intRange Low High R @ -> is_list is_integer R
< intros IsLow R.
Variables: Low High R
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
IsLow : is_integer Low
R : intRange Low High R @
============================
is_list is_integer R
< R: case R.
Subgoal 1:
Variables: Low High
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
IsLow : is_integer Low
R : Low > High
============================
is_list is_integer []
< search.
Subgoal 2:
Variables: Low High PlusOne Rest
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
IsLow : is_integer Low
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
============================
is_list is_integer (Low::Rest)
< IsPlusOne: apply plus_integer_is_integer to _ _ R1.
Subgoal 2:
Variables: Low High PlusOne Rest
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
IsLow : is_integer Low
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
============================
is_list is_integer (Low::Rest)
< apply IH to IsPlusOne R2.
Subgoal 2:
Variables: Low High PlusOne Rest
IH : forall Low High R,
is_integer Low -> intRange Low High R * -> is_list is_integer R
IsLow : is_integer Low
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
H1 : is_list is_integer Rest
============================
is_list is_integer (Low::Rest)
< search.
Proof completed.
< Theorem intRange_low_lesseq :
forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R -> Low <= X.
============================
forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R -> Low <= X
< induction on 3.
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
============================
forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R @ -> Low <= X
< intros IsLow Range Mem.
Variables: Low High R X
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer Low
Range : intRange Low High R
Mem : mem X R @
============================
Low <= X
< apply intRange_is to IsLow Range.
Variables: Low High R X
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer Low
Range : intRange Low High R
Mem : mem X R @
H1 : is_list is_integer R
============================
Low <= X
< IsX: apply is_list_int_mem to _ Mem.
Variables: Low High R X
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer Low
Range : intRange Low High R
Mem : mem X R @
H1 : is_list is_integer R
IsX : is_integer X
============================
Low <= X
< Mem: case Mem.
Subgoal 1:
Variables: Low High X Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer Low
Range : intRange Low High (X::Rest)
H1 : is_list is_integer (X::Rest)
IsX : is_integer X
============================
Low <= X
< R: case Range.
Subgoal 1:
Variables: High X Rest PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer X
H1 : is_list is_integer (X::Rest)
IsX : is_integer X
R : X <= High
R1 : 1 + X = PlusOne
R2 : intRange PlusOne High Rest
============================
X <= X
< apply is_integer_lesseq to IsX.
Subgoal 1:
Variables: High X Rest PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer X
H1 : is_list is_integer (X::Rest)
IsX : is_integer X
R : X <= High
R1 : 1 + X = PlusOne
R2 : intRange PlusOne High Rest
H2 : X <= X
============================
X <= X
< search.
Subgoal 2:
Variables: Low High X Rest I
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer Low
Range : intRange Low High (I::Rest)
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
============================
Low <= X
< R: case Range.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
============================
I <= X
< apply plus_integer_is_integer to _ _ R1.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
H2 : is_integer PlusOne
============================
I <= X
< LEq: apply IH to _ R2 Mem.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
H2 : is_integer PlusOne
LEq : PlusOne <= X
============================
I <= X
< L: apply lt_plus_one to R1 _.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
H2 : is_integer PlusOne
LEq : PlusOne <= X
L : I < PlusOne
============================
I <= X
< LEq': apply less_integer_lesseq to L.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
H2 : is_integer PlusOne
LEq : PlusOne <= X
L : I < PlusOne
LEq' : I <= PlusOne
============================
I <= X
< apply lesseq_integer_transitive to LEq' LEq.
Subgoal 2:
Variables: High X Rest I PlusOne
IH : forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R * -> Low <= X
IsLow : is_integer I
H1 : is_list is_integer (I::Rest)
IsX : is_integer X
Mem : mem X Rest *
R : I <= High
R1 : 1 + I = PlusOne
R2 : intRange PlusOne High Rest
H2 : is_integer PlusOne
LEq : PlusOne <= X
L : I < PlusOne
LEq' : I <= PlusOne
H3 : I <= X
============================
I <= X
< search.
Proof completed.
< Theorem intRange_high_lesseq :
forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R -> X <= High.
============================
forall Low High R X,
is_integer Low -> intRange Low High R -> mem X R -> X <= High
< induction on 2.
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
============================
forall Low High R X,
is_integer Low -> intRange Low High R @ -> mem X R -> X <= High
< intros IsLow Range Mem.
Variables: Low High R X
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Range : intRange Low High R @
Mem : mem X R
============================
X <= High
< Range: case Range.
Subgoal 1:
Variables: Low High X
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Mem : mem X []
Range : Low > High
============================
X <= High
< case Mem.
Subgoal 2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Mem : mem X (Low::Rest)
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest *
============================
X <= High
< Mem: case Mem.
Subgoal 2.1:
Variables: Low High PlusOne Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest *
============================
Low <= High
< search.
Subgoal 2.2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest *
Mem : mem X Rest
============================
X <= High
< apply plus_integer_is_integer to _ _ Range1.
Subgoal 2.2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest *
Mem : mem X Rest
H1 : is_integer PlusOne
============================
X <= High
< apply IH to _ Range2 Mem.
Subgoal 2.2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> intRange Low High R * -> mem X R -> X <= High
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest *
Mem : mem X Rest
H1 : is_integer PlusOne
H2 : X <= High
============================
X <= High
< search.
Proof completed.
< Theorem in_intRange :
forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R -> Low <= X -> X <= High ->
mem X R.
============================
forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R -> Low <= X -> X <= High ->
mem X R
< induction on 3.
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
============================
forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R @ -> Low <= X -> X <= High ->
mem X R
< intros IsLow IsX R LowX XHigh.
Variables: Low High R X
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
R : intRange Low High R @
LowX : Low <= X
XHigh : X <= High
============================
mem X R
< R: case R.
Subgoal 1:
Variables: Low High X
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low > High
============================
mem X []
< L: apply lesseq_integer_transitive to LowX XHigh.
Subgoal 1:
Variables: Low High X
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low > High
L : Low <= High
============================
mem X []
< apply greater_lesseq_integer_false to R L.
Subgoal 2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
============================
mem X (Low::Rest)
< Or: apply lesseq_integer_less_or_eq to LowX.
Subgoal 2:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
Or : Low < X \/ Low = X
============================
mem X (Low::Rest)
< L: case Or.
Subgoal 2.1:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
L : Low < X
============================
mem X (Low::Rest)
< P: apply plus_integer_comm to _ _ R1.
Subgoal 2.1:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
L : Low < X
P : Low + 1 = PlusOne
============================
mem X (Low::Rest)
< IsPlusOne: apply plus_integer_is_integer to _ _ P.
Subgoal 2.1:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
L : Low < X
P : Low + 1 = PlusOne
IsPlusOne : is_integer PlusOne
============================
mem X (Low::Rest)
< apply less_lesseq_plus_one to _ _ L P.
Subgoal 2.1:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
L : Low < X
P : Low + 1 = PlusOne
IsPlusOne : is_integer PlusOne
H1 : PlusOne <= X
============================
mem X (Low::Rest)
< apply IH to _ _ R2 _ _.
Subgoal 2.1:
Variables: Low High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer Low
IsX : is_integer X
LowX : Low <= X
XHigh : X <= High
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
L : Low < X
P : Low + 1 = PlusOne
IsPlusOne : is_integer PlusOne
H1 : PlusOne <= X
H2 : mem X Rest
============================
mem X (Low::Rest)
< search.
Subgoal 2.2:
Variables: High X PlusOne Rest
IH : forall Low High R X,
is_integer Low -> is_integer X -> intRange Low High R * -> Low <= X -> X <= High ->
mem X R
IsLow : is_integer X
IsX : is_integer X
LowX : X <= X
XHigh : X <= High
R : X <= High
R1 : 1 + X = PlusOne
R2 : intRange PlusOne High Rest *
============================
mem X (X::Rest)
< search.
Proof completed.
< Theorem intRange_unique :
forall Low High R1 R2,
intRange Low High R1 -> intRange Low High R2 -> R1 = R2.
============================
forall Low High R1 R2, intRange Low High R1 -> intRange Low High R2 -> R1 = R2
< induction on 1.
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
============================
forall Low High R1 R2,
intRange Low High R1 @ -> intRange Low High R2 -> R1 = R2
< intros RA RB.
Variables: Low High R1 R2
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : intRange Low High R1 @
RB : intRange Low High R2
============================
R1 = R2
< RA: case RA.
Subgoal 1:
Variables: Low High R2
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RB : intRange Low High R2
RA : Low > High
============================
[] = R2
< RB: case RB.
Subgoal 1.1:
Variables: Low High
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low > High
RB : Low > High
============================
[] = []
< search.
Subgoal 1.2:
Variables: Low High PlusOne Rest
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low > High
RB : Low <= High
RB1 : 1 + Low = PlusOne
RB2 : intRange PlusOne High Rest
============================
[] = Low::Rest
< apply greater_lesseq_integer_false to RA RB.
Subgoal 2:
Variables: Low High R2 PlusOne Rest
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RB : intRange Low High R2
RA : Low <= High
RA1 : 1 + Low = PlusOne
RA2 : intRange PlusOne High Rest *
============================
Low::Rest = R2
< RB: case RB.
Subgoal 2.1:
Variables: Low High PlusOne Rest
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low <= High
RA1 : 1 + Low = PlusOne
RA2 : intRange PlusOne High Rest *
RB : Low > High
============================
Low::Rest = []
< apply greater_lesseq_integer_false to RB RA.
Subgoal 2.2:
Variables: Low High PlusOne Rest PlusOne1 Rest1
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low <= High
RA1 : 1 + Low = PlusOne
RA2 : intRange PlusOne High Rest *
RB : Low <= High
RB1 : 1 + Low = PlusOne1
RB2 : intRange PlusOne1 High Rest1
============================
Low::Rest = Low::Rest1
< apply plus_integer_unique to RA1 RB1.
Subgoal 2.2:
Variables: Low High Rest PlusOne1 Rest1
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low <= High
RA1 : 1 + Low = PlusOne1
RA2 : intRange PlusOne1 High Rest *
RB : Low <= High
RB1 : 1 + Low = PlusOne1
RB2 : intRange PlusOne1 High Rest1
============================
Low::Rest = Low::Rest1
< apply IH to RA2 RB2.
Subgoal 2.2:
Variables: Low High PlusOne1 Rest1
IH : forall Low High R1 R2,
intRange Low High R1 * -> intRange Low High R2 -> R1 = R2
RA : Low <= High
RA1 : 1 + Low = PlusOne1
RA2 : intRange PlusOne1 High Rest1 *
RB : Low <= High
RB1 : 1 + Low = PlusOne1
RB2 : intRange PlusOne1 High Rest1
============================
Low::Rest1 = Low::Rest1
< search.
Proof completed.
< Theorem intRange_smaller_exists :
forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R -> Low < Low' ->
exists R', intRange Low' High R'.
============================
forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R -> Low < Low' -> exists R',
intRange Low' High R'
< induction on 3.
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
============================
forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R @ -> Low < Low' -> exists R',
intRange Low' High R'
< intros IsLow IsLow' R L.
Variables: Low High R Low'
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R @
L : Low < Low'
============================
exists R', intRange Low' High R'
< R: case R.
Subgoal 1:
Variables: Low High Low'
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low > High
============================
exists R', intRange Low' High R'
< G: apply less_integer_flip_greater to L.
Subgoal 1:
Variables: Low High Low'
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low > High
G : Low' > Low
============================
exists R', intRange Low' High R'
< apply greater_integer_transitive to G R.
Subgoal 1:
Variables: Low High Low'
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low > High
G : Low' > Low
H1 : Low' > High
============================
exists R', intRange Low' High R'
< search.
Subgoal 2:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
============================
exists R', intRange Low' High R'
< IsPlusOne: apply plus_integer_is_integer to _ _ R1.
Subgoal 2:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
============================
exists R', intRange Low' High R'
< P: apply plus_integer_comm to _ _ R1.
Subgoal 2:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
P : Low + 1 = PlusOne
============================
exists R', intRange Low' High R'
< LEq: apply less_lesseq_plus_one to _ _ L P.
Subgoal 2:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
P : Low + 1 = PlusOne
LEq : PlusOne <= Low'
============================
exists R', intRange Low' High R'
< Or: apply lesseq_integer_less_or_eq to LEq.
Subgoal 2:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
P : Low + 1 = PlusOne
LEq : PlusOne <= Low'
Or : PlusOne < Low' \/ PlusOne = Low'
============================
exists R', intRange Low' High R'
< L: case Or.
Subgoal 2.1:
Variables: Low High Low' PlusOne Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
P : Low + 1 = PlusOne
LEq : PlusOne <= Low'
L1 : PlusOne < Low'
============================
exists R', intRange Low' High R'
< apply IH to _ _ R2 L1.
Subgoal 2.1:
Variables: Low High Low' PlusOne Rest R'
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = PlusOne
R2 : intRange PlusOne High Rest *
IsPlusOne : is_integer PlusOne
P : Low + 1 = PlusOne
LEq : PlusOne <= Low'
L1 : PlusOne < Low'
H1 : intRange Low' High R'
============================
exists R', intRange Low' High R'
< search.
Subgoal 2.2:
Variables: Low High Low' Rest
IH : forall Low High R Low',
is_integer Low -> is_integer Low' -> intRange Low High R * -> Low < Low' ->
exists R', intRange Low' High R'
IsLow : is_integer Low
IsLow' : is_integer Low'
L : Low < Low'
R : Low <= High
R1 : 1 + Low = Low'
R2 : intRange Low' High Rest *
IsPlusOne : is_integer Low'
P : Low + 1 = Low'
LEq : Low' <= Low'
============================
exists R', intRange Low' High R'
< search.
Proof completed.
< Theorem intRange_subset :
forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' ->
Low < Low' -> subset R' R.
============================
forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' ->
Low < Low' -> subset R' R
< induction on 4.
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
============================
forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' @ ->
Low < Low' -> subset R' R
< intros IsLow IsLow' R R' L.
Variables: Low Low' High R R'
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
R' : intRange Low' High R' @
L : Low < Low'
============================
subset R' R
< R': case R'.
Subgoal 1:
Variables: Low Low' High R
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' > High
============================
subset [] R
< search.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
============================
subset (Low'::Rest) R
< P: apply plus_integer_comm to _ _ R'1.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
============================
subset (Low'::Rest) R
< LEq: apply less_integer_lesseq to L.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
============================
subset (Low'::Rest) R
< M: apply in_intRange to _ _ R _ R'.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
M : mem Low' R
============================
subset (Low'::Rest) R
< L': apply lt_plus_one to R'1 _.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
M : mem Low' R
L' : Low' < PlusOne
============================
subset (Low'::Rest) R
< apply less_integer_transitive to L L'.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
M : mem Low' R
L' : Low' < PlusOne
H1 : Low < PlusOne
============================
subset (Low'::Rest) R
< apply plus_integer_is_integer to _ _ R'1.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
M : mem Low' R
L' : Low' < PlusOne
H1 : Low < PlusOne
H2 : is_integer PlusOne
============================
subset (Low'::Rest) R
< apply IH to _ _ R R'2 _.
Subgoal 2:
Variables: Low Low' High R PlusOne Rest
IH : forall Low Low' High R R',
is_integer Low -> is_integer Low' -> intRange Low High R -> intRange Low' High R' * ->
Low < Low' -> subset R' R
IsLow : is_integer Low
IsLow' : is_integer Low'
R : intRange Low High R
L : Low < Low'
R' : Low' <= High
R'1 : 1 + Low' = PlusOne
R'2 : intRange PlusOne High Rest *
P : Low' + 1 = PlusOne
LEq : Low <= Low'
M : mem Low' R
L' : Low' < PlusOne
H1 : Low < PlusOne
H2 : is_integer PlusOne
H3 : subset Rest R
============================
subset (Low'::Rest) R
< search.
Proof completed.
< Theorem intRange_select_unique :
forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R -> select X Rest R -> select X Rest' R ->
Rest = Rest'.
============================
forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R -> select X Rest R -> select X Rest' R ->
Rest = Rest'
< induction on 2.
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
============================
forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R @ -> select X Rest R -> select X Rest' R ->
Rest = Rest'
< intros IsLow Range Slct Slct'.
Variables: Low High R X Rest Rest'
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : intRange Low High R @
Slct : select X Rest R
Slct' : select X Rest' R
============================
Rest = Rest'
< Range: case Range.
Subgoal 1:
Variables: Low High X Rest Rest'
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Slct : select X Rest []
Slct' : select X Rest' []
Range : Low > High
============================
Rest = Rest'
< case Slct.
Subgoal 2:
Variables: Low High X Rest Rest' PlusOne Rest1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Slct : select X Rest (Low::Rest1)
Slct' : select X Rest' (Low::Rest1)
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
============================
Rest = Rest'
< Slct: case Slct.
Subgoal 2.1:
Variables: Low High Rest' PlusOne Rest1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Slct' : select Low Rest' (Low::Rest1)
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
============================
Rest1 = Rest'
< Slct': case Slct'.
Subgoal 2.1.1:
Variables: Low High PlusOne Rest1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
============================
Rest1 = Rest1
< search.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
============================
Rest1 = Low::L1
< L: apply lt_plus_one to Range1 _.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
L : Low < PlusOne
============================
Rest1 = Low::L1
< M: apply select_mem to Slct'.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
============================
Rest1 = Low::L1
< IsPlusOne: apply plus_integer_is_integer to _ _ Range1.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
============================
Rest1 = Low::L1
< LEq: apply intRange_low_lesseq to _ Range2 M.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
LEq : PlusOne <= Low
============================
Rest1 = Low::L1
< G: apply less_integer_flip_greater to L.
Subgoal 2.1.2:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct' : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
LEq : PlusOne <= Low
G : PlusOne > Low
============================
Rest1 = Low::L1
< apply greater_lesseq_integer_false to G LEq.
Subgoal 2.2:
Variables: Low High X Rest' PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Slct' : select X Rest' (Low::Rest1)
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select X L1 Rest1
============================
Low::L1 = Rest'
< Slct': case Slct'.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
============================
Low::L1 = Rest1
< L: apply lt_plus_one to Range1 _.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
L : Low < PlusOne
============================
Low::L1 = Rest1
< M: apply select_mem to Slct.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
============================
Low::L1 = Rest1
< IsPlusOne: apply plus_integer_is_integer to _ _ Range1.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
============================
Low::L1 = Rest1
< LEq: apply intRange_low_lesseq to _ Range2 M.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
LEq : PlusOne <= Low
============================
Low::L1 = Rest1
< G: apply less_integer_flip_greater to L.
Subgoal 2.2.1:
Variables: Low High PlusOne Rest1 L1
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select Low L1 Rest1
L : Low < PlusOne
M : mem Low Rest1
IsPlusOne : is_integer PlusOne
LEq : PlusOne <= Low
G : PlusOne > Low
============================
Low::L1 = Rest1
< apply greater_lesseq_integer_false to G LEq.
Subgoal 2.2.2:
Variables: Low High X PlusOne Rest1 L1 L2
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select X L1 Rest1
Slct' : select X L2 Rest1
============================
Low::L1 = Low::L2
< apply plus_integer_is_integer to _ _ Range1.
Subgoal 2.2.2:
Variables: Low High X PlusOne Rest1 L1 L2
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select X L1 Rest1
Slct' : select X L2 Rest1
H1 : is_integer PlusOne
============================
Low::L1 = Low::L2
< apply IH to _ Range2 Slct Slct'.
Subgoal 2.2.2:
Variables: Low High X PlusOne Rest1 L2
IH : forall Low High R X Rest Rest',
is_integer Low -> intRange Low High R * -> select X Rest R -> select X Rest' R ->
Rest = Rest'
IsLow : is_integer Low
Range : Low <= High
Range1 : 1 + Low = PlusOne
Range2 : intRange PlusOne High Rest1 *
Slct : select X L2 Rest1
Slct' : select X L2 Rest1
H1 : is_integer PlusOne
============================
Low::L2 = Low::L2
< search.
Proof completed.
< Theorem intRange_exists :
forall Low High,
is_integer Low -> is_integer High -> exists R, intRange Low High R.
============================
forall Low High,
is_integer Low -> is_integer High -> exists R, intRange Low High R
< assert forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R.
Subgoal 1:
============================
forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
< induction on 4.
Subgoal 1:
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
============================
forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff @ -> exists R,
intRange Low High R
< intros IsLow IsHigh Minus Acc.
Subgoal 1:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
============================
exists R, intRange Low High R
< Or: apply integer_compare_total to IsLow IsHigh.
Subgoal 1:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Or : Low <= High \/ Low > High
============================
exists R, intRange Low High R
< Comp: case Or.
Subgoal 1.1:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
============================
exists R, intRange Low High R
< P: apply plus_integer_total to _ IsLow with
N1 = 1.
Subgoal 1.1:
Variables: Low High Diff N3
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
P : 1 + Low = N3
============================
exists R, intRange Low High R
< IsN3: apply plus_integer_is_integer to _ _ P.
Subgoal 1.1:
Variables: Low High Diff N3
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
============================
exists R, intRange Low High R
< LowN3: apply lt_plus_one to P _.
Subgoal 1.1:
Variables: Low High Diff N3
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
============================
exists R, intRange Low High R
< Minus': apply minus_integer_total to IsHigh IsN3.
Subgoal 1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
============================
exists R, intRange Low High R
< L: apply minus_larger to _ Minus Minus' LowN3.
Subgoal 1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
============================
exists R, intRange Low High R
< Acc: case Acc.
Subgoal 1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
============================
exists R, intRange Low High R
< Or: apply integer_compare_total to IsN3 IsHigh.
Subgoal 1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Or : N3 <= High \/ N3 > High
============================
exists R, intRange Low High R
< Comp: case Or.
Subgoal 1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
============================
exists R, intRange Low High R
< Or: apply lesseq_integer_less_or_eq to Comp1.
Subgoal 1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
Or : N3 < High \/ N3 = High
============================
exists R, intRange Low High R
< L': case Or.
Subgoal 1.1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
L' : N3 < High
============================
exists R, intRange Low High R
< L0N1: apply minus_smaller_positive to Minus' L'.
Subgoal 1.1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
L' : N3 < High
L0N1 : 0 < N1
============================
exists R, intRange Low High R
< LEq: apply less_integer_lesseq to L0N1.
Subgoal 1.1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
L' : N3 < High
L0N1 : 0 < N1
LEq : 0 <= N1
============================
exists R, intRange Low High R
< A: apply Acc to LEq L.
Subgoal 1.1.1.1:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
L' : N3 < High
L0N1 : 0 < N1
LEq : 0 <= N1
A : acc N1 *
============================
exists R, intRange Low High R
< apply IH to _ _ Minus' A.
Subgoal 1.1.1.1:
Variables: Low High Diff N3 N1 R
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 <= High
L' : N3 < High
L0N1 : 0 < N1
LEq : 0 <= N1
A : acc N1 *
H1 : intRange N3 High R
============================
exists R, intRange Low High R
< search.
Subgoal 1.1.1.2:
Variables: Low High Diff N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = High
IsN3 : is_integer High
LowN3 : Low < High
Minus' : High - High = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : High <= High
============================
exists R, intRange Low High R
< M: apply minus_integer_same to IsHigh.
Subgoal 1.1.1.2:
Variables: Low High Diff N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = High
IsN3 : is_integer High
LowN3 : Low < High
Minus' : High - High = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : High <= High
M : High - High = 0
============================
exists R, intRange Low High R
< apply minus_integer_unique to M Minus'.
Subgoal 1.1.1.2:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = High
IsN3 : is_integer High
LowN3 : Low < High
Minus' : High - High = 0
L : 0 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : High <= High
M : High - High = 0
============================
exists R, intRange Low High R
< A: apply Acc to _ L.
Subgoal 1.1.1.2:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = High
IsN3 : is_integer High
LowN3 : Low < High
Minus' : High - High = 0
L : 0 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : High <= High
M : High - High = 0
A : acc 0 *
============================
exists R, intRange Low High R
< apply IH to _ _ Minus' A.
Subgoal 1.1.1.2:
Variables: Low High Diff R
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = High
IsN3 : is_integer High
LowN3 : Low < High
Minus' : High - High = 0
L : 0 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : High <= High
M : High - High = 0
A : acc 0 *
H1 : intRange High High R
============================
exists R, intRange Low High R
< search.
Subgoal 1.1.2:
Variables: Low High Diff N3 N1
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Comp : Low <= High
P : 1 + Low = N3
IsN3 : is_integer N3
LowN3 : Low < N3
Minus' : High - N3 = N1
L : N1 < Diff
Acc : forall M, 0 <= M -> M < Diff -> acc M *
Comp1 : N3 > High
============================
exists R, intRange Low High R
< search.
Subgoal 1.2:
Variables: Low High Diff
IH : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff * -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = Diff
Acc : acc Diff @
Comp : Low > High
============================
exists R, intRange Low High R
< search.
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
============================
forall Low High,
is_integer Low -> is_integer High -> exists R, intRange Low High R
< intros IsLow IsHigh.
Variables: Low High
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
============================
exists R, intRange Low High R
< Minus: apply minus_integer_total to IsHigh IsLow.
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
============================
exists R, intRange Low High R
< IsN3: apply minus_integer_is_integer to _ _ Minus.
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
============================
exists R, intRange Low High R
< Or: apply integer_compare_total to _ IsN3 with
A = 0.
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Or : 0 <= N3 \/ 0 > N3
============================
exists R, intRange Low High R
< Comp: case Or.
Subgoal 2:
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 <= N3
============================
exists R, intRange Low High R
< apply all_acc to IsN3 Comp.
Subgoal 2:
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 <= N3
H2 : acc N3
============================
exists R, intRange Low High R
< apply H1 to _ _ Minus _.
Subgoal 2:
Variables: Low High N3 R
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 <= N3
H2 : acc N3
H3 : intRange Low High R
============================
exists R, intRange Low High R
< search.
Subgoal 3:
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 > N3
============================
exists R, intRange Low High R
< NegN3: apply greater_integer_flip_less to Comp.
Subgoal 3:
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 > N3
NegN3 : N3 < 0
============================
exists R, intRange Low High R
< apply minus_integer_diff_neg to NegN3 Minus.
Subgoal 3:
Variables: Low High N3
H1 : forall Low High Diff,
is_integer Low -> is_integer High -> High - Low = Diff -> acc Diff -> exists R,
intRange Low High R
IsLow : is_integer Low
IsHigh : is_integer High
Minus : High - Low = N3
IsN3 : is_integer N3
Comp : 0 > N3
NegN3 : N3 < 0
H2 : High < Low
============================
exists R, intRange Low High R
< search.
Proof completed.
