Parametric Presburger arithmetic: complexity of counting and quantifier elimination

We consider an expansion of Presburger arithmetic which allows multiplication by k parameters $t_1,\dots ,t_k$. A formula in this language defines a parametric set $S_{\mathbf{t}}?{\mathbb{Z}}^d$ as $\mathbf{t}$ varies in ${\mathbb{Z}}^k$, and we examine the counting function $|S_{\mathbf{t}}|$ as a function of t . For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming $\mathbf{P}\ne \mathbf{NP}$) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1,t_2}|$ is not even polynomial‐time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_{\mathbf{t}}?{\mathbb{Z}}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_{\mathbf{t}}|$ is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions.     

Strongly unfoldable,splitting and bounding

Assuming $\mathsf{GCH}$, we show that generalized eventually narrow sequences on a strongly inaccessible cardinal κ are preserved under a one step iteration of the Hechler forcing for adding a dominating κ-real. Moreover, we show that if κ is strongly unfoldable, $2^{\kappa }={\kappa }^{+}$ and λ is a regular cardinal such that , then there is a set generic extension in which .     

More about divisibility in βN

We continue the research of an extension $\stackrel{～}{\mid }$ of the divisibility relation to the Stone-?ech compactification $\beta \mathbb{N}$. First we prove that ultrafilters we call prime actually possess the algebraic property of primality. Several questions concerning the connection between divisibilities in $\beta \mathbb{N}$ and nonstandard extensions of $\mathbb{N}$ are answered, providing a few more equivalent conditions for divisibility in $\beta \mathbb{N}$. Results on uncountable chains in $(\beta \mathbb{N},\stackrel{～}{\mid })$ are proved and used in a construction of a well-ordered chain of maximal cardinality. Probably the most interesting result is the existence of a chain of type $(\mathbb{R},<)$ in $(\beta \mathbb{N},\stackrel{～}{\mid })$. Finally, we consider ultrafilters without divisors in $\mathbb{N}$ and among them find the greatest class.     

Concrete barriers to quantifier elimination in finite dimensional C*‐algebras

Work of Eagle, Farah, Goldbring, Kirchberg, and Vignati shows that the only separable C*‐algebras that admit quantifier elimination in continuous logic are $\mathbb{C}$, ${\mathbb{C}}^2$, $M_2(\mathbb{C})$, and the continuous functions on the Cantor set. We show that, among finite dimensional C*‐algebras, quantifier elimination does hold if the language is expanded to include two new predicate symbols: One for minimal projections, and one for pairs of unitarily conjugate elements. Both of these predicates are definable, but not quantifier‐free definable, in the usual language of C*‐algebras. We also show that adding just the predicate for minimal projections is sufficient in the case of full matrix algebras, but that in general both new predicate symbols are required.     

Degrees of categoricity of trees and the isomorphism problem

In this paper, we show that for any computable ordinal α, there exists a computable tree of rank $\alpha +1$ with strong degree of categoricity ${\mathbf{0}}^{(2\alpha )}$ if α is finite, and with strong degree of categoricity ${\mathbf{0}}^{(2\alpha +1)}$ if α is infinite. In fact, these are the greatest possible degrees of categoricity for such trees. For a computable limit ordinal α, we show that there is a computable tree of rank α with strong degree of categoricity ${\mathbf{0}}^{(\alpha )}$ (which equals ${\mathbf{0}}^{(2\alpha )}$). It follows from our proofs that, for every computable ordinal $\alpha >0$, the isomorphism problem for trees of rank α is ${\mathrm{\Pi }}_{2\alpha }^0$‐complete.     

A game-theoretic proof of Shelah's theorem on labeled trees

We give a new proof of a theorem of Shelah which states that for every family of labeled trees, if the cardinality κ of the family is much larger (in the sense of large cardinals) than the cardinality λ of the set of labels, more precisely if the partition relation $\kappa \to {(\omega )}_{\lambda }^{<\omega }$ holds, then there is a homomorphism from one labeled tree in the family to another. Our proof uses a characterization of such homomorphisms in terms of games.     

On universal modules with pure embeddings

We show that certain classes of modules have universal models with respect to pure embeddings: Let R be a ring, T a first-order theory with an infinite model extending the theory of R-modules and ${\mathbf{K}}^T=(Mod(T),{\le }_{\mathrm{pp}})$ (where ⩽_pp stands for “pure submodule”). Assume ${\mathbf{K}}^T$ has the joint embedding and amalgamation properties. If ${\lambda }^{|T|}=\lambda$ or $\forall \mu <\lambda ({\mu }^{|T|}<\lambda )$, then ${\mathbf{K}}^T$ has a universal model of cardinality λ. As a special case, we get a recent result of Shelah [28, 1.2] concerning the existence of universal reduced torsion-free abelian groups with respect to pure embeddings. We begin the study of limit models for classes of R-modules with joint embedding and amalgamation. We show that limit models with chains of long cofinality are pure-injective and we characterize limit models with chains of countable cofinality. This can be used to answer [18, Question 4.25]. As this paper is aimed at model theorists and algebraists an effort was made to provide the background for both.     

Decidable fan theorem and uniform continuity theorem with continuous moduli

