We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on and which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
We show that if ℱ is a hereditary family of subsets of satisfying certain definable conditions, then the reals are precisely the reals α such that . This generalizes the results for measure and category. Appropriate generalization to the higher levels of the projective hierarchy is obtained under Projective Determinacy. Application of this result to the -encodable reals is also shown.
We study the descriptive set theoretical complexity of various randomness notions.
Let be a one-variable function field over a field of constants of characteristic 0. Let be a holomorphy subring of , not equal to . We prove the following undecidability results for : if is recursive, then Hilbert’s Tenth Problem is undecidable in . In general, there exist such that there is no algorithm to tell whether a polynomial equation with coefficients in has solutions in .