On ω-categorical,generically stable groups and rings

We prove that every ω-categorical, generically stable group is nilpotent-by-finite and that every ω-categorical, generically stable ring is nilpotent-by-finite.     

On omega-categorical simple theories

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.     

Amalgamation functors and boundary properties in simple theories

This paper continues the study of generalized amalgamation properties begun in [1], [2], [3], [5] and [6]. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. We show that such groupoids must be abelian and we link the binding group of the groupoids to a certain automorphism group of the monster model, showing that the group must be abelian as well. We also study connections between n-existence and n-uniqueness properties for various “dimensions” n in the wider context of simple theories. We introduce a family of weaker existence and uniqueness properties. Many of these properties did appear in the literature before; we give a category-theoretic formulation and study them systematically. Finally, we give examples of first-order simple unstable theories showing, in particular, that there is no straightforward generalization of the groupoid construction in an unstable context.     

A modal logic framework for reasoning about comparative distances and topology

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s S4 for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances (i.e., between minimum and infimum). Due to its greater expressive power, this logic turns out to behave quite differently from both S4 and conditional logics. We provide finite (Hilbert-style) axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line (and various other important metric spaces) is not recursively enumerable. This result is proved by an encoding of Diophantine equations.     

A semantic study of the first-order predicate logic with uncertainty involved

In this paper, we provide a semantic study of the first-order predicate logic for situations involving uncertainty. We introduce the concepts of uncertain predicate proposition, uncertain predicate formula, uncertain interpretation and degree of truth in the framework of uncertainty theory. Compared with classical predicate formula taking true value in \(\{0,1\}\) , the degree of truth of uncertain predicate formula may take any value in the unit interval \([0,1]\) . We also show that the uncertain first-order predicate logic is consistent with the classical first-order predicate logic on some laws of the degree of truth.     

Degrees of isomorphism types and countably categorical groups

It is shown that for every Turing degree d there is an ω-categorical group G such that the isomorphism type of G is of degree d. We also find an ω-categorical group G such that the isomorphism type of G has no degree.     

Effectiveness in RPL, with applications to continuous logic

In this paper, we introduce a foundation for computable model theory of rational Pavelka logic (an extension of ?ukasiewicz logic) and continuous logic, and prove effective versions of some related theorems in model theory. We show how to reduce continuous logic to rational Pavelka logic. We also define notions of computability and decidability of a model for logics with computable, but uncountable, set of truth values; we show that provability degree of a formula with respect to a linear theory is computable, and use this to carry out an effective Henkin construction. Therefore, for any effectively given consistent linear theory in continuous logic, we effectively produce its decidable model. This is the best possible, since we show that the computable model theory of continuous logic is an extension of computable model theory of classical logic. We conclude with noting that the unique separable model of a separably categorical and computably axiomatizable theory (such as that of a probability space or an L^p Banach lattice) is decidable.     

Enumerating teams in first-order team logics

We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problem where only maximal or minimal solutions, with respect to cardinality or inclusion, are considered. For the most part these share the same complexity as the original problem. One exception is the cardinality minimum-variant for inclusion logic, which is DelNP-complete, the other is the inclusion maximal-variant for dependence and independence logic, which is in Del⁺NP and DelNP-hard.     

A folk model structure on omega-cat

The primary aim of this work is an intrinsic homotopy theory of strict ω-categories. We establish a model structure on ωCat, the category of strict ω-categories. The constructions leading to the model structure in question are expressed entirely within the scope of ωCat, building on a set of generating cofibrations and a class of weak equivalences as basic items. All objects are fibrant while free objects are cofibrant. We further exhibit model structures of this type on n-categories for arbitrary n∈N, as specializations of the ω-categorical one along right adjoints. In particular, known cases for n=1 and n=2 nicely fit into the scheme.     

On some classes of Lindelöf Σ-spaces

We consider special subclasses of the class of Lindelöf Σ-spaces obtained by imposing restrictions on the weight of the elements of compact covers that admit countable networks: A space X is in the class LΣ(?κ) if it admits a cover by compact subspaces of weight κ and a countable network for the cover. We restrict our attention to κ?ω. In the case κ=ω, the class includes the class of metrizably fibered spaces considered by Tkachuk, and the P-approximable spaces considered by Tka?enko. The case κ=1 corresponds to the spaces of countable network weight, but even the case κ=2 gives rise to a nontrivial class of spaces. The relation of known classes of compact spaces to these classes is considered. It is shown that not every Corson compact of weight ℵ₁ is in the class LΣ(?ω), answering a question of Tkachuk. As well, we study whether certain compact spaces in LΣ(?ω) have dense metrizable subspaces, partially answering a question of Tka?enko. Other interesting results and examples are obtained, and we conclude the paper with a number of open questions.     

New results on q-positivity

