A recursion principle for linear orderings

Journal of Symbolic Logic 57 (1):82-96 (1992)
  Copy   BIBTEX

Abstract

The idea of this paper is to approach linear orderings as generalized ordinals and to study how they are made from their initial segments. First we look at how the equality of two linear orderings can be expressed in terms of equality of their initial segments. Then we shall use similar methods to define functions by recursion with respect to the initial segment relation. Our method is based on the use of a game where smaller and smaller initial segments of linear orderings are considered. The length of the game is assumed to exceed that of the descending sequences of elements of the linear orderings considered. By use of such game-theoretical methods we can for example extend the recursive definitions of the operations of sum, product and exponentiation of ordinals in a unique and natural way for arbitrary linear orderings. Extensions coming from direct limits do not satisfy our game-theoretic requirements in general. We also show how our recursive definitions allow very simple constructions for fixed points of functions, giving rise to certain interesting linear orderings

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,391

External links

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

Through your library

Similar books and articles

On the equimorphism types of linear orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
A coding of the countable linear orderings.Patrick Dehornoy - 1990 - Studia Logica 49 (4):585 - 590.
Up to Equimorphism, Hyperarithmetic Is Recursive.Antonio Montalbán - 2005 - Journal of Symbolic Logic 70 (2):360 - 378.
On Ehrenfeucht-fraïssé equivalence of linear orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
Recursive linear orderings and hyperarithmetical functions.Shih-Chao Liu - 1962 - Notre Dame Journal of Formal Logic 3 (3):129-132.
A construction for recursive linear orderings.C. J. Ash - 1991 - Journal of Symbolic Logic 56 (2):673-683.

Analytics

Added to PP
2009-01-28

Downloads
49 (#241,451)

6 months
1 (#451,971)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Game-theoretic inductive definability.Juha Oikkonen & Jouko Väänänen - 1993 - Annals of Pure and Applied Logic 65 (3):265-306.
X Latin American Symposium on Mathematical Logic.Xavier Caicedo - 1996 - Bulletin of Symbolic Logic 2 (2):214-237.

Add more citations

References found in this work

No references found.

Add more references