
Accession Number : AD0684698
Title : A NONINTERPOLATION THEOREM ABOUT Pi SUB ONE, SUPERSCRIPT ZERO UNDECIDABLE SENTENCES OF ARITHMETIC,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : DiPaola,Robert A.
Report Date : MAR 1969
Pagination or Media Count : 23
Abstract : Given the fact that the partial ordering induced by the implication relation on equivalence classes of undecidable (not mechanically derivable) sentences of formal systems of arithmetic is dense, the ordering is investigated with respect to undecidable sentences which are substitution instances of the same formula. It is shown that if S is a recursively enumerable set having n specified members in its complement, n greater than or equal to 2, then one can effectively find a formula F which represents S in T such that notF is undecidable on the complement of S, and the n substitution instances of notF arising from the n specified members of the complement of S constitute an initial segment of length n. (Author)
Descriptors : (*MATHEMATICAL LOGIC, AUTOMATA), RECURSIVE FUNCTIONS, SET THEORY, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE