- Award ID(s):
- 1905641
- PAR ID:
- 10400300
- Date Published:
- Journal Name:
- International Journal of Algebra and Computation
- Volume:
- 33
- Issue:
- 01
- ISSN:
- 0218-1967
- Page Range / eLocation ID:
- 105 to 122
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths.more » « less
-
For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text].
We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability.
Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic.
Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics.
-
Let [Formula: see text] be a residually finite dimensional algebra (not necessarily associative) over a field [Formula: see text]. Suppose first that [Formula: see text] is algebraically closed. We show that if [Formula: see text] satisfies a homogeneous almost identity [Formula: see text], then [Formula: see text] has an ideal of finite codimension satisfying the identity [Formula: see text]. Using well known results of Zelmanov, we conclude that, if a residually finite dimensional Lie algebra [Formula: see text] over [Formula: see text] is almost [Formula: see text]-Engel, then [Formula: see text] has a nilpotent (respectively, locally nilpotent) ideal of finite codimension if char [Formula: see text] (respectively, char [Formula: see text]). Next, suppose that [Formula: see text] is finite (so [Formula: see text] is residually finite). We prove that, if [Formula: see text] satisfies a homogeneous probabilistic identity [Formula: see text], then [Formula: see text] is a coset identity of [Formula: see text]. Moreover, if [Formula: see text] is multilinear, then [Formula: see text] is an identity of some finite index ideal of [Formula: see text]. Along the way we show that if [Formula: see text] has degree [Formula: see text], and [Formula: see text] is a finite [Formula: see text]-algebra such that the probability that [Formula: see text] (where [Formula: see text] are randomly chosen) is at least [Formula: see text], then [Formula: see text] is an identity of [Formula: see text]. This solves a ring-theoretic analogue of a (still open) group-theoretic problem posed by Dixon,more » « less
-
The Littlewood–Paley decomposition for functions defined on the whole space [Formula: see text] and related Besov space techniques have become indispensable tools in the study of many partial differential equations (PDEs) with [Formula: see text] as the spatial domain. This paper intends to develop parallel tools for the periodic domain [Formula: see text]. Taking advantage of the boundedness and convergence theory on the square-cutoff Fourier partial sum, we define the Littlewood–Paley decomposition for periodic functions via the square cutoff. We remark that the Littlewood–Paley projections defined via the circular cutoff in [Formula: see text] with [Formula: see text] in the literature do not behave well on the Lebesgue space [Formula: see text] except for [Formula: see text]. We develop a complete set of tools associated with this decomposition, which would be very useful in the study of PDEs defined on [Formula: see text]. As an application of the tools developed here, we study the periodic weak solutions of the [Formula: see text]-dimensional Boussinesq equations with the fractional dissipation [Formula: see text] and without thermal diffusion. We obtain two main results. The first assesses the global existence of [Formula: see text]-weak solutions for any [Formula: see text] and the existence and uniqueness of the [Formula: see text]-weak solutions when [Formula: see text] for [Formula: see text]. The second establishes the zero thermal diffusion limit with an explicit convergence rate.more » « less
-
Assume [Formula: see text]. If [Formula: see text] is an ordinal and X is a set of ordinals, then [Formula: see text] is the collection of order-preserving functions [Formula: see text] which have uniform cofinality [Formula: see text] and discontinuous everywhere. The weak partition properties on [Formula: see text] and [Formula: see text] yield partition measures on [Formula: see text] when [Formula: see text] and [Formula: see text] when [Formula: see text]. The following almost everywhere continuity properties for functions on partition spaces with respect to these partition measures will be shown. For every [Formula: see text] and function [Formula: see text], there is a club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. For every [Formula: see text] and function [Formula: see text], there is an [Formula: see text]-club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. The previous two continuity results will be used to distinguish the cardinalities of some important subsets of [Formula: see text]. [Formula: see text]. [Formula: see text]. [Formula: see text]. It will also be shown that [Formula: see text] has the Jónsson property: For every [Formula: see text], there is an [Formula: see text] with [Formula: see text] so that [Formula: see text].