For countable structures U and B, let $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ abbreviate the statement that every Σ0 α (Lω1,ω) sentence true in U also holds in B. One can define a back and forth game between the structures U and B that determines whether $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω Σ0 n sentence, then there are countably infinite models U and B such that $\mathfrak{U} \vDash \theta, \mathfrak{B} \vDash (...) \neg \theta$ , and $\mathfrak{U}\overset{n}{\rightarrow}\mathfrak{B}$ . For countable languages L there is a natural way to view L structures with universe ω as a topological space, XL. Let [U] = {B ∈ XL∣B ≅ U} denote the isomorphism class of U. Let U and B be countably infinite nonisomorphic L structures, and let $C \subseteq \omega^\omega$ be any Π0 α subset. Our main result states that if $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ , then there is a continuous function f: ωω → XL with the property that $x \in C \Rightarrow f(x) \in \lbrack\mathfrak{U}\rbrack$ and $x \notin C \Rightarrow f(x) \in \lbrack\mathfrak{B}\rbrack$ . In fact, for α ≤ 3, the continuous function f can be defined from the $\overset{\alpha}{\rightarrow}$ relation. (shrink)

Let L be a finite relational language. The age of a structure M over L is the set of isomorphism types of finite substructures of M. We classify those ages U for which there are less than 2ω countably infinite pairwise nonisomorphic L-structures of age U.

Strengthening a theorem of D.W. Kueker, this paper completely characterizes which countable structures do not admit uncountable L ω 1 ω -elementarily equivalent models. In particular, it is shown that if the automorphism group of a countable structure M is abelian, or even just solvable, then there is no uncountable model of the Scott sentence of M. These results arise as part of a study of Polish groups with compatible left-invariant complete metrics.

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short (...) and simple proofs where possible, followed by a survey of recent advances. (shrink)

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This (...) led to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

We study the complexity of the classification problem of conjugacy on dynamical systems on some compact metrizable spaces. Especially we prove that the conjugacy equivalence relation of interval dynamical systems is Borel bireducible to isomorphism equivalence relation of countable graphs. This solves a special case of Hjorth’s conjecture which states that every orbit equivalence relation induced by a continuous action of the group of all homeomorphisms of the closed unit interval is classifiable by countable structures. We also (...) prove that conjugacy equivalence relation of Hilbert cube homeomorphisms is Borel bireducible to the universal orbit equivalence relation. (shrink)

