On Ehrenfeucht-Fraisse Equivalence of Linear Orderings
Oikkonen, Juha
J. Symbolic Logic, Tome 55 (1990) no. 1, p. 65-73 / Harvested from Project Euclid
C. Karp has shown that if $\alpha$ is an ordinal with $\omega^\alpha = \alpha$ and $A$ is a linear ordering with a smallest element, then $\alpha$ and $\alpha \bigotimes A$ are equivalent in $L_{\infty\omega}$ up to quantifer rank $\alpha$. This result can be expressed in terms of Ehrenfeucht-Fraisse games where player $\forall$ has to make additional moves by choosing elements of a descending sequence in $\alpha$. Our aim in this paper is to prove a similar result for Ehrenfeucht-Fraisse games of length $\omega_1$. One implication of such a result will be that a certain infinite quantifier language cannot say that a linear ordering has no descending $\omega_1$-sequences (when the alphabet contains only one binary relation symbol). Connected work is done by Hyttinen and Oikkonen in [H] and [O].
Publié le : 1990-03-14
Classification: 
@article{1183743185,
     author = {Oikkonen, Juha},
     title = {On Ehrenfeucht-Fraisse Equivalence of Linear Orderings},
     journal = {J. Symbolic Logic},
     volume = {55},
     number = {1},
     year = {1990},
     pages = { 65-73},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743185}
}
Oikkonen, Juha. On Ehrenfeucht-Fraisse Equivalence of Linear Orderings. J. Symbolic Logic, Tome 55 (1990) no. 1, pp.  65-73. http://gdmltest.u-ga.fr/item/1183743185/