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)

The Forrest-Armstrong argument, as reconfigured by David Lewis, is a reductio against an unrestricted principle of recombination. There is a gap in the argument which Lewis thought could be bridged by an appeal to recombination. After presenting the argument, I show that no plausible principle of recombination can bridge the gap. But other plausible principles of plenitude can bridge the gap, both principles of plenitude for world contents and principles of plenitude for world structures. I conclude that the Forrest-Armstrong argument, (...) when fortified in one of these ways, demands that unrestricted recombination be rejected. The appropriate restriction comes from a consideration of what world structures are possible. I argue that, although there are too many worlds to form a set, for any world, the individuals at that world do form a set. To defend it I invoke a principle of Limitation of Size together with an iterative conception of structure. (shrink)

Causal set theory and the theory of linear structures (which has recently been developed by Tim Maudlin as an alternative to standard topology) share some of their main motivations. In view of that, I raise and answer the question how these two theories are related to each other and to standard topology. I show that causal set theory can be embedded into Maudlin’s more general framework and I characterise what Maudlin’s topological concepts boil down to when applied to discrete linear (...) structures that correspond to causal sets. Moreover, I show that all topological aspects of causal sets that can be described in Maudlin’s theory can also be described in the framework of standard topology. Finally, I discuss why these results are relevant for evaluating Maudlin’s theory. The value of this theory depends crucially on whether it is true that (a) its conceptual framework is as expressive as that of standard topology when it comes to describing well-known continuous as well as discrete models of spacetime and (b) it is even more expressive or fruitful when it comes to analysing topological aspects of discrete structures that are intended as models of spacetime. On the one hand, my theorems support (a): the theory is rich enough to incorporate causal set theory and its definitions of topological notions yield a plausible outcome in the case of causal sets. On the other hand, the results undermine (b): standard topology, too, has the conceptual resources to capture those topological aspects of causal sets that are analysable within Maudlin’s framework. This fact poses a challenge for the proponents of Maudlin’s theory to prove it fruitful. (shrink)

A structure has a (finite-string)automatic presentationif the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

This paper develops the model theory of ordered structures that satisfy Keisler’s regularity scheme and its strengthening REF ${(\mathcal{L})}$ (the reflection scheme) which is an analogue of the reflection principle of Zermelo-Fraenkel set theory. Here ${\mathcal{L}}$ is a language with a distinguished linear order <, and REF ${(\mathcal {L})}$ consists of formulas of the form $$\exists x \forall y_{1} < x \ldots \forall y_{n} < x \varphi (y_{1},\ldots ,y_{n})\leftrightarrow \varphi^{ < x}(y_1, \ldots ,y_n),$$ where φ is an ${\mathcal{L}}$ -formula, φ (...) 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.

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)

First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is uncountable. Complete (...) axiomatizations for each of these cases are given. The r.e. prenex, negation-free, and existential fragments of all first-order Gödel logics are also characterized. (shrink)

The stability theory of first order theories was initiated by Saharon Shelah in 1969. The classification of abstract elementary classes was initiated by Shelah, too. In several papers, he introduced non-forking relations. Later, Shelah [17, II] introduced the good non-forking frame, an axiomatization of the non-forking notion.We improve results of Shelah on good non-forking frames, mainly by weakening the stability hypothesis in several important theorems, replacing it by the almost λ-stability hypothesis: The number of types over a model of cardinality (...) λ is at most λ+.We present conditions on Kλ, that imply the existence of a model in Kλ+n for all n. We do this by providing sufficiently strong conditions on Kλ, that they are inherited by a properly chosen subclass of Kλ+. What are these conditions? We assume that there is a ‘non-forking’ relation which satisfies the properties of the non-forking relation on superstable first order theories. Note that here we deal with models of a fixed cardinality, λ.While in Shelah [17, II] we assume stability in λ, so we can use brimmed models, here we assume almost stability only, but we add an assumption: The conjugation property.In the context of elementary classes, the superstability assumption gives the existence of types with well-defined dimension and the ω-stability assumption gives the existence and uniqueness of models prime over sets. In our context, the local character assumption is an analog to superstability and the density of the class of uniqueness triples with respect to the relation ≼bs is the analog to ω-stability. (shrink)

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.

Two linear orderings are equimorphic if each can be embedded into the other. We prove that every hyperarithmetic linear ordering is equimorphic to a recursive one. On the way to our main result we prove that a linear ordering has Hausdorff rank less than $\omega _{1}^{\mathit{CK}}$ if and only if it is equimorphic to a recursive one. As a corollary of our proof we prove that, given a recursive ordinal α, the partial ordering of equimorphism types of linear orderings of (...) Hausdorff rank at most α ordered by embeddablity is recursively presentable. (shrink)

We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, A is a countable structure with finite signature, and d is a degree, we say that A has αth-jump degree d if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of A with universe ω in (...) which the functions and relations have degree at most c. We show that every degree d ≥ 0 (ω) is the ωth jump degree of a Boolean algebra, but that for $n no Boolean algebra has nth-jump degree $\mathbf{d} > 0^{(n)}$ . The former result follows easily from work of L. Feiner. The proof of the latter result uses the forcing methods of J. Knight together with an analysis of various equivalences between Boolean algebras based on a study of their Stone spaces. A byproduct of the proof is a method for constructing Stone spaces with various prescribed properties. (shrink)

