[TYPES] Is one-step conversion rule of CC equivalent to the multi-step one?
Yang, Yanpeng
yangyp at connect.hku.hk
Wed Aug 23 04:21:31 EDT 2017
Dear all,
The conversion rule of the Calculus of Constructions (CC) is usually
defined as follows:
G |- e : A
G |- A : s
A ==beta B
------------------- Conv
G |- e : B
I wonder if this rule is equivalent to the one using *one-step* beta
reduction:
G |- e : A
G |- A : s
A --> B \/ B --> A
-------------------------- Conv-Step
G |- e : B
This "Conv-Step" rule is shown in Geuvers' paper [1, Definition 4.1] but
which never mentions if it is equivalent to the original "Conv" rule.
So, my question is: has it ever been proved that the two conversion rules
are equivalent? If so, what is the appropriate article to refer to for this
proof?
Thanks a lot!
Sincerely,
Yanpeng
[1] Geuvers, Herman. "A short and flexible proof of Strong Normalization
for the Calculus of Constructions." International Workshop on Types for
Proofs and Programs. Springer, Berlin, Heidelberg, 1994.
URL: http://flint.cs.yale.edu/trifonov/cs629/Geuvers-SN-CC-2up.ps
More information about the Types-list
mailing list