Search

This file is composed of questions that emerged or were of interest duringthe workshop "Interactions between Descriptive Set Theory and Smooth Dynamics"that took place in Banff, Canada on 2022.

The paper considers the equivalence relation of conjugacy-by-homeomorphism ondiffeomorphisms of smooth manifolds. In dimension 2 and above it is shown thatthere is no Borel method of attaching complete numerical invariants. Indimension 5 and above it is shown that the equivalence relation is not Borel,and in fact is complete analytic.

Abstract We continue the study of n-dependent groups, fields and related structures, largely motivated by the conjecture that every n-dependent field is dependent. We provide evidence toward this conjecture by showing that every infinite n-dependent valued field of positive characteristic is henselian, obtaining a variant of Shelah’s Henselianity Conjecture in this case and generalizing a recent result of Johnson for dependent fields. Additionally, we prove a result on intersections of type-definable connected components over generic sets of parameters in n-dependent groups, generalizing Shelah’s absoluteness of $G^{00}$ in dependent theories and relative absoluteness of $G^{00}$ in $2$ -dependent theories. In an effort to clarify the scope of this conjecture, we provide new examples of strictly $2$ -dependent fields with additional structure, showing that Granger’s examples of non-degenerate bilinear forms over dependent fields are $2$ -dependent. Along the way, we obtain some purely model-theoretic results of independent interest: we show that n-dependence is witnessed by formulas with all but one variable singletons; provide a type-counting criterion for $2$ -dependence and use it to deduce $2$ -dependence for compositions of dependent relations with arbitrary binary functions (the Composition Lemma); and show that an expansion of a geometric theory T by a generic predicate is dependent if and only if it is n-dependent for some n, if and only if the algebraic closure in T is disintegrated. An appendix by Martin Bays provides an explicit isomorphism in the Kaplan-Scanlon-Wagner theorem.

We generalize the fact that graphs with small VC-dimension can beapproximated by rectangles, showing that hypergraphs with small VC_k-dimension(equivalently, omitting a fixed finite (k+1)-partite (k+1)-uniform hypergraph)can be approximated by k-ary cylinder sets. In the language of hypergraph regularity, this shows that when H is ak'-uniform hypergraph with small VC_k-dimension for some k

We establish a cutting lemma for definable families of sets in distalstructures, as well as the optimality of the distal cell decomposition fordefinable families of sets on the plane in $o$-minimal expansions of fields.Using it, we generalize the results in [J. Fox, J. Pach, A. Sheffer, A. Suk,and J. Zahl. "A semi-algebraic version of Zarankiewicz's problem"] on thesemialgebraic planar Zarankiewicz problem to arbitrary $o$-minimal structures,in particular obtaining an $o$-minimal generalization of theSzemer\'edi-Trotter theorem.

AbstractWe prove that every ultraproduct of p-adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic 0 in the RV language.

We show that the Abraham-Rubin-Shelah Open Coloring Axiom is consistent witha large continuum, in particular, consistent with $2^{\aleph_0}=\aleph_3$. Thisanswers one of the main open questions from the 1985 paper ofAbraham-Rubin-Shelah. As in their paper, we need to construct names forso-called preassignments of colors in order to add the necessary homogeneoussets. However, these names are constructed over models satisfying the CH. Inorder to address this difficulty, we show how to construct such names with verystrong symmetry conditions. This symmetry allows us to combine them in manydifferent ways, using a new type of poset called a Partition Product, andthereby obtain a model of this axiom in which $2^{\aleph_0}=\aleph_3$.

Mekler's construction gives an interpretation of any structure in a finiterelational language in a group (nilpotent of class $2$ and exponent $p>2$, butnot finitely generated in general). Even though this construction is not abi-interpretation, it is known to preserve some model-theoretic tamenessproperties of the original structure including stability and simplicity. Wedemonstrate that $k$-dependence of the theory is preserved, for all $k \in\mathbb{N}$, and that NTP$_2$ is preserved. We apply this result to obtainfirst examples of strictly $k$-dependent groups (with no additional structure).

