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)

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)

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)

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)

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)

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

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)

Multidimensional concepts are everywhere, and they are important. Examples include moral value, welfare, scientific confirmation, democracy, and biodiversity. How, if at all, can we aggregate the underlying dimensions of a multidimensional concept F to yield verdicts about which things are Fer than which overall? Social choice theory can be used to model and investigate this aggregation problem. Here, we focus on a particularly thorny problem made salient by this social choice-theoretic framework: the underlying dimensions of a given concept might be (...) measurable on different types of scales—e.g., some ordinal and some cardinal. An underappreciated impossibility theorem due to Anna Khmelnitskaya shows that seemingly plausible constraints on aggregation across scale types are inconsistent. This impossibility threatens to render the notion of overall Fness incoherent. We attempt to defuse this threat, arguing that the impossibility depends on an overly restrictive conception of measurement and of how measurement constrains aggregation. Adopting a more flexible—and, we think, more perspicuous—conception of measurement opens an array of possibilities for aggregation across disparate scale types. (shrink)

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.

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)

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)

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.

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

Let $\mathcal M=$ be a linearly ordered first-order structure and T its complete theory. We investigate conditions for T that could guarantee that $\mathcal M$ is not much more complex than some colored orders. Motivated by Rubin’s work [5], we label three conditions expressing properties of types of T and/or automorphisms of models of T. We prove several results which indicate the “geometric” simplicity of definable sets in models of theories satisfying these conditions. For example, we prove that the strongest (...) condition characterizes, up to definitional equivalence, theories of colored orders expanded by equivalence relations with convex classes. (shrink)

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

The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique countably saturated linear order of cardinality \. We provide some examples of pairwise non-isomorphic countably saturated linear orders of cardinality \, under different set-theoretic assumptions. We give a new proof of the old theorem of Harzheim, that the class of countably saturated linear orders has a uniquely determined one-element basis. From (...) our proof it follows that this minimal linear order is a Fraïssé limit of certain Fraïssé class. In particular, it is homogeneous with respect to countable subsets. Next we prove the existence and uniqueness of the uncountable version of the random graph. This graph is isomorphic to \,\in \cup \ni )\), where \\) is the set of hereditarily countable sets, and two sets are connected if one of them is an element of the other. In the last section, an example of a prime countably saturated Boolean algebra is presented. (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)

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.

Suppose A is a linear order, possibly with countably many unary predicates added. We classify the isomorphism relation for countable models of Th\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {Th}$$\end{document} up to Borel bi-reducibility, showing there are exactly five possibilities and characterizing exactly when each can occur in simple model-theoretic terms. We show that if the language is finite, then the theory is ℵ0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\aleph _0$$\end{document}-categorical or Borel complete; this (...) generalizes a theorem due to Schirmann. (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 structureexpands, 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 ℵ1of 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 languageL′, to the algebraic closure (inL′) of an infinite indiscernible sequence (inL′). 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 an ℵ1-saturated ACI-model, (c)every saturated model of T is an Ehrenfeucht-Mostowski model. The unstable case is more complicated, however we show thatif T has an ℵ1-saturated ACI-model then T doesn't have the independence property. (shrink)

We give a valuation theoretic characterization for a real closed field to be recursively saturated. This builds on work in [9], where the authors gave such a characterization forκ-saturation, for a cardinal$\kappa \ge \aleph _0 $. Our result extends the characterization of Harnik and Ressayre [7] for a divisible ordered abelian group to be recursively saturated.

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 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.

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.

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)+).

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)

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.