Search

We lay the foundations of the first-order model theory of Coxeter groups. Firstly, with the exception of the $2$-spherical non-affine case (which we leave open), we characterize the superstable Coxeter groups of finite rank, which we show to be essentially the Coxeter groups of affine type. Secondly, we characterize the Coxeter groups of finite rank which are domains, a central assumption in the theory of algebraic geometry over groups, which in many respects (e.g. $\lambda$-stability) reduces the model theory of a given Coxeter system to the model theory of its associated irreducible components. In the second part of the paper we move to specific definability questions in right-angled Coxeter groups (RACGs) and $2$-spherical Coxeter groups. In this respect, firstly, we prove that RACGs of finite rank do not have proper elementary subgroups which are Coxeter groups, and prove further that reflection independent ones do not have proper elementary subgroups at all. Secondly, we prove that if the monoid $Sim(W, S)$ of $S$-self-similarities of $W$ is finitely generated, then $W$ is a prime model of its theory. Thirdly, we prove that in reflection independent RACGs of finite rank the Coxeter elements are type-determined. We then move to $2$-spherical Coxeter groups, proving that if $(W, S)$ is irreducible, $2$-spherical even and not affine, then $W$ is a prime model of its theory, and that if $W_{\Gamma}$ and $W_{\Theta}$ are as in the previous sentence, then $W_{\Gamma}$ is elementary equivalent to $W_{\Theta}$ if and only if $\Gamma \cong \Theta$, thus solving the elementary equivalence problem for most of the $2$-spherical Coxeter groups. In the last part of the paper we focus on model theoretic applications of the notion of reflection length from Coxeter group theory, proving in particular that affine Coxeter groups are not connected., Comment: 38 pages

We extend classical Propositional Logic (PL) by adding a new primitive binary connective $\varphi|\psi$, intended to represent the "superposition" of sentences $\varphi$ and $\psi$, an operation motivated by the corresponding notion of quantum mechanics, but not intended to capture all aspects of the latter as they appear in physics. To interpret the new connective, we extend the classical Boolean semantics by employing models of the form $\langle M,f\rangle$, where $M$ is an ordinary two-valued assignment for the sentences of PL and $f$ is a choice function for all pairs of classical sentences. In the new semantics $\varphi|\psi$ is strictly interpolated between $\varphi\wedge\psi$ and $\varphi\vee\psi$. By imposing several constraints on the choice functions we obtain corresponding notions of logical consequence relations and corresponding systems of tautologies, with respect to which $|$ satisfies some natural algebraic properties such as associativity, closedness under logical equivalence and distributivity over its dual connective. Thus various systems of Propositional Superposition Logic (PLS) arise as extensions of PL. Axiomatizations for these systems of tautologies are presented and soundness is shown for all of them. Completeness is proved for the weakest of these systems. For the other systems completeness holds if and only if every consistent set of sentences is extendible to a consistent and complete one, a condition whose truth is closely related to the validity of the deduction theorem., Comment: 55 pages

We improve on and generalize a 1960 result of Maltsev. For a field $F$, we denote by $H(F)$ the Heisenberg group with entries in $F$. Maltsev showed that there is a copy of $F$ defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair $(u,v)$ as parameters. We show that $F$ is interpreted in $H(F)$ using computable $\Sigma_1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Montalb\'an. This proof allows the possibility that the elements of $F$ are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of $F$ represented by triples in $H(F)$. Looking at what was used to arrive at this parameter-free interpretation of $F$ in $H(F)$, we give general conditions sufficient to eliminate parameters from interpretations., Comment: Published online by the *Journal of Symbolic Logic*, 23 December 2021. Print version to appear subsequently

This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience., Comment: 6 pages. Paper E98

