Nuprl Lemma : lexico_induction
∀[T:Type]. ∀[lt:T ⟶ T ⟶ ℙ].
((∀[Q:T ⟶ ℙ]. ((∀b:T. ((∀a:T. (lt[a;b] ⇒ Q[a])) ⇒ Q[b])) ⇒ (∀b:T. Q[b])))
⇒ (∀[P:(T List) ⟶ ℙ]
((∀L:T List. ((∀L':T List. ((L' lexico(T; a,b.lt[a;b]) L) ⇒ P[L'])) ⇒ P[L])) ⇒ (∀L:T List. P[L]))))
Proof
Definitions occuring in Statement :
lexico: lexico(T; a,b.lt[a; b]),
list: T List,
uall: ∀[x:A]. B[x],
prop: ℙ,
infix_ap: x f y,
so_apply: x[s1;s2],
so_apply: x[s],
all: ∀x:A. B[x],
implies: P ⇒ Q,
function: x:A ⟶ B[x],
universe: Type
Definitions unfolded in proof :
uall: ∀[x:A]. B[x],
member: t ∈ T,
implies: P ⇒ Q,
prop: ℙ,
so_lambda: λ2x.t[x],
so_apply: x[s1;s2],
so_apply: x[s],
wellfounded: WellFnd{i}(A;x,y.R[x; y]),
guard: {T}
Lemmas referenced :
lexico_well_fnd,
uall_wf,
all_wf,
list_wf
Rules used in proof :
cut,
lemma_by_obid,
sqequalSubstitution,
sqequalTransitivity,
computationStep,
sqequalReflexivity,
isect_memberFormation,
hypothesis,
sqequalHypSubstitution,
isectElimination,
thin,
hypothesisEquality,
lambdaFormation,
independent_functionElimination,
instantiate,
functionEquality,
cumulativity,
universeEquality,
sqequalRule,
lambdaEquality,
applyEquality
Latex:
\mforall{}[T:Type]. \mforall{}[lt:T {}\mrightarrow{} T {}\mrightarrow{} \mBbbP{}].
((\mforall{}[Q:T {}\mrightarrow{} \mBbbP{}]. ((\mforall{}b:T. ((\mforall{}a:T. (lt[a;b] {}\mRightarrow{} Q[a])) {}\mRightarrow{} Q[b])) {}\mRightarrow{} (\mforall{}b:T. Q[b])))
{}\mRightarrow{} (\mforall{}[P:(T List) {}\mrightarrow{} \mBbbP{}]
((\mforall{}L:T List. ((\mforall{}L':T List. ((L' lexico(T; a,b.lt[a;b]) L) {}\mRightarrow{} P[L'])) {}\mRightarrow{} P[L]))
{}\mRightarrow{} (\mforall{}L:T List. P[L]))))
Date html generated:
2016_05_15-PM-06_36_31
Last ObjectModification:
2015_12_27-AM-11_55_10
Theory : general
Home
Index