In this note we develop and clarify some of the basic combinatorialproperties of the new notion of $n$-dependence (for $1\leq n < \omega$)recently introduced by Shelah. In the same way as dependence of a theory meansits inability to encode a bipartite random graph with a definable edgerelation, $n$-dependence corresponds to the inability to encode a random$(n+1)$-partite $(n+1)$-hypergraph with a definable edge relation. Mostimportantly, we characterize $n$-dependence by counting $\varphi$-types overfinite sets (generalizing Sauer-Shelah lemma and answering a question ofShelah) and in terms of the collapse of random ordered $(n+1)$-hypergraphindiscernibles down to order-indiscernibles (which implies that the failure of$n$-dependence is always witnessed by a formula in a single free variable).

We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension and show that the two notions are independent. For any real number a greater than or equal to 2 and any non-negative real b be less than or equal to 2 / a, we show that there is a Cantor-like set with Hausdorff dimension equal to b such that, with respect to its uniform measure, almost all real numbers have irrationality exponent equal to a. We give an analogous result relating the irrationality exponent and the effective Hausdorff dimension of individual real numbers. We prove that there is a Cantor-like set such that, with respect to its uniform measure, almost all elements in the set have effective Hausdorff dimension equal to b and irrationality exponent equal to a. In each case, we obtain the desired set as a distinguished path in a tree of Cantor sets.

We prove a generalizations of the Elekes-Szab\'o theorem for relationsdefinable in strongly minimal structures that are interpretable in distalstructures.

Let $\mathscr{L}$ be a recursive language. Let $S(\mathscr{L})$ be the set of$\mathscr{L}$-structures with domain $\omega$. Let $\Phi : {}^\omega 2\rightarrow S(\mathscr{L})$ be a $\Delta_1^1$ function with the property thatfor all $x,y \in {}^\omega 2$, $\omega_1^x = \omega_1^y$ if and only if$\Phi(x) \approx_{\mathscr{L}} \Phi(y)$. Then there is some $x \in {}^\omega 2$so that $\mathrm{SR}(\Phi(x)) = \omega_1^x + 1$.

The Denjoy integral is an integral that extends the Lebesgue integral and canintegrate any derivative. In this paper, it is shown that the graph of theindefinite Denjoy integral $f\mapsto \int_a^x f$ is a coanalytic non-Borelrelation on the product space $M[a,b]\times C[a,b]$, where $M[a,b]$ is thePolish space of real-valued measurable functions on $[a,b]$ and where $C[a,b]$is the Polish space of real-valued continuous functions on $[a,b]$. Using thesame methods, it is also shown that the class of indefinite Denjoy integrals,called $ACG_{\ast}[a,b]$, is a coanalytic but not Borel subclass of the space$C[a,b]$, thus answering a question posed by Dougherty and Kechris. Some basicmodel theory of the associated spaces of integrable functions is also studied.Here the main result is that, when viewed as an $\mathbb{R}[X]$-module with theindeterminate $X$ being interpreted as the indefinite integral, the space ofcontinuous functions on the interval $[a,b]$ is elementarily equivalent to theLebesgue-integrable and Denjoy-integrable functions on this interval, and eachis stable but not superstable, and that they all have a common decidable theorywhen viewed as $\mathbb{Q}[X]$-modules.

Abstract: A semantics for quantified modal logic is presented that is based on Kleene’s notion of realizability. This semantics generalizes Flagg’s 1985 construction of a model of a modal version of Church’s Thesis and first-order arithmetic. While the bulk of the paper is devoted to developing the details of the semantics, to illustrate the scope of this approach, we show that the construction produces (i) a model of a modal version of Church’s Thesis and a variant of a modal set theory due to Goodman and Scedrov, (ii) a model of a modal version of Troelstra’s generalized continuity principle together with a fragment of second-order arithmetic, and (iii) a model based on Scott’s graph model (for the untyped lambda calculus) which witnesses the failure of the stability of nonidentity.