The uniform continuity theorem $(\mathsf{UCT})$ states that every pointwise continuous real-valued function on the unit interval is uniformly continuous. In constructive mathematics, $\mathsf{UCT}$ is strictly stronger than the decidable fan theorem $(\mathsf{DFT})$, but Loeb [17] has shown that the two principles become equivalent by encoding continuous real-valued functions as type-one functions. However, the precise relation between such type-one functions and continuous real-valued functions (usually described as type-two objects) has been unknown. In this paper, we introduce an appropriate notion of continuity for a modulus of a continuous real-valued function on [0, 1], and show that real-valued functions with continuous moduli are exactly those functions induced by Loeb's codes. Our characterisation relies on two assumptions: (1) real numbers are represented by regular sequences (equivalently Cauchy sequences with explicitly given moduli); (2) the continuity of a modulus is defined with respect to the product metric on the regular sequences inherited from the Baire space. Our result implies that $\mathsf{DFT}$ is equivalent to the statement that every pointwise continuous real-valued function on [0, 1] with a continuous modulus is uniformly continuous. We also show that $\mathsf{DFT}$ is equivalent to a similar principle for real-valued functions on the Cantor space ${\{0,1\}}^{\mathbb{N}}$. These results extend Berger's [2] characterisation of $\mathsf{DFT}$ for integer-valued functions on ${\{0,1\}}^{\mathbb{N}}$ and unify some characterisations of $\mathsf{DFT}$ in terms of functions having continuous moduli.     

When does every definable nonempty set have a definable element?

The assertion that every definable set has a definable element is equivalent over $\mathsf{ZF}$ to the principle $\mathbf{V}=\mathbf{HOD}$, and indeed, we prove, so is the assertion merely that every Π₂‐definable set has an ordinal‐definable element. Meanwhile, every model of $\mathsf{ZFC}$ has a forcing extension satisfying $\mathbf{V}\ne \mathbf{HOD}$ in which every Σ₂‐definable set has an ordinal‐definable element. Similar results hold for $\mathbf{HOD}(\mathbb{R})$ and $\mathbf{HOD}({\mathrm{Ord}}^{\omega })$ and other natural instances of $\mathbf{HOD}(X)$.     

Evolving Shelah-Spencer graphs

We define an evolving Shelah-Spencer process as one by which a random graph grows, with at each time $\tau \in \mathbb{N}$ a new node incorporated and attached to each previous node with probability ${\tau }^{?\alpha }$, where $\alpha \in (0,1)?\mathbb{Q}$ is fixed. We analyse the graphs that result from this process, including the infinite limit, in comparison to Shelah-Spencer sparse random graphs discussed in [21] and throughout the model-theoretic literature. The first order axiomatisation for classical Shelah-Spencer graphs comprises a Generic Extension axiom scheme and a No Dense Subgraphs axiom scheme. We show that in our context Generic Extension continues to hold. While No Dense Subgraphs fails, a weaker Few Rigid Subgraphs property holds.     

Incomparable Vγ$V_\gamma$-degrees

In [3], Shi proved that there exist incomparable Zermelo degrees at γ if there exists an ω-sequence of measurable cardinals, whose limit is γ. He asked whether there is a size ${\gamma }^{\omega }$ antichain of Zermelo degrees. We consider this question for the $V_{\gamma }$-degree structure. We use a kind of Prikry-type forcing to show that if there is an ω-sequence of measurable cardinals, then there are ${\gamma }^{\omega }$-many pairwise incomparable $V_{\gamma }$-degrees, where γ is the limit of the ω-sequence of measurable cardinals.     

Coding of real-valued continuous functions under WKL$\mathsf {WKL}$

In the context of constructive reverse mathematics, we show that weak Kőnig's lemma ($\mathsf{WKL}$) implies that every pointwise continuous function $f:[0,1]\to \mathbb{R}$ is induced by a code in the sense of reverse mathematics. This, combined with the fact that $\mathsf{WKL}$ implies the Fan theorem, shows that $\mathsf{WKL}$ implies the uniform continuity theorem: every pointwise continuous function $f:[0,1]\to \mathbb{R}$ has a modulus of uniform continuity. Our results are obtained in Heyting arithmetic in all finite types with quantifier-free axiom of choice.     

Orders on computable rings

The Artin-Schreier theorem says that every formally real field has orders. Friedman, Simpson and Smith showed in [6] that the Artin-Schreier theorem is equivalent to ${\mathsf{WKL}}_0$ over ${\mathsf{RCA}}_0$. We first prove that the generalization of the Artin-Schreier theorem to noncommutative rings is equivalent to ${\mathsf{WKL}}_0$ over ${\mathsf{RCA}}_0$. In the theory of orderings on rings, following an idea of Serre, we often show the existence of orders on formally real rings by extending pre-orders to orders, where Zorn's lemma is used. We then prove that “pre-orders on rings not necessarily commutative extend to orders” is equivalent to ${\mathsf{WKL}}_0$.     

A note on chain-based semi-Heyting algebras

We determine the number of non-isomorphic semi-Heyting algebras on an n-element chain, where n is a positive integer, using a recursive method. We then prove that the numbers obtained agree with those determined in [1]. We apply the formula to calculate the number of non-isomorphic semi-Heyting chains of a given size in some important subvarieties of the variety of semi-Heyting algebras that were introduced in [5]. We further exploit this recursive method to calculate the numbers $A(n,m)$ of non-isomorphic semi-Heyting chains with n elements such that removing the mth element ($1<m<n$) we are left with a subalgebra. We also solve a related problem posed in [1] of determining the number of ways a semi-Heyting chain with $n-1$ elements can be extended to a n element semi-Heyting chain by adding a new element in the mth place. Finally we combine these results by finding a second way to calculate the numbers $A(n,m)$ that provides some extra information.