Recent zbMATH articles in MSC 03C https://www.zbmath.org/atom/cc/03C 2021-03-30T15:24:00+00:00 Werkzeug Universally and existentially definable subsets of global fields. https://www.zbmath.org/1455.11167 2021-03-30T15:24:00+00:00 "Eisenträger, Kirsten" https://www.zbmath.org/authors/?q=ai:eisentrager.kirsten "Morrison, Travis" https://www.zbmath.org/authors/?q=ai:morrison.travis This paper belongs to the area studying definability and decidability in Number Theory. One can arguably call the solution to Hilbert's Tenth Problem by Matiyasevich, building on results of Davis, Putnam and J. Robinson the event that brought the area into being. The solution left open the question whether there was an algorithm for solving diophantine equations over $$\mathbb Q$$, and whether there was an existential definition of $$\mathbb Z$$ over $$\mathbb Q$$ that would imply absence of such an algorithm. Some conjectures by B. Mazur imply that a definition does not exist. At the same time a definition of $$\mathbb Z$$ over $$\mathbb Q$$ using both existential and universal quantifiers due to J. Robinson has been known for a long time. More recently, Robinson's definition was simplified in various ways. Poonen produced a first-order definition of algebraic integers over number fields using only two universal quantifiers in the definition. Koenigsmann produced a universal (i.e. using only universal quantifiers) definition of $$\mathbb Z$$ over $$\mathbb Q$$. He also constructed a definition of $$\mathbb Z$$ over $$\mathbb Q$$ using only one universal and several existential quantifiers. J. Park generalized the universal definition to number fields, that is she constructed a universal definition of the ring of algebraic integers of a number field $$K$$ over $$K$$ for all number fields $$K$$. The question posed by Hilbert and related problems of definability make sense over many other rings, such as a global function fields. We know that Hilbert's Tenth problem to be undecidable over all global function fields. R. Rumely constructed the first version of first-order definitions of polynomial rings and rings of $$S$$-integers over global function field. A. Shlapentokh produced an analog of Koenigsmann's one universal quantifier definition for global function fields. The paper under review constructs the analog of the universal definitions of Koenigsmann and Park over these function fields. It also contains other interesting definability results known over number fields. The authors give a Diophantine (existential) definition of non-squares and non-norms. Many tools used by Park and Koenigsmann to construct their definitions transfer to the global function field setting, but not all. This leads to several technical difficulties successfully handled by the authors. For a student in the area reading side by side the Park paper and the paper under review would make for a very nice introduction to many technical aspects of definability. Reviewer: Alexandra Shlapentokh (Greenville) Stable forking and imaginaries. https://www.zbmath.org/1455.03041 2021-03-30T15:24:00+00:00 "Casanovas, Enrique" https://www.zbmath.org/authors/?q=ai:casanovas.enrique "Potier, Joris" https://www.zbmath.org/authors/?q=ai:potier.joris Summary: We prove that a theory $$T$$ has stable forking if and only if $$T^{\mathrm{eq}}$$ has stable forking. Syllogistic logic with cardinality comparisons, on infinite sets. https://www.zbmath.org/1455.03039 2021-03-30T15:24:00+00:00 "Moss, Lawrence S." https://www.zbmath.org/authors/?q=ai:moss.lawrence-s "Topal, Selçuk" https://www.zbmath.org/authors/?q=ai:topal.selcuk This paper presents a study of what the author calls extended syllogistic logics''. These logics deal with expressions of the form $$\forall (p, q)$$, $$\exists (p, q)$$, $$\exists^\geq (p, q)$$, and $$\exists^> (p, q)$$, which are to be read as All $$p$$ are $$q$$'', Some $$p$$ are $$q$$'', There are at least as many $$p$$ as $$q$$'', and There are more $$p$$ than $$q$$'' respectively. Variables $$p$$, $$q$$, etc. stand for nouns, which can also be complemented, so that $$\overline{p}$$, $$\overline{q}$$, etc. are also nouns. One defines an interpretation function $$[[{\, }]]$$ as a map from the set of nouns to the power set of a universe of discourse, interpreting thus nouns as subsets of the universe $$M$$. There is an additional property that for all $$p$$, $$[[\overline{p}]] = M\,\backslash\,[[p]]$$ for all nouns $$p$$. A satisfaction relation between models and expressions of the language is defined as follows: $$\mathcal{M}\models \forall (p, q)$$ iff $$[[p]] \subseteq [[q]]$$; $$\mathcal{M}\models \exists (p, q)$$ iff $$[[p]] \cap [[q]] \neq\emptyset$$; $$\mathcal{M}\models \exists^\geq (p, q)$$ iff $$\operatorname{card}[[p]] \geq \operatorname{card}[[q]]$$; $$\mathcal{M}\models \exists^> (p, q)$$ iff $$\operatorname{card}[[p]] > \operatorname{card}[[q]]$$, where $$\operatorname{card} S$$ stands for the cardinality of a given set $$S$$. Importantly, $$[[p]]$$ and $$[[q]]$$ could be empty or infinite, but not necessarily so. The consequence relation $$\Gamma \models\varphi$$ is defined as usual, saying that in any model $$\mathcal{M}$$, $$\mathcal{M} \models [[\varphi]]$$ whenever $$\mathcal{M} \models [[\Gamma]]$$. The author constructs a proof system which formalizes the semantic consequence relation so defined, and proves the soundness and completeness theorems for this system. Reviewer: Yaroslav Shramko (Kryvyi Rih) A first-order theory of Ulm type. https://www.zbmath.org/1455.03043 2021-03-30T15:24:00+00:00 "Harrison-Trainor, Matthew" https://www.zbmath.org/authors/?q=ai:harrison-trainor.matthew Author's abstract: The class of abelian $$p$$-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory $$T_p$$ whose models are each bi-interpretable with the disjoint union of an abelian $$p$$-group and a pure set (and so that every abelian $$p$$-group is bi-interpretable with a model of $$T_p$$) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of Ulm type'': Any two models, low for $$\omega_1^{CK}$$, and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is $$\mathbf{\Sigma}_1^1$$-complete but not Borel complete. Reviewer: Andrei S. Morozov (Novosibirsk) General non-commutative locally compact locally Hausdorff Stone duality. https://www.zbmath.org/1455.06005 2021-03-30T15:24:00+00:00 "Bice, Tristan" https://www.zbmath.org/authors/?q=ai:bice.tristan-matthew "Starling, Charles" https://www.zbmath.org/authors/?q=ai:starling.charles Classical Stone duality constructs a contravariant equivalence between the categories of $$0$$-dimensional compact Hausdorff spaces (plus continuous maps) and Boolean algebras (plus homomorphisms). On the one side there is a category of topological structures and continuous homomorphisms; on the other there is a category whose objects constitute an elementary productive class -- in the model-theoretic sense -- of finitary relational structures. (Another famous example of this phenomenon is Pontryagin duality between the compact Hausdorff and the discrete abelian groups.) In the early 1980s, this reviewer asked whether Stone duality could be properly extended to a full subcategory of the compact Hausdorff spaces -- in such a way that the dual category is still an elementary productive class -- and \textit{B. Banaschewski} [Can. J. Math. 36, 1113--1118 (1984; Zbl 0561.18004)] gave an elegant proof that it could not. In the present paper, the authors take a different approach to the problem of going beyond $$0$$-dimensionality and set about showing that certain bases of general locally compact locally Hausdorff étale groupoids are dual to a natural first order finitely axiomatizable class of inverse semigroups.'' The details are quite involved, and the interested reader is invited to consult the paper. Reviewer: Paul Bankston (Milwaukee) Semigroups in stable structures. https://www.zbmath.org/1455.03046 2021-03-30T15:24:00+00:00 "Halevi, Yatir" https://www.zbmath.org/authors/?q=ai:halevi.yatir Summary: Assume that $$G$$ is a definable group in a stable structure $$M$$. \textit{L. Newelski} [J. Symb. Log. 79, No. 4, 1199--1223 (2014; Zbl 1353.03022)] showed that the semigroup $$S_{G}(M)$$ of complete types concentrated on $$G$$ is an inverse limit of the $$\infty$$-definable (in $$M^{\text{eq}}$$) semigroups $$S_{G,\Delta}(M)$$. He also showed that it is strongly $$\pi$$-regular: for every $$p\in S_{G,\Delta}(M)$$, there exists $$n\in\mathbb{N}$$ such that $$p^{n}$$ is in a subgroup of $$S_{G,\Delta}(M)$$. We show that $$S_{G,\Delta}(M)$$ is in fact an intersection of definable semigroups, so $$S_{G}(M)$$ is an inverse limit of definable semigroups, and that the latter property is enjoyed by all $$\infty$$-definable semigroups in stable structures. More automorphism groups of countable, arithmetically saturated models of Peano arithmetic. https://www.zbmath.org/1455.03047 2021-03-30T15:24:00+00:00 "Schmerl, James H." https://www.zbmath.org/authors/?q=ai:schmerl.james-h Summary: There is an infinite set $$\mathscr{T}$$ of Turing-equivalent completions of Peano Arithmetic ($$\mathsf{PA}$$) such that whenever $$\mathcal{M}$$ and $$\mathcal{N}$$ are nonisomorphic countable, arithmetically saturated models of $$\mathsf{PA}$$ and $$\mathrm{Th}(\mathcal{M})$$, $$\mathrm{Th}(\mathcal{N})\in\mathcal{T}$$, then $$\mathrm{Aut}(\mathcal{M})\ncong\mathrm{Aut}(\mathcal{N})$$. Invariance and definability, with and without equality. https://www.zbmath.org/1455.03003 2021-03-30T15:24:00+00:00 "Bonnay, Denis" https://www.zbmath.org/authors/?q=ai:bonnay.denis "Engström, Fredrik" https://www.zbmath.org/authors/?q=ai:engstrom.fredrik Summary: The dual character of invariance under transformations and definability by some operations has been used in classical works by, for example, Galois and Klein. Following Tarski, philosophers of logic have claimed that logical notions themselves could be characterized in terms of invariance. In this article, we generalize a correspondence due to Krasner between invariance under groups of permutations and definability in $$\mathcal{L}_{\infty\infty}$$ so as to cover the cases (quantifiers, logics without equality) that are of interest in the logicality debates, getting McGee's theorem about quantifiers invariant under all permutations and definability in pure $$\mathcal{L}_{\infty\infty}$$ as a particular case. We also prove some optimality results along the way, regarding the kinds of relations which are needed so that every subgroup of the full permutation group is characterizable as a group of automorphisms. On superstable expansions of free abelian groups. https://www.zbmath.org/1455.03042 2021-03-30T15:24:00+00:00 "Palacín, Daniel" https://www.zbmath.org/authors/?q=ai:palacin.daniel "Sklinos, Rizos" https://www.zbmath.org/authors/?q=ai:sklinos.rizos Summary: We prove that $$(\mathbb{Z},+,0)$$ has no proper superstable expansions of finite Lascar rank. Nevertheless, this structure equipped with a predicate defining powers of a given natural number is superstable of Lascar rank $$\omega$$. Additionally, our methods yield other superstable expansions such as $$(\mathbb{Z},+,0)$$ equipped with the set of factorial elements. Geometric characterization of preduals of injective Banach lattices. https://www.zbmath.org/1455.46022 2021-03-30T15:24:00+00:00 "Kusraev, A. G." https://www.zbmath.org/authors/?q=ai:kusraev.anatolii-georievich|kusraev.anatoly-georgievich "Kutatelatze, S. S." https://www.zbmath.org/authors/?q=ai:kutateladze.semen-s The paper under review is concerned with preduals of injective Banach lattices, considered in the category of Banach lattices with positive operators. In other words, a Banach lattice $$X$$ is injective if, for every Banach lattice $$Y$$, every sublattice $$Z\subset Y$$ and every positive linear operator $$T:Z\rightarrow X$$, there is a positive linear operator $$\tilde T:Y\rightarrow X$$ such that the restriction to $$Z$$ satsifies $$\tilde T|_Z=T$$ and $$\|\tilde T\|=\|T\|$$. The study of this class of Banach lattices dates back to the 1970s due to deep works by H. P. Lotz, D. I. Cartwright, R. Haydon, J. Lindenstrauss and L. Tzafriri. In this paper, the authors provide several characterizations for the dual of a given Banach space to be an injective Banach lattice. Their approach is based on earlier work by the authors on Boolean valued analysis. The reader is referred to this interesting paper for details. Reviewer: Pedro Tradacete (Madrid) On elementary theories of algebraically closed groups. https://www.zbmath.org/1455.03045 2021-03-30T15:24:00+00:00 "Durnev, Valeriĭ Georgievich" https://www.zbmath.org/authors/?q=ai:durnev.valerii-georgievich "Zetkina, Oksana Valer'evna" https://www.zbmath.org/authors/?q=ai:zetkina.oksana-valerevna "Zetkina, Alena Igor'evna" https://www.zbmath.org/authors/?q=ai:zetkina.alena-igorevna Summary: In paper for any algebraically closed group $$G$$, as well as for the class of the algebraically closed groups, we prove algorithmic undecidability of the positive $$\forall^2 \exists^{24}$$-theory and $$\forall^3 \exists^2$$-theory. For an arbitrary $$g\in G$$, we also prove the decidability of the equation of the type $w(x_1, \ldots , x_n) = g,$ where $$w(x_1, \ldots , x_n)$$ is a non-empty irreducible word in the unknowns $$x_1,\ldots x_n\in G$$. Coding and definability in computable structures. https://www.zbmath.org/1455.03056 2021-03-30T15:24:00+00:00 "Montalbán, Antonio" https://www.zbmath.org/authors/?q=ai:montalban.antonio Summary: These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author's research on back-and-forth relations. Classifications of computable structures. https://www.zbmath.org/1455.03044 2021-03-30T15:24:00+00:00 "Lange, Karen" https://www.zbmath.org/authors/?q=ai:lange.karen "Miller, Russell" https://www.zbmath.org/authors/?q=ai:miller.russell-g "Steiner, Rebecca M." https://www.zbmath.org/authors/?q=ai:steiner.rebecca-m Summary: Let $$\mathcal{K}$$ be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from $$\mathcal{K}$$ such that every structure in $$\mathcal{K}$$ is isomorphic to exactly one structure on the list. Such a list is called a computable classification of $$\mathcal{K}$$, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a $$\mathbf{0'}$$-oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank $$1$$, even though these families are both closely allied with computable algebraic fields. On a metric generalization of the $$tt$$-degrees and effective dimension theory. https://www.zbmath.org/1455.03055 2021-03-30T15:24:00+00:00 "Kihara, Takayuki" https://www.zbmath.org/authors/?q=ai:kihara.takayuki In classical computability, tt-reducibility can be characterised as follows: $$A \leq_\text{tt} B$$ iff there exists a total computable functional $$\Phi\colon 2^\omega \to 2^\omega$$ such that $$\Phi(A) = B$$. \textit{T. H. McNicholl} and \textit{J. Rute} [A uniform reducibility in computably presented Polish spaces'', talk held at AMS sectional meeting AMS special session on effective mathematics in discrete and continuous worlds'', October 28--30, 2016] generalised this to a metric setting. For computable metric spaces $$\mathcal{X}$$ and $$\mathcal{Y}$$ and points $$x \in \mathcal{X}$$, $$y \in \mathcal{Y}$$, $$x \leq_\text{tt} y$$ if there is a total computable functional $$\Phi\colon \omega^\omega \to \omega^\omega$$ mapping every Cauchy name of $$x$$ to one of $$y$$. The author further explores the metric $$\leq_\text{tt}$$ relation and the associated degree structure. A first-level Borel function $$f\colon \mathcal{X} \to \mathcal{Y}$$ is one for which the preimage of any F$$_\sigma$$ set is F$$_\sigma$$; the author shows that $$\omega \times \mathcal{X}$$ and $$\omega \times \mathcal{Y}$$ are first-level Borel isomorphic iff they have the same tt-degree structures relative to a common oracle. In \S3, metric tt-degrees are used to connect (effective) topological dimension to the Schnorr packing dimension $$\operatorname{dim}^\text{Sch}_P$$ of \textit{R. Downey} et al. [Math. Struct. Comput. Sci. 16, No. 5, 789--811 (2006; Zbl 1125.03033)]. The main result is that every point in an $$n$$-dimensional computable compact metric space is tt-equivalent to some $$y$$ with $$\operatorname{dim}^\text{Sch}_P(y) \leq n$$. Reviewer: Jordan Mitchell Barrett (Wellington) Book review of: T. Button and S. Walsh, Philosophy and model theory. https://www.zbmath.org/1455.00006 2021-03-30T15:24:00+00:00 "Halimi, Brice" https://www.zbmath.org/authors/?q=ai:halimi.brice Review of [Zbl 1384.03001]. Ehrenfeucht's lemma in set theory. https://www.zbmath.org/1455.03065 2021-03-30T15:24:00+00:00 "Fuchs, Gunter" https://www.zbmath.org/authors/?q=ai:fuchs.gunter "Gitman, Victoria" https://www.zbmath.org/authors/?q=ai:gitman.victoria "Hamkins, Joel David" https://www.zbmath.org/authors/?q=ai:hamkins.joel-david Summary: Ehrenfeucht's lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, they satisfy different types. We consider here the analogue of Ehrenfeucht's lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and, in particular, Ehrenfeucht's lemma holds fully for models of set theory satisfying $$V=\mathsf{HOD}$$. We show that the lemma fails in the forcing extension of the universe by adding a Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht's lemma, namely, the principles of the form $$\mathsf{EL}(A,P,Q)$$, which asserts that $$P$$-definability from $$A$$ implies $$Q$$-discernibility. We also consider various analogues of Ehrenfeucht's lemma obtained by using algebraicity in place of definability, where a set $$b$$ is algebraic in $$a$$ if it is a member of a finite set definable from $$a$$. Ehrenfeucht's lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using a similar analysis, we answer two open questions posed earlier by the third author and C. Leahy, showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.