Abstract For any subset$$Z \subseteq {\mathbb {Q}}$$, consider the set$$S_Z$$of subfields$$L\subseteq {\overline {\mathbb {Q}}}$$which contain a co-infinite subset$$C \subseteq L$$that is universally definable inLsuch that$$C \cap {\mathbb {Q}}=Z$$. Placing a natural topology on the set$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$of subfields of$${\overline {\mathbb {Q}}}$$, we show that ifZis not thin in$${\mathbb {Q}}$$, then$$S_Z$$is meager in$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$. Here,thinandmeagerboth mean “small”, in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fieldsLhave the property that the ring of algebraic integers$$\mathcal {O}_L$$is universally definable inL. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every$$\exists $$-definable subset of an algebraic extension of$${\mathbb Q}$$is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials.
more »
« less
GADTs are not (Even partial) functors
Abstract Generalized Algebraic Data Types(GADTs) are a syntactic generalization of the usual algebraic data types (ADTs), such as lists, trees, etc. ADTs’ standard initial algebra semantics (IAS) in the category$$\mathit{Set}$$of sets justify critical syntactic constructs – such as recursion, pattern matching, and fold – for programming with them. In this paper, we show that semantics for GADTs that specialize to the IAS for ADTs are necessarily unsatisfactory. First, we show that the functorial nature of such semantics for GADTs in$$\mathit{Set}$$introducesghostelements, i.e., elements not writable in syntax. Next, we show how such ghost elements break parametricity. We observe that the situation for GADTs contrasts dramatically with that for ADTs, whose IAS coincides with the parametric model constructed via their Church encodings in System F. Our analysis reveals that the fundamental obstacle to giving a functorial IAS for GADTs is the inherently partial nature of their map functions. We show that this obstacle cannot be overcome by replacing$$\mathit{Set}$$with other categories that account for this partiality.
more »
« less
- Award ID(s):
- 2203217
- PAR ID:
- 10612398
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Mathematical Structures in Computer Science
- Volume:
- 34
- Issue:
- 10
- ISSN:
- 0960-1295
- Page Range / eLocation ID:
- 1079 to 1102
- Subject(s) / Keyword(s):
- GADTs functorial semantics (higher-order) initial algebra semantics partial functions
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We considerG, a linear algebraic group defined over$$\Bbbk $$, an algebraically closed field (ACF). By considering$$\Bbbk $$as an embedded residue field of an algebraically closed valued fieldK, we can associate to it a compactG-space$$S^\mu _G(\Bbbk )$$consisting of$$\mu $$-types onG. We show that for each$$p_\mu \in S^\mu _G(\Bbbk )$$,$$\mathrm {Stab}^\mu (p)=\mathrm {Stab}\left (p_\mu \right )$$is a solvable infinite algebraic group when$$p_\mu $$is centered at infinity and residually algebraic. Moreover, we give a description of the dimension of$$\mathrm {Stab}\left (p_\mu \right )$$in terms of the dimension ofp.more » « less
-
Abstract This is the second installment in a series of papers applying descriptive set theoretic techniques to both analyze and enrich classical functors from homological algebra and algebraic topology. In it, we show that the Čech cohomology functorson the category of locally compact separable metric spaces each factor into (i) what we term theirdefinable version, a functortaking values in the category$$\mathsf {GPC}$$ofgroups with a Polish cover(a category first introduced in this work’s predecessor), followed by (ii) a forgetful functor from$$\mathsf {GPC}$$to the category of groups. These definable cohomology functors powerfully refine their classical counterparts: we show that they are complete invariants, for example, of the homotopy types of mapping telescopes ofd-spheres ord-tori for any$$d\geq 1$$, and, in contrast, that there exist uncountable families of pairwise homotopy inequivalent mapping telescopes of either sort on which the classical cohomology functors are constant. We then apply the functorsto show that a seminal problem in the development of algebraic topology – namely, Borsuk and Eilenberg’s 1936 problem of classifying, up to homotopy, the maps from a solenoid complement$$S^3\backslash \Sigma $$to the$$2$$-sphere – is essentially hyperfinite but not smooth. Fundamental to our analysis is the fact that the Čech cohomology functorsadmit two main formulations: a more combinatorial one and a more homotopical formulation as the group$$[X,P]$$of homotopy classes of maps fromXto a polyhedral$$K(G,n)$$spaceP. We describe the Borel-definable content of each of these formulations and prove a definable version of Huber’s theorem reconciling the two. In the course of this work, we record definable versions of Urysohn’s Lemma and the simplicial approximation and homotopy extension theorems, along with a definable Milnor-type short exact sequence decomposition of the space$$\mathrm {Map}(X,P)$$in terms of its subset ofphantom maps; relatedly, we provide a topological characterization of this set for any locally compact Polish spaceXand polyhedronP. In aggregate, this work may be more broadly construed as laying foundations for the descriptive set theoretic study of the homotopy relation on such spaces$$\mathrm {Map}(X,P)$$, a relation which, together with the more combinatorial incarnation of, embodies a substantial variety of classification problems arising throughout mathematics. We show, in particular, that ifPis a polyhedralH-group, then this relation is both Borel and idealistic. In consequence,$$[X,P]$$falls in the category ofdefinable groups, an extension of the category$$\mathsf {GPC}$$introduced herein for its regularity properties, which facilitate several of the aforementioned computations.more » « less
-
Abstract For$$E \subset \mathbb {N}$$, a subset$$R \subset \mathbb {N}$$isE-intersectiveif for every$$A \subset E$$having positive relative density,$$R \cap (A - A) \neq \varnothing $$. We say thatRischromatically E-intersectiveif for every finite partition$$E=\bigcup _{i=1}^k E_i$$, there existsisuch that$$R\cap (E_i-E_i)\neq \varnothing $$. When$$E=\mathbb {N}$$, we recover the usual notions of intersectivity and chromatic intersectivity. We investigate to what extent the known intersectivity results hold in the relative setting when$$E = \mathbb {P}$$, the set of primes, or other sparse subsets of$$\mathbb {N}$$. Among other things, we prove the following: (1) the set of shifted Chen primes$$\mathbb {P}_{\mathrm {Chen}} + 1$$is both intersective and$$\mathbb {P}$$-intersective; (2) there exists an intersective set that is not$$\mathbb {P}$$-intersective; (3) every$$\mathbb {P}$$-intersective set is intersective; (4) there exists a chromatically$$\mathbb {P}$$-intersective set which is not intersective (and therefore not$$\mathbb {P}$$-intersective).more » « less
-
Abstract Let$$\mathrm {R}$$be a real closed field. Given a closed and bounded semialgebraic set$$A \subset \mathrm {R}^n$$and semialgebraic continuous functions$$f,g:A \rightarrow \mathrm {R}$$such that$$f^{-1}(0) \subset g^{-1}(0)$$, there exist an integer$$N> 0$$and$$c \in \mathrm {R}$$such that the inequality (Łojasiewicz inequality)$$|g(x)|^N \le c \cdot |f(x)|$$holds for all$$x \in A$$. In this paper, we consider the case whenAis defined by a quantifier-free formula with atoms of the form$$P = 0, P>0, P \in \mathcal {P}$$for some finite subset of polynomials$$\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_n]_{\leq d}$$, and the graphs of$$f,g$$are also defined by quantifier-free formulas with atoms of the form$$Q = 0, Q>0, Q \in \mathcal {Q}$$, for some finite set$$\mathcal {Q} \subset \mathrm {R}[X_1,\ldots ,X_n,Y]_{\leq d}$$. We prove that the Łojasiewicz exponent in this case is bounded by$$(8 d)^{2(n+7)}$$. Our bound depends ondandnbut is independent of the combinatorial parameters, namely the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. The previous best-known upper bound in this generality appeared inP. Solernó, Effective Łojasiewicz Inequalities in Semi-Algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991)and depended on the sum of degrees of the polynomials defining$$A,f,g$$and thus implicitly on the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. As a consequence, we improve the current best error bounds for polynomial systems under some conditions. Finally, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common upper bound on the Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)).more » « less
An official website of the United States government