For an infinite cardinal κ, let ded κ denote the supremum of the number of Dedekind cuts in linear orders of size κ. It is known that κ < ded κ ≤2κ for all κ and that ded κ < 2κ is consistent for any κ of uncountable cofinality. We prove however that 2κ≤ ded(ded(ded(ded κ))) always holds. Using this result we calculate the Hanf numbers for the existence of two-cardinal models with arbitrarily large gaps and for the existence of arbitrarily large models omitting a type in the class of countable dependent first-order theories. Specifically, we show that these bounds are as large as in the class of all countable theories.

This article surveys recent literature by Parsons, McGee, Shapiro and otherson the significance of categoricity arguments in the philosophy of mathematics.After discussing whether categoricity arguments are sufficient to securereference to mathematical structures up to isomorphism, we assess what exactlyis achieved by recent `internal' renditions of the famous categoricityarguments for arithmetic and set theory.

We present a systematic study of the regularity phenomena for NIP hypergraphsand connections to the theory of (locally) generically stable measures,providing a model-theoretic hypergraph version of the results from [L.Lov\'asz, B. Szegedy, "Regularity partitions and the topology of graphons", Anirregular mind, Springer Berlin Heidelberg, 2010, 415-446]. Besides, we revisethe two extremal cases of regularity for stable and distal hypergraphs,improving and generalizing the results from [A. Chernikov, S. Starchenko,"Regularity lemma for distal structures", J. Eur. Math. Soc. 20 (2018),2437-2466] and [M. Malliaris, S. Shelah, "Regularity lemmas for stable graphs",Transactions of the American Mathematical Society, 366.3, 2014, 1551-1585].Finally, we consider a related question of the existence of large(approximately) homogeneous definable subsets of NIP hypergraphs and providesome positive results and counterexamples.

This paper sets out a predicative response to the Russell-Myhill paradox ofpropositions within the framework of Church's intensional logic. A predicativeresponse places restrictions on the full comprehension schema, which assertsthat every formula determines a higher-order entity. In addition to motivatingthe restriction on the comprehension schema from intuitions about the stabilityof reference, this paper contains a consistency proof for the predicativeresponse to the Russell-Myhill paradox. The models used to establish thisconsistency also model other axioms of Church's intensional logic that havebeen criticized by Parsons and Klement: this, it turns out, is due to resourceswhich also permit an interpretation of a fragment of Gallin's intensionallogic. Finally, the relation between the predicative response to theRussell-Myhill paradox of propositions and the Russell paradox of sets isdiscussed, and it is shown that the predicative conception of set induced bythis predicative intensional logic allows one to respond to the Wehmeierproblem of many non-extensions.

Abstract: Frege’sGrundgesetzewas one of the 19th century forerunners to contemporary set theory which was plagued by the Russell paradox. In recent years, it has been shown that subsystems of theGrundgesetzeformed by restricting the comprehension schema are consistent. One aim of this paper is to ascertain how much set theory can be developed within these consistent fragments of theGrundgesetze, and our main theorem (Theorem 2.9) shows that there is a model of a fragment of theGrundgesetzewhich defines a model of all the axioms of Zermelo–Fraenkel set theory with the exception of the power set axiom. The proof of this result appeals to Gödel’s constructible universe of sets and to Kripke and Platek’s idea of the projectum, as well as to a weak version of uniformization (which does not involve knowledge of Jensen’s fine structure theory). The axioms of theGrundgesetzeare examples ofabstraction principles, and the other primary aim of this paper is to articulate a sufficient condition for the consistency of abstraction principles with limited amounts of comprehension (Theorem 3.5). As an application, we resolve an analogue of the joint consistency problem in the predicative setting.

Abstract: Frege’s theorem says that second-order Peano arithmetic is interpretable in Hume’s Principle and full impredicative comprehension. Hume’s Principle is one example of anabstraction principle, while another paradigmatic example is Basic Law V from Frege’sGrundgesetze. In this paper we study the strength of abstraction principles in the presence of predicative restrictions on the comprehension schema, and in particular we study a predicative Fregean theory which contains all the abstraction principles whose underlying equivalence relations can be proven to be equivalence relations in a weak background second-order logic. We show that this predicative Fregean theory interprets second-order Peano arithmetic (cf. Theorem 3.2).

There is a fascinating interplay and overlap between recursion theory anddescriptive set theory. A particularly beautiful source of such interaction hasbeen Martin's conjecture on Turing invariant functions. This longstanding openproblem in recursion theory has connected to many problems in descriptive settheory, particularly in the theory of countable Borel equivalence relations. In this paper, we shall give an overview of some work that has been done onMartin's conjecture, and applications that it has had in descriptive settheory. We will present a long unpublished result of Slaman and Steel thatarithmetic equivalence is a universal countable Borel equivalence relation.This theorem has interesting corollaries for the theory of universal countableBorel equivalence relations in general. We end with some open problems, anddirections for future research.

© 2015 The Author(s) We consider certain families of automorphic representations over number fields arising from the principle of functoriality of Langlands. Let (Formula presented.) be a reductive group over a number field (Formula presented.) which admits discrete series representations at infinity. Let (Formula presented.) be the associated (Formula presented.)-group and (Formula presented.) a continuous homomorphism which is irreducible and does not factor through (Formula presented.). The families under consideration consist of discrete automorphic representations of (Formula presented.) of given weight and level and we let either the weight or the level grow to infinity. We establish a quantitative Plancherel and a quantitative Sato–Tate equidistribution theorem for the Satake parameters of these families. This generalizes earlier results in the subject, notably of Sarnak (Prog Math 70:321–331, 1987) and Serre (J Am Math Soc 10(1):75–102, 1997). As an application we study the distribution of the low-lying zeros of the associated family of (Formula presented.)-functions (Formula presented.), assuming from the principle of functoriality that these (Formula presented.)-functions are automorphic. We find that the distribution of the (Formula presented.)-level densities coincides with the distribution of the (Formula presented.)-level densities of eigenvalues of one of the unitary, symplectic and orthogonal ensembles, in accordance with the Katz–Sarnak heuristics. We provide a criterion based on the Frobenius–Schur indicator to determine this symmetry type. If (Formula presented.) is not isomorphic to its dual (Formula presented.) then the symmetry type is unitary. Otherwise there is a bilinear form on (Formula presented.) which realizes the isomorphism between (Formula presented.) and (Formula presented.). If the bilinear form is symmetric (resp. alternating) then (Formula presented.) is real (resp. quaternionic) and the symmetry type is symplectic (resp. orthogonal).

H\"older-Brascamp-Lieb inequalities provide upper bounds for a class ofmultilinear expressions, in terms of $L^p$ norms of the functions involved.They have been extensively studied for functions defined on Euclidean spaces.Bennett-Carbery-Christ-Tao have initiated the study of these inequalities fordiscrete Abelian groups and, in terms of suitable data, have characterized theset of all tuples of exponents for which such an inequality holds for specifieddata, as the convex polyhedron defined by a particular finite set of affineinequalities. In this paper we advance the theory of such inequalities for torsion-freediscrete Abelian groups in three respects. The optimal constant in any suchinequality is shown to equal $1$ whenever it is finite. An algorithm thatcomputes the admissible polyhedron of exponents is developed. It is shown thatnonetheless, existence of an algorithm that computes the full list ofinequalities in the Bennett-Carbery-Christ-Tao description of the admissiblepolyhedron for all data, is equivalent to an affirmative solution of Hilbert'sTenth Problem over the rationals. That problem remains open. Applications to computer science will be explored in a forthcoming companionpaper.

Abstract: Many recent writers in the philosophy of mathematics have put great weight on the relative categoricity of the traditional axiomatizations of our foundational theories of arithmetic and set theory (Parsons, 1990; Parsons, 2008, sec. 49; McGee, 1997; Lavine, 1999; Väänänen & Wang, 2014). Another great enterprise in contemporary philosophy of mathematics has been Wright’s and Hale’s project of founding mathematics on abstraction principles (Hale & Wright, 2001; Cook, 2007). In Walsh (2012), it was noted that one traditional abstraction principle, namely Hume’s Principle, had a certain relative categoricity property, which here we termnatural relative categoricity. In this paper, we show that most other abstraction principles arenotnaturally relatively categorical, so that there is in fact a large amount of incompatibility between these two recent trends in contemporary philosophy of mathematics. To better understand the precise demands of relative categoricity in the context of abstraction principles, we compare and contrast these constraints to (i) stability-like acceptability criteria on abstraction principles (cf. Cook, 2012), (ii) the Tarski-Sher logicality requirements on abstraction principles studied by Antonelli (2010b) and Fine (2002), and (iii) supervaluational ideas coming out of the work of Hodes (1984, 1990, 1991).

We continue investigating the structure of externally definable sets in NIP theories and preservation of NIP after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; over a model, a family of non-forking instances of a formula (with parameters ranging over a type-definable set) can be covered with finitely many invariant types; we give some criteria for the boundedness of an expansion by a new predicate in a distal theory; naming an arbitrary small indiscernible sequence preserves NIP, while naming a large one doesn’t; there are models of NIP theories over which all 1-types are definable, but not all n-types.

© 2015 The Author(s) We consider certain families of automorphic representations over number fields arising from the principle of functoriality of Langlands. Let (Formula presented.) be a reductive group over a number field (Formula presented.) which admits discrete series representations at infinity. Let (Formula presented.) be the associated (Formula presented.)-group and (Formula presented.) a continuous homomorphism which is irreducible and does not factor through (Formula presented.). The families under consideration consist of discrete automorphic representations of (Formula presented.) of given weight and level and we let either the weight or the level grow to infinity. We establish a quantitative Plancherel and a quantitative Sato–Tate equidistribution theorem for the Satake parameters of these families. This generalizes earlier results in the subject, notably of Sarnak (Prog Math 70:321–331, 1987) and Serre (J Am Math Soc 10(1):75–102, 1997). As an application we study the distribution of the low-lying zeros of the associated family of (Formula presented.)-functions (Formula presented.), assuming from the principle of functoriality that these (Formula presented.)-functions are automorphic. We find that the distribution of the (Formula presented.)-level densities coincides with the distribution of the (Formula presented.)-level densities of eigenvalues of one of the unitary, symplectic and orthogonal ensembles, in accordance with the Katz–Sarnak heuristics. We provide a criterion based on the Frobenius–Schur indicator to determine this symmetry type. If (Formula presented.) is not isomorphic to its dual (Formula presented.) then the symmetry type is unitary. Otherwise there is a bilinear form on (Formula presented.) which realizes the isomorphism between (Formula presented.) and (Formula presented.). If the bilinear form is symmetric (resp. alternating) then (Formula presented.) is real (resp. quaternionic) and the symmetry type is symplectic (resp. orthogonal).

We study properties of a group, abelian group, ring, or monoid B which (a) guarantee that every homomorphism from an infinite direct product ΠI Ai of objects of the same sort onto B factors through the direct product of finitely many ultraproducts of the Ai (possibly after composition with the natural map B → B/Z(B) or some variant), and/or (b) guarantee that when a map does so factor (and the index set has reasonable cardinality), the ultrafilters involved must be principal. A number of open questions and topics for further investigation are noted.

NTP2 is a large class of first-order theories defined by Shelah generalizing simple and NIP theories. Algebraic examples of NTP2 structures are given by ultra-products of p-adics and certain valued difference fields (such as a non-standard Frobenius automorphism living on an algebraically closed valued field of characteristic 0). In this note we present some results on groups and fields definable in NTP2 structures. Most importantly, we isolate a chain condition for definable normal subgroups and use it to show that any NTP2 field has only finitely many Artin-Schreier extensions. We also discuss a stronger chain condition coming from imposing bounds on burden of the theory (an appropriate analogue of weight) and show that every strongly dependent valued field is Kaplansky.

We show that the theory of the non-standard Frobenius automorphism, acting on an algebraically closed valued field of equal characteristic 0, is NTP2. More generally, in the contractive as well as in the isometric case, we prove that a σ-Henselian valued difference field of equicharacteristic 0 is NTP2, provided both the residue difference field and the value group (as an ordered difference group) are NTP2.

Most discussions of G\"odel's theorems fall into one of two types: either they emphasize perceived philosophical, cultural "meanings" of the theorems, and perhaps sketch some of the ideas of the proofs, usually relating G\"odel's proofs to riddles and paradoxes, but do not attempt to present rigorous, complete proofs; or they do present rigorous proofs, but in the traditional style of mathematical logic, with all of its heavy notation and difficult definitions, and technical issues which reflect G\"odel's original approach and broader logical issues. Many non-specialists are frustrated by these two extreme types of expositions and want a complete, rigorous proof that they can understand. Such an exposition is possible, because many people have realized that variants of G\"odel's first incompleteness theorem can be rigorously proved by a simpler middle approach, avoiding philosophical discussions and hand-waiving at one extreme; and also avoiding the heavy machinery of traditional mathematical logic, and many of the harder detail's of G\"odel's original proof, at the other extreme. This is the just-right Goldilocks approach. In this exposition we give a short, self-contained Goldilocks exposition of G\"odel's first theorem, aimed at a broad, undergraduate audience.

NTP2 is a large class of first-order theories defined by Shelah generalizing simple and NIP theories. Algebraic examples of NTP2 structures are given by ultra-products of p-adics and certain valued difference fields (such as a non-standard Frobenius automorphism living on an algebraically closed valued field of characteristic 0). In this note we present some results on groups and fields definable in NTP2 structures. Most importantly, we isolate a chain condition for definable normal subgroups and use it to show that any NTP2 field has only finitely many Artin-Schreier extensions. We also discuss a stronger chain condition coming from imposing bounds on burden of the theory (an appropriate analogue of weight) and show that every strongly dependent valued field is Kaplansky.

We prove that many properties and invariants of definable groups in NIP theories (i.e. theories without the independence property), such as definable amenability, G/G^{00}, etc., are preserved when passing to the theory of the Shelah expansion by externally definable sets, M^{\operatorname {ext} }, of a model M. In the light of these results, we continue the study of the 'definable topological dynamics' of groups in \operatorname {NIP} theories. In particular, we prove the Ellis group conjecture relating the Ellis group to G/G^{00} in some new cases, including definably amenable groups in o-minimal structures. © 2014 London Mathematical Society.

Criteria are obtained for a filter F of subsets of a set I to be an intersection of finitely many ultrafilters, respectively, finitely many κ-complete ultrafilters for a given uncountable cardinal κ. From these, general results are deduced concerning homomorphisms on infinite direct product groups, which yield quick proofs of some results in the literature: the Łoś–Eda theorem (characterizing homomorphisms from a not-necessarily-countable direct product of modules to a slender module), and some results of Nahlus and the author on homomorphisms on infinite direct products of not-necessarily-associative k-algebras. The same tools allow other results of Nahlus and the author to be nontrivially strengthened, and yield an analog to one of their results, with nonabelian groups taking the place of k-algebras. We briefly examine the question of how the common technique used in applying the general results of this note to k-algebras on the one hand, and to nonabelian groups on the other, might be extended to more general varieties of algebras in the sense of universal algebra. In a final section, the Erd˝os–Kaplansky theorem on dimensions of vector spaces DI (D a division ring) is extended to reduced products DI /F, and an application is noted.

We establish several results regarding dividing and forking in NTP2 theories. We show that dividing is the same as array-dividing. Combining it with existence of strictly invariant sequences we deduce that forking satisfies the chain condition over extension bases (namely, the forking ideal is S1, in Hrushovski’s terminology). Using it we prove an independence theorem over extension bases (which, in the case of simple theories, specializes to the ordinary independence theorem). As an application we show that Lascar strong type and compact strong type coincide over extension bases in an NTP2 theory. We also define the dividing order of a theory—a generalization of Poizat’s fundamental order fromstable theories—and give some equivalent characterizations under the assumption of NTP2. The last section is devoted to a refinement of the class of strong theories and its place in the classification hierarchy.

We initiate a systematic study of the class of theories without the tree property of the second kind - NTP2. Most importantly, we show: the burden is "sub-multiplicative" in arbitrary theories (in particular, if a theory has TP2 then there is a formula with a single variable witnessing this); NTP2 is equivalent to the generalized Kim's lemma and to the boundedness of ist-weight; the dp-rank of a type in an arbitrary theory is witnessed by mutually indiscernible sequences of realizations of the type, after adding some parameters - so the dp-rank of a 1-type in any theory is always witnessed by sequences of singletons; in NTP2 theories, simple types are co-simple, characterized by the co-independence theorem, and forking between the realizations of a simple type and arbitrary elements satisfies full symmetry; a Henselian valued field of characteristic (0, 0) is NTP2 (strong, of finite burden) if and only if the residue field is NTP2 (the residue field and the value group are strong, of finite burden respectively), so in particular any ultraproduct of p-adics is NTP2; adding a generic predicate to a geometric NTP2 theory preserves NTP2. © 2013 Elsevier B.V.

This paper presents new constructions of models of Hume's Principle and BasicLaw V with restricted amounts of comprehension. The techniques used in theseconstructions are drawn from hyperarithmetic theory and the model theory offields, and formalizing these techniques within various subsystems ofsecond-order Peano arithmetic allows one to put upper and lower bounds on theinterpretability strength of these theories and hence to compare these theoriesto the canonical subsystems of second-order arithmetic. The main results ofthis paper are: (i) there is a consistent extension of the hyperarithmeticfragment of Basic Law V which interprets the hyperarithmetic fragment ofsecond-order Peano arithmetic, and (ii) the hyperarithmetic fragment of Hume'sPrinciple does not interpret the hyperarithmetic fragment of second-order Peanoarithmetic, so that in this specific sense there is no predicative version ofFrege's Theorem.

In this short note we show that if we add predicate for a dense completeindiscernible sequence in a dependent theory then the result is stilldependent. This answers a question of Baldwin and Benedikt and implies thatevery unstable dependent theory has a dependent expansion interpreting linearorder.

From among (n/3) triangles with vertices chosen from n points in the unit square, let T be the one with the smallest area, and let A be the area of T. Heilbronn's triangle problem asks for the maximum value assumed by A over all choices of n points. We consider the average-case: If the n points are chosen independently and at random (with a uniform distribution), then there exist positive constants c and C such that c/n3 < μn < C/n3 for all large enough values of n, where μn is the expectation of A. Moreover, c/n3 < A < C/n3, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in "general position." © 2002 Wiley Periodicals, Inc.

It is proved undecidable in ZFC + GCH whether every Z-module has a^{perp}{Z}-precover.

We show that it is consistent that there is a strongly aleph_1-freealeph_1-coseparable group of cardinality aleph_1 which is notaleph_1-separable.

As a consequence of identifying the principle described in the title, weprove that for any uncountable cardinal lambda, if there is a lambda-freeWhitehead group of cardinality lambda which is not free, then there are many``nice'' Whitehead groups of cardinality lambda which are not free.

We investigate conditions under which a co-computably enumerable set in a computable metric space is computable. Using higher-dimensional chains and spherical chains we prove that in each computable metric space which is locally computable each co-computably enumerable sphere is computable and each co-c.e. cell with co-c.e. boundary sphere is computable.

Consider a linear ordering equipped with a finite sequence of monadic predicates. If the ordering contains an interval of order type \omega or -\omega, and the monadic second-order theory of the combined structure is decidable, there exists a non-trivial expansion by a further monadic predicate that is still decidable.