### Nuprl Lemma : count-quotient

`∀k:ℕ`
`  ∀[A:Type]`
`    (A ~ ℕk`
`    `` (∀[E:A ⟶ A ⟶ ℙ]. (EquivRel(A;x,y.E[x;y]) `` (∀x,y:A.  Dec(E[x;y])) `` (∃j:ℕ. ((j ≤ k) ∧ x,y:A//E[x;y] ~ ℕj)))))`

Proof

Definitions occuring in Statement :  equipollent: `A ~ B` equiv_rel: `EquivRel(T;x,y.E[x; y])` quotient: `x,y:A//B[x; y]` int_seg: `{i..j-}` nat: `ℕ` decidable: `Dec(P)` uall: `∀[x:A]. B[x]` prop: `ℙ` so_apply: `x[s1;s2]` le: `A ≤ B` all: `∀x:A. B[x]` exists: `∃x:A. B[x]` implies: `P `` Q` and: `P ∧ Q` function: `x:A ⟶ B[x]` natural_number: `\$n` universe: `Type`
Definitions unfolded in proof :  all: `∀x:A. B[x]` member: `t ∈ T` uall: `∀[x:A]. B[x]` implies: `P `` Q` exists: `∃x:A. B[x]` and: `P ∧ Q` uimplies: `b supposing a` cand: `A c∧ B` prop: `ℙ` nat: `ℕ` so_lambda: `λ2x y.t[x; y]` so_apply: `x[s1;s2]` so_lambda: `λ2x.t[x]` so_apply: `x[s]`
Lemmas referenced :  distinct-representatives equipollent-distinct-representatives length_wf_nat and_wf le_wf equipollent_wf quotient_wf int_seg_wf all_wf decidable_wf equiv_rel_wf nat_wf
Rules used in proof :  cut lemma_by_obid sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity lambdaFormation hypothesis sqequalHypSubstitution dependent_functionElimination thin hypothesisEquality isect_memberFormation isectElimination independent_functionElimination productElimination independent_isectElimination dependent_pairFormation independent_pairFormation setElimination rename sqequalRule lambdaEquality applyEquality natural_numberEquality functionEquality cumulativity universeEquality

Latex:
\mforall{}k:\mBbbN{}
\mforall{}[A:Type]
(A  \msim{}  \mBbbN{}k
{}\mRightarrow{}  (\mforall{}[E:A  {}\mrightarrow{}  A  {}\mrightarrow{}  \mBbbP{}]
(EquivRel(A;x,y.E[x;y])
{}\mRightarrow{}  (\mforall{}x,y:A.    Dec(E[x;y]))
{}\mRightarrow{}  (\mexists{}j:\mBbbN{}.  ((j  \mleq{}  k)  \mwedge{}  x,y:A//E[x;y]  \msim{}  \mBbbN{}j)))))

Date html generated: 2016_05_14-PM-04_04_53
Last ObjectModification: 2015_12_26-PM-07_41_53

Theory : equipollence!!cardinality!

Home Index