In the early eighties, answering a question of A. Macintyre, J. H. Schmerl ([13]) proved that every countable recursively saturated structure, equipped with a function β encoding the finite functions, is the β-closure of an infinite indiscernible sequence. This result implies that every countably saturated structure, in a countable but not necessarily recursive language, is an Ehrenfeucht-Mostowski model, by which we mean that the structure expands, in a countable language, to the Skolem hull of an infinite indiscernible sequence (in the (...) new language). More recently, D. Lascar ([5]) showed that the saturated model of cardinality ℵ 1 of an ω-stable theory is also an Ehrenfeucht-Mostowski model. These results naturally raise the following problem: which (countable) complete theories have an uncountably saturated Ehrenfeucht-Mostowski model. We study a generalization of this question. Namely, we call ACI-model a structure which can be expanded, in a countable language L', to the algebraic closure (in L') of an infinite indiscernible sequence (in L'). And we try to characterize the λ-saturated structures which are ACI-models. The main results are the following. First it is enough to restrict ourselves to ℵ 1 -saturated structures: if T has an ℵ 1 -saturated ACI-model then, for every infinite λ, T has a λ-saturated ACI-model. We obtain a complete answer in the case of stable theories: if T is stable then the three following properties are equivalent: (a) T is ω-stable, (b) T has a ℵ 1 saturated ACI-model, (c) every saturated model of T is an Ehrenfeucht-Mostowski model. The unstable case is more complicated, however we show that if T has an ℵ 1 -saturated ACI-model then T doesn't have the independence property. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis (...) ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that the theories without induction (...) tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

For any Boolean Algebra A, let cmm be the smallest size of an infinite partition of unity in A. The relationship of this function to the 21 common functions described in Monk [4] is described, for the class of all Boolean algebras, and also for its most important subclasses. This description involves three main results: the existence of a rigid tree algebra in which cmm exceeds any preassigned number, a rigid interval algebra with that property, and the construction of an (...) interval algebra in which every well-ordered chain has size less than cmm. (shrink)

This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...) systems of reverse mathematics. While retaining the usual base theory and working still within second order arithmetic, theorems are described that range from those far below the usual systems to ones far above. (shrink)

Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theory.

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a (...) Δ 0 2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting. (shrink)

We show that the separative quotient of the poset 〈P,⊂〉 of isomorphic suborders of a countable scattered linear order L is σ-closed and atomless. So, under the CH, all these posets are forcing-equivalent /Fin)+).

The notion of countable well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with Fraïssé’s conjecture, which has been proved by Laver. We also fill a small gap in Shore’s proof that Fraïssé’s conjecture implies arithmetic transfinite recursion over $\mathbf {RCA}_0$, by giving a new proof of $\Sigma ^0_2$ -induction.

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.

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.

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...) is still noncomputable.In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting. (shrink)

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that the theories without induction (...) tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

We introduce a notion of simplicity for types in discretely ordered first order structures. We prove that all the structure on the locus of a simple type is induced exclusively by the ordering relation. As an application we determine all possible expansions of satisfying CB = 1.

We say that a linear ordering is extendible if every partial ordering that does not embed can be extended to a linear ordering which does not embed either. Jullien’s theorem is a complete classification of the countable extendible linear orderings. Fraïssé’s conjecture, which is actually a theorem, is the statement that says that the class of countable linear ordering, quasiordered by the relation of embeddability, contains no infinite descending chain and no infinite antichain. In this paper we study the strength (...) of these two theorems from the viewpoint of Reverse Mathematics and Effective Mathematics. As a result of our analysis we get that they are equivalent over the basic system of .We also prove that Fraïssé’s conjecture is equivalent, over , to two other interesting statements. One that says that the class of well founded labeled trees, with labels from {+,−}, and with a very natural order relation, is well quasiordered. The other statement says that every linear ordering which does not contain a copy of the rationals is equimorphic to a finite sum of indecomposable linear orderings.While studying the proof theoretic strength of Jullien’s theorem, we prove the extendibility of many linear orderings, including ω2 and η, using just . Moreover, for all these linear orderings, , we prove that any partial ordering, , which does not embed has a linearization, hyperarithmetic in , which does not embed. (shrink)

We show a faithful restriction theorem among infinite chains which implies a reconstructibility conjecture of Halin. This incite us to study the reconstructibility in the sense of Fraïssé and to prove it for orders of cardinality infinite or ≥ 3 and for multirelations of cardinality infinite or ≥ 7, what improves the theory obtained by G. Lopez in the finite case. For this work we had to study the infinite classes of difference which have to be a linear order of (...) type ω, ω* or ω* + ω; this complete the theory made by G. Lopez for the finite case . We show also Ulam-reconstructibility for linear orders which have a fixed point. (shrink)

We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees.

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

We give a Hilbert style axiomatization for the set of formulas in the temporal language with Until and Since which are valid over the real number flow of time. The axiomatization, which is orthodox in the sense of only having the usual temporal rules of inference, is complete with respect to single formulas.

§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)

The lexicographic power ΔΓ of chains Δ and Γ is, roughly, the Cartesian power Πγ∈Γ Δ, totally ordered lexicographically from the left. Here the focus is on certain powers in which either Δ = R or Γ = R, with emphasis on when two such powers are isomorphic and on when ΔΓ is 2-homogeneous. The main results are: (1) For a countably infinite ordinal α, Rα* +α ≃ Rα. (2) RR ≄ RQ. (3) For Δ a countable ordinal ≥ 2. (...) ΔR, with its smallest element deleted, is 2-homogeneous. (shrink)