An Undecidable Linear Order That Is $n$-Decidable for All $n$

&
Notre Dame Journal of Formal Logic 39 (4):519-526 (1998)
  Copy   BIBTEX

Abstract

A linear order is -decidable if its universe is and the relations defined by formulas are uniformly computable. This means that there is a computable procedure which, when applied to a formula and a sequence of elements of the linear order, will determine whether or not is true in the structure. A linear order is decidable if the relations defined by all formulas are uniformly computable. These definitions suggest two questions. Are there, for each , -decidable linear orders that are not -decidable? Are there linear orders that are -decidable for all but not decidable? The former was answered in the positive by Moses in 1993. Here we answer the latter, also positively

Categories

Keywords

Reprint years

DOI

10.1305/ndjfl/1039118866

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,672

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The undecidability of second order linear logic without exponentials.Yves Lafont - 1996 - Journal of Symbolic Logic 61 (2):541-548.
A decidable variety that is finitely undecidable.Joohee Jeong - 1999 - Journal of Symbolic Logic 64 (2):651-677.
Decidable discrete linear orders.M. Moses - 1988 - Journal of Symbolic Logic 53 (2):531-539.
Unification grammars and off-line parsability.Efrat Jaeger, Nissim Francez & Shuly Wintner - 2005 - Journal of Logic, Language and Information 14 (2):199-234.
Decidable and undecidable logics with a binary modality.ágnes Kurucz, István Németi, Ildikó Sain & András Simon - 1995 - Journal of Logic, Language and Information 4 (3):191-206.
On the membership problem for non-linear abstract categorial grammars.Sylvain Salvati - 2010 - Journal of Logic, Language and Information 19 (2):163-183.
On first-order theories with provability operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
Decidability and undecidability of theories with a predicate for the primes.P. T. Bateman, C. G. Jockusch & A. R. Woods - 1993 - Journal of Symbolic Logic 58 (2):672-687.
Decidable subspaces and recursively enumerable subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
Modal Logics Between Propositional and First Order.Melvin Fitting - unknown
Products of 'transitive' modal logics.David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2005 - Journal of Symbolic Logic 70 (3):993-1021.
Undecidability of first-order intuitionistic and modal logics with two variables.Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev - 2005 - Bulletin of Symbolic Logic 11 (3):428-438.
First-order Frege theory is undecidable.Warren Goldfarb - 2001 - Journal of Philosophical Logic 30 (6):613-616.
Decision problems for classes of diagonalizable algebras.Aldo Ursini - 1985 - Studia Logica 44 (1):87 - 89.

Analytics

Added to PP
2010-08-24

Downloads
63 (#255,462)

6 months
16 (#154,579)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Sequences of n-diagrams.Valentina S. Harizanov, Julia F. Knight & Andrei S. Morozov - 2002 - Journal of Symbolic Logic 67 (3):1227-1247.

Add more citations

References found in this work

Computability theory and linear orders.Rod Downey - 1998 - In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. pp. 138--823.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Mathematical Logic Quarterly 32 (25-30):467-472.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Mathematical Logic Quarterly 32 (25‐30):467-472.

Add more references