Proof of Nuprl Lemma : linearization-value

Step * 1 2 1 2 1 1 1 2 of Lemma linearization-value

1. u : ℤ List
2. v : ℤ List List
3. ∀[p:iPolynomial()]
     ∀f:ℤ ⟶ ℤ
       (int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;p)))
       = linearization(p;v) ⋅ map(λvs.accumulate (with value x and list item v):
                                       x * (f v)
                                      over list:
                                        vs
                                      with starting value:
                                       1);v)
       ∈ ℤ)
     supposing no_repeats(ℤ List;v)
4. no_repeats(ℤ List;v) ∧ (¬(u ∈ v))
5. f : ℤ ⟶ ℤ
6. u1 : iMonomial()
7. v1 : iMonomial() List
8. int_term_value(f;ipolynomial-term(filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)))
= (int_term_value(f;ipolynomial-term(filter(λm.(list-deq(IntDeq) u (snd(m)));v1)))
  + int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;v1))))
∈ ℤ
⊢ int_term_value(f;ipolynomial-term(if (list-deq(IntDeq) u (snd(u1))) ∨_bsnd(u1) ∈_b v
then [u1 / filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)]
else filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)
fi ))
= (int_term_value(f;ipolynomial-term(if list-deq(IntDeq) u (snd(u1))
  then [u1 / filter(λm.(list-deq(IntDeq) u (snd(m)));v1)]
  else filter(λm.(list-deq(IntDeq) u (snd(m)));v1)
  fi ))
  + int_term_value(f;ipolynomial-term(if snd(u1) ∈_b v
    then [u1 / filter(λm.snd(m) ∈_b v;v1)]
    else filter(λm.snd(m) ∈_b v;v1)
    fi )))
∈ ℤ
BY
{ TACTIC:(BoolCase ⌜snd(u1) ∈_b v⌝⋅ THEN Auto) }

1
1. u : ℤ List
2. v : ℤ List List
3. ∀[p:iPolynomial()]
     ∀f:ℤ ⟶ ℤ
       (int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;p)))
       = linearization(p;v) ⋅ map(λvs.accumulate (with value x and list item v):
                                       x * (f v)
                                      over list:
                                        vs
                                      with starting value:
                                       1);v)
       ∈ ℤ)
     supposing no_repeats(ℤ List;v)
4. no_repeats(ℤ List;v)
5. ¬(u ∈ v)
6. f : ℤ ⟶ ℤ
7. u1 : iMonomial()
8. v1 : iMonomial() List
9. int_term_value(f;ipolynomial-term(filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)))
= (int_term_value(f;ipolynomial-term(filter(λm.(list-deq(IntDeq) u (snd(m)));v1)))
  + int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;v1))))
∈ ℤ
10. (snd(u1) ∈ v)
⊢ int_term_value(f;ipolynomial-term(if (list-deq(IntDeq) u (snd(u1))) ∨_btt
then [u1 / filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)]
else filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)
fi ))
= (int_term_value(f;ipolynomial-term(if list-deq(IntDeq) u (snd(u1))
  then [u1 / filter(λm.(list-deq(IntDeq) u (snd(m)));v1)]
  else filter(λm.(list-deq(IntDeq) u (snd(m)));v1)
  fi ))
  + int_term_value(f;ipolynomial-term([u1 / filter(λm.snd(m) ∈_b v;v1)])))
∈ ℤ

2
1. u : ℤ List
2. v : ℤ List List
3. ∀[p:iPolynomial()]
     ∀f:ℤ ⟶ ℤ
       (int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;p)))
       = linearization(p;v) ⋅ map(λvs.accumulate (with value x and list item v):
                                       x * (f v)
                                      over list:
                                        vs
                                      with starting value:
                                       1);v)
       ∈ ℤ)
     supposing no_repeats(ℤ List;v)
