A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings

• Published in: The Journal of symbolic logic 1984-06, Vol.49 (2), p.563-569
• Main Author: Watnick, Richard
• Format: Article
• Language: English
• Subjects: Counterexamples; Exact sciences and technology; Logic and foundations; Logical theorems; Mathematical logic, foundations, set theory; Mathematics; Recursion theory; Sciences and techniques of general use
• ISSN: 0022-4812; 1943-5886
• DOI: 10.2307/2274189

An effective translation of the fact that any infinite ordered set contains an infinite ascending or descending sequence is that any infinite recursive set A ⊆ Q has a recursive subset with order type ω or ω *. Tennenbaum's theorem states that this translation is false, and there is a counterexample A with order type ω + ω *. Tennenbaum suggested that this counterexample is an infinite recursive linearly ordered set which is effectively finite, and that the collection of all such counterexamples could provide a concrete model of nonstandard arithmetic. The purpose of this paper is to determine the collection of order types for which there is a counterexample. It is readily seen that any counterexample to the effective translation must have order type ω + Z · α + ω * for some α [2], [3]. Let be the collection of order types α for which there is a counterexample. As a test case, we have previously shown that contains the constructive scattered orderings [3], [4]. In this paper we determine exactly which order types are in . We easily show that if ω + Z · α + ω * is recursive, then α is . The main result is that . Consequently, .