O-minimal structures have long been thought to occupy the base of a hierarchy of ordered structures, in analogy with the role that strongly minimal structures play with respect to stable theories. This is the first in an anticipated series of papers whose aim is the development of model theory for ordered structures of rank greater than one. A class of ordered structures to which a notion of finite rank can be assigned, the decomposable structures, is introduced here. These include all (...) ordered structures definable in o-minimal structures. The principal result in this paper, Theorem 5.1, asserts roughly that a decomposable structure [Formula: see text] can be partitioned into finitely many definable subsets such that on each set the restriction of < is a "twisted lexicographic" order. As a consequence, for all n and linear orders ≺ definable on a subset X ⊆ Mn in an o-minimal structure [Formula: see text], there is a definable partition of X such that the restriction of ≺ to each set in the partition is "lexicographic". (shrink)

LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized (...) byE. One can also define the following pre-order$ \le _{lo} $on the class of all c.e. equivalence relations:$E_1 \le _{lo} E_2 $if every linear order realized byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. (shrink)

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities U is recursively categorical if every recursive linear order with recursive successivities isomorphic to U is in fact recursively isomorphic to U . We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k 1 + g 1 + k 2 + g (...) 2 +…+ g n -1 + k n where each k n is a finite order type, non-empty for i ϵ{2,…, n -1} and each g i is an order type from among {ω,ω * ,ω+ω * }∪{ k ·η: k. (shrink)

When a linear order has an order preserving surjection onto each of its suborders, we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is a [Formula: see text]-complete set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders.

Let ⪯R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order . We show that ⪯R has fairly high complexity with respect to Borel reducibility , although its exact classification remains open.

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than with (...) defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. (shrink)

We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

Linguistic category learning has been shown to be highly sensitive to linear order, and depending on the task, differentially sensitive to the information provided by preceding category markers (premarkers, e.g., gendered articles) or succeeding category markers (postmarkers, e.g., gendered suffixes). Given that numerous systems for marking grammatical categories exist in natural languages, it follows that a better understanding of these findings can shed light on the factors underlying this diversity. In two discriminative learning simulations and an artificial language learning (...) experiment, we identify two factors that modulate linear order effects in linguistic category learning: category structure and the level of abstraction in a category hierarchy. Regarding category structure, we find that postmarking brings an advantage for learning category diagnostic stimulus dimensions, an effect not present when categories are non‐confusable. Regarding levels of abstraction, we find that premarking of super‐ordinate categories (e.g., noun class) facilitates learning of subordinate categories (e.g., nouns). We present detailed simulations using a plausible candidate mechanism for the observed effects, along with a comprehensive analysis of linear order effects within an expectation‐based account of learning. Our findings indicate that linguistic category learning is differentially guided by pre‐ and postmarking, and that the influence of each is modulated by the specific characteristics of a given category system. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...) that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power (...) of$\mathcal {L}$has order-type$\omega + \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$. (shrink)

This commentary discusses the division of labor between syntax and phonology, starting with the parallel model of grammar developed by Jackendoff. It is proposed that linear, left-to-right order of linguistic items is not represented in syntax, but in phonology. Syntax concerns the abstract relations of categories alone. All components of grammar contribute to linear order, by means of the interface rules.

We introduce the logics GLP Λ, a generalization of Japaridze’s polymodal provability logic GLP ω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP ω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLP Λ and the decidability of GLP Λ for recursive orderings Λ. Further, we give a restricted axiomatization of the variable-free fragment (...) of GLP Λ. (shrink)

We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP? Easily, if acl(A)= A for all A, then this is true. Otherwise, we give counterexamples. More precisely, there is a totally categorical theory for which every expansion by a linear order has IP. There is also an ω-stable NDOP theory for which every expansion by a linear order interprets pseudofinite arithmetic.

The decision problem for positively quantified formulae in the theory of linearly ordered Heyting algebras is known, as a special case of work of Kreisel, to be solvable; a simple solution is here presented, inspired by related ideas in Gödel-Dummett logic.

§1. Introduction. A linear ordering embedsinto another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to beequimorphicif they can be embedded in each other. This is an equivalence relation, and we call the equivalence classesequimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also (...) obtain results, as the definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.This study of linear orderings started by analyzing the proof-theoretic strength of a theorem due to Jullien [Jul69]. As is often the case in Reverse Mathematics, to solve this problem it was necessary to develop a deeper understanding of the objects involved. This led to a variety of results on the structure of linear orderings and the embeddability relation on them. These results can be divided into three groups. (shrink)