Let $T$ be a theory. If $T$ eliminates $\exists^\infty$, it need not follow that $T^{eq}$ eliminates $\exists^\infty$, as shown by the example of the $p$-adics. We give a criterion to determine whether $T^{eq}$ eliminates $\exists^\infty$. Specifically, we show that $T^{eq}$ eliminates $\exists^\infty$ if and only if $\exists^\infty$ is eliminated on all interpretable sets of "unary imaginaries." This criterion can be applied in cases where a full description of $T^{eq}$ is unknown. As an application, we show that $T^{eq}$ eliminates $\exists^\infty$ when $T$ is a C-minimal expansion of ACVF., Comment: 6 pages

In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as $\mathsf {P}\neq \mathsf {NP}$ [23–25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been proved in [20, 22].In this paper, we generalize and strengthen these results. Another question that we address concerns the dependence between these conjectures. We construct two oracles that enable us to answer questions about relativized separations asked in [19, 25] (i.e., for the pairs of conjectures mentioned in the questions, we construct oracles such that one conjecture from the pair is true in the relativized world and the other is false and vice versa). We also show several new connections between the studied conjectures. In particular, we show that the relation between the finite reflection principle and proof systems for existentially quantified Boolean formulas is similar to the one for finite consistency statements and proof systems for non-quantified propositional tautologies.

We show that certain type of tree forcings, including Sacks forcing, increases the covering of the strong measure zero ideal $\mathcal{SN}$. As a consequence, in Sacks model, such covering number is equal to the size of the continuum, which indicates that this covering number is consistently larger than any other classical cardinal invariant of the continuum. Even more, Sacks forcing can be used to force that $\mathrm{non}(\mathcal{SN}), Comment: 10 pages, 3 figures

We study the definability of ultrafilter bases on $$\omega $$ in the sense of descriptive set theory. As a main result we show that there is no coanalytic base for a Ramsey ultrafilter, while in L we can construct $$\Pi ^1_1$$ P-point and Q-point bases. We also show that the existence of a $${\varvec{\Delta }}^1_{n+1}$$ ultrafilter is equivalent to that of a $${\varvec{\Pi }}^1_n$$ ultrafilter base, for $$n \in \omega $$ . Moreover we introduce a Borel version of the classical ultrafilter number and make some observations.

We prove a result which describes, for each $n\ge 1$, all linear dependencies among $n$ images in elliptic curves of special points in modular or Shimura curves under parameterizations (or correspondences). Our result unifies and improves in certain aspects previous work of Rosen-Silverman--K\"uhne and Buium-Poonen., Comment: 18 pages, comments welcome!

We prove that there exists a functorial correspondence between MV-algebras and partially cyclically ordered groups which are wound round of lattice-ordered groups. It follows that some results about cyclically ordered groups can be stated in terms of MV-algebras. For example, the study of groups together with a cyclic order allows to get a first-order characterization of groups of unimodular complex numbers and of finite cyclic groups. We deduce a characterization of pseudofinite MV-chains and of pseudo-simple MV-chains (i.e. which share the same first-order properties as some simple ones). We can generalize these results to some non-lineraly ordered MV-algebras, for example hyper-archimedean MV-algebras.

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games., 56 pages. Journal of Philosophical Logic (2021)

We introduce a generalization of stationary set reflection which we call "filter reflection", and show it is compatible with the axiom of constructibility as well as with strong forcing axioms. We prove the independence of filter reflection from ZFC, and present applications of filter reflection to the study of canonical equivalence relations of the higher Cantor and Baire spaces.

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$ , $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated with this ordering, the Levin–V’yugin degrees (or $\mathrm {LV}$ -degrees), can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree.

We establish an approximate zero-one law for sentences of continuous logic over finite metric spaces of diameter at most $1$. More precisely, we axiomatize a complete metric theory $T_{\mathrm{as}}$ such that, given any sentence $\sigma$ in the language of pure metric spaces and any $\epsilon>0$, the probability that the difference of the value of $\sigma$ in a random metric space of size $n$ and the value of $\sigma$ in any model of $T_{\mathrm{as}}$ is less than $\epsilon$ approaches $1$ as $n$ approaches infinity. We also establish some model-theoretic properties of the theory $T_{\mathrm{as}}$., Comment: Final version

We prove an algebraic canonicity theorem for normal LE-logics of arbitrary signature, in a generalized setting in which the non-lattice connectives are interpreted as operations mapping tuples of elements of the given lattice to closed or open elements of its canonical extension. Interestingly, the syntactic shape of LE-inequalities which guarantees their canonicity in this generalized setting turns out to coincide with the syntactic shape of analytic inductive inequalities, which guarantees LE-inequalities to be equivalently captured by analytic structural rules of a proper display calculus. We show that this canonicity result connects and strengthens a number of recent canonicity results in two different areas: subordination algebras, and transfer results via G\"odel-McKinsey-Tarski translations., Comment: arXiv admin note: text overlap with arXiv:1603.08515, arXiv:1603.08341

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA_0 and hence is computably true., Only minor (non mathematical) changes introduced. To appear in Computability

We investigate the asymptotic densities of theorems provable in Zermelo-Fraenkel set theory ZF and its extension ZFC including the axiom of choice. Assuming a canonical De Bruijn representation of formulae, we construct asymptotically large sets of sentences unprovable within ZF, yet provable in ZFC. Furthermore, we link the asymptotic density of ZFC theorems with the provable consistency of ZFC itself. Consequently, if ZFC is consistent, it is not possible to refute the existence of the asymptotic density of ZFC theorems within ZFC. Both these results address a recent question by Zaionc regarding the asymptotic equivalence of ZF and ZFC., Included funding acknowledgements

The tetravalent modal logic ( $${\mathcal {TML}}$$ ) is one of the two logics defined by Font and Rius (J Symb Log 65(2):481–518, 2000) (the other is the normal tetravalent modal logic $${{\mathcal {TML}}}^N$$ ) in connection with Monteiro’s tetravalent modal algebras. These logics are expansions of the well-known Belnap–Dunn’s four-valued logic that combine a many-valued character (tetravalence) with a modal character. In fact, $${\mathcal {TML}}$$ is the logic that preserves degrees of truth with respect to tetravalent modal algebras. As Font and Rius observed, the connection between the logic $${\mathcal {TML}}$$ and the algebras is not so good as in $${{\mathcal {TML}}}^N$$ , but, as a compensation, it has a better proof-theoretic behavior, since it has a strongly adequate Gentzen calculus (see Font and Rius in J Symb Log 65(2):481–518, 2000). In this work, we prove that the sequent calculus given by Font and Rius does not enjoy the cut-elimination property. Then, using a general method proposed by Avron et al. (Log Univ 1:41–69, 2006), we provide a sequent calculus for $${\mathcal {TML}}$$ with the cut-elimination property. Finally, inspired by the latter, we present a natural deduction system, sound and complete with respect to the tetravalent modal logic.

We prove the equivalence of the semantic version of Tarski's theorem on the undefinability of truth with a semantic version of the Diagonal Lemma, and also show the equivalence of syntactic Tarski's Undefinability Theorem with a weak syntactic diagonal lemma. We outline two seemingly diagonal-free proofs for these theorems from the literature, and show that syntactic Tarski's theorem can deliver G\"odel-Rosser's Incompleteness Theorem., Comment: 8 pages

We prove, under a computational complexity hypothesis, that it is consistent with the true universal theory of p-time algorithms that a specific p-time function extending $n$ bits to $m \geq n^2$ bits violates the dual weak pigeonhole principle: every string $y$ of length $m$ equals the value of the function for some $x$ of length $n$. The function is the truth-table function assigning to a circuit the table of the function it computes and the hypothesis is that every language in P has circuits of a fixed polynomial size $n^d$., Preprint April 2020, revision December 2020

We describe how properties of metric groups and of unitary representations of metric groups can be presented in continuous logic. In particular we find $L_{\omega_1 \omega}$-axiomatization of amenability. We also show that in the case of locally compact groups some uniform version of the negation of Kazhdan's property {\bf (T)} can be viewed as a union of first-order axiomatizable classes. We will see when these properties are preserved under taking elementary substructures., Comment: 15 pages; to appear in Communications in Mathematics, special issue "Ostrava seminar on Mathematical Physics". arXiv admin note: substantial text overlap with arXiv:1706.04157

We shall defend three philosophical theses about the extent of intrinsic justification based on various technical results. We shall present a set of theorems which indicate intriguing structural similarities between a family of “weak” reflection principles roughly at the level of those considered by Tait and Koellner and a family of “strong” reflection principles roughly at the level of those of Welch and Roberts, which we claim to lend support to the view that the stronger reflection principles are intrinsically justified as well as the weaker ones. We consider connections with earlier work of Marshall.

Assuming Schanuel's Conjecture we prove that for any variety V over the algebraic closure over the rational numbers, of dimension n and with dominant projections, there exists a generic point in V. We obtain in this way many instances of the Strong Exponential Closure introduced by Zilber., Comment: 10 pages

We prove a tight bound on the number of realized $0/1$ patterns (or equivalently on the Vapnik-Chervonenkis codensity) of definable families in models of the theory of algebraically closed valued fields with a non-archimedean valuation. Our result improves the best known result in this direction proved by Aschenbrenner, Dolich, Haskell, Macpherson and Starchenko, who proved a weaker bound in the restricted case where the characteristics of the field $K$ and its residue field are both assumed to be $0$. The bound obtained here is optimal and without any restriction on the characteristics. We obtain the aforementioned bound as a consequence of another result on bounding the Betti numbers of semi-algebraic subsets of certain Berkovich analytic spaces, mirroring similar results known already in the case of o-minimal structures and for real closed, as well as, algebraically closed fields. The latter result is the first result in this direction and is possibly of independent interest. Its proof relies heavily on recent results of Hrushovski and Loeser on the topology of semi-algebraic subsets of Berkovich analytic spaces., 40 pages. Extensively revised

LP$^{\supset,\mathsf{F}}$ is a three-valued paraconsistent propositional logic which is essentially the same as J3. It has most properties that have been proposed as desirable properties of a reasonable paraconsistent propositional logic. However, it follows easily from already published results that there are exactly 8192 different three-valued paraconsistent propositional logics that have the properties concerned. In this paper, properties concerning the logical equivalence relation of a logic are used to distinguish LP$^{\supset,\mathsf{F}}$ from the others. As one of the bonuses of focussing on the logical equivalence relation, it is found that only 32 of the 8192 logics have a logical equivalence relation that satisfies the identity, annihilation, idempotent, and commutative laws for conjunction and disjunction. For most properties of LP$^{\supset,\mathsf{F}}$ that have been proposed as desirable properties of a reasonable paraconsistent propositional logic, its paracomplete analogue has a comparable property. In this paper, properties concerning the logical equivalence relation of a logic are also used to distinguish the paracomplete analogue of LP$^{\supset,\mathsf{F}}$ from the other three-valued paracomplete propositional logics with those comparable properties., Comment: 17 pages, version that is accepted for publication, there is some text overlap between this paper and arXiv:1508.06899 [cs.LO]

The present paper develops a unified correspondence treatment of the Sahlqvist theory for possibility semantics, extending the results in \cite{Ya16} from Sahlqvist formulas to the strictly larger class of inductive formulas, and from the full possibility frames to filter-descriptive possibility frames. Specifically, we define the possibility semantics version of the algorithm ALBA, and an adapted interpretation of the expanded modal language used in the algorithm. We prove the soundness of the algorithm with respect to both (the dual algebras of) full possibility frames and (the dual algebras of) filter-descriptive possibility frames. We make some comparisons among different semantic settings in the design of the algorithms, and fit possibility semantics into this broader picture. One notable feature of the adaptation of ALBA to possibility frames setting is that the so-called nominal variables, which are interpreted as complete join-irreducibles in the standard setting, are interpreted as regular open closures of "singletons" in the present setting., This is a preliminary version of the full paper

In the present paper, we endow semi De Morgan logic and a family of its axiomatic extensions with proper multi-type display calculi which are sound, complete, conservative, and enjoy cut elimination and subformula property. Our proposal builds on an algebraic analysis of the variety of semi De Morgan algebras, and applies the guidelines of the multi-type methodology in the design of display calculi.

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

Extending Aanderaa's classical result that $\pi^1_1, Comment: 21 pages. This version: March 2019

We analyse the complexity of the class of (special) Aronszajn, Suslin and Kurepa trees in the projective hierarchy of the higher Baire-space $\omega_1^{\omega_1}$. First, we will show that none of these classes have the Baire property (unless they are empty). Moreover, under $(V=L)$, (a) the class of Aronszajn and Suslin trees is $\Pi_1^1$-complete, (b) the class of special Aronszajn trees is $\Sigma_1^1$-complete, and (c) the class of Kurepa trees is $\Pi^1_2$-complete. We achieve these results by finding nicely definable reductions that map subsets $X$ of $\omega_1$ to trees $T_X$ so that $T_X$ is in a given tree-class $\mathcal T$ if and only if $X$ is stationary/non-stationary (depending on the class $\mathcal T$). Finally, we present models of CH where these classes have lower projective complexity., Comment: 16 pages

This paper studies the relationship between labelled and nested calculi for propositional intuitionistic logic, first-order intuitionistic logic with non-constant domains and first-order intuitionistic logic with constant domains. It is shown that Fitting's nested calculi naturally arise from their corresponding labelled calculi--for each of the aforementioned logics--via the elimination of structural rules in labelled derivations. The translational correspondence between the two types of systems is leveraged to show that the nested calculi inherit proof-theoretic properties from their associated labelled calculi, such as completeness, invertibility of rules and cut admissibility. Since labelled calculi are easily obtained via a logic's semantics, the method presented in this paper can be seen as one whereby refined versions of labelled calculi (containing nested calculi as fragments) with favourable properties are derived directly from a logic's semantics., arXiv admin note: text overlap with arXiv:1910.06576

We prove that $ZF+DC+"$there exists a transcendence basis for the reals$"+"$there is no well-ordering of the reals$"$ is consistent relative to $ZFC$. This answers a question of Larson and Zapletal., We corrected a gap in the proof of Claim 6

A countable semigroup is $$\aleph _0$$ ℵ 0 -categorical if it can be characterised, up to isomorphism, by its first-order properties. In this paper we continue our investigation into the $$\aleph _0$$ ℵ 0 -categoricity of semigroups. Our main results are a complete classification of $$\aleph _0$$ ℵ 0 -categorical orthodox completely 0-simple semigroups, and descriptions of the $$\aleph _0$$ ℵ 0 -categorical members of certain classes of strong semilattices of semigroups.

The o-minimal structure generated by the restricted Pfaffian functions, known as restricted sub-Pfaffian sets, admits a natural measure of complexity in terms of a format${{\mathcal{F}}}$, recording information like the number of variables and quantifiers involved in the definition of the set, and a degree$D$, recording the degrees of the equations involved. Khovanskii and later Gabrielov and Vorobjov have established many effective estimates for the geometric complexity of sub-Pfaffian sets in terms of these parameters. It is often important in applications that these estimates are polynomial in $D$. Despite much research done in this area, it is still not known whether cell decomposition, the foundational operation of o-minimal geometry, preserves polynomial dependence on $D$. We slightly modify the usual notions of format and degree and prove that with these revised notions, this does in fact hold. As one consequence, we also obtain the first polynomial (in $D$) upper bounds for the sum of Betti numbers of sets defined using quantified formulas in the restricted sub-Pfaffian structure.

We give a structural theorem for pseudofinite groups of finite centraliser dimension. As a corollary, we observe that there is no finitely generated pseudofinite group of finite centraliser dimension.

In this note, we establish a version of the local Cauchy-Crofton formula for definable sets in Henselian discretely valued fields of characteristic zero. It allows to compute the motivic local density of a set from the densities of its projections integrated over the Grassmannian., Manuscripta Mathematica, 166 (3), ISSN:0025-2611, ISSN:1432-1785

We construct, in $\mathsf{ZFC}$, a countably compact subgroup of $2^{\mathfrak{c}}$ without non-trivial convergent sequences, answering an old problem of van Douwen. As a consequence we also prove the existence of two countably compact groups $\mathbb{G}_{0}$ and $\mathbb{G}_{1}$ such that the product $\mathbb{G}_{0} \times \mathbb{G}_{1}$ is not countably compact, thus answering a classical problem of Comfort., 21 pages, to be published in Transactions of the American Mathematical Society

Let $\mathcal M=(M, be a linearly ordered first-order structure and T its complete theory. We investigate conditions for T that could guarantee that $\mathcal M$ is not much more complex than some colored orders (linear orders with added unary predicates). Motivated by Rubin’s work [5], we label three conditions expressing properties of types of T and/or automorphisms of models of T. We prove several results which indicate the “geometric” simplicity of definable sets in models of theories satisfying these conditions. For example, we prove that the strongest condition characterizes, up to definitional equivalence (inter-definability), theories of colored orders expanded by equivalence relations with convex classes.

We establish effective elimination theorems for ordinary differential-difference equations. Specifically, we find a computable function B ( r , s ) B(r,s) of the natural number parameters r r and s s so that for any system of algebraic ordinary differential-difference equations in the variables x = x 1 , … , x q \mathbfit {x} = x_1, \ldots , x_q and y = y 1 , … , y r \mathbfit {y} = y_1, \ldots , y_r , each of which has order and degree in y \mathbfit {y} bounded by s s over a differential-difference field, there is a nontrivial consequence of this system involving just the x \mathbfit {x} variables if and only if such a consequence may be constructed algebraically by applying no more than B ( r , s ) B(r,s) iterations of the basic difference and derivation operators to the equations in the system. We relate this finiteness theorem to the problem of finding solutions to such systems of differential-difference equations in rings of functions showing that a system of differential-difference equations over C \mathbb {C} is algebraically consistent if and only if it has solutions in a certain ring of germs of meromorphic functions.

We set up a general context in which one can prove Sauer–Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer–Shelah type lemma in the context of $ \operatorname {\textrm{op}}$ -rank, a notion of Guingona and Hill [4].

We show that if $M$ is a countable transitive model of ZF and if $a,b$ are reals not in $M$, then there is a $G$ generic over $M$ such that $b \in L[a,G]$. We then present several applications such as the following: if $J$ is any countable transitive model of ZFC and $M \not\subseteq J$ is another countable transitive model of ZFC of the same ordinal height $\alpha$, then there is a forcing extension $N$ of $J$ such that $M \cup N$ is not included in any transitive model of ZFC of height $\alpha$. Also, assuming $0^\#$ exists, letting $S$ be the set of reals generic over $L$, although $S$ is disjoint from the Turing cone above $0^\#$, we have that for any non-constructible real $a$, $\{ a \oplus s : s \in S \}$ is cofinal in the Turing degrees., Comment: 14 pages

In this paper, firstly, we determine the number of sublogics of variable inclusion of an arbitrary finitary logic L with partition function. Then, we investigate their position into the lattice of consequence relations over the language of L., Comment: arXiv admin note: text overlap with arXiv:1804.08897, arXiv:1809.06761

In this paper, we provide a new characterization of Keisler's order in terms of saturation of Boolean ultrapowers. To do so, we apply and expand the framework of 'separation of variables' recently developed by Malliaris and Shelah. We also show that good ultrafilters on Boolean algebras are precisely the ones which capture the maximum class in Keisler's order, answering a question posed by Benda in 1974.

In this paper we define the monadic pseudo BE-algebras and investigate their properties. We prove that the existential and universal quantifiers of a monadic pseudo BE-algebra form a residuated pair. Special properties are studied for the particular case of monadic bounded commutative pseudo BE-algebras. Monadic classes of pseudo BE-algebras are investigated and it is proved that the quantifiers on bounded commutative pseudo BE-algebras are also quantifiers on the corresponding pseudo MV-algebras. The monadic deductive systems and monadic congruences of monadic pseudo BE-algebras are defined and their properties are studied. It is proved that, in the case of a monadic distributive commutative pseudo BE-algebra there is a one-to-one correspondence between monadic congruences and monadic deductive systems, and the monadic quotient pseudo BE-algebra algebra is also defined.

We show that the following operator algebras have hyperarithmetic theory: the hyperfinite II$_1$ factor $\mathcal R$, $L(\Gamma)$ for $\Gamma$ a finitely generated group with solvable word problem, $C^*(\Gamma)$ for $\Gamma$ a finitely presented group, $C^*_\lambda(\Gamma)$ for $\Gamma$ a finitely generated group with solvable word problem, $C(2^\omega)$, and $C(\mathbb P)$ (where $\mathbb P$ is the pseudoarc). We also show that the Cuntz algebra $\mathcal O_2$ has a hyperarithmetic theory provided that the Kirchberg embedding problem has an affirmative answer. Finally, we prove that if there is an existentially closed (e.c.) II$_1$ factor (resp. C$^*$-algebra) that does not have hyperarithmetic theory, then there are continuum many theories of e.c. II$_1$ factors (resp. e.c. C$^*$-algebras)., Comment: 18 pages; second draft reflects new results

In this paper we prove the following results: $1)$ We show that any arithmetic quotient of a homogeneous space admits a natural real semi-algebraic structure for which its Hecke correspondences are semi-algebraic. A particularly important example is given by Hodge varieties, which parametrize pure polarized integral Hodge structures. $2)$ We prove that the period map associated to any pure polarized variation of integral Hodge structures $\mathbb{V}$ on a smooth complex quasi-projective variety $S$ is definable with respect to an o-minimal structure on the relevant Hodge variety induced by the above semi-algebraic structure. $3)$ As a corollary of $2)$ and of Peterzil-Starchenko's o-minimal Chow theorem we recover that the Hodge locus of $(S, \mathbb{V})$ is a countable union of algebraic subvarieties of $S$, a result originally due to Cattani-Deligne-Kaplan. Our approach simplifies the proof of Cattani-Deligne-Kaplan, as it does not use the full power of the difficult multivariable $SL_2$-orbit theorem of Cattani-Kaplan-Schmid., 23 pages, final version. arXiv admin note: substantial text overlap with arXiv:1803.09384

