Our purpose in this note is to study countable ℵ0-categorical structures whose theories are tree-decomposable in the sense of Baldwin and Shelah. The permutation group corresponding to such a structure can be decomposed in a canonical manner into simpler permutation groups in the same class. As an application of the analysis we show that these structures are finitely homogeneous.

It is shown that the first-order theory Th R (A) of a countable module over an arbitrary countable ring R is ℵ 0 -categorical if and only if $A \cong \bigoplus_{t finite, n ∈ ω, κ i ≤ ω. Furthermore, Th R (A) is ℵ 0 -categorical for all R-modules A if and only if R is finite and there exist only finitely many isomorphism classes of indecomposable R-modules.

0-categorical o-minimal structures were completely described by Pillay and Steinhorn 565–592), and are essentially built up from copies of the rationals as an ordered set by ‘cutting and copying’. Here we investigate the possible structures which an 0-categorical weakly o-minimal set may carry, and find that there are some rather more interesting examples. We show that even here the possibilities are limited. We subdivide our study into the following principal cases: the structure is 1-indiscernible, in which case all (...) possibilities are classified up to binary structure; the structure is 2-indiscernible, classified up to ternary structure; the structure is 3-indiscernible, in which case we show that it is k-indiscernible for every finite k. We also make some remarks about the possible structures of higher arities which an 0-categorical weakly o-minimal structure may carry. (shrink)

We continue exploring analogues of o-minimality and weak o-minimality for circularly ordered sets. The main result is a description of ℵ0-categorical 1-transitive non-primitive weakly circularly minimal structures of convexity rank 1 up to binarity.

THEOREM. The Jacobson radical of an ℵ 0 -categorical associative ring is nilpotent.

Orthogonality of all families of pairwise weakly orthogonal 1-types for ℵ0-categorical weakly o-minimal theories of finite convexity rank has been proved in 6. Here we prove orthogonality of all such families for binary 1-types in an arbitrary ℵ0-categorical weakly o-minimal theory and give an extended criterion for binarity of ℵ0-categorical weakly o-minimal theories . © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We give an axiomatic framework for the non-modular simple 0-categorical structures constructed by Hrushovski. This allows us to verify some of their properties in a uniform way, and to show that these properties are preserved by iterations of the construction.

This paper has three parts. First, we establish some of the basic model theoretic facts about, the Tsirelson space of Figiel and Johnson [20]. Second, using the results of the first part, we give some facts about general Banach spaces. Third, we study model‐theoretic dividing lines in some Banach spaces and their theories. In particular, we show: (1) has the non independence property (NIP); (2) every Banach space that is ℵ0‐categorical up to small perturbations embeds c0 or () almost (...) isometrically; consequently the (continuous) first‐order theory of does not characterize, up to almost isometric isomorphism. (shrink)

