Nuprl Lemma : l_tree_ind_wf
∀[L,T,A:Type]. ∀[R:A ⟶ l_tree(L;T) ⟶ ℙ]. ∀[v:l_tree(L;T)]. ∀[leaf:val:L ⟶ {x:A| R[x;l_tree_leaf(val)]} ].
∀[node:val:T
⟶ left_subtree:l_tree(L;T)
⟶ right_subtree:l_tree(L;T)
⟶ {x:A| R[x;left_subtree]}
⟶ {x:A| R[x;right_subtree]}
⟶ {x:A| R[x;l_tree_node(val;left_subtree;right_subtree)]} ].
(l_tree_ind(v;
Leaf(val)⇒ leaf[val];
Node(val,left_subtree,right_subtree)⇒ rec1,rec2.node[val;left_subtree;right_subtree;rec1;rec2])
∈ {x:A| R[x;v]} )
Proof
Definitions occuring in Statement :
l_tree_ind: l_tree_ind,
l_tree_node: l_tree_node(val;left_subtree;right_subtree),
l_tree_leaf: l_tree_leaf(val),
l_tree: l_tree(L;T),
uall: ∀[x:A]. B[x],
prop: ℙ,
so_apply: x[s1;s2;s3;s4;s5],
so_apply: x[s1;s2],
so_apply: x[s],
member: t ∈ T,
set: {x:A| B[x]} ,
function: x:A ⟶ B[x],
universe: Type
Definitions unfolded in proof :
uall: ∀[x:A]. B[x],
member: t ∈ T,
l_tree_ind: l_tree_ind,
so_apply: x[s1;s2;s3;s4;s5],
so_apply: x[s],
so_apply: x[s1;s2],
l_tree-definition,
l_tree-induction,
uniform-comp-nat-induction,
l_tree-ext,
eq_atom: x =a y,
bool_cases_sqequal,
eqff_to_assert,
any: any x,
btrue: tt,
bfalse: ff,
it: ⋅,
top: Top,
all: ∀x:A. B[x],
implies: P ⇒ Q,
has-value: (a)↓,
prop: ℙ,
so_lambda: so_lambda(x,y,z,w.t[x; y; z; w]),
so_apply: x[s1;s2;s3;s4],
so_lambda: λ2x.t[x],
uimplies: b supposing a,
strict4: strict4(F),
and: P ∧ Q,
guard: {T},
or: P ∨ Q,
squash: ↓T,
subtype_rel: A ⊆r B
Lemmas referenced :
l_tree-definition,
top_wf,
equal_wf,
has-value_wf_base,
is-exception_wf,
lifting-strict-atom_eq,
base_wf,
l_tree_wf,
l_tree_leaf_wf,
l_tree_node_wf,
all_wf,
set_wf,
l_tree-induction,
uniform-comp-nat-induction,
l_tree-ext,
bool_cases_sqequal,
eqff_to_assert
Rules used in proof :
sqequalSubstitution,
sqequalTransitivity,
computationStep,
sqequalReflexivity,
isect_memberFormation,
cut,
sqequalRule,
isect_memberEquality,
voidElimination,
voidEquality,
thin,
introduction,
extract_by_obid,
hypothesis,
lambdaFormation,
because_Cache,
sqequalSqle,
divergentSqle,
callbyvalueDecide,
sqequalHypSubstitution,
hypothesisEquality,
unionEquality,
unionElimination,
sqleReflexivity,
isectElimination,
equalityTransitivity,
equalitySymmetry,
dependent_functionElimination,
independent_functionElimination,
decideExceptionCases,
axiomSqleEquality,
exceptionSqequal,
baseApply,
closedConclusion,
baseClosed,
independent_isectElimination,
independent_pairFormation,
inrFormation,
imageMemberEquality,
imageElimination,
inlFormation,
instantiate,
applyEquality,
lambdaEquality,
isectEquality,
functionEquality,
cumulativity,
universeEquality,
setEquality,
functionExtensionality,
setElimination,
rename,
dependent_set_memberEquality
Latex:
\mforall{}[L,T,A:Type]. \mforall{}[R:A {}\mrightarrow{} l\_tree(L;T) {}\mrightarrow{} \mBbbP{}]. \mforall{}[v:l\_tree(L;T)].
\mforall{}[leaf:val:L {}\mrightarrow{} \{x:A| R[x;l\_tree\_leaf(val)]\} ].
\mforall{}[node:val:T
{}\mrightarrow{} left$_{subtree}$:l\_tree(L;T)
{}\mrightarrow{} right$_{subtree}$:l\_tree(L;T)
{}\mrightarrow{} \{x:A| R[x;left$_{subtree}$]\}
{}\mrightarrow{} \{x:A| R[x;right$_{subtree}$]\}
{}\mrightarrow{} \{x:A| R[x;l\_tree\_node(val;left$_{subtree}$;right$_{subtree\000C}$)]\} ].
(l\_tree\_ind(v;
Leaf(val){}\mRightarrow{} leaf[val];
Node(val,left$_{subtree}$,right$_{subtree}$){}\mRightarrow{}\000C rec1,rec2.node[val;left$_{subtree}$;...;rec1;rec2])
\mmember{} \{x:A| R[x;v]\} )
Date html generated:
2018_05_22-PM-09_39_20
Last ObjectModification:
2017_03_04-PM-07_25_47
Theory : labeled!trees
Home
Index