Universal and Doubly Universal Systems
Raymond M. Smullyan · 1993
Abstract We now turn to two theorems (Theorems A and B below) that will play a major role in this study. We will give three different proofs of them in the course of this volume, since each proof reveals certain interesting features of its own. . . . Theorem A. If( A1 , A2 ) is semi-D.U. and A1 and A2 are both r.e., then A1 and A2 are both universal sets. Theorem B. I f ( A1 , A2 ) is semi-D.U. and A1 and A2 are both r.e., then (A1, A2) is D.U. . . Of course, Theorem A is a trivial corollary of Theorem B, but our proofs of Theorem A reveal facts not revealed by our proofs of Theorem B. We give our first proofs in this chapter. After each proof, we establish a metamathematical corollary: Theorem A yields the result of Ehrenfeucht-Feferman [1960] that for any consistent axiomatizable Rosser system S for sets in which all recursive functions of one argument are strongly definable, all r.e. sets are representable in S. Theorem B yields the stronger result of Putnam-Smullyan [1960]— that any such system S is an exact Rosser system for sets. This result is apparently incomparable in strength with Shepherdson’s result that any consistent axiomatizable Rosser system for binary relations is an exact Rosser system for sets. Both results, of course, yield different proofs that every consistent axiomatizable extension of (R) is an exact Rosser system for sets. §1. Generativity and Universality. We have shown that every universal set is generative. Our first proof of Theorem A will be based on the converse. Theorem 1. Every generative set is universal. We will, in fact, prove something considerably stronger which will have other applications as well. Consider a collection C of r.e. sets.