This paper is primarily concerned with ℵ 0 -categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ 0 -categoricity. Among the latter are the following. Corollary 3.3. For every countable ℵ 0 -categorical U there is a linear order of A such that $(\mathfrak{U}, is ℵ 0 -categorical. Corollary 6.7. Every ℵ 0 -categorical theory of a partially ordered set of finite width has (...) a decidable theory. Theorem 7.7. Every ℵ 0 -categorical theory of reticles has a decidable theory. There is a section dealing just with decidability of partially ordered sets, the main result of this section being. Theorem 8.2. If $(P, is a finite partially ordered set and K P is the class of partially ordered sets which do not embed $(P, , then Th(K P ) is decidable iff K P contains only reticles. (shrink)

It is possible to define a combinatorial closure on alternating bilinear maps with few relations similar to that in [2]. For the ℵ 0 - categorical case we show that this closure is part of the algebraic closure.

We address the classification of the possible finitely-additive probability measures on the Boolean algebra of definable subsets of M which are invariant under the natural action of $\operatorname{Aut}(M)$ . This pursuit requires a generalization of Shelah's forking formulas [8] to "essentially measure zero" sets and an application of Myer's "rank diagram" [5] of the Boolean algebra under consideration. The classification is completed for a large class of ℵ 0 -categorical structures without the independence property including those which are stable.

Every ℵ 0 -categorical partially ordered set of finite width has a finitely axiomatizable theory. Every ℵ 0 -categorical partially ordered set of finite weak width has a decidable theory. This last statement constitutes a major portion of the complete (with three exceptions) characterization of those finite partially ordered sets for which any ℵ 0 -categorical partially ordered set not embedding one of them has a decidable theory.

We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.

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 describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures (...) can possess arbitrarily complex automorphism orbits.As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability. (shrink)

The categorical dualities presented are: (first) for the category of bi-algebraic lattices that belong to the variety generated by the smallest non-modular lattice with complete (0,1)-lattice homomorphisms as morphisms, and (second) for the category of non-trivial (0,1)-lattices belonging to the same variety with (0,1)-lattice homomorphisms as morphisms. Although the two categories coincide on their finite objects, the presented dualities essentially differ mostly but not only by the fact that the duality for the second category uses topology. Using the presented (...) dualities and some known in the literature results we prove that the Q-lattice of any non-trivial variety of (0,1)-lattices is either a 2-element chain or is uncountable and non-distributive. (shrink)

Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).

Computable structures of Scott rank ${\omega_1^{CK}}$ are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of ${\mathcal{L}_{\omega_1 \omega}}$ , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank ${\omega_1^{CK}}$ whose computable infinitary theories are each ${\aleph_0}$ -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank ${\omega_1^{CK}}$ , which guarantee that (...) the resulting structure is a model of an ${\aleph_0}$ -categorical computable infinitary theory. (shrink)

Let be an abstract elementary class with amalgamation, and Lowenheim Skolem number LS. We prove that for a suitable Hanf number gc0 if χ0 < λ0 λ1, and is categorical inλ1+ then it is categorical in λ0.

We prove a categoricity transfer theorem for tame abstract elementary classes. Theorem 0.1. Suppose that K is a χ-tame abstract elementary class and satisfies the amalgamation and joint embedding properties and has arbitrarily large models. Let λ ≥ Max{χ.LS(K)⁺}. If K is categorical in λ and λ⁺, then K is categorical in λ⁺⁺. Combining this theorem with some results from [37], we derive a form of Shelah's Categoricity Conjecture for tame abstract elementary classes: Corollary 0.2. Suppose K is (...) a χ-tame abstract elementary class satisfying the amalgamation and joint embedding properties. Let μ₀:= Hanf(K). If χ ≤ ‮ב‬(2μ0)+ and K is categorical in some λ⁺ > ‮ב‬(2μ0)+, then K is categorical in μ for all μ > ‮ב‬(2μ0)+. (shrink)

We generalise the correspondence between $\aleph _0$ -categorical theories and their automorphism groups to arbitrary complete theories in classical logic, and to some theories in continuous logic.

Using the category of metric spaces as a template, we develop a metric analogue of the categorical semantics of classical/intuitionistic logic, and show that the natural notion of predicate in this “continuous semantics” is equivalent to the a priori separate notion of predicate in continuous logic, a logic which is independently well-studied by model theorists and which finds various applications. We show this equivalence by exhibiting the real interval $[0,1]$ in the category of metric spaces as a “continuous subobject (...) classifier” giving a correspondence not only between the two notions of predicate, but also between the natural notion of quantification in the continuous semantics and the existing notion of quantification in continuous logic.Along the way, we formulate what it means for a given category to behave like the category of metric spaces, and afterwards show that any such category supports the aforementioned continuous semantics. As an application, we show that categories of presheaves of metric spaces are examples of such, and in fact even possess continuous subobject classifiers. (shrink)

We give a new proof of the classification of $\aleph_0$-categorical quasivarieties by using Morita equivalence to reduce to term minimal quasivarieties.

We continue our study of finitary abstract elementary classes, defined in [7]. In this paper, we prove a categoricity transfer theorem for a case of simple finitary AECs. We introduce the concepts of weak κ-categoricity and f-primary models to the framework of א₀-stable simple finitary AECs with the extension property, whereby we gain the following theorem: Let (������, ≼ ������ ) be a simple finitary AEC, weakly categorical in some uncountable κ. Then (������, ≼ ������ ) is weakly (...) class='Hi'>categorical in each λ ≥ min { \group{ \{\kappa,\beth_{ \group{ (2^{ \aleph_{ 0 _} ^});^{ + ^} \group} _}\}; \group} . If the class (������, ≼ ������ ) is also LS(������)-tame, weak κ-categoricity is equivalent with κ-categoricity in the usual sense. We also discuss the relation between finitary AECs and some other non-elementary frameworks and give several examples. (shrink)

We introduce a new approach to the model theory of metric structures by defining the notion of a metric abstract elementary class (MAEC) closely resembling the notion of an abstract elementary class. Further we define the framework of a homogeneous MAEC were we additionally assume the existence of arbitrarily large models, joint embedding, amalgamation, homogeneity and a property which we call the perturbation property. We also assume that the Löwenheim-Skolem number, which in this setting refers to the density character of (...) the set instead of the cardinality, is ${\aleph_0}$ . In these settings we prove an analogue of Morley’s categoricity transfer theorem. We also give concrete examples of homogeneous MAECs. (shrink)

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d' = θ", but that not all such fields are 0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...) of categoricity is $\Pi_{1}^{1}$-complete. (shrink)

We investigate the reverse-mathematical status of several theorems to the effect that the natural number system is second-order categorical. One of our results is as follows. Define a system to be a triple A,i,f such that A is a set and i∈A and f:A→A. A subset X⊆A is said to be inductive if i∈X and ∀a ∈X). The system A,i,f is said to be inductive if the only inductive subset of A is A itself. Define a Peano system to (...) be an inductive system such that f is one-to-one and i∉the range of f. The standard example of a Peano system is N,0,S where N={0,1,2,…,n,…}=the set of natural numbers and S:N→N is given by S=n+1 for all n∈N. Consider the statement that all Peano systems are isomorphic to N,0,S. We prove that this statement is logically equivalent to WKL0 over RCA0⁎ source. From this and similar equivalences we draw some foundational/philosophical consequences. (shrink)

We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...) of computing an isomorphism between the given structure and another copy${\cal B}$in the cone is a c.e. degree in${\rm{\Delta }}_\alpha ^0\left$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions. (shrink)

A coherence-based probability semantics for categorical syllogisms of Figure I, which have transitive structures, has been proposed recently (Gilio, Pfeifer, & Sanfilippo [15]). We extend this work by studying Figure II under coherence. Camestres is an example of a Figure II syllogism: from Every P is M and No S is M infer No S is P. We interpret these sentences by suitable conditional probability assessments. Since the probabilistic inference of ~????|???? from the premise set {????|????, ~????|????} is not (...) informative, we add ????(????|(????∨????))>0 as a probabilistic constraint (i.e., an “existential import assumption”) to obtain probabilistic informativeness. We show how to propagate the assigned (precise or interval-valued) probabilities to the sequence of conditional events (????|????,~????|????,????|(????∨????)) to the conclusion ~????|???? . Thereby, we give a probabilistic meaning to the other syllogisms of Figure II. Moreover, our semantics also allows for generalizing the traditional syllogisms to new ones involving generalized quantifiers (like Most S are P) and syllogisms in terms of defaults and negated defaults. (shrink)

Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.

Shelah has shown that $\aleph_1$-categoricity for Abstract Elementary Classes (AECs) is not absolute in the following sense: There is an example $K$ of an AEC (which is actually axiomatizable in the logic $L(Q)$) such that if $2^{\aleph_0}.