Fourth Annual IEEE Symposium on

Logic in Computer Science (LICS 1989)

Paper: How complete is PER? (at LICS 1989)

Authors: Robinson, E.


The category of partial equivalence relations (PER) on the natural numbers has been used extensively in recent years to model various forms of higher-order type theory. It is known that PER can be viewed as a category of sets in a nonstandard model of intuitionistic Zermelo-Fraenkel set theory. The use of PER as a vehicle for modeling-type theory then arises from completeness properties of this category. The paper demonstrates these completeness properties, and shows that, constructively, some complete categories are more complete than others


    author = 	 {Robinson, E.},
    title = 	 {How complete is PER?},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {106--111},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}