### Nuprl Lemma : finite-acyclic-rel

`∀[T:Type]. ((∃n:ℕ. T ~ ℕn) `` (∀[R:T ⟶ T ⟶ ℙ]. ((∀x,y:T.  Dec(x R y)) `` (SWellFounded(x R y) `⇐⇒` acyclic-rel(T;R)))))`

Proof

Definitions occuring in Statement :  equipollent: `A ~ B` acyclic-rel: `acyclic-rel(T;R)` strongwellfounded: `SWellFounded(R[x; y])` int_seg: `{i..j-}` nat: `ℕ` decidable: `Dec(P)` uall: `∀[x:A]. B[x]` prop: `ℙ` infix_ap: `x f y` all: `∀x:A. B[x]` exists: `∃x:A. B[x]` iff: `P `⇐⇒` Q` implies: `P `` Q` function: `x:A ⟶ B[x]` natural_number: `\$n` universe: `Type`
Definitions unfolded in proof :  uall: `∀[x:A]. B[x]` implies: `P `` Q` iff: `P `⇐⇒` Q` and: `P ∧ Q` member: `t ∈ T` acyclic-rel: `acyclic-rel(T;R)` all: `∀x:A. B[x]` not: `¬A` false: `False` infix_ap: `x f y` subtype_rel: `A ⊆r B` prop: `ℙ` so_lambda: `λ2x y.t[x; y]` so_apply: `x[s1;s2]` rev_implies: `P `` Q` so_lambda: `λ2x.t[x]` so_apply: `x[s]` nat: `ℕ` exists: `∃x:A. B[x]` uimplies: `b supposing a` strongwellfounded: `SWellFounded(R[x; y])` equipollent: `A ~ B` rel_plus: `R+` nat_plus: `ℕ+` le: `A ≤ B` less_than': `less_than'(a;b)` rel_exp: `R^n` guard: `{T}` int_seg: `{i..j-}` lelt: `i ≤ j < k` decidable: `Dec(P)` or: `P ∨ Q` satisfiable_int_formula: `satisfiable_int_formula(fmla)` top: `Top` bool: `𝔹` unit: `Unit` it: `⋅` btrue: `tt` uiff: `uiff(P;Q)` ifthenelse: `if b then t else f fi ` bfalse: `ff` sq_type: `SQType(T)` cand: `A c∧ B` pi1: `fst(t)` sq_exists: `∃x:{A| B[x]}` ge: `i ≥ j ` squash: `↓T` true: `True` compose: `f o g` subtract: `n - m` rel-path-between: `rel-path-between(T;R;x;y;L)` bnot: `¬bb` assert: `↑b` nequal: `a ≠ b ∈ T ` biject: `Bij(A;B;f)` inject: `Inj(A;B;f)` less_than: `a < b`
Rules used in proof :  sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity isect_memberFormation lambdaFormation independent_pairFormation introduction cut extract_by_obid sqequalHypSubstitution isectElimination thin hypothesisEquality independent_functionElimination hypothesis sqequalRule lambdaEquality dependent_functionElimination voidElimination applyEquality cumulativity functionExtensionality functionEquality universeEquality natural_numberEquality setElimination rename productElimination instantiate because_Cache independent_isectElimination intEquality dependent_pairFormation dependent_set_memberEquality addEquality unionElimination int_eqEquality isect_memberEquality voidEquality computeAll equalityTransitivity equalitySymmetry applyLambdaEquality baseApply closedConclusion baseClosed equalityElimination impliesFunctionality productEquality promote_hyp imageElimination imageMemberEquality hyp_replacement setEquality addLevel levelHypothesis pointwiseFunctionality

Latex:
\mforall{}[T:Type]
((\mexists{}n:\mBbbN{}.  T  \msim{}  \mBbbN{}n)
{}\mRightarrow{}  (\mforall{}[R:T  {}\mrightarrow{}  T  {}\mrightarrow{}  \mBbbP{}].  ((\mforall{}x,y:T.    Dec(x  R  y))  {}\mRightarrow{}  (SWellFounded(x  R  y)  \mLeftarrow{}{}\mRightarrow{}  acyclic-rel(T;R)))))

Date html generated: 2017_04_17-AM-09_35_53
Last ObjectModification: 2017_02_27-PM-05_35_42

Theory : equipollence!!cardinality!

Home Index