In connection with the work of Anscombe, Macpherson, Steinhorn and the present author in [1] we investigate the notion of a multidimensional exact class (R-mec), a special kind of multidimensional asymptotic class (R-mac) with measuring functions that yield the exact sizes of definable sets, not just approximations. We use results about smooth approximation [24] and Lie coordinatization [13] to prove the following result (Theorem 4.6.4), as conjectured by Macpherson: For any countable language $\mathcal {L}$ and any positive integer d the class $\mathcal {C}(\mathcal {L},d)$ of all finite $\mathcal {L}$-structures with at most d 4-types is a polynomial exact class in $\mathcal {L}$, where a polynomial exact class is a multidimensional exact class with polynomial measuring functions.

Consider a definably complete uniformly locally o-minimal expansion of the second kind of a densely linearly ordered abelian group. Let $f:X \rightarrow R^n$ be a definable map, where X is a definable set and R is the universe of the structure. We demonstrate the inequality $\dim (f(X)) \leq \dim (X)$ in this paper. As a corollary, we get that the set of the points at which f is discontinuous is of dimension smaller than $\dim (X)$. We also show that the structure is definably Baire in the course of the proof of the inequality.

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert--Bernays' consistency statement. Secondly, we improve Buchholz's schematic proof of provable $\Sigma_1$-completeness. Then among other things, we show that Hilbert--Bernays' conditions and L\"ob's conditions are mutually incomparable. We also show that neither Hilbert--Bernays' conditions nor L\"ob's conditions accomplish G\"odel's original statement of the second incompleteness theorem., Comment: 36 pages