The order types of termination orderings on monadic terms, strings and monadic terms, strings and multisets
Journal of Symbolic Logic 62 (2):624-635 (1997)
| Abstract | We consider total well-founded orderings on monadic terms satisfying the replacement and full invariance properties. We show that any such ordering on monadic terms in one variable and two unary function symbols must have order type ω, ω 2 or ω ω . We show that a familiar construction gives rise to continuum many such orderings of order type ω. We construct a new family of such orderings of order type ω 2 , and show that there are continuum many of these. We show that there are only four such orderings of order type ω ω , the two familiar recursive path orderings and two closely related orderings. We consider also total well-founded orderings on N n which are preserved under vector addition. We show that any such ordering must have order type ω k for some 1 ≤ k ≤ n. We show that if $k there are continuum many such orderings, and if k = n there are only n!, the n! lexicographic orderings | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesLudwig von Auer (1999). Dynamic Choice Mechanisms. Theory and Decision 46 (3):295-312.
Shmuel Lifsches & Saharon Shelah (1998). Uniformization and Skolem Functions in the Class of Trees. Journal of Symbolic Logic 63 (1):103-127.
M. Marshall (2006). Local-Global Properties of Positive Primitive Formulas in the Theory of Spaces of Orderings. Journal of Symbolic Logic 71 (4):1097 - 1107.
Patrick Dehornoy (1990). A Coding of the Countable Linear Orderings. Studia Logica 49 (4):585 - 590.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Shmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
Juha Oikkonen (1992). A Recursion Principle for Linear Orderings. Journal of Symbolic Logic 57 (1):82-96.
C. J. Ash (1991). A Construction for Recursive Linear Orderings. Journal of Symbolic Logic 56 (2):673-683.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,556 of 548,984 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
