Library Acceptability


Definition of L-acceptability


Definition pi s t := converges (s (tenc t)).

Definition lacc (P : termProp) :=
   u, proc u t, P t pi u t.

Properties of acceptance


Goal s1 s2 t, s1 == s2 → (pi s1 t pi s2 t).

L-acceptable predicates are closed under conjunction and disjunction


Definition acc_conj (p q : term) := lam ((lam (q #1)) (p #0) ).

Lemma acc_conj_correct p q s : closed pclosed q → (pi (acc_conj p q) s pi p s pi q s).

Lemma lacc_conj P Q : lacc Placc Qlacc (conj P Q).

Lemma lacc_disj M N : lacc Mlacc Nlacc (disj M N).

L-ecidable predicates are L-acceptable (and their complement too)


Lemma dec_lacc M : ldec Mlacc M.

Lemma dec_acc : M, ldec Mlacc M lacc (complement M).