4. no_repeats(ℤ List;v)
5. ¬(u ∈ v)
6. f : ℤ ⟶ ℤ
7. u1 : iMonomial()
8. ¬(snd(u1) ∈ v)
9. v1 : iMonomial() List
10. int_term_value(f;ipolynomial-term(filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)))
= (int_term_value(f;ipolynomial-term(filter(λm.(list-deq(IntDeq) u (snd(m)));v1)))
  + int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;v1))))
∈ ℤ
⊢ int_term_value(f;ipolynomial-term(if (list-deq(IntDeq) u (snd(u1))) ∨_bff
then [u1 / filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)]
else filter(λm.((list-deq(IntDeq) u (snd(m))) ∨_bsnd(m) ∈_b v);v1)
fi ))
= (int_term_value(f;ipolynomial-term(if list-deq(IntDeq) u (snd(u1))
  then [u1 / filter(λm.(list-deq(IntDeq) u (snd(m)));v1)]
  else filter(λm.(list-deq(IntDeq) u (snd(m)));v1)
  fi ))
  + int_term_value(f;ipolynomial-term(filter(λm.snd(m) ∈_b v;v1))))
∈ ℤ

Latex:

Latex:
1. u : \mBbbZ{} List 2. v : \mBbbZ{} List List 3. \mforall{}[p:iPolynomial()] \mforall{}f:\mBbbZ{} {}\mrightarrow{} \mBbbZ{} (int\_term\_value(f;ipolynomial-term(filter(\mlambda{}m.snd(m) \mmember{}\msubb{} v;p))) = linearization(p;v) \mcdot{} map(\mlambda{}vs.accumulate (with value x and list item v): x * (f v) over list: vs with starting value: 1);v)) supposing no\_repeats(\mBbbZ{} List;v) 4. no\_repeats(\mBbbZ{} List;v) \mwedge{} (\mneg{}(u \mmember{} v)) 5. f : \mBbbZ{} {}\mrightarrow{} \mBbbZ{} 6. u1 : iMonomial() 7. v1 : iMonomial() List 8. int\_term\_value(f;ipolynomial-term(filter(\mlambda{}m.((list-deq(IntDeq) u (snd(m))) \mvee{}\msubb{}snd(m) \mmember{}\msubb{} v);v1))) = (int\_term\_value(f;ipolynomial-term(filter(\mlambda{}m.(list-deq(IntDeq) u (snd(m)));v1))) + int\_term\_value(f;ipolynomial-term(filter(\mlambda{}m.snd(m) \mmember{}\msubb{} v;v1)))) \mvdash{} int\_term\_value(f;ipolynomial-term(if (list-deq(IntDeq) u (snd(u1))) \mvee{}\msubb{}snd(u1) \mmember{}\msubb{} v then [u1 / filter(\mlambda{}m.((list-deq(IntDeq) u (snd(m))) \mvee{}\msubb{}snd(m) \mmember{}\msubb{} v);v1)] else filter(\mlambda{}m.((list-deq(IntDeq) u (snd(m))) \mvee{}\msubb{}snd(m) \mmember{}\msubb{} v);v1) fi )) = (int\_term\_value(f;ipolynomial-term(if list-deq(IntDeq) u (snd(u1)) then [u1 / filter(\mlambda{}m.(list-deq(IntDeq) u (snd(m)));v1)] else filter(\mlambda{}m.(list-deq(IntDeq) u (snd(m)));v1) fi )) + int\_term\_value(f;ipolynomial-term(if snd(u1) \mmember{}\msubb{} v then [u1 / filter(\mlambda{}m.snd(m) \mmember{}\msubb{} v;v1)] else filter(\mlambda{}m.snd(m) \mmember{}\msubb{} v;v1) fi ))) By Latex: TACTIC:(BoolCase \mkleeneopen{}snd(u1) \mmember{}\msubb{} v\mkleeneclose{}\mcdot{} THEN Auto) Home Index