Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-13T09:20:50.108Z Has data issue: false hasContentIssue false
  • English
  • Français

A recursion principle for linear orderings

Published online by Cambridge University Press:  12 March 2014

Juha Oikkonen
Juha Oikkonen*
Affiliation:
Department of Mathematics, University of Helsinki, 00100 Helsinki, Finland, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 82 - 96
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[A]Aczel, P., Inductive definability, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 739–782.CrossRefGoogle Scholar
[BP]Bonnet, R. and Pouzet, M., Linear extensions of ordered sets, Ordered sets (Rival, I., editor), Reidel, Dordrecht, 1982, pp. 125–170.CrossRefGoogle Scholar
[H]Huuskonen, T., A nondetermined Ehrenfeucht-Fraïssé game (to appear).Google Scholar
[Hy]Hyttinen, T., Model theory for infinite quantifier logics, Fundamenta Mathematicae, vol. 134 (1990), pp. 125–142.Google Scholar
[K]Karp, C., Finite quantifier equivalence, The theory of models (Addison, J. W.et al., editors), North-Holland, Amsterdam, 1965, pp. 407–412.Google Scholar
[NS]Nadel, M. and Stavi, J., L∞λ-equivalence, isomorphism and potential isomorphism, Transactions of the American Mathematical Society, vol. 236 (1978), pp. 51–74.Google Scholar
[O]Oikkonen, J., How to obtain interpolation for Lk + k, Logic colloquium '86 (Drake, F. and Truss, J., editors), North-Holland, Amsterdam, 1988, pp. 175–208.Google Scholar
[O2]Oikkonen, J., On Ehrenfeucht-Fraïssé equivalence of linear orderings, this Journal, vol. 55 (1990), pp. 65–73.Google Scholar
[OV]Oikkonen, J. and Väänänen, J., Game-theoretic inductive definability (to appear).Google Scholar