A recent article of Chernikov, Hrushovski, Kruckman, Krupinski, Moconja, Pillay, and Ramsey finds the first examples of simple structures with formulas which do not fork over the empty set but are universally measure zero. In this article we give the first known simple $\omega $ -categorical counterexamples. These happen to be various $\omega $ -categorical Hrushovski constructions. Using a probabilistic independence theorem from Jahel and Tsankov, we show how simple $\omega $ -categorical (...) class='Hi'>structures where a formula forks over $\emptyset $ if and only if it is universally measure zero must satisfy a stronger version of the independence theorem. (shrink)

The endomorphism monoid of a model-theoretic structure carries two interesting topologies: on the one hand, the topology of pointwise convergence induced externally by the action of the endomorphisms on the domain via evaluation; on the other hand, the Zariski topology induced within the monoid by (non-)solutions to equations. For all concrete endomorphism monoids of $\omega $ -categorical structures on which the Zariski topology has been analysed thus far, the two topologies were shown to coincide, in turn yielding (...) that the pointwise topology is the coarsest Hausdorff semigroup topology on those endomorphism monoids. We establish two systematic reasons for the two topologies to agree, formulated in terms of the model-complete core of the structure. Further, we give an example of an $\omega $ -categorical structure on whose endomorphism monoid the topology of pointwise convergence and the Zariski topology differ, answering a question of Elliott, Jonušas, Mitchell, Péresse, and Pinsker. (shrink)

The age of a structure M is the set of all isomorphism types of finite substructures of M. We study ages of generic expansions of ω-stable ω-categorical structures.

We study $$\omega $$ ω -categorical MS-measurable structures. Our main result is that a certain class of $$\omega $$ ω -categorical Hrushovski constructions, supersimple of finite SU-rank is not MS-measurable. These results complement the work of Evans on a conjecture of Macpherson and Elwes. In constrast to Evans’ work, our structures may satisfy independent n-amalgamation for all n. We also prove some general results in the context of $$\omega $$ ω -categorical MS-measurable (...) structures. Firstly, in these structures, the dimension in the MS-dimension-measure can be chosen to be SU-rank. Secondly, non-forking independence implies a form of probabilistic independence in the measure. The latter follows from more general unpublished results of Hrushovski, but we provide a self-contained proof. (shrink)

A first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $ -categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, (...) and finite index first-order reducts. Using our classification we show that every structure in $\mathcal {M}$ is first-order interdefinable with a finitely bounded homogeneous structure. We also prove that every structure in $\mathcal {M}$ has finitely many reducts up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathcal {M}$. (shrink)

We prove that if an $\omega $ -categorical structure has an $\omega $ -categorical homogeneous Ramsey expansion, then so does its model-complete core.

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)

It is known that a countable $\omega $ -categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.

We explore the interplay between $\omega $ -categoricity and pseudofiniteness for groups, and we conjecture that $\omega $ -categorical pseudofinite groups are finite-by-abelian-by-finite. We show that the conjecture reduces to nilpotent p-groups of class 2, and give a proof that several of the known examples of $\omega $ -categorical p-groups satisfy the conjecture. In particular, we show by a direct counting argument that for any odd prime p the ( $\omega $ -categorical) model (...) companion of the theory of nilpotent class 2 exponent p groups, constructed by Saracino and Wood, is not pseudofinite, and that an $\omega $ -categorical group constructed by Baudisch with supersimple rank 1 theory is not pseudofinite. We also survey some scattered literature on $\omega $ -categorical groups over 50 years. (shrink)

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.

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)

In the present paper we shall prove that countable ω-categorical simple CM-trivial theories and countable ω-categorical simple theories with strong stable forking are low. In addition, we observe that simple theories of bounded finite weight are low.

Within the context of an involutive monoidal category the notion of a comparison relation ${\mathsf{cp} : \overline{X} \otimes X \rightarrow \Omega}$ is identified. Instances are equality = on sets, inequality ${\leq}$ on posets, orthogonality ${\perp}$ on orthomodular lattices, non-empty intersection on powersets, and inner product ${\langle {-}|{-} \rangle}$ on vector or Hilbert spaces. Associated with a collection of such (symmetric) comparison relations a dagger category is defined with “tame” relations as morphisms. Examples include familiar categories in the foundations of (...) quantum mechanics, such as sets with partial injections, or with locally bifinite relations, or with formal distributions between them, or Hilbert spaces with bounded (continuous) linear maps. Of one particular example of such a dagger category of tame relations, involving sets and bifinite multirelations between them, the categorical structure is investigated in some detail. It turns out to involve symmetric monoidal dagger structure, with biproducts, and dagger kernels. This category may form an appropriate universe for discrete quantum computations, just like Hilbert spaces form a universe for continuous computation. (shrink)

