Origin Sections AutomataTheory Doc

choice_1

Nuprl Section: choice_1

Selected Objects
defmin_ar(rec) MinAr(f;i;n) == if (f(n-i))=(f(n)) i else MinAr(f;i-1;n) fi
THMmin_ar_altf:(), n:, i:(n+1), j:(n-i+1). f(n-i) = f(n) MinAr(f;j+i;n) = MinAr(f;j;n-i)+i
THMmin_ar_soundf:(), n:, i:(n+1). f(n-MinAr(f;i;n)) = f(n)
defmin_argMinArg(f : {0..n}) == n-MinAr(f;n;n)
THMmin_arg_uniquef:(), n,k:. f(n) = f(k) MinArg(f : {0..n}) = MinArg(f : {0..k})
THMmin_arg_soundf:(), n:. f(MinArg(f : {0..n})) = f(n)
THMmin_arg_ifff:(), n,k:. f(n) = f(k) MinArg(f : {0..n}) = MinArg(f : {0..k})
defmin_elMin{ x | xEn } == MinArg(E(n) : {0..n})
THMequiv_rel_funE:(TT), s,t:T. (EquivRel x,y:T. x E y) (s E t) E(s) = E(t)
THMmin_el_uniqueE:(), n,k:. (EquivRel x,y:. x E y) (n E k) Min{ x | xEn } = Min{ x | xEk }
THMmin_el_soundE:(), n:. (EquivRel x,y:. x E y) (n E Min{ x | xEn })
THMmin_el_iffE:(), n,k:. (EquivRel x,y:. x E y) ((n E k) Min{ x | xEn } = Min{ x | xEk })
THMdecide_imp_boolR:(TTProp). (x,y:T. Dec(x R y)) (r:(TT). x,y:T. (x r y) (x R y))
THMcomp_choiceE:(Prop). (EquivRel x,y:. x E y) & (x,y:. Dec(x E y)) (h:(). (n,k:. (n E k) h(n) = h(k)) & (n:. n E (h(n))))