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 not-F is undecidable on the complement of S, and the n substitution instances of not-F 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