LetMbe a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by definingd(g, h) = Ω{2−n:g(xn) ≠h(xn) org−1(xn) ≠h−1(xn)} where {xn:n∈ ω} is an enumeration ofMAn automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In (...) the present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms ofMwhich can be considered as an atomic model of some theory naturally associated toM. We do it in a general context of weak models for second-order quantifiers.The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks. (shrink)

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

If categorical equivalence is a good criterion of theoretical equivalence, then it would seem that if some class of mathematical structures is represented as a category, then any other class of structures categorically equivalent to it will have the same representational capacities. Hudetz (2019a) has presented an apparent counterexample to this claim; in this note, I argue that the counterexample fails.

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

It is shown that no infinite group is interpretable in any structure which is homogeneous in a finite relational language. Related questions are discussed for other ω-categorical structures.

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the natural uniformity (...) on it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (shrink)

Using new techniques for controlling the categoricity spectrum of a structure, we construct a structure with degree of categoricity but infinite spectral dimension, answering a question of Bazhenov, Kalimullin and Yamaleev. Using the same techniques, we construct a computably categorical structure of non-computable Scott rank.

We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable (...) equivalence structures are relatively categorical, we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures. (shrink)

A Dedekind Algebra is an ordered pair (B,h) where B is a non-empty set and h is an injective unary function on B. Each Dedekind algebra can be decomposed into a family of disjoint, countable subalgebras called configurations of the Dedekind algebra. There are N0 isomorphism types of configurations. Each Dedekind algebra is associated with a cardinal-valued function on omega called its configuration signature. The configuration signature of a Dedekind algebra counts the number of configurations in the decomposition of (...) the algebra in each isomorphism type.The configuration signature of a Dedekind algebra encodes the structure of that algebra in the sense that two Dedekind algebras are isomorphic iff their configuration signatures are identical. Configuration signatures are used to establish various results in the first-order model theory of Dedekind algebras. These include categoricity results for the first-order theories of Dedekind algebras and existence and uniqueness results for homogeneous, universal and saturated Dedekind algebras. Fundamental to these results is a condition on configuration signatures that is necessary and sufficient for elementary equivalence. (shrink)

For a computable structure $\mathcal {M}$, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of $\mathcal {M}$. If the spectrum has a least degree, this degree is called the degree of categoricity of $\mathcal {M}$. In this paper we investigate spectra of categoricity for computable rigid structures. In particular, we give examples of rigid structures without degrees of categoricity.

Journal of Mathematical Logic, Ahead of Print.

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

Let D be a strongly minimal set in the language L, and $D' \supset D$ an elementary extension with infinite dimension over D. Add to L a unary predicate symbol D and let T' be the theory of the structure (D', D), where D interprets the predicate D. It is known that T' is ω-stable. We prove Theorem A. If D is not locally modular, then T' has Morley rank ω. We say that a strongly minimal set D is pseudoprojective (...) if it is nontrivial and there is a $k < \omega$ such that, for all a, b ∈ D and closed $X \subset D, a \in \mathrm{cl}(Xb) \Rightarrow$ there is a $Y \subset X$ with a ∈ cl(Yb) and |Y| ≤ k. Using Theorem A, we prove Theorem B. If a strongly minimal set D is pseudoprojective, then D is locally projective. The following result of Hrushovski's (proved in $\S4$ ) plays a part in the proof of Theorem B. Theorem C. Suppose that D is strongly minimal, and there is some proper elementary extension D1 of D such that the theory of the pair (D1, D) is ω1-categorical. Then D is locally modular. (shrink)

Review by: Alexander G. Melnikov The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 400-401, September 2013.

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.

This article surveys recent literature by Parsons, McGee, Shapiro and others on the significance of categoricity arguments in the philosophy of mathematics. After discussing whether categoricity arguments are sufficient to secure reference to mathematical structures up to isomorphism, we assess what exactly is achieved by recent ‘internal’ renditions of the famous categoricity arguments for arithmetic and set theory.

A precise notion of ‘mathematical structure’ other than that given by model theory may prove fruitful in the philosophy of mathematics. It is shown how the language and methods of category theory provide such a notion, having developed out of a structural approach in modern mathematical practice. As an example, it is then shown how the categorical notion of a topos provides a characterization of ‘logical structure’, and an alternative to the Pregean approach to logic which is continuous with (...) the modern structural approach in mathematics. (shrink)