A model of idealized scientific inquiry is presented in which scientists are required to infer the nature of the structure that makes true the data they examine. A necessary and sufficient condition is presented for scientific success within this paradigm.

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought (...) of as a (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

Let ???? be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of ???? in which the image of R (¬R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on ???? and R, a necessary and sufficient condition for the existence of a computable copy ℬ of ???? in which the image of R (¬R, resp.) (...) is simple (immune, resp.). (shrink)

It is shown that the relations of recursive isomorphism on countable trees, groups, Boolean algebras, fields and total orderings are universal countable Borel equivalence relations, thus providing a countable analogue of the Borel completeness of the isomorphism relations on these same classes. I.

We study the class of ω-categorical structures with n-degenerate algebraic closure for some n ε ω, which includes ω-categorical structures with distributive lattice of algebraically closed subsets , and in particular those with degenerate algebraic closure. We focus on the models of ω-categorical universal theories, absolutely ubiquitous structures, and ω-categorical structures generated by an indiscernible set. The assumption of n-degeneracy implies total categoricity for the first class, stability for the second, and ω-stability for the third.

Countable homogeneous relational structures have been studied by many people. One area of focus is the Ramsey theory of such structures. After a review of background material, a partition theorem of Laflamme, Sauer, and Vuksanovic for countable homogeneous binary relational structures is discussed with a focus on the size of the set of unavoidable colors.

An important application of ultrafilters is in the ultraproduct construction in model theory. In this paper we study ultraproducts of countable structures, whose universe we assume is ω , using ultrafilters on a countable index set, which we also assume to be ω . Many of the properties of the ultraproduct are in fact inherent properties of the ultrafilter. For example, if we take a sequence of countable linear orders without maximal element, then their ultraproduct will (...) have no maximal element, and we can ask what its cofinality is. This cardinal depends only on the ultrafilter; it does not depend on what linear orders comprise the factors. (shrink)

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in (...) terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers. (shrink)

Every transformation monoid comes equipped with a canonical topology, the topology of pointwise convergence. For some structures, the topology of the endomorphism monoid can be reconstructed from its underlying abstract monoid. This phenomenon is called automatic homeomorphicity. In this paper we show that whenever the automorphism group of a countable saturated structure has automatic homeomorphicity and a trivial center, then the monoid of elementary self-embeddings has automatic homeomorphicity, too. As a second result we strengthen a result by Lascar (...) by showing that whenever \ is a countable \-categorical G-finite structure whose automorphism group has a trivial center and if \ is any other countable structure, then every isomorphism between the monoids of elementary self-embeddings is a homeomorphism. (shrink)

We consider the complexity of the isomorphism relation on countable first-order structures with transitive automorphism groups. We use the theory of Borel reducibility of equivalence relations to show that the isomorphism problem for vertex-transitive graphs is as complicated as the isomorphism problem for arbitrary graphs and determine for which first-order languages the isomorphism problem for transitive countable structures is as complicated as it is for arbitrary countable structures. We then use these results to characterize (...) the complexity of the isometry relation for certain classes of homogeneous and ultrahomogeneous metric spaces. (shrink)

This paper addresses the issue of finite versus countable additivity in Bayesian probability and decision theory -- in particular, Savage's theory of subjective expected utility and personal probability. I show that Savage's reason for not requiring countable additivity in his theory is inconclusive. The assessment leads to an analysis of various highly idealised assumptions commonly adopted in Bayesian theory, where I argue that a healthy dose of, what I call, conceptual realism is often helpful in understanding the interpretational (...) value of sophisticated mathematical structures employed in applied sciences like decision theory. In the last part, I introduce countable additivity into Savage's theory and explore some technical properties in relation to other axioms of the system. (shrink)

For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical example due to (...) Makkai, and codes it into a computable structure. The second re-works Makkai's construction, incorporating an idea of Sacks. (shrink)

The structure of ordinals of the form ωωβ for countable β is studied. The main result is:Theorem 1If β<ω1 is the sum of one or two indecomposable ordinals, thenωωβ→2. Also an example is given to show that α→2 need not imply α→2 for all n<ω.

The distinction between abstract and concrete concepts is fundamental to cognitive linguistics and cognitive science. This distinction is commonly operationalized through concreteness ratings based on the aggregated judgments of many people. What is often overlooked in experimental studies using this operationalization is that ratings are attributed to words, not to concepts directly. In this paper we explore the relationship between the linguistic properties of English words and conceptual abstractness/concreteness. Based on hypotheses stated in the existing linguistic literature we select a (...) set of variables and verify whether they are statistically associated with concreteness ratings. We show that English nouns are rated as more concrete compared to other parts of speech, but mass nouns are rated as less concrete than count nouns. Furthermore, a more complex morphological structure is associated with abstractness, and as for etymology, French- and Latin-derived words are more abstract than words of other origin. This shows that linguistic properties of words are indeed associated with the degree of concreteness that we attribute to the underlying concepts, and we discuss the implications that these findings have for linguistic theory and for empirical investigations in the cognitive sciences. (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.

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees (...) in these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π10 subsets of Cantor space, we also show that every nonzero finite-2-piecewise degree includes infinitely many Medvedev degrees, every nonzero countable-Δ20-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-2-countable-Δ20-piecewise degree includes infinitely many countable-Δ20-piecewise degrees, and every nonzero Muchnik degree includes infinitely many finite-2-countable-Δ20-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ20-piecewise degree of a nonempty Π10 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above. (shrink)

We continue the study of the theories of Baldwin–Shi hypergraphs from [5]. Restricting our attention to when the rank δ is rational valued, we show that each countable model of the theory of a given Baldwin–Shi hypergraph is isomorphic to a generic structure built from some suitable subclass of the original class used in the construction. We introduce a notion of dimension for a model and show that there is a an elementary chain $\left\{ {\mathfrak{M}_\beta :\beta \leqslant \omega } (...) \right\}$ of countable models of the theory of a fixed Baldwin–Shi hypergraph with $\mathfrak{M}_\beta \preccurlyeq \mathfrak{M}_\gamma $ if and only if the dimension of $\mathfrak{M}_\beta $ is at most the dimension of $\mathfrak{M}_\gamma $ and that each countable model is isomorphic to some $\mathfrak{M}_\beta $. We also study the regular types that appear in these theories and show that the dimension of a model is determined by a particular regular type. Further, drawing on a large body of work, we use these structures to give an example of a pseudofinite, ω-stable theory with a nonlocally modular regular type, answering a question of Pillay in [11]. (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)

Every Berman’s variety \ which is the subvariety of Ockham algebras defined by the equation \ and \) determines a finitary substitution invariant consequence relation \. A sequent system \ is introduced as an axiomatization of the consequence relation \. The system \ is characterized by a single finite frame \ under the frame semantics given for the formal language. By the duality between frames and algebras, \ can be viewed as a \-valued logic as it is characterized by a (...) distributive lattice of \ elements with a unary operator. Moreover, a structural-rule-free, cut-free and terminating sequent system \ is established for \. The Craig interpolation property of \ is shown proof-theoretically utilizing \. (shrink)

Let L be a countable language, let I be an isomorphism-type of countable L-structures, and let a∈2ω. We say that I is a-strange if it contains a computable-from-a structure and its Scott rank is exactly ω1a. For all a, a-strange structures exist. Theorem : If C is a collection of ℵ1 isomorphism-types of countable structures, then for a Turing cone of a’s, no member of C is a-strange.

The model theoretic `back and forth' construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ 0 -categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called `going forth') and to determine when it works and when it fails. Partial answers to this question are found, extending (...) those earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ 0 -categorical ω-stable structures. The work is based on the author's Ph.D. thesis. (shrink)

Let κ be an uncountable cardinal. Using the theory of conditional probability associated with de Finetti and Dubins, subject to several structural assumptions for creating sufficiently many measurable sets, and assuming that κ is not a weakly inaccessible cardinal, we show that each probability that is not κ-­additive has conditional probabilities that fail to be conglomerable in a partition of cardinality no greater than κ. This generalizes our result, where we established that each finite but not countably additive probability has (...) conditional probabilities that fail to be conglomerable in some countable partition. (shrink)

Reviewed Works:B. I. Zil'ber, L. Pacholski, J. Wierzejewski, A. J. Wilkie, Totally Categorical Theories: Structural Properties and the Non-Finite Axiomatizability.B. I. Zil'ber, Strongly Minimal Countably Categorical Theories.B. I. Zil'ber, Strongly Minimal Countably Categorical Theories. II.B. I. Zil'ber, Strongly Minimal Countably Categorical Theories. III.B. I. Zil'ber, E. Mendelson, Totally Categorical Structures and Combinatorial Geometries.B. I. Zil'ber, The Structure of Models of Uncountably Categorical Theories.

We compare two different notions of generic expansions of countable saturated structures. One kind of genericity is related to existential closure, and another is defined via topological properties and Baire category theory. The second type of genericity was first formulated by Truss for automorphisms. We work with a later generalization, due to Ivanov, to finite tuples of predicates and functions. Let $N$ be a countable saturated model of some complete theory $T$ , and let $(N,\sigma)$ denote an (...) expansion of $N$ to the signature $L_{0}$ which is a model of some universal theory $T_{0}$ . We prove that when all existentially closed models of $T_{0}$ have the same existential theory, $(N,\sigma)$ is Truss generic if and only if $(N,\sigma)$ is an e-atomic model. When $T$ is $\omega$ -categorical and $T_{0}$ has a model companion $T_{\mathrm {mc}}$ , the e-atomic models are simply the atomic models of $T_{\mathrm {mc}}$. (shrink)

Answering some of the main questions from [L. Motto Ros, The descriptive set-theoretical complexity of the embeddability relation on models of large size, Ann. Pure Appl. Logic164(12) (2013) 1454–1492], we show that whenever κ is a cardinal satisfying κ<κ=κ>ω, then the embeddability relation between κ-sized structures is strongly invariantly universal, and hence complete for (κ-)analytic quasi-orders. We also prove that in the above result we can further restrict our attention to various natural classes of structures, including (generalized) trees, (...) graphs, or groups. This fully generalizes to the uncountable case the main results of [A. Louveau and C. Rosendal, Complete analytic equivalence relations, Trans. Amer. Math. Soc.357(12) (2005) 4839–4866; S.-D. Friedman and L. Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symbolic Logic76(1) (2011) 243–266; J. Williams, Universal countable Borel quasi-orders, J. Symbolic Logic79(3) (2014) 928–954; F. Calderoni and L. Motto Ros, Universality of group embeddability, Proc. Amer. Math. Soc.146 (2018) 1765–1780]. (shrink)

We study the possible structures which can be carried by sets which have no countable subset, but which fail to be ‘surjectively Dedekind finite’, in two possible senses, that there is surjection to $\omega $, or alternatively, that there is a surjection to a proper superset.

We present three examples of countable homogeneous structures whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures.Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification, leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums, leading to a Fraïssé class with all (...) finite symmetric groups appearing as automorphism groups and at the same time with a torsion-free automorphism group of its Fraïssé limit. Our last example is a Fraïssé class of finite models with arbitrarily large finite abelian automorphism groups, such that the automorphism group of its Fraïssé limit is again torsion-free. (shrink)

We prove that each ∀1 free amalgamation class K over a finite relational language L admits a countable generic structure M isometrically embedding all countable structuresin K relative to a fixed metric. We expand L by infinitely many binary predicates expressingdistance, and prove that the resulting expansion of K has a model companion axiomatizedby the first-order theory of M. The model companion is non-finitely axiomatizable, evenover a strong form of the axiom scheme of infinity.

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.

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure (...) is categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Fraïssé’s theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets {0}, {1}, K, and L, which are the only orbits of the group of (...) base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non-trivial extensional BCA we know which has this property. (shrink)