A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this property (...) until now. We also prove that, over RCA0, INDEC is implied by [Formula: see text] and implies ACA0, but of course, neither ACA0, nor ACA 0+ imply it. We introduce five other statements of hyperarithmetic analysis and study the relations among them. Four of them are related to finitely-terminating games. The fifth one, related to iterations of the Turing jump, is strictly weaker than all the other statements that we study in this paper, as we prove using Steel's method of forcing with tagged trees. (shrink)

We re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a ▵ 0 2β + 1 linear ordering of type τ, then there is a recursive ordering of type ω β · τ.

Pursuing the proof-theoretic program of Friedman and Simpson, we begin the study of the metamathematics of countable linear orderings by proving two main results. Over the weak base system consisting of arithmetic comprehension, II 1 1 -CA0 is equivalent to Hausdorff's theorem concerning the canonical decomposition of countable linear orderings into a sum over a dense or singleton set of scattered linear orderings. Over the same base system, ATR0 is equivalent to a version of the Continuum Hypothesis (...) for linear orderings, which states that every countable linear ordering either has countably many or continuum many Dedekind cuts. (shrink)

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)

We study the first-order theories of some natural and important classes of coloured trees, including the four classes of trees whose paths have the order type respectively of the natural numbers, the integers, the rationals, and the reals. We develop a technique for approximating a tree as a suitably coloured linear order. We then present the first-order theories of certain classes of coloured linear orders and use them, along with the approximating technique, to establish complete axiomatisations of (...) the four classes of trees mentioned above. (shrink)

In this paper, we give a classification of ℵ0-categorical coloured linear orders, generalizing Rosenstein's characterization of ℵ0-categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and ℚn-combinations . We give a method using coding trees to describe all structures in our list.

Linguistic category learning has been shown to be highly sensitive to linear order, and depending on the task, differentially sensitive to the information provided by preceding category markers (premarkers, e.g., gendered articles) or succeeding category markers (postmarkers, e.g., gendered suffixes). Given that numerous systems for marking grammatical categories exist in natural languages, it follows that a better understanding of these findings can shed light on the factors underlying this diversity. In two discriminative learning simulations and an artificial language learning (...) experiment, we identify two factors that modulate linear order effects in linguistic category learning: category structure and the level of abstraction in a category hierarchy. Regarding category structure, we find that postmarking brings an advantage for learning category diagnostic stimulus dimensions, an effect not present when categories are non‐confusable. Regarding levels of abstraction, we find that premarking of super‐ordinate categories (e.g., noun class) facilitates learning of subordinate categories (e.g., nouns). We present detailed simulations using a plausible candidate mechanism for the observed effects, along with a comprehensive analysis of linear order effects within an expectation‐based account of learning. Our findings indicate that linguistic category learning is differentially guided by pre‐ and postmarking, and that the influence of each is modulated by the specific characteristics of a given category system. (shrink)

A linear order is -decidable if its universe is and the relations defined by formulas are uniformly computable. This means that there is a computable procedure which, when applied to a formula and a sequence of elements of the linear order, will determine whether or not is true in the structure. A linear order is decidable if the relations defined by all formulas are uniformly computable. These definitions suggest two questions. Are there, for each , -decidable (...) class='Hi'>linear orders that are not -decidable? Are there linear orders that are -decidable for all but not decidable? The former was answered in the positive by Moses in 1993. Here we answer the latter, also positively. (shrink)

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.

In this article we investigate the complexity of isomorphisms between scattered linear orders of constructive ranks. We give the general upper bound and prove that this bound is sharp. Also, we construct examples showing that the categoricity level of a given scattered linear order can be an arbitrary ordinal from 3 to the upper bound, except for the case when the ordinal is the successor of a limit ordinal. The existence question of the scattered linear (...) class='Hi'>orders whose categoricity level equals the successor of a limit ordinal is still open. (shrink)

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

It is well known that infinite minimal sets for continuous functions on the interval are Cantor sets; that is, compact zero dimensional metrizable sets without isolated points. On the other hand, it was proved in Alcaraz and Sanchis (Bifurcat Chaos 13:1665–1671, 2003) that infinite minimal sets for continuous functions on connected linearly ordered spaces enjoy the same properties as Cantor sets except that they can fail to be metrizable. However, no examples of such subsets have been known. In this note (...) we construct, in ZFC, ${2^{\mathfrak{c}}}$ non-metrizable infinite pairwise non-homeomorphic minimal sets on compact connected linearly ordered spaces. (shrink)

The complexity of aII 4 set of natural numbers is encoded into a linear order to show that the finite condensation of a recursive linear order can beII 2–II 1. A priority argument establishes the same result, and is extended to a complete classification of finite condensations iterated finitely many times.

