Search

For which choices of $X,Y,Z\in\{\Sigma^1_1,\Pi^1_1\}$ does no sufficiently strong $X$-sound and $Y$-definable extension theory prove its own $Z$-soundness? We give a complete answer, thereby delimiting the generalizations of G\"odel's second incompleteness theorem that hold within second-order arithmetic.

For $n \in \mathbb{N}$ and $\varepsilon > 0$, given a sufficiently long sequence of events in a probability space all of measure at least $\varepsilon$, some $n$ of them will have a common intersection. A more subtle pattern: for any $0 < p < q < 1$, we cannot find events $A_i$ and $B_i$ so that $\mu \left( A_i \cap B_j \right) \leq p$ and $\mu \left( A_j \cap B_i\right) \geq q$ for all $1 < i < j < n$, assuming $n$ is sufficiently large. This is closely connected to model-theoretic stability of probability algebras. We survey some results from our recent work on more complicated patterns that arise when our events are indexed by multiple indices. In particular, how such results are connected to higher arity generalizations of de Finetti's theorem in probability, structural Ramsey theory, hypergraph regularity in combinatorics, and model theory., Comment: 6 pages; to appear in the Proceedings of the 14th Panhellenic Logic Symposium

It is often convenient to represent a process for randomly generating a graph as a graphon. (More precisely, these give \emph{vertex exchangeable} processes -- those processes in which each vertex is treated the same way.) Other structures can be treated by generalizations like hypergraphons, permutatons, and, for a very general class, theons. These representations are not unique: different representations can lead to the same probability distribution on graphs. This naturally leads to questions (going back at least to Hoover's proof of the Aldous--Hoover Theorem on the existence of such representations) that ask when quasirandomness properties on the distribution guarantee the existence of particularly simple representations. We extend the usual theon representation by adding an additional datum of a random permutation to each tuple, which we call a $\ast$-representation. We show that if a process satisfies the \emph{unique coupling} property UCouple[$\ell$], which says roughly that all $\ell$-tuples of vertices ``look the same'', then the process is $\ast$-$\ell$-independent: there is a $\ast$-representation that does not make use of any random information about $\ell$-tuples (including tuples of length $<\ell$). Simple examples show that the use of $\ast$-representations is necessary. This resolves a question of Coregliano and Razborov, since it easily follows that UCouple[l] implies Independence[\ell'] (the existence of an $\ell'$-independent ordinary representation) for $\ell'<\ell$.

In this paper we give an ordinal analysis of the theory of second order arithmetic. We do this by working with proof trees -- that is, "deductions" which may not be well-founded. Working in a suitable theory, we are able to represent functions on proof trees as yet further proof trees satisfying a suitable analog of well-foundedness. Iterating this process allows us to represent higher order functions as well: since functions on proof trees are just proof trees themselves, these functions can easily be extended to act on proof trees which are themselves understood as functions. The corresponding system of ordinals parallels this, using higher order collapsing function., Comment: Work in progress

We investigate various forms of (model-theoretic) stability for hypergraphs and their corresponding strengthenings of the hypergraph regularity lemma with respect to partitions of vertices. On the one hand, we provide a complete classification of the various possibilities in the ternary case. On the other hand, we provide an example of a family of slice-wise stable 3-hypergraphs so that for no partition of the vertices, any triple of parts has density close to 0 or 1. In particular, this addresses some questions and conjectures of Terry and Wolf. We work in the general measure theoretic context of graded probability spaces, so all our results apply both to measures in ultraproducts of finite graphs, leading to the aforementioned combinatorial applications, and to commuting definable Keisler measures, leading to applications in model theory., Comment: 67 pages

Quantifier elimination theorems show that each formula in a certain theory is equivalent to a formula of a specific form -- usually a quantifier-free one, sometimes in an extended language. Model theoretic embedding tests are a frequently used tool for proving such results without providing an explicit algorithm. We explain how proof mining methods can be adapted to apply to embedding tests, and provide two explicit examples, giving algorithms for theories of algebraic and real closed fields with a distinguished small subgroup corresponding to the embedding test proofs given by van den Dries and G\"unaydin.

We show that the Aldous--Hoover Theorem, giving representations for exchangeable arrays of Borel-valued random variables, extends to random variables where the common distribution of the random variables is Radon, or even merely compact, a weaker condition that does not even require that the values come from a Hausdorff space. This extends work of Alam \cite{alam2023generalizing} who showed a similar generalization of the di Finetti--Hewitt-Savage Theorem.

We show that the Priess-Crampe & Ribenboim fixed point theorem is provable in $\mathsf{RCA}_0$. Furthermore, we show that Caristi's fixed point theorem for both Baire and Borel functions is equivalent to the transfinite leftmost path principle, which falls strictly between $\mathsf{ATR}_0$ and $\Pi^1_1\mbox{-}\mathsf{CA}_0$. We also exhibit several weakenings of Caristi's theorem that are equivalent to $\mathsf{WKL}_0$ and to $\mathsf{ACA}_0$.

We characterize the completely determined Borel subsets of HYP as exactly the omega_1^{ck} subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalban, Solomon & the third author., Comment: 19 pages

We prove a removal lemma for induced ordered hypergraphs, simultaneously generalizing Alon--Ben-Eliezer--Fischer's removal lemma for ordered graphs and the induced hypergraph removal lemma. That is, we show that if an ordered hypergraph $(V,G,<)$ has few induced copies of a small ordered hypergraph $(W,H,\prec)$ then there is a small modification $G'$ so that $(V,G',<)$ has no induced copies of $(W,H,\prec)$. (Note that we do \emph{not} need to modify the ordering $<$.) We give our proof in the setting of an ultraproduct (that is, a Keisler graded probability space), where we can give an abstract formulation of hypergraph removal in terms of sequences of $\sigma$-algebras. We then show that ordered hypergraphs can be viewed as hypergraphs where we view the intervals as an additional notion of a ``very structured'' set. Along the way we give an explicit construction of the bijection between the ultraproduct limit object and the corresponding hyerpgraphon.

We generalize the fact that graphs with small VC-dimension can be approximated 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 a k'-uniform hypergraph with small VC_k-dimension for some k

Suppose $I$ is an ideal of a polynomial ring over a field, $I\subseteq k[x_1,\ldots,x_n]$, and whenever $fg\in I$ with degree $\leq b$, then either $f\in I$ or $g\in I$. When $b$ is sufficiently large, it follows that $I$ is prime. Schmidt-G\"ottsch proved that "sufficiently large" can be taken to be a polynomial in the degree of generators of $I$ (with the degree of this polynomial depending on $n$). However Schmidt-G\"ottsch used model-theoretic methods to show this, and did not give any indication of how large the degree of this polynomial is. In this paper we obtain an explicit bound on $b$, polynomial in the degree of the generators of $I$. We also give a similar bound for detecting maximal ideals in $k[x_1,\ldots,x_n]$.

The first-order part of the Ramsey's Theorem for pairs with an arbitrary number of colors is known to be precisely BSigma03. We compare this to the known division of Ramsey's Theorem for pairs into the weaker principles, EM (the Erd\H{o}s-Moser principle) and ADS (the ascending-descending sequence principle): we show that the additional strength beyond ISigma02 is entirely due to the arbitrary color analog of ADS. Specifically, we show that ADS for an arbitrary number of colors implies BSigma03 while EM for an arbitrary number of colors is Pi11-conservative over ISigma02 and it does not imply ISigma02.

We describe a syntactic method for taking proofs which use ultraproducts and translating them into direct, constructive proofs.

Recently the breakthrough method of hypergraph containers, developed independently by Balogh, Morris, and Samotij as well as Saxton and Thomason, has been used to study sparse random analogs of a variety of classical problems from combinatorics and number theory. The previously known proofs of the containers theorem use the so-called scythe algorithm---an iterative procedure that runs through the vertices of the hypergraph. (Saxton and Thomason have also proposed an alternative, randomized construction in the case of simple hypergraphs.) Here we present the first known deterministic proof of the containers theorem that is not algorithmic, i.e., it does not involve an iterative process. Our proof is less than 4 pages long while being entirely self-contained and conceptually transparent. Although our proof is completely elementary, it was inspired by considering hypergraphs in the setting of nonstandard analysis, where there is a notion of dimension capturing the logarithmic rate of growth of finite sets. Before presenting the proof in full detail, we include a one-page informal outline that refers to this notion of dimension and summarizes the essence of the argument., Comment: Changes made according to the referee's suggestions

Uniform metastable convergence is a weak form of uniform convergence for a family of sequences. In this paper we explore the way that metastable convergence stratifies into a family of notions indexed by countable ordinals. We give two versions of this stratified family, loosely speaking, they correspond to the model theoretic and proof theoretic perspectives. For the model theoretic version, which we call abstract alpha-uniform convergence, we show that uniform metastable convergence is equivalent to abstract $\alpha$-uniform convergence for some alpha, and that abstract omega-uniform convergence is equivalent to uniformly bounded oscillation of the family of sequences. The proof theoretic version, which we call concrete alpha-uniform convergence, is less canonical (it depends on a choice of ordinal notation), but appears naturally when "proof mining" convergence proofs to obtain quantitative bounds. We show that these hierarchies are strict by exhibiting a family of which is concretely alpha+1-uniformly convergent but not abstractly alpha-uniformly convergent for each alpha

If we know that some kind of sequence always converges, we can ask how quickly and how uniformly it converges. Many convergent sequences converge non-uniformly and, relatedly, have no computable rate of convergence. However proof-theoretic ideas often guarantee the existence of a uniform "meta-stable" rate of convergence. We show that obtaining a stronger bound---a uniform bound on the number of jumps the sequence makes---is equivalent to being able to strengthen convergence to occur in the nonstandard numbers. We use this to obtain bounds on the number of jumps in nonconventional ergodic averages.

Recently, Boutonnet, Chifan, and Ioana proved that McDuff's examples of continuum many pairwise non-isomorphic separable II$_1$ factors are in fact pairwise non-elementarily equivalent. Their proof proceeded by showing that any ultrapowers of any two distinct McDuff examples are not isomorphic. In a paper by the first two authors of this paper, Ehrenfeucht-Fra\"isse games were used to find an upper bound on the quantifier complexity of sentences distinguishing the McDuff examples, leaving it as an open question to find concrete sentences distinguishing the McDuff factors. In this paper, we answer this question by providing such concrete sentences., Comment: 10 pages

Using the functional interpretation from proof theory, we analyze nonconstructive proofs of several central theorems about polynomial and differential polynomial rings. We extract effective bounds, some of which are new to the literature, from the resulting proofs. In the process we discuss the constructive content of Noetherian rings and the Nullstellensatz in both the classical and differential settings. Sufficient background is given to understand the proof-theoretic and differential-algebraic framework of the main results.

We propose a new method for constructing Turing ideals satisfying principles of reverse mathematics below the Chain-Antichain Principle (CAC). Using this method, we are able to prove several new separations in the presence of Weak Konig's Lemma (WKL), including showing that CAC+WKL does not imply the thin set theorem for pairs, and that the principle "the product of well-quasi-orders is a well-quasi-order" is strictly between CAC and the Ascending/Descending Sequences principle, even in the presence of WKL.

We describe an Aldous--Hoover-type characterization of random relational structures that are exchangeable relative to a fixed structure which may have various equivalence relations. Our main theorem gives the common generalization of the results on relative exchangeability due to Ackerman \cite{Ackerman2015} and Crane and Towsner \cite{CraneTowsner2015} and hierarchical exchangeability results due to Austin and Panchenko \cite{AustinPanchenko2014}.

Every exchangeable Feller process taking values in a suitably nice combinatorial state space can be constructed by a system of iterated random Lipschitz functions. In discrete time, the construction proceeds by iterated application of independent, identically distributed functions, while in continuous time the random functions occur as the atoms of a time homogeneous Poisson point process. We further show that every exchangeable Feller process projects to a Feller process in an appropriate limit space, akin to the projection of partition-valued processes into the ranked-simplex and graph-valued processes into the space of graph limits. Together, our main theorems establish common structural features shared by all exchangeable combinatorial Feller processes, regardless of the dynamics or resident state space, thereby generalizing behaviors previously observed for exchangeable coalescent and fragmentation processes as well as other combinatorial stochastic processes. If, in addition, an exchangeable Feller process evolves on a state space satisfying the $n$-disjoint amalgamation property for all $n\geq1$, then its jump measure can be decomposed explicitly in the sense of L\'evy--It\^o--Khintchine., Comment: 58 pages

We study random relational structures that are \emph{relatively exchangeable}---that is, whose distributions are invariant under the automorphisms of a reference structure $\mathfrak{M}$. When $\mathfrak{M}$ has {\em trivial definable closure}, every relatively exchangeable structure satisfies a general Aldous--Hoover-type representation. If $\mathfrak{M}$ satisfies the stronger properties of {\em ultrahomogeneity} and {\em $n$-disjoint amalgamation property} ($n$-DAP) for every $n\geq1$, then relatively exchangeable structures have a more precise description whereby each component depends locally on $\mathfrak{M}$.

The $\epsilon$-substitution method is a technique for giving consistency proofs for theories of arithmetic. We use this technique to give a proof of the consistency of the impredicative theory $ID_1$ using a variant of the cut-elimination formalism introduced by Mints.

In \cite{J}, Theorem 4.2, Jockusch proves that for any computable k-coloring of pairs of integers, there is an infinite $\Pi^0_2$ homogeneous set. The proof uses a countable collection of $\Pi^0_2$ sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch states without proof that it can be shown that there is no computable way to prove this result with a finite number of $\Pi^0_2$ sets. We provide a proof of this latter fact.

The functional interpretation is a systematic, syntactic method for transforming certain non-constructive proofs into constructive proofs with explicit bounds. We illustrate the interpretation by working through a concrete, fairly simple example, with almost no reference to formal logic, and then explain the connection with the underlying proof-theoretic methods.

The proof that the James space is not locally unconditional appears to be non-constructive, since it makes use of an ultraproduct construction. Using proof mining, we extract a constructive proof and obtain a lower bound on the growth of the local unconditionality constants.

We give a constructive, metastable formulation of a theorem about the exchange of limits for convergent sequence $L^1$ functions. A crucial tool is a one-dimensional version of Szemeredi's regularity lemma for $L^1$ functions.

In this paper, we study Ramsey-type Konig's Lemma, written RWKL, using a technique introduced by Lerman, Solomon, and the second author. This technique uses iterated forcing to construct an omega-model satisfying one principle T_1 but not another T_2. The technique often allows one to translate a "one step" construction (building an instance of T_2 along with a collection of solutions to each computable instance of T_1) into an omega-model separation (building a computable instance of T_2 together with a Turing ideal where T_1 holds). We illustrate this translation by separating d-DNR from DNR (reproving a result of Ambos-Spies, Kjos-Hanssen, Lempp, and Slaman), and then apply this technique to separate RWKL$ from DNR (which has been shown separately by Bienvenu, Patey, and Schafer).

We show that any countable model of a model complete theory has an elementary extension with a "pseudofinite-like" quasidimension that detects dividing., Comment: 5 pages; the second version corrects some mistakes

We study the limiting object of a sequence of Markov chains analogous to the limits of graphs, hypergraphs, and other objects which have been studied. Following a suggestion of Aldous, we assign to a sequence of finite Markov chains with bounded mixing times a unique limit object: an infinite Markov chain with a measurable state space. The limits of the Markov chains we consider have discrete spectra, which makes the limit theory simpler than the general graph case, and illustrates how the discrete spectrum setting (sometimes called "random-free" or "product measurable") is simpler than the general case.

We examine the correspondence between the various notions of quasirandomness for k-uniform hypergraphs and sigma-algebras related to measurable hypergraphs. This gives a uniform formulation of most of the notions of quasirandomness for dense hypergraphs which have been studied, with each notion of quasirandomness corresponding to a sigma-algebra defined by a collection of subsets of [1,k]. We associate each notion of quasirandomness I with a collection of hypergraphs, the I-adapted hypergraphs, so that G is quasirandom exactly when it contains roughly the correct number of copies of each I-adapted hypergraph. We then identify, for each I, a particular I-adapted hypergraph M_k[I] with the property that if G contains roughly the correct number of copies of M_k[I] then G is quasirandom in the sense of I. This generalizes recent results of Kohayakawa, Nagle, R\"odl, and Schacht; Conlon, H\`an, Person, and Schacht; and Lenz and Mubayi giving this result for some notions of quasirandomness.

We give a proof of Szemeredi's regularity lemma in the special case of a graph with bounded VC dimension and show that it is possible to obtain "merely" doubly exponential bounds on the size of the partition in this case.

We investigate the set of Pi-1-2 sentences which are Pi-1-1 conservative over the theories of reverse mathematics RCA0+ISigma_n and ACA0. We exhibit new elements of these sets and conclude that the sets are Pi_2 complete. Along the way, we show that, over the theory RCA, induction for Sigma-n formulas has essentially no consequences for Delta-(n+1) formulas.

In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from $\RT$, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below $\RT$ has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that $\ADS$ is not equivalent to $\CAC$ and that $\EM$ is not equivalent to $\RT$.

We characterize the points that satisfy Birkhoff's ergodic theorem under certain computability conditions in terms of algorithmic randomness. First, we use the method of cutting and stacking to show that if an element x of the Cantor space is not Martin-Lof random, there is a computable measure-preserving transformation and a computable set that witness that x is not typical with respect to the ergodic theorem, which gives us the converse of a theorem by V'yugin. We further show that if x is weakly 2-random, then it satisfies the ergodic theorem for all computable measure-preserving transformations and all lower semi-computable functions.

The use of tools from analysis to approach problems in graph theory has become an active area of research. Usually such methods are applied to problems involving dense graphs and hypergraphs; here we give the an extension of such methods to sparse but pseudorandom hypergraphs. We use this framework to give a proof of hypergraph removal for sub-hypergraphs of sparse random hypergraphs.

We extend theories of reverse mathematics by a non-principal ultrafilter, and show that these are conservative extensions of the usual theories ACA0, ATR0, and Pi11-Comprehension.

In reverse mathematics, is is possible to have a curious situation where we know that an implication does not reverse, but appear to have no information on on how to weaken the assumption while preserving the conclusion. A main cause of this phenomenon is the proof of a $\Pi^1_2$ sentence from the theory {\Pioo}. Using methods based on the functional interpretation, we introduce a family of weakenings of {\Pioo} and use them to give new upper bounds for the Nash-Williams Theorem of wqo theory and Menger's Theorem for countable graphs.

We present a logical framework for formalizing connections between finitary combinatorics and measure theory or ergodic theory that have appeared various places throughout the literature. We develop the basic syntax and semantics of this logic and give applications, showing that the method can express the classic Furstenberg correspondence and to give a short proof of the Szemer\'edi Regularity Lemma. We also derive some connections between the model-theoretic notion of stability and the Gowers uniformity norms from combinatorics., Comment: New version contains a much simplified presentation of the semantics as well as a new subsection on hypergraph removal

We present a short proof of Szemer\'edi's Theorem using a dynamical system enriched by ideas from model theory. The resulting proof contains features reminiscent of proofs based on both ergodic theory and on hypergraph regularity.

The Dense Hindman's Theorem states that, in any finite coloring of the integers, one may find a single color and a "dense" set $B_1$, for each $b_1\in B_1$ a "dense" set $B_2^{b_1}$ (depending on $b_1$), for each $b_2\in B_2^{b_1}$ a "dense" set $B_3^{b_1,b_2}$ (depending on $b_1,b_2$), and so on, such that for any such sequence of $b_i$, all finite sums belong to the chosen color. (Here density is often taken to be "piecewise syndetic", but the proof is unchanged for any notion of density satisfying certain properties.) This theorem is an example of a combinatorial statement for which the only known proof requires the use of ultrafilters or a similar infinitary formalism. Here we give a direct combinatorial proof of the theorem.

Hindman's Theorem states that in any finite coloring of the integers, there is an infinite set all of whose finite sums belong to the same color. This is much stronger than the corresponding finite form, stating that in any finite coloring of the integers there are arbitrarily long finite sets with the same property. We extend the finite form of Hindman's Theorem to a "transfinite" version for each countable ordinal, and show that Hindman's Theorem is equivalent to the appropriate transfinite approximation holding for every countable ordinal. We then give a proof of Hindman's Theorem by directly proving these transfinite approximations.

The Furstenberg-Zimmer structure theorem for $\mathbb{Z}^d$ actions says that every measure-preserving system can be decomposed into a tower of primitive extensions. Furstenberg and Katznelson used this analysis to prove the multidimensional Szemer\'edi's theorem, and Bergelson and Liebman further generalized to a polynomial Szemer\'edi's theorem. Beleznay and Foreman showed that, in general, this tower can have any countable height. Here we show that these proofs do not require the full height of this tower; we define a weaker combinatorial property which is sufficient for these proofs, and show that it always holds at fairly low levels in the transfinite construction (specifically, $\omega^{\omega^{\omega^\omega}}$).

We give a short, explicit proof of Hindman's Theorem that in every finite coloring of the integers, there is an infinite set all of whose finite sums have the same color. We give several exampls of colorings of the integers which do not have computable witnesses to Hindman's Theorem.