---

Step * 2 of Lemma sorted-by-unique


1. T : Type
2. R : T ⟶ T ⟶ ℙ
3. Trans(T;a,b.R a b)
4. AntiSym(T;a,b.R a b)
5. u : T
6. v : T List
7. ∀[sb:T List]
     (v = sb ∈ (T List)) supposing 
        (no_repeats(T;v) and 
        sorted-by(R;v) and 
        no_repeats(T;sb) and 
        sorted-by(R;sb) and 
        set-equal(T;v;sb))
⊢ ∀[sb:T List]
    ([u / v] = sb ∈ (T List)) supposing 
       (no_repeats(T;[u / v]) and 
       sorted-by(R;[u / v]) and 
       no_repeats(T;sb) and 
       sorted-by(R;sb) and 
       set-equal(T;[u / v];sb))
BY
{ (InductionOnList THENA Auto)⋅ }

1
1. T : Type
2. R : T ⟶ T ⟶ ℙ
3. Trans(T;a,b.R a b)
4. AntiSym(T;a,b.R a b)
5. u : T
6. v : T List
7. ∀[sb:T List]
     (v = sb ∈ (T List)) supposing 
        (no_repeats(T;v) and 
        sorted-by(R;v) and 
        no_repeats(T;sb) and 
        sorted-by(R;sb) and 
        set-equal(T;v;sb))
⊢ ([u / v] = [] ∈ (T List)) supposing 
     (no_repeats(T;[u / v]) and 
     sorted-by(R;[u / v]) and 
     no_repeats(T;[]) and 
     sorted-by(R;[]) and 
     set-equal(T;[u / v];[]))

2
1. T : Type
2. R : T ⟶ T ⟶ ℙ
3. Trans(T;a,b.R a b)
4. AntiSym(T;a,b.R a b)
5. u : T
6. v : T List
7. ∀[sb:T List]
     (v = sb ∈ (T List)) supposing 
        (no_repeats(T;v) and 
        sorted-by(R;v) and 
        no_repeats(T;sb) and 
        sorted-by(R;sb) and 
        set-equal(T;v;sb))
8. u1 : T
9. v1 : T List
10. ([u / v] = v1 ∈ (T List)) supposing 
       (no_repeats(T;[u / v]) and 
       sorted-by(R;[u / v]) and 
       no_repeats(T;v1) and 
       sorted-by(R;v1) and 
       set-equal(T;[u / v];v1))
⊢ ([u / v] = [u1 / v1] ∈ (T List)) supposing 
     (no_repeats(T;[u / v]) and 
     sorted-by(R;[u / v]) and 
     no_repeats(T;[u1 / v1]) and 
     sorted-by(R;[u1 / v1]) and 
     set-equal(T;[u / v];[u1 / v1]))

---

Latex:

---

Latex:

1.  T  :  Type
2.  R  :  T  {}\mrightarrow{}  T  {}\mrightarrow{}  \mBbbP{}
3.  Trans(T;a,b.R  a  b)
4.  AntiSym(T;a,b.R  a  b)
5.  u  :  T
6.  v  :  T  List
7.  \mforall{}[sb:T  List]
          (v  =  sb)  supposing 
                (no\_repeats(T;v)  and 
                sorted-by(R;v)  and 
                no\_repeats(T;sb)  and 
                sorted-by(R;sb)  and 
                set-equal(T;v;sb))
\mvdash{}  \mforall{}[sb:T  List]
        ([u  /  v]  =  sb)  supposing 
              (no\_repeats(T;[u  /  v])  and 
              sorted-by(R;[u  /  v])  and 
              no\_repeats(T;sb)  and 
              sorted-by(R;sb)  and 
              set-equal(T;[u  /  v];sb))


By

---

Latex:
(InductionOnList  THENA  Auto)\mcdot{}

---

Home Index