Library Acceptability
Definition of L-acceptability
Definition
pi
s
t
:=
converges
(
s
(
tenc
t
)).
Definition
lacc
(
P
:
term
→
Prop
) :=
∃
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
p
→
closed
q
→ (
pi
(
acc_conj
p
q
)
s
↔
pi
p
s
∧
pi
q
s
).
Lemma
lacc_conj
P
Q
:
lacc
P
→
lacc
Q
→
lacc
(
conj
P
Q
).
Lemma
lacc_disj
M
N
:
lacc
M
→
lacc
N
→
lacc
(
disj
M
N
).
L-ecidable predicates are L-acceptable (and their complement too)
Lemma
dec_lacc
M
:
ldec
M
→
lacc
M
.
Lemma
dec_acc
:
∀
M
,
ldec
M
→
lacc
M
∧
lacc
(
complement
M
).