An observer attempts to infer the unobserved ranking of two ideal objects, A and B, from observed rankings in which these objects are `accompanied' by `noise' components, C and D. In the first ranking, A is accompanied by C and B is accompanied by D, while in the second ranking, A is accompanied by D and B is accompanied by C. In both rankings, noisy-A is ranked above noisy-B. The observer infers that ideal-A is ranked above ideal-B. This commonly used (...) inference rule is formalized for the case in which A,B,C,D are sets. Let X be a finite set and let be a linear ordering on 2X. The following condition is imposed on . For every quadruple (A,B,C,D)∈Y, where Y is some domain in (2X)4, if and , then . The implications and interpretation of this condition for various domains Y are discussed. (shrink)

The block relation B(x,y) in a linear order is satisfied by elements that are finitely far apart; a block is an equivalence class under this relation. We show that every computable linear order with dense condensation-type (i.e., a dense collection of blocks) but no infinite, strongly η-like interval (i.e., with all blocks of size less than some fixed, finite k ) has a computable copy with the nonblock relation ¬ B(x,y) computably enumerable. This implies that every computable (...) class='Hi'>linear order has a computable copy with a computable nontrivial self-embedding and that the long-standing conjecture characterizing those computable linear orders every computable copy of which has a computable nontrivial self-embedding (as precisely those that contain an infinite, strongly η-like interval) holds for all linear orders with dense condensation-type. (shrink)

A wide family of many-valued logics—for instance, those based on the weak Kleene algebra—includes a non-classical truth-value that is ‘contaminating’ in the sense that whenever the value is assigned to a formula φ⁠, any complex formula in which φ appears is assigned that value as well. In such systems, the contaminating value enjoys a wide range of interpretations, suggesting scenarios in which more than one of these interpretations are called for. This calls for an evaluation of systems with multiple contaminating (...) values. In this paper, we consider the countably infinite family of multiple-conclusion consequence relations in which classical logic is enriched with one or more contaminating values whose behavior is determined by a linear ordering between them. We consider some motivations and applications for such systems and provide general characterizations for all consequence relations in this family. Finally, we provide sequent calculi for a pair of four-valued logics including two linearly ordered contaminating values before defining two-sided sequent calculi corresponding to each of the infinite family of many-valued logics studied in this paper. (shrink)

Three classes of decidable discrete linear orders with varying degrees of effectiveness are investigated. We consider how a classical order type may lie in relation to these three classes, and we characterize by their order types elements of these classes that have effective nontrivial self-embeddings.

The deductive relationships between six statements are examined in set theory without the axiom of choice. Each of these statements follows from the axiom of choice and involves linear orderings in some way.

We compute the model-theoretic Grothendieck ring, \\), of a dense linear order with or without end points, \\), as a structure of the signature \, and show that it is a quotient of the polynomial ring over \ generated by \\) by an ideal that encodes multiplicative relations of pairs of generators. This ring can be embedded in the polynomial ring over \ generated by \. As a corollary we obtain that a DLO satisfies the pigeon hole principle for (...) definable subsets and definable bijections between them—a property that is too strong for many structures. (shrink)

Pseudo-BCK-algebras are a non-commutative generalization of well-known BCK-algebras. The paper describes a situation when a linearly ordered pseudo-BCK-algebra is an ordinal sum of linearly ordered cone algebras. In addition, we present two identities giving such a possibility of the decomposition and axiomatize the residuation subreducts of representable pseudo-hoops and pseudo-BL-algebras.

We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and (...) lower bounds established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to$2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong$\eta $-representation with no computable copy that is the simplest possible example.

First we prove that the set of countable linear orders of the form I + I form a complete analytic set. As a consequence of this we improve a result of Humke and Laczkovich, who showed in [HL] that the set of functions of the form f ⚬ f form a true analytic set in C[0, 1]. We show that these functions form a complete analytic set, solving a problem mentioned on p. 215 of [K1] and on p. (...) 4 of [B]. (shrink)

A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order-types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order-type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of (...) order-types, each of which either has finitely many blocks, or has order-type n · η for some integer n. (shrink)

We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has (...) an optimal ${\Pi ^{\mathrm {c}}_{3}}$ or ${d\text {-}\Sigma ^{\mathrm {c}}_{3}}$ Scott sentence and give a characterization of those linear orders of rank $1$ with ${\Pi ^{\mathrm {c}}_{3}}$ optimal Scott sentences. At last we show that for all countable $\alpha $ the class of Hausdorff rank $\alpha $ linear orders is $\boldsymbol {\Sigma }_{2\alpha +2}$ complete and obtain analogous results for index sets of computable linear orders. (shrink)