Some properties of pseudo-complements of recursively enumerable sets
Robert A. Di Paola · Transactions of the American Mathematical Society · 1966
Introductory remarks.Those first order systems which exhibit some real mathematical pretensions fall into what is called in [1] the class of arithmetical logics; it is there demonstrated that that any oj-consistent and adequate arithmetical logic is incomplete and brought out that the undecidable sentence can always be taken to be a closed well-formed formula which truly expresses that n0$S where n0 is an integer and S a nonrecursive recursively enumerable set.Thus, we are led to consider those sets of integers whose members are probably (in a system T) in the complement of a given recursively enumerable set S, or, as we shall call them, the pseudo-complements of S, a notion introduced by Davis in [3].It is to be observed that being a pseudo-complement of S is not a purely extensional property; that is to say, the pseudo-complement of an re (recursively enumerable) set S is not simply a function of S as a set, but also of the particular representation of S in the system T. Different representations of the one set S may give rise to markedly different pseudo-complements even with respect to the same theory T.In this paper we shall explore some of the properties of pseudo-complements of re sets in re consistent extensions of Peano arithmetic.Also, since our definition of a pseudo-complement function provides a natural setting for Davis' theorems, we state his results to achieve comprehensiveness.We prove a separation theorem, Theorem 6, to the effect that if A and B are disjoint re sets, they can be so represented that B is the pseudo-complement of A. From this it easily follows that all re sets are pseudo-complements.The fact that the pseudo-complement of the pseudo-complement is always empty [3] distinguishes sharply the enumeration of the re sets given by a pseudocomplement function from the standard enumerations.Given two numbers, one occurring in a standard enumeration and the other produced by a pseudocomplement function, the problem arises of deciding if these numbers represent Presented to the Society, April 20, 1964 under the title Pseudo-complements: their extent, creative sets, and effectively inseparable sets ; received by the editors June 11, 1964.