### Nuprl Lemma : prec-size-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)| ||j;z|| < ||i;x||} .  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-size: `||i;x||` prec: `prec(lbl,p.a[lbl; p];i)` list: `T List` less_than: `a < b` uall: `∀[x:A]. B[x]` so_apply: `x[s1;s2]` all: `∀x:A. B[x]` implies: `P `` Q` set: `{x:A| B[x]} ` function: `x:A ⟶ B[x]` union: `left + right` atom: `Atom` universe: `Type`
Definitions unfolded in proof :  guard: `{T}` less_than: `a < b` squash: `↓T` less_than': `less_than'(a;b)` or: `P ∨ Q` decidable: `Dec(P)` le: `A ≤ B` lelt: `i ≤ j < k` prop: `ℙ` and: `P ∧ Q` top: `Top` exists: `∃x:A. B[x]` satisfiable_int_formula: `satisfiable_int_formula(fmla)` not: `¬A` ge: `i ≥ j ` false: `False` int_seg: `{i..j-}` subtype_rel: `A ⊆r B` uimplies: `b supposing a` so_apply: `x[s1;s2]` so_lambda: `λ2x y.t[x; y]` all: `∀x:A. B[x]` nat: `ℕ` member: `t ∈ T` implies: `P `` Q` uall: `∀[x:A]. B[x]`
Lemmas referenced :  le_witness_for_triv istype-universe list_wf int_term_value_add_lemma itermAdd_wf decidable__le istype-false int_seg_subtype_nat int_term_value_subtract_lemma int_formula_prop_not_lemma itermSubtract_wf intformnot_wf subtract_wf decidable__lt subtract-1-ge-0 int_seg_properties istype-less_than ge_wf int_formula_prop_wf int_formula_prop_less_lemma int_term_value_var_lemma int_term_value_constant_lemma int_formula_prop_le_lemma istype-void int_formula_prop_and_lemma istype-int intformless_wf itermVar_wf itermConstant_wf intformle_wf intformand_wf full-omega-unsat nat_properties istype-nat prec-size_wf istype-le istype-atom prec_wf int_seg_wf
Rules used in proof :  applyLambdaEquality functionExtensionality imageElimination universeEquality cumulativity unionEquality instantiate TYPEIsType setIsType addEquality equalityIstype equalitySymmetry equalityTransitivity productIsType unionElimination dependent_set_memberEquality_alt productElimination functionIsTypeImplies axiomEquality independent_pairFormation voidElimination isect_memberEquality_alt dependent_functionElimination int_eqEquality dependent_pairFormation_alt independent_functionElimination approximateComputation independent_isectElimination intWeakElimination TYPEMemberIsType inhabitedIsType applyEquality lambdaEquality_alt because_Cache functionIsType hypothesis hypothesisEquality rename setElimination natural_numberEquality thin isectElimination sqequalHypSubstitution extract_by_obid introduction universeIsType isectIsType sqequalRule cut lambdaFormation_alt isect_memberFormation_alt sqequalReflexivity computationStep sqequalTransitivity sqequalSubstitution

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)|  ||j;z||  <  ||i;x||\}  .    Q[j;z])  {}\mRightarrow{}  Q[i;x]))
{}\mRightarrow{}  (\mforall{}i:P.  \mforall{}x:prec(lbl,p.a[lbl;p];i).    Q[i;x]))

Date html generated: 2019_10_15-AM-10_25_03
Last ObjectModification: 2019_09_26-PM-04_38_54

Theory : tuples

Home Index