### Nuprl Lemma : prec-induction

`∀[P:Type]. ∀[a:Atom ⟶ P ⟶ ((P + P + Type) List)]. ∀[Q:i:P ⟶ prec(lbl,p.a[lbl;p];i) ⟶ TYPE].`
`  ((∀i:P. ∀x:prec(lbl,p.a[lbl;p];i).  ((∀j:P. ∀z:{z:prec(lbl,p.a[lbl;p];j)| prec_sub+(P;lbl,p.a[lbl;p]) <j, z> <i, x>} .\000C  Q[j;z]) `` Q[i;x]))`
`  `` (∀i:P. ∀x:prec(lbl,p.a[lbl;p];i).  Q[i;x]))`

Proof

Definitions occuring in Statement :  prec_sub+: `prec_sub+(P;lbl,p.a[lbl; p])` prec: `prec(lbl,p.a[lbl; p];i)` list: `T List` uall: `∀[x:A]. B[x]` so_apply: `x[s1;s2]` all: `∀x:A. B[x]` implies: `P `` Q` set: `{x:A| B[x]} ` apply: `f a` function: `x:A ⟶ B[x]` pair: `<a, b>` union: `left + right` atom: `Atom` universe: `Type`
Definitions unfolded in proof :  uall: `∀[x:A]. B[x]` member: `t ∈ T` implies: `P `` Q` all: `∀x:A. B[x]` so_lambda: `λ2x y.t[x; y]` so_apply: `x[s1;s2]` subtype_rel: `A ⊆r B` nat: `ℕ` prop: `ℙ` uimplies: `b supposing a`
Lemmas referenced :  prec-size-induction-ext prec_wf istype-atom prec_sub+_wf istype-less_than prec-size_wf subtype_rel_self list_wf istype-universe prec-sub+-size
Rules used in proof :  cut introduction extract_by_obid sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity Error :isect_memberFormation_alt,  hypothesis sqequalHypSubstitution isectElimination thin hypothesisEquality Error :lambdaFormation_alt,  independent_functionElimination dependent_functionElimination Error :setIsType,  Error :universeIsType,  sqequalRule Error :lambdaEquality_alt,  applyEquality Error :inhabitedIsType,  Error :dependent_pairEquality_alt,  because_Cache Error :functionIsType,  setElimination rename equalityTransitivity equalitySymmetry Error :TYPEMemberIsType,  instantiate universeEquality Error :TYPEIsType,  unionEquality cumulativity Error :dependent_set_memberEquality_alt,  independent_isectElimination

Latex:
\mforall{}[P:Type].  \mforall{}[a:Atom  {}\mrightarrow{}  P  {}\mrightarrow{}  ((P  +  P  +  Type)  List)].  \mforall{}[Q:i:P  {}\mrightarrow{}  prec(lbl,p.a[lbl;p];i)  {}\mrightarrow{}  TYPE].
((\mforall{}i:P.  \mforall{}x:prec(lbl,p.a[lbl;p];i).
((\mforall{}j:P.  \mforall{}z:\{z:prec(lbl,p.a[lbl;p];j)|  prec\_sub+(P;lbl,p.a[lbl;p])  <j,  z>  <i,  x>\}  .    Q[j;z])  {}\mRightarrow{}\000C  Q[i;x]))
{}\mRightarrow{}  (\mforall{}i:P.  \mforall{}x:prec(lbl,p.a[lbl;p];i).    Q[i;x]))

Date html generated: 2019_06_20-PM-02_14_28
Last ObjectModification: 2019_03_12-PM-06_04_12

Theory : tuples

Home Index