In this paper we discuss symmetrically self-dual spaces, which are simply real vector spaces with a symmetric bilinear form. Certain subsets of the space will be called q-positive, where q is the quadratic form induced by the original bilinear form. The notion of q-positivity generalizes the classical notion of the monotonicity of a subset of a product of a Banach space and its dual. Maximal q-positivity then generalizes maximal monotonicity. We discuss concepts generalizing the representations of monotone sets by convex functions, as well as the number of maximally q -positive extensions of a q-positive set. We also discuss symmetrically self-dual Banach spaces, in which we add a Banach space structure, giving new characterizations of maximal q-positivity. The paper finishes with two new examples.     

Use of abstract Hardy spaces, real interpolation and applications to bilinear operators

This paper can be considered as the sequel of Bernicot and Zhao (J Func Anal 255:1761–1796, 2008), where the authors have proposed an abstract construction of Hardy spaces H ¹. They shew an interpolation result for these Hardy spaces with the Lebesgue spaces. Here we describe a more precise result using the real interpolation theory and we clarify the use of Hardy spaces. Then with the help of the bilinear interpolation theory, we then give applications to study bilinear operators on Lebesgue spaces. These ideas permit us to study singular operators with singularities similar to those of bilinear Calderón-Zygmund operators in a far more abstract framework as in the Euclidean case.     

Logical laws for existential monadic second-order sentences with infinite first-order parts

We consider existential monadic second-order sentences ?X φ(X) about undirected graphs, where ?X is a finite sequence of monadic quantifiers and φ(X) ∈ +_∞ω^ω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.     

Frames and oversampling formulas for band limited functions

In this article, we obtain families of frames for the space B _ω of functions with band in [?ω, ω] by using the theory of shift-invariant spaces. Our results are based on the Gramian analysis of Ron and Shen and a variant, due to Bownik, of their characterization of families of functions whose shifts form frames or Riesz bases. We give necessary and sufficient conditions for the translates of a finite number of functions (generators) to be a frame or a Riesz basis for B _ω . We also give explicit formulas for the dual generators, and we apply them to Hilbert transform sampling and derivative sampling. Finally we provide numerical experiments that support the theory.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

A categorical characterization of strong Steiner ω-categories

Strong Steiner ω-categories are a class of ω-categories that admit algebraic models in the form of chain complexes, whose formalism allows for several explicit computations. The conditions defining strong Steiner ω-categories are traditionally expressed in terms of the associated chain complex, making them somewhat disconnected from the ω-categorical intuition. The purpose of this paper is to characterize this class as the class of ω-categories generated by polygraphs that satisfy a loop-freeness condition that does not make explicit use of the associated chain complex and instead relies on the categorical features of ω-categories.     

Categories with families and first-order logic with dependent sorts

First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Löf type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle.     

Reduction of database independence to dividing in atomless Boolean algebras

We prove that the form of conditional independence at play in database theory and independence logic is reducible to the first-order dividing calculus in the theory of atomless Boolean algebras. This establishes interesting connections between independence in database theory and stochastic independence. As indeed, in light of the aforementioned reduction and recent work of Ben-Yaacov (Isr. J. Math. 194(2):957–1012, 2013), the former case of independence can be seen as the discrete version of the latter.     

A Non-Standard Analysis of a Cultural Icon: The Case of Paul Halmos

We examine Paul Halmos’ comments on category theory, Dedekind cuts, devil worship, logic, and Robinson’s infinitesimals. Halmos’ scepticism about category theory derives from his philosophical position of naive set-theoretic realism. In the words of an MAA biography, Halmos thought that mathematics is “certainty” and “architecture” yet 20th century logic teaches us is that mathematics is full of uncertainty or more precisely incompleteness. If the term architecture meant to imply that mathematics is one great solid castle, then modern logic tends to teach us the opposite lesson, namely that the castle is floating in midair. Halmos’ realism tends to color his judgment of purely scientific aspects of logic and the way it is practiced and applied. He often expressed distaste for nonstandard models, and made a sustained effort to eliminate first-order logic, the logicians’ concept of interpretation, and the syntactic vs semantic distinction. He felt that these were vague, and sought to replace them all by his polyadic algebra. Halmos claimed that Robinson’s framework is “unnecessary” but Henson and Keisler argue that Robinson’s framework allows one to dig deeper into set-theoretic resources than is common in Archimedean mathematics. This can potentially prove theorems not accessible by standard methods, undermining Halmos’ criticisms.     

Bilattice logic of epistemic actions and knowledge

Baltag, Moss, and Solecki proposed an expansion of classical modal logic, called logic of epistemic actions and knowledge (EAK), in which one can reason about knowledge and change of knowledge. Kurz and Palmigiano showed how duality theory provides a flexible framework for modeling such epistemic changes, allowing one to develop dynamic epistemic logics on a weaker propositional basis than classical logic (for example an intuitionistic basis). In this paper we show how the techniques of Kurz and Palmigiano can be further extended to define and axiomatize a bilattice logic of epistemic actions and knowledge (BEAK). Our propositional basis is a modal expansion of the well-known four-valued logic of Belnap and Dunn, which is a system designed for handling inconsistent as well as potentially conflicting information. These features, we believe, make our framework particularly promising from a computer science perspective.