We prove that the class of trees with no branches of cardinality ≥κ is not RPC definable in L ∞κ when κ is regular. Earlier such a result was known for L κ + κ under the assumption $\kappa^{ . Our main result is actually proved in a stronger form which covers also L ∞λ (and makes sense there) for every strong limit cardinal $\lambda > \kappa$ of cofinality κ.

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. (shrink)

Oikkonen, J. and J. Väänänen, Game-theoretic inductive definability, Annals of Pure and Applied Logic 65 265-306. We use game-theoretic ideas to define a generalization of the notion of inductive definability. This approach allows induction along non-well-founded trees. Our definition depends on an underlying partial ordering of the objects. In this ordering every countable ascending sequence is assumed to have a unique supremum which enables us to go over limits. We establish basic properties of this induction and examine examples where it (...) emerges naturally. In the main results we prove an abstract Kleene Theorem and restricted versions of the Stage-Comparison Theorem and the Reduction Theorem. (shrink)

C. Karp has shown that if α is an ordinal with ω α = α and A is a linear ordering with a smallest element, then α and $\alpha \bigotimes A$ are equivalent in L ∞ω up to quantifer rank α. This result can be expressed in terms of Ehrenfeucht-Fraïssé games where player ∀ has to make additional moves by choosing elements of a descending sequence in α. Our aim in this paper is to prove a similar result for Ehrenfeucht-Fraïssé (...) games of length ω 1 . One implication of such a result will be that a certain infinite quantifier language cannot say that a linear ordering has no descending ω 1 -sequences (when the alphabet contains only one binary relation symbol). Connected work is done by Hyttinen and Oikkonen in [H] and [O]. (shrink)

We prove that the class of trees with no branches of cardinality $\geq\kappa$ is not RPC definable in $L_{\infty\kappa}$ when $\kappa$ is regular. Earlier such a result was known for $L_{\kappa^+\kappa}$ under the assumption $\kappa^{<\kappa} = \kappa$. Our main result is actually proved in a stronger form which covers also $L_{\infty\lambda}$ (and makes sense there) for every strong limit cardinal $\lambda > \kappa$ of cofinality $\kappa$.

We discuss an abstract notion of a logical operation and corresponding logics. It is shown that if all the logical operations considered are implicitely definable in a logic *, then the same holds also for the logic obtained from these operations. As an application we show that certain iterated forms of infinitely deep languages are implicitely definable in game quantifier languages. We consider also relations between structures and show that Karttunen's characterization of elementary equivalence for the ordinary infinitely deep languages (...) can be generalized to hold for the iterated infinitely deep languages. An early version of this work was presented in the Abstracts Section of ICM '78. (shrink)