var bibbase_data = {"data":"\"Loading..\"\n\n
\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n
\n generated by\n \n \"bibbase.org\"\n\n \n
\n \n\n
\n\n \n\n\n
\n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page by copying & pasting\n any of the following snippets.\n\n
\n JavaScript\n (easiest)\n
\n \n <script src=\"https://bibbase.org/show?bib=https://www.sas.upenn.edu/~htowsner/papers.bib&simplegroups=true&group0=year&css=https://www.sas.upenn.edu/~htowsner/mybibstyle.css&jsonp=1&jsonp=1\"></script>\n \n
\n\n PHP\n
\n \n <?php\n $contents = file_get_contents(\"https://bibbase.org/show?bib=https://www.sas.upenn.edu/~htowsner/papers.bib&simplegroups=true&group0=year&css=https://www.sas.upenn.edu/~htowsner/mybibstyle.css&jsonp=1\");\n print_r($contents);\n ?>\n \n
\n\n iFrame\n (not recommended)\n
\n \n <iframe src=\"https://bibbase.org/show?bib=https://www.sas.upenn.edu/~htowsner/papers.bib&simplegroups=true&group0=year&css=https://www.sas.upenn.edu/~htowsner/mybibstyle.css&jsonp=1\"></iframe>\n \n
\n\n

\n For more details see the documention.\n

\n
\n
\n\n
\n\n This is a preview! To use this list on your own web site\n or create a new web site from it,\n create a free account. The file will be added\n and you will be able to edit it in the File Manager.\n We will show you instructions once you've created your account.\n
\n\n
\n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

    \n
  1. renew the authorization for BibBase on Mendeley, and
  2. \n
  3. update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n
  4. \n
\n

\n\n

\n \n \n Fix it now\n

\n
\n\n
\n\n\n
\n \n \n
\n
\n  \n 2023\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Metric fixed point theory and partial impredicativity.\n \n \n \n \n\n\n \n Fernández-Duque, D.; Shafer, P.; Towsner, H.; and Yokoyama, K.\n\n\n \n\n\n\n Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 381(2248). April 2023.\n \n\n\n\n
\n\n\n\n \n \n \"MetricPaper\n  \n \n \n \"MetricArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 13 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{FernndezDuque2023,\n  title = {Metric fixed point theory and partial impredicativity},\n  volume = {381},\n  ISSN = {1471-2962},\n  url = {http://dx.doi.org/10.1098/rsta.2022.0012},\n  DOI = {10.1098/rsta.2022.0012},\n  urlarxiv = {https://arxiv.org/abs/2302.08874},\n  number = {2248},\n  journal = {Philosophical Transactions of the Royal Society A: Mathematical,  Physical and Engineering Sciences},\n  publisher = {The Royal Society},\n  author = {Fernández-Duque,  D. and Shafer,  P. and Towsner,  H. and Yokoyama,  K.},\n  year = {2023},\n  month = apr ,\n  abstract = {    We show that the Priess-Crampe & Ribenboim fixed point theorem is provable in 𝖱𝖢𝖠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 𝖠𝖳𝖱0 and Π11-𝖢𝖠0. We also exhibit several weakenings of Caristi's theorem that are equivalent to 𝖶𝖪𝖫0 and to 𝖠𝖢𝖠0. }\n}\n\n
\n
\n\n\n
\n We show that the Priess-Crampe & Ribenboim fixed point theorem is provable in 𝖱𝖢𝖠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 𝖠𝖳𝖱0 and Π11-𝖢𝖠0. We also exhibit several weakenings of Caristi's theorem that are equivalent to 𝖶𝖪𝖫0 and to 𝖠𝖢𝖠0. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n From Saturated Embedding Tests to Explicit Algorithms.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n 2023.\n \n\n\n\n
\n\n\n\n \n \n \"FromArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 12 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{2306.12239,\nAuthor = {Henry Towsner},\nTitle = {From Saturated Embedding Tests to Explicit Algorithms},\nYear = {2023},\nEprint = {arXiv:2306.12239},\nurlarxiv = {https://arxiv.org/abs/2306.12239},\nabstract = {     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.\n    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ünaydin. },\n}\n\n
\n
\n\n\n
\n 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ünaydin. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n An Aldous–Hoover Theorem for Radon Distributions.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n 2023.\n \n\n\n\n
\n\n\n\n \n \n \"AnArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{2306.03057,\nAuthor = {Henry Towsner},\nTitle = {An Aldous--Hoover Theorem for Radon Distributions},\nYear = {2023},\nEprint = {arXiv:2306.03057},\nurlarxiv = {https://arxiv.org/abs/2306.03057},\nabstract = {     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. },\n}\n\n
\n
\n\n\n
\n 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 i̧tealam2023generalizing who showed a similar generalization of the di Finetti–Hewitt-Savage Theorem. \n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2022\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Borel combinatorics fail in HYP.\n \n \n \n \n\n\n \n Towsner, H.; Weisshaar, R.; and Westrick, L.\n\n\n \n\n\n\n Journal of Mathematical Logic. December 2022.\n \n\n\n\n
\n\n\n\n \n \n \"BorelPaper\n  \n \n \n \"BorelArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{CombinatoricsFails,\n  doi = {10.1142/s0219061322500234},\n  url = {https://doi.org/10.1142/s0219061322500234},\n  year = {2022},\n  month = dec,\n  publisher = {World Scientific Pub Co Pte Ltd},\n  author = {Henry Towsner and Rose Weisshaar and Linda Westrick},\n  title = {Borel combinatorics fail in HYP},\n  journal = {Journal of Mathematical Logic},\n  urlarxiv = {https://arxiv.org/abs/2106.13330},\n  abstract={     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. },\n}\n\n\n
\n
\n\n\n
\n 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. \n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2021\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n A Removal Lemma for Ordered Hypergraphs.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n 2021.\n draft\n\n\n\n
\n\n\n\n \n \n \"AArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 60 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{towsner2021removal,\n      title={A Removal Lemma for Ordered Hypergraphs}, \n      author={Henry Towsner},\nnote={draft},\n      year={2021},\n      eprint={2101.09769},\n      archivePrefix={arXiv},\n      primaryClass={math.CO},\n      urlarxiv={https://arxiv.org/abs/2101.09769},\n      abstract={    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,≺) then there is a small modification G′ so that (V,G′,<) has no induced copies of (W,H,≺). (Note that we do \\emph{not} need to modify the ordering <.)\n      \n    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 σ-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. },\n}\n\n
\n
\n\n\n
\n 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,≺) then there is a small modification G′ so that (V,G′,<) has no induced copies of (W,H,≺). (Note that we do \\emphnot 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 σ-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. \n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2020\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hypergraph regularity and higher arity VC-dimension.\n \n \n \n \n\n\n \n Chernikov, A.; and Towsner, H.\n\n\n \n\n\n\n 2020.\n draft\n\n\n\n
\n\n\n\n \n \n \"HypergraphArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 21 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{chernikov2020hypergraph,\n      title={Hypergraph regularity and higher arity VC-dimension}, \n      author={Artem Chernikov and Henry Towsner},\nnote={draft},\n      year={2020},\n      eprint={2010.00726},\n      archivePrefix={arXiv},\n      primaryClass={math.CO},\n      urlarxiv={https://arxiv.org/abs/2010.00726},\n      abstract={ 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.\nIn the language of hypergraph regularity, this shows that when H is a k'-uniform hypergraph with small VC_k-dimension for some k<k', the decomposition of H given by hypergraph regularity only needs the first k levels---one can approximate H using sets of vertices, sets of pairs, and so on up to sets of k-tuples---and that on most of the resulting k-ary cylinder sets, the density of H is either close to 0 or close to 1.\nWe also show a suitable converse: k'-uniform hypergraphs with large VC_k-dimension cannot have such approximations uniformly under all measures on the vertices. },\n}\n\n
\n
\n\n\n
\n 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\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Explicit polynomial bounds on prime ideals in polynomial rings over fields.\n \n \n \n \n\n\n \n Simmons, W.; and Towsner, H.\n\n\n \n\n\n\n Pacific Journal of Mathematics,721–754. August 2020.\n \n\n\n\n
\n\n\n\n \n \n \"ExplicitArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 16 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{2018arXiv180804805S,\n   author = {{Simmons}, W. and {Towsner}, H.},\n    title = "{Explicit polynomial bounds on prime ideals in polynomial rings over fields}",\n    month = {August},\n    year = {2020},\n    urlarxiv={https://arxiv.org/abs/1808.04805},\n    journal={Pacific Journal of Mathematics},\n    vol = {306},\n    issue = {2},\n    doi = {10.2140/pjm.2020.306.721},\n    pages = {721--754},\n    abstract={Suppose I is an ideal of a polynomial ring over a field, I⊆k[x1,…,xn], and whenever fg∈I with degree ≤b, then either f∈I or g∈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[x1,…,xn].}\n}\n\n
\n
\n\n\n
\n Suppose I is an ideal of a polynomial ring over a field, I⊆k[x1,…,xn], and whenever fg∈I with degree ≤b, then either f∈I or g∈I. When b is sufficiently large, it follows that I is prime. Schmidt-Göttsch 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öttsch 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[x1,…,xn].\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Constructing Sequences One Step at a Time.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Journal of Mathematical Logic, 20. 2020.\n \n\n\n\n
\n\n\n\n \n \n \"ConstructingArxiv\n  \n \n \n \"ConstructingJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 31 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1609.05509,\nauthor = {Henry Towsner},\ntitle = {Constructing Sequences One Step at a Time},\njournal = {Journal of Mathematical Logic},\nyear = {2020},\nurlarxiv={http://arxiv.org/abs/1609.05509},\ndoi={10.1142/S0219061320500178},\nurljournal={ https:///dx.doi.org/10.1142/S0219061320500178 },\nvolume=20,\nissue=3,\n\nabstract = {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.}\n}\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2019\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n A short nonalgorithmic proof of the containers theorem for hypergraphs.\n \n \n \n \n\n\n \n Bernshteyn, A.; Delcourt, M.; Towsner, H.; and Tserunyan, A.\n\n\n \n\n\n\n Proc. Amer. Math. Soc,1739–1749. 2019.\n \n\n\n\n
\n\n\n\n \n \n \"AArxiv\n  \n \n \n \"AJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 22 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1801.07186,\n   author = {{Bernshteyn}, A. and {Delcourt}, M. and {Towsner}, H. and {Tserunyan}, A.\n\t},\n    title = "{A short nonalgorithmic proof of the containers theorem for hypergraphs}",\nvol=147,\npages={1739--1749},\n     year = 2019,\n   urlarxiv = {https://arxiv.org/abs/1801.07186},\n   urljournal={https://www.ams.org/journals/proc/0000-000-00/S0002-9939-2019-14368-9/},\n   journal = {Proc. Amer. Math. Soc},\n   doi = {10.1090/proc/14368},\nabstract={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 analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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.\n}\n}\n\n\n
\n
\n\n\n
\n 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 analogues of a variety of classical problems from combinatorics and number theory. In this paper, we give the first known proof of this theorem that does not involve an inductive construction (i.e., the so-called scythe algorithm). This proof is less than 4 pages long while being entirely self-contained. 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. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Nonstandard Convergence Gives Bounds on Jumps.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n New York Journal of Mathematics,651–667. August 2019.\n \n\n\n\n
\n\n\n\n \n \n \"NonstandardPaper\n  \n \n \n \"NonstandardArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1705.10355,\nauthor = {Henry Towsner},\ntitle = {Nonstandard Convergence Gives Bounds on Jumps},\nyear = {2019},\nmonth = aug,\njournal = {New York Journal of Mathematics},\nvol = {25},\npages = {651--667},\nurl = {http://nyjm.albany.edu/j/2019/25-31.html},\nurlarxiv={https://arxiv.org/abs/1705.10355},\nabstract={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.}\n}\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Proof mining and effective bounds in differential polynomial rings.\n \n \n \n \n\n\n \n Simmons, W.; and Towsner, H.\n\n\n \n\n\n\n Advances in Mathematics, 343: 567 - 623. 2019.\n \n\n\n\n
\n\n\n\n \n \n \"ProofJournal\n  \n \n \n \"ProofArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 34 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1609.07509,\nauthor={William Simmons and Henry Towsner},\ntitle={Proof mining and effective bounds in differential polynomial rings},\njournal = {Advances in Mathematics},\nvolume = 343,\npages = {567 - 623},\nyear = 2019,\nissn = {0001-8708},\ndoi = {https://doi.org/10.1016/j.aim.2018.11.026},\nurljournal = {http://www.sciencedirect.com/science/article/pii/S0001870818304900},\nurlarxiv={http://arxiv.org/abs/1609.07509},\nabstract={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.}\n}\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2018\n \n \n (9)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Erdos-Moser and ISigma_2.\n \n \n \n \n\n\n \n Towsner, H.; and Yokoyama, K.\n\n\n \n\n\n\n July 2018.\n draft\n\n\n\n
\n\n\n\n \n \n \"Erdos-MoserArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 14 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{1807.04452,\nauthor = {{Towsner}, H. and {Yokoyama}, K.},\ntitle="{Erdos-Moser and ISigma_2}",\nnote={draft},\nyear=2018,\nmonth=jul,\nurlarxiv={https://arxiv.org/abs/1807.04452},\nabstract={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. \nSpecifically, 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.}}\n\n\n
\n
\n\n\n
\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ő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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Realism in Mathematics: The Case of the Hyperreals.\n \n \n \n \n\n\n \n Easwaren, K.; and Towsner, H.\n\n\n \n\n\n\n June 2018.\n submitted\n\n\n\n
\n\n\n\n \n \n \"RealismArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 26 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{EaswarenTowsner,\nauthor = {{Easwaren}, K. and {Towsner}, H.},\ntitle = "{Realism in Mathematics: The Case of the Hyperreals}",\nnote={submitted},\nyear=2018,\nmonth= jun,\nurlarxiv={https://www.dropbox.com/s/vmgevvgmy9bhl2c/Hyperreals.pdf?raw=1},\nabstract={A traditional question in the philosophy of mathematics is whether abstract\nmathematical objects really exist, just as planets and atoms and giraffes do,\nindependently of the human mind. Views on this question are often grouped into\n“platonist”, “nominalist”, and “constructivist” groups depending on whether\nthey state that mathematical objects have their own independent existence, or\ndon’t truly exist at all, or exist but only as constructions of the human mind.\nThis paper will not directly address this question. We expect that to the extent\nthat each of these views is defensible, they will not settle the questions that we\nare interested in (though there may be some affinities between some possible\nanswers to these questions). Rather, we will focus on two other questions of\nmathematical realism: the question of which mathematical claims can be taken\nas meaningful and true within mathematics, and which mathematical ideas can\nbe taken as applying to the physical world as part of a scientific theory.\nWe will focus on these questions for the case of the “hyperreals” of nonstandard\nanalysis, introduced by Abraham Robinson in the 1960’s (which we\nwill describe in greater detail later). Because of their mathematical properties,\nthe hyperreals have attracted attacks and defenses in ways that are uncommon\nfor mathematical entities. Our central claim is that many of the views on both\nsides of these debates conflate two distinct philosophical questions. Defenders\nof the hyperreals give realist answers to both questions, while attackers give\nantirealist answers to both. We defend a realist answer to one question and\nan antirealist answer to the other. We think the distinction between these two\nquestions is important not just for thinking about the hyperreals, but for other\nrelated mathematical entities, and particularly those whose existence depend\non the Axiom of Choice.}\n}\n\n\n
\n
\n\n\n
\n A traditional question in the philosophy of mathematics is whether abstract mathematical objects really exist, just as planets and atoms and giraffes do, independently of the human mind. Views on this question are often grouped into “platonist”, “nominalist”, and “constructivist” groups depending on whether they state that mathematical objects have their own independent existence, or don’t truly exist at all, or exist but only as constructions of the human mind. This paper will not directly address this question. We expect that to the extent that each of these views is defensible, they will not settle the questions that we are interested in (though there may be some affinities between some possible answers to these questions). Rather, we will focus on two other questions of mathematical realism: the question of which mathematical claims can be taken as meaningful and true within mathematics, and which mathematical ideas can be taken as applying to the physical world as part of a scientific theory. We will focus on these questions for the case of the “hyperreals” of nonstandard analysis, introduced by Abraham Robinson in the 1960’s (which we will describe in greater detail later). Because of their mathematical properties, the hyperreals have attracted attacks and defenses in ways that are uncommon for mathematical entities. Our central claim is that many of the views on both sides of these debates conflate two distinct philosophical questions. Defenders of the hyperreals give realist answers to both questions, while attackers give antirealist answers to both. We defend a realist answer to one question and an antirealist answer to the other. We think the distinction between these two questions is important not just for thinking about the hyperreals, but for other related mathematical entities, and particularly those whose existence depend on the Axiom of Choice.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n What do ultraproducts remember about the original structures?.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n April 2018.\n draft\n\n\n\n
\n\n\n\n \n \n \"WhatArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 36 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{1804.10809,\n   author = {{Towsner}, H.},\n    title = "{What do ultraproducts remember about the original structures?}",\n    note={draft},\n     year = 2018,\n    month = apr,\nurlarxiv={https://arxiv.org/abs/1804.10809},\nabstract={We describe a syntactic method for taking proofs which use ultraproducts and translating them into direct, constructive proofs.}\n}\n\n\n
\n
\n\n\n
\n We describe a syntactic method for taking proofs which use ultraproducts and translating them into direct, constructive proofs.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Explicit sentences distinguishing McDuff's II$_1$ factors.\n \n \n \n \n\n\n \n Goldbring, I.; Hart, B.; and Towsner, H.\n\n\n \n\n\n\n Israel Journal of Mathematics, 227(1): 365–377. Aug 2018.\n \n\n\n\n
\n\n\n\n \n \n \"ExplicitArxiv\n  \n \n \n \"ExplicitJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 6 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1701.07928,\n   author = {I. Goldbring and B. Hart and H. Towsner},\n    title = {Explicit sentences distinguishing McDuff's II$\\_1$ factors},\n    urlarxiv={https://arxiv.org/abs/1701.07928},\n    journal={Israel Journal of Mathematics},\n doi = {10.1007/s11856-018-1735-8},\nyear=2018,\nmonth={Aug},\nday=01,\nvolume=227,\nnumber=1,\npages={365--377},\nissn={1565-8511},\nurljournal={https://doi.org/10.1007/s11856-018-1735-8},\n    abstract={Recently, Boutonnet, Chifan, and Ioana proved that McDuff's examples of continuum many pairwise non-isomorphic separable $\\Pi_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.}\n}\n\n
\n
\n\n\n
\n Recently, Boutonnet, Chifan, and Ioana proved that McDuff's examples of continuum many pairwise non-isomorphic separable $Π_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ïsse 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Relative exchangeability with equivalence relations.\n \n \n \n \n\n\n \n Crane, H.; and Towsner, H.\n\n\n \n\n\n\n Archive for Mathematical Logic, 57: 533-556. 2018.\n \n\n\n\n
\n\n\n\n \n \n \"RelativeArxiv\n  \n \n \n \"RelativeJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 11 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{1605.04484,\nAuthor = {Harry Crane and Henry Towsner},\nTitle = {Relative exchangeability with equivalence relations},\nYear = {2018},\nvolume = {57},\nissue = {5},\npages={533-556},\njournal={Archive for Mathematical Logic},\nEprint = {arXiv:1605.04484},\ndoi = {10.1007/s00153-017-0591-2},\nurlarxiv={http://arxiv.org/abs/1605.04484},\nurljournal={http://link.springer.com/article/10.1007/s00153-017-0591-2},\nabstract={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}.\n}\n}\n\n
\n
\n\n\n
\n 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 i̧teAckerman2015 and Crane and Towsner i̧teCraneTowsner2015 and hierarchical exchangeability results due to Austin and Panchenko i̧teAustinPanchenko2014. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Epsilon Substitution for $ID_1$ via Cut-Elimination.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Archive for Mathematical Logic, 57: 497-531. 2018.\n \n\n\n\n
\n\n\n\n \n \n \"EpsilonArxiv\n  \n \n \n \"EpsilonJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@ARTICLE{towsner15:epsilon_cutelim,\nauthor = {{Towsner}, H.},\ntitle="{Epsilon Substitution for $ID_1$ via Cut-Elimination}",\nyear=2018,\nvolume = {57},\nissue = {5},\npages={497-531},\njournal={Archive for Mathematical Logic},\ndoi = {10.1007/s00153-017-0590-3},\nurlarxiv={http://arxiv.org/abs/1509.00390},\nurljournal={https://link.springer.com/article/10.1007/s00153-017-0590-3},\nabstract={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.}\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Relatively exchangeable structures.\n \n \n \n \n\n\n \n Crane, H.; and Towsner, H.\n\n\n \n\n\n\n Journal of Symbolic Logic, 83(2): 416-442. 2018.\n \n\n\n\n
\n\n\n\n \n \n \"RelativelyArxiv\n  \n \n \n \"RelativelyJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@ARTICLE{2015arXiv150906733C,\n   author = {{Crane}, H. and {Towsner}, H.},\n    title = "{Relatively exchangeable structures}",\njournal={Journal of Symbolic Logic},\nyear = 2018,\nvolume={83},\nnumber={2},\npages={416-442},\nurlarxiv={http://arxiv.org/abs/1509.06733},\nurljournal={https://doi.org/10.1017/jsl.2017.61},\ndoi={10.1017/jsl.2017.61},\nabstract={We study random relational structures that are \\emph{relatively exchangeable}---that is, whose distributions are invariant under the automorphisms of a reference structure &#x1D510;. When &#x1D510; has <i>trivial definable closure</i>, every relatively exchangeable structure satisfies a general Aldous--Hoover-type representation. If &#x1D510; satisfies the stronger properties of <i>ultrahomogeneity</i> and <i>n-disjoint amalgamation property</i> (n-DAP) for every n&geq;1, then relatively exchangeable structures have a more precise description whereby each component depends locally on &#x1D510;.},\n}\n\n\n
\n
\n\n\n
\n We study random relational structures that are \\emphrelatively exchangeable—that is, whose distributions are invariant under the automorphisms of a reference structure 𝔐. When 𝔐 has trivial definable closure, every relatively exchangeable structure satisfies a general Aldous–Hoover-type representation. If 𝔐 satisfies the stronger properties of ultrahomogeneity and n-disjoint amalgamation property (n-DAP) for every n≥1, then relatively exchangeable structures have a more precise description whereby each component depends locally on 𝔐.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n An Inverse Ackermannian Lower Bound on the Local Unconditionality Constant of the James Space.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Houston Journal of Mathematics, 44: 873–885. August 2018.\n \n\n\n\n
\n\n\n\n \n \n \"AnJournal\n  \n \n \n \"AnArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{towsner15:lower_bound_james_space,\n   author = {{Towsner}, H.},\n    title = "{An Inverse Ackermannian Lower Bound on the Local Unconditionality Constant of the James Space}",\njournal={Houston Journal of Mathematics},\n     year = 2018,\n    month = aug,\n    volume = 44,\n    issue = 3,\n    pages = {873--885},\n    urljournal={https://www.math.uh.edu/~hjm/restricted/pdf44(3)/09towsner.pdf},\n    urlarxiv={http://arxiv.org/abs/1503.04745},\n    abstract={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.}\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n An Analytic Approach to Sparse Hypergraphs: Hypergraph Removal.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Discrete Analysis, (4). 2018.\n \n\n\n\n
\n\n\n\n \n \n \"AnArxiv\n  \n \n \n \"AnJournal\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 16 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{towsner12:_analy_approac_spars_hyper,\n  author = \t {Towsner, Henry},\n  title = \t {An Analytic Approach to Sparse Hypergraphs: Hypergraph Removal},\n  year = \t 2018,\n  journal={Discrete Analysis},\n  number={4},\nurlarxiv={http://arxiv.org/abs/1204.1884},\nurljournal={http://discreteanalysisjournal.com/article/3104-an-analytic-approach-to-sparse-hypergraphs-hypergraph-removal},\nabstract={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.},\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2017\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n More or Less Uniform Convergence.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n September 2017.\n submitted\n\n\n\n
\n\n\n\n \n \n \"MoreArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{1709.05687,\nauthor ={Henry Towsner},\ntitle = {More or Less Uniform Convergence},\nyear={2017},\nmonth= sep,\nnote={submitted},\nurlarxiv={https://arxiv.org/abs/1709.05687},\nabstract={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.\n\nWe 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. \n\nThe 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. \n\nWe 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<omega_1.}\n}\n\n\n
\n
\n\n\n
\n 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\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Computable Ramsey's Theorem for Pairs Needs Infinitely Many Pi-0-2 Sets.\n \n \n \n \n\n\n \n Igusa, G.; and Towsner, H.\n\n\n \n\n\n\n Archive for Mathematical Logic, 56(1). 2017.\n \n\n\n\n
\n\n\n\n \n \n \"ComputableJournal\n  \n \n \n \"ComputableArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@ARTICLE{igusa15:computable_ramseys_theorem,\n   author = {{Igusa}, G. and {Towsner}, H.},\n    title = "{Computable Ramsey's Theorem for Pairs Needs Infinitely Many Pi-0-2 Sets}",\nyear="2017",\nvolume="56",\nnumber="1",\n    journal = {Archive for Mathematical Logic},\n    doi="10.1007/s00153-016-0519-2",\n    urljournal={http://link.springer.com/article/10.1007/s00153-016-0519-2},\nurlarxiv={http://arxiv.org/abs/1507.03256},\nabstract={In [J], Theorem 4.2, Jockusch proves that for any computable k-coloring of pairs of integers, there is an infinite &Pi;<sup>0</sup><sup>2</sub> homogeneous set. The proof uses a countable collection of &Pi;<sup>0</sup><sup>2</sub> 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;<sup>0</sup><sup>2</sub> sets. We provide a proof of this latter fact.\n}\n}\n\n\n
\n
\n\n\n
\n In [J], Theorem 4.2, Jockusch proves that for any computable k-coloring of pairs of integers, there is an infinite Π02 homogeneous set. The proof uses a countable collection of Π02 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 Π02 sets. We provide a proof of this latter fact. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Sigma-Algebras for Quasirandom Hypergraphs.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Random Struct. Alg., 50(1): 114–139. 2017.\n \n\n\n\n
\n\n\n\n \n \n \"Sigma-AlgebrasJournal\n  \n \n \n \"Sigma-AlgebrasArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 11 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{towsner13:quasirandom_hypergraphs,\nauthor = {{Towsner}, H.},\ntitle = {Sigma-Algebras for Quasirandom Hypergraphs},\njournal = {Random Struct. Alg.},\nfjournal = {Random Structures \\& Algoritmhs},\nvolume = {50},\nnumber = {1},\npages = {114--139},\nyear = {2017},\nurljournal={http://onlinelibrary.wiley.com/doi/10.1002/rsa.20641/abstract},\ndoi={10.1002/rsa.20641},\nurlarxiv={http://arxiv.org/abs/1312.4882},\nabstract = {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]. \nWe 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.}\n}\n\n\n\n
\n
\n\n\n
\n 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ödl, and Schacht; Conlon, Hàn, Person, and Schacht; and Lenz and Mubayi giving this result for some notions of quasirandomness.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2016\n \n \n (4)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n Hanf Locality and Invariant Elementary Definability.\n \n \n \n\n\n \n Lindell, S.; Towsner, H.; and Weinstein, S.\n\n\n \n\n\n\n 2016.\n submitted\n\n\n\n
\n\n\n\n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{hanf_locality,\nauthor = {Steven Lindell and Henry Towsner and Scott Weinstein},\ntitle = {Hanf Locality and Invariant Elementary Definability},\nyear = {2016},\nnote = {submitted},\nabstract = {We introduce some notions of invariant elementary definability which extend the notions of first-order order-invariant definability, and, more generally, definability invariant with respect to arbitrary numerical rela tions. In particular, we study invariance with respect to expansions which depend not only on (an ordering of) the universe of a structure, but also on the particular relations which determine the structure; we call\nsuch expansions presentations of a structure. We establish two locality results in this context. The first is an extension of the original Hanf Locality Theorem to boolean queries which are invariantly definable over classes of locally finite structures with respect\nto elementary, neighborhood-bounded presentations. The second is a non-uniform version of the Fagin-\nStockmeyer-Vardi Hanf Threshold Locality Theorem to boolean queries which are invariantly definable over classes of bounded degree structures with respect to elementary, neighborhood-bounded, local presentations.}\n}\n\n
\n
\n\n\n
\n We introduce some notions of invariant elementary definability which extend the notions of first-order order-invariant definability, and, more generally, definability invariant with respect to arbitrary numerical rela tions. In particular, we study invariance with respect to expansions which depend not only on (an ordering of) the universe of a structure, but also on the particular relations which determine the structure; we call such expansions presentations of a structure. We establish two locality results in this context. The first is an extension of the original Hanf Locality Theorem to boolean queries which are invariantly definable over classes of locally finite structures with respect to elementary, neighborhood-bounded presentations. The second is a non-uniform version of the Fagin- Stockmeyer-Vardi Hanf Threshold Locality Theorem to boolean queries which are invariantly definable over classes of bounded degree structures with respect to elementary, neighborhood-bounded, local presentations.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n The structure of combinatorial Markov processes.\n \n \n \n \n\n\n \n Crane, H.; and Towsner, H.\n\n\n \n\n\n\n 2016.\n submitted\n\n\n\n
\n\n\n\n \n \n \"TheArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@misc{1603.05954,\nAuthor = {Harry Crane and Henry Towsner},\nTitle = {The structure of combinatorial Markov processes},\nYear = {2016},\nEprint = {arXiv:1603.05954},\nnote={submitted},\nurlarxiv={http://arxiv.org/abs/1603.05954},\nabstract={ Every exchangeable Feller process taking values in a suitably\nnice combinatorial state space can be constructed by a system of\niterated random Lipschitz functions. In discrete time, the construction\nproceeds by iterated application of independent, identically distributed\nfunctions, while in continuous time the random functions occur as the\natoms of a time homogeneous Poisson point process. We further show\nthat every exchangeable Feller process projects to a Feller process in an\nappropriate limit space, akin to the projection of partition-valued processes\ninto the ranked-simplex and graph-valued processes into the space\nof graph limits. Together, our main theorems establish common structural\nfeatures shared by all exchangeable combinatorial Feller processes,\nregardless of the dynamics or resident state space, thereby generalizing\nbehaviors previously observed for exchangeable coalescent and fragmentation\nprocesses as well as other combinatorial stochastic processes. If,\nin addition, an exchangeable Feller process evolves on a state space satisfying\nthe n-disjoint amalgamation property for all n >= 1, then its\njump measure can be decomposed explicitly in the sense of Lévy–Itô–\nKhintchine.}\n}\n\n\n
\n
\n\n\n
\n 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 >= 1, then its jump measure can be decomposed explicitly in the sense of Lévy–Itô– Khintchine.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n 8.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Volume 3 of Studies in Weak Arithmetic. Towards an Effective Theory of Absolutely Continuous Measures. Patrick Cégielski, A. E.; and Kossak, R., editor(s). CSLI, 2016.\n \n\n\n\n
\n\n\n\n \n \n \"TowardsJournal\n  \n \n \n \"TowardsArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@inbook{towsner:abs_cont,\n\tAuthor = {Towsner, Henry},\n\tChapter = {8},\n\tEditor = {Patrick C\\'egielski, Ali Enayat, and Roman Kossak},\n\tPublisher = {CSLI},\n\tSeries = {Studies in Weak Arithmetic},\n\tTitle = {Towards an Effective Theory of Absolutely Continuous Measures},\n\tVolume = {3},\n\tYear = {2016},\nurljournal={https://web.stanford.edu/group/cslipublications/cslipublications/site/9781575867236.shtml},\nurlarxiv={http://arxiv.org/abs/1503.04743},\n    abstract={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.\n}\n}\n\n
\n
\n\n\n
\n 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. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Separating Principles Below WKL0.\n \n \n \n \n\n\n \n Flood, S.; and Towsner, H.\n\n\n \n\n\n\n Mathematical Logic Quarterly, 62(6): 507–529. December 2016.\n \n\n\n\n
\n\n\n\n \n \n \"SeparatingJournal\n  \n \n \n \"SeparatingArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{flood14:separating_principles_below_wkl0,\n   author = {{Flood}, S. and {Towsner}, H.},\n    title = "{Separating Principles Below WKL0}",\njournal={Mathematical Logic Quarterly},\nyear={2016},\nmonth=dec,\nvolume = {62},\nnumber = {6},\nissn = {1521-3870},\nurljournal = {http://dx.doi.org/10.1002/malq.201500001},\ndoi = {10.1002/malq.201500001},\npages = {507--529},\nurlarxiv={http://arxiv.org/abs/1410.4068},\nabstract={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). \n\nWe 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).\n}\n}\n\n\n\n\n
\n
\n\n\n
\n 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). \n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2015\n \n \n (5)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Dividing and weak quasi-dimensions in arbitrary theories.\n \n \n \n \n\n\n \n Goldbring, I.; and Towsner, H.\n\n\n \n\n\n\n Archive for Mathematical Logic, 54(7-8): 915-920. 2015.\n \n\n\n\n
\n\n\n\n \n \n \"DividingPaper\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n \n \n\n\n\n
\n
@article{goldbring15:dividing,\nyear={2015},\nissn={0933-5846},\njournal={Archive for Mathematical Logic},\nvolume={54},\nnumber={7-8},\ndoi={10.1007/s00153-015-0449-4},\ntitle={Dividing and weak quasi-dimensions in arbitrary theories},\nurl={http://dx.doi.org/10.1007/s00153-015-0449-4},\npublisher={Springer Berlin Heidelberg},\nkeywords={Pseudofinite structure; Quasidimension; Dividing; 03C20; 03C45},\nauthor={Goldbring, Isaac and Towsner, Henry},\npages={915-920},\nlanguage={English},\nabstract={We show that any countable model of a model complete\ntheory has an elementary extension with a “pseudofinite-like” quasidimension\nthat detects dividing.}\n}\n\n\n
\n
\n\n\n
\n We show that any countable model of a model complete theory has an elementary extension with a “pseudofinite-like” quasidimension that detects dividing.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A Worked Example of the Functional Interpretation.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n March 2015.\n submitted\n\n\n\n
\n\n\n\n \n \n \"AArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 10 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@unpublished{towsner15:worked_example,\n   author = {{Towsner}, H.},\n    title = "{A Worked Example of the Functional Interpretation}",\n    note={submitted},\n     year = 2015,\n    month = mar,\n   urlarxiv = {http://arxiv.org/abs/1503.05572},\n  abstract = {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.}\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Limits of sequences of Markov chains.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Electron. J. Probab., 20: no. 77, 1-23. 2015.\n \n\n\n\n
\n\n\n\n \n \n \"LimitsJournal\n  \n \n \n \"LimitsArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n \n \n \n \n \n \n\n\n\n
\n
@article{towsner14:sequence_markov_chains,\n\tauthor = {Henry Towsner},\n\ttitle = {Limits of sequences of Markov chains},\n\tjournal = {Electron. J. Probab.},\n\tfjournal = {Electronic Journal of Probability},\n\tvolume = {20},\n\tyear = {2015},\n\tkeywords = {Markov chain, graph limit, ultraproduct},\n\tabstract = {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 convergent 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.},\n\tpages = {no. 77, 1-23},\n\tissn = {1083-6489},\n\tdoi = {10.1214/EJP.v20-4188},    \n        urljournal = {http://ejp.ejpecp.org/article/view/4188},\nurlarxiv={http://arxiv.org/abs/1404.3815},\n}\n\n\n\n\n
\n
\n\n\n
\n 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 convergent 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Infinitary methods in finite model theory.\n \n \n \n \n\n\n \n Lindell, S.; Towsner, H.; and Weinstein, S.\n\n\n \n\n\n\n In Hirvonen, A.; Kontinen, J.; Kossak, R.; and Villaveces, A., editor(s), Logic Without Borders. De Gruyter, 2015.\n \n\n\n\n
\n\n\n\n \n \n \"InfinitaryPdf\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@InCollection{lindell13:_infin,\n  author = \t {Steven Lindell and Henry Towsner and Scott Weinstein},\n  title = \t {Infinitary methods in finite model theory},\n  booktitle = {Logic Without Borders},\n  publisher = {de Gruyter},\n  year = \t 2015,\n  editor = \t {Asa Hirvonen and Juha Kontinen and Roman Kossak and Andr\\'es Villaveces},\n  urlpdf = {http://ww3.haverford.edu/cmsc/slindell/Infinitary%20methods.pdf},\nabstract={\nThis paper explores applications of the infinitary techniques of classical model theory in\nthe context of finite model theory, and thus elaborates on themes explored by V&auml;&auml;n&auml;nen\n(2003). We are grateful for the opportunity to celebrate Jouko's inclusive vision of logic\nin this way.\n}\n}\n\n
\n
\n\n\n
\n This paper explores applications of the infinitary techniques of classical model theory in the context of finite model theory, and thus elaborates on themes explored by Väänänen (2003). We are grateful for the opportunity to celebrate Jouko's inclusive vision of logic in this way. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n On Maximum Conservative Extensions.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Computability, 4: 57–68. 2015.\n \n\n\n\n
\n\n\n\n \n \n \"OnArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 12 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@Article{towsner13:maximal_conservatve,\n  author = \t {Towsner, H.},\n  title = \t {On Maximum Conservative Extensions},\n  journal = \t {Computability},\n  year = \t 2015,\n  volume = \t 4,\n  pages = \t {57--68},\nurlarxiv={http://arxiv.org/abs/1302.1488},\nabstract={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.}\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2014\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Randomness and non-ergodic systems.\n \n \n \n \n\n\n \n Franklin, J. N. Y.; and Towsner, H.\n\n\n \n\n\n\n Mosc. Math. J., 14(4): 711–744, 827. 2014.\n \n\n\n\n
\n\n\n\n \n \n \"RandomnessArxiv\n  \n \n \n \"RandomnessJournal\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {franklin12:_random_non_system,\n    AUTHOR = {Franklin, Johanna N. Y. and Towsner, Henry},\n     TITLE = {Randomness and non-ergodic systems},\n   JOURNAL = {Mosc. Math. J.},\n  FJOURNAL = {Moscow Mathematical Journal},\n    VOLUME = {14},\n      YEAR = {2014},\n    NUMBER = {4},\n     PAGES = {711--744, 827},\n      ISSN = {1609-3321},\n   MRCLASS = {37A25 (03D32)},\n  MRNUMBER = {3292047},\nurlarxiv={http://arxiv.org/abs/1206.2682},\nurljournal={http://www.mathjournals.org/mmj/2014-014-004/2014-014-004-004.html},\nabstract={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.},\n}\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Ultrafilters in reverse mathematics.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n J. Math. Logic, 14(01): 1450001. 2014.\n \n\n\n\n
\n\n\n\n \n \n \"UltrafiltersArxiv\n  \n \n \n \"UltrafiltersJournal\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 155 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{doi:10.1142/S0219061314500019,\nauthor = {Towsner, Henry},\ntitle = {Ultrafilters in reverse mathematics},\njournal={J. Math. Logic},\nfjournal={Journal of Mathematical Logic},\nvolume = {14},\nnumber = {01},\npages = {1450001},\nyear = {2014},\ndoi = {10.1142/S0219061314500019},\nurlarxiv={http://arxiv.org/abs/1109.3902},\nabstract={We extend theories of reverse mathematics by a non-principal ultrafilter, and show that these are conservative extensions of the usual theories ACA<sub>0</sub>, ATR<sub>0</sub>, and &Pi;<sup>1</sup><sub>1</sub>-Comprehension.},\nurljournal = {http://www.worldscientific.com/doi/pdf/10.1142/S0219061314500019}\n}\n\n\n\n
\n
\n\n\n
\n 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 Π11-Comprehension.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n An approximate logic for measures.\n \n \n \n \n\n\n \n Goldbring, I.; and Towsner, H.\n\n\n \n\n\n\n Israel J. Math., 199(2): 867-913. 2014.\n \n\n\n\n
\n\n\n\n \n \n \"AnJournal\n  \n \n \n \"AnArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 69 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{goldbring:_approx_logic_measur,\nyear={2014},\nissn={0021-2172},\njournal={Israel J. Math.},\nfjournal={Israel Journal of Mathematics},\nvolume={199},\nnumber={2},\ndoi={10.1007/s11856-013-0054-3},\ntitle={An approximate logic for measures},\nurljournal={http://dx.doi.org/10.1007/s11856-013-0054-3},\npublisher={The Hebrew University Magnes Press},\nauthor={Goldbring, Isaac and Towsner, Henry},\npages={867-913},\nlanguage={English},\nurlarxiv={http://arxiv.org/abs/1106.2854},\nabstract={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&eacute;di Regularity Lemma. We also derive some connections between the model-theoretic notion of stability and the Gowers uniformity norms from combinatorics.},\n}\n\n\n
\n
\n\n\n
\n 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édi Regularity Lemma. We also derive some connections between the model-theoretic notion of stability and the Gowers uniformity norms from combinatorics.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2013\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Separating principles below Ramsey's Theorem for Pairs.\n \n \n \n \n\n\n \n Lerman, M.; Solomon, R.; and Towsner, H.\n\n\n \n\n\n\n J. Math. Logic, 13(02): 1350007. 2013.\n \n\n\n\n
\n\n\n\n \n \n \"SeparatingJournal\n  \n \n \n \"SeparatingArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 35 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{doi:10.1142/S0219061313500074,\nauthor = {{Lerman}, M. and {Solomon}, R. and {Towsner}, H.},\ntitle = {Separating principles below Ramsey's Theorem for Pairs},\njournal={J. Math. Logic},\nfjournal={Journal of Mathematical Logic},\nvolume = {13},\nnumber = {02},\npages = {1350007},\nyear = {2013},\ndoi = {10.1142/S0219061313500074},\nURLjournal = {http://www.worldscientific.com/doi/abs/10.1142/S0219061313500074},\nurlarxiv={http://arxiv.org/abs/1302.0828},\nabstract={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.},\n}\n\n\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Partial Impredicativity in Reverse Mathematics.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n J. Symbolic Logic, 78(2): 459–488. 2013.\n \n\n\n\n
\n\n\n\n \n \n \"PartialJournal\n  \n \n \n \"PartialArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 33 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article{towsner11:_approx_impred_rever_mathem,\n  author = \t {Towsner, Henry},\n  title = \t {Partial Impredicativity in Reverse Mathematics},\njournal={J. Symbolic Logic},\nfjournal={Journal of Symbolic Logic},\nvolume={78},\nnumber={2},\npages={459--488},\nurljournal={http://projecteuclid.org/euclid.jsl/1368627060},\n  year = \t 2013,\nurlarxiv={http://arxiv.org/abs/1106.6063},\nabstract={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;<sup>1</sup><sub>2</sub> sentence from the theory &Pi;<sup>1</sup><sub>1</sub>-Comprehension. Using methods based on the functional interpretation, we introduce a family of weakenings of &Pi;<sup>1</sup><sub>1</sub>-Comprehension and use them to give new upper bounds for the Nash-Williams Theorem of wqo theory and Menger's Theorem for countable graphs.}\n}\n\n
\n
\n\n\n
\n 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 Π12 sentence from the theory Π11-Comprehension. Using methods based on the functional interpretation, we introduce a family of weakenings of Π11-Comprehension and use them to give new upper bounds for the Nash-Williams Theorem of wqo theory and Menger's Theorem for countable graphs.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2012\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Transfinite approximation of Hindman's theorem.\n \n \n \n \n\n\n \n Beiglbock, M.; and Towsner, H.\n\n\n \n\n\n\n Israel J. Math., 191: 41–59. 2012.\n \n\n\n\n
\n\n\n\n \n \n \"TransfiniteJournal\n  \n \n \n \"TransfiniteArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 45 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2970862,\n    AUTHOR = {Beiglbock, Mathias and Towsner, Henry},\n     TITLE = {Transfinite approximation of {H}indman's theorem},\n   JOURNAL = {Israel J. Math.},\n  FJOURNAL = {Israel Journal of Mathematics},\n    VOLUME = {191},\n      YEAR = {2012},\n     PAGES = {41--59},\n      ISSN = {0021-2172},\n     CODEN = {ISJMAP},\n   MRCLASS = {Preliminary Data},\n  MRNUMBER = {2970862},\n       DOI = {10.1007/s11856-011-0195-1},\n       URLJOURNAL = {http://dx.doi.org/10.1007/s11856-011-0195-1},\nurlarxiv={http://arxiv.org/abs/1001.1175},\nabstract={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.},\n}\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A Simple Proof and Some Difficult Examples for Hindman's Theorem.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Notre Dame J. Formal Logic, 53(1): 53-65. 2012.\n \n\n\n\n
\n\n\n\n \n \n \"AJournal\n  \n \n \n \"AArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 47 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@Article{towsner12:_simpl_proof_some_diffic_examp_hindm_theor,\n  author = \t {Towsner, Henry},\n  title = \t {A Simple Proof and Some Difficult Examples for {H}indman's Theorem},\njournal = {Notre Dame J. Formal Logic},\n  fjournal = \t {Notre Dame Journal of Formal Logic},\n  year = \t 2012,\n  volume = \t 53,\n  number = \t 1,\n  pages = \t {53-65},\nurljournal={http://projecteuclid.org/euclid.ndjfl/1336586237},\nurlarxiv={http://arxiv.org/abs/0906.3885},\nabstract={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.},\n}\n\n
\n
\n\n\n
\n 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A Correspondence Principle for the Gowers Uniformity Norms.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Journal of Logic and Analysis, 4. February 2012.\n \n\n\n\n
\n\n\n\n \n \n \"AJournal\n  \n \n \n \"AArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 30 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@Article{towsner12:_corres_princ_gower_unifor_norms,\n  author = \t {Towsner, Henry},\n  title = \t {A Correspondence Principle for the {G}owers Uniformity Norms},\n  journal = \t {Journal of Logic and Analysis},\n  year = \t 2012,\n  volume = \t 4,\n  month = \t {February},\nurljournal={http://logicandanalysis.org/index.php/jla/article/view/139/51},\nurlarxiv={http://arxiv.org/abs/0905.0493},\nabstract={We give a variation of the Furstenberg Correspondence which preserves the Gowers uniformity norms.},\n}\n\n
\n
\n\n\n
\n We give a variation of the Furstenberg Correspondence which preserves the Gowers uniformity norms.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2011\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n A combinatorial proof of the dense Hindman's theorem.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Discrete Math., 311(14): 1380–1384. 2011.\n \n\n\n\n
\n\n\n\n \n \n \"AJournal\n  \n \n \n \"AArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 44 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2795548,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {A combinatorial proof of the dense {H}indman's theorem},\n   JOURNAL = {Discrete Math.},\n  FJOURNAL = {Discrete Mathematics},\n    VOLUME = {311},\n      YEAR = {2011},\n    NUMBER = {14},\n     PAGES = {1380--1384},\n      ISSN = {0012-365X},\n     CODEN = {DSMHA4},\n   MRCLASS = {05D10 (03C20)},\n  MRNUMBER = {2795548 (2012h:05349)},\nMRREVIEWER = {Damir D. Dzhafarov},\n       DOI = {10.1016/j.disc.2011.03.006},\n       URLJOURNAL= {http://dx.doi.org/10.1016/j.disc.2011.03.006},\nurlarxiv={http://arxiv.org/abs/1002.0347},\nabstract={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<sub>1</sub>, for each b<sub>1</sub>&isin; B<sub>1</sub> a "dense" set B<sub>2</sub>(b<sub>1</sub>) (depending on b<sub>1</sub>), for each b<sub>2</sub>&isin; B<sub>2</sub>(b<sub>1</sub>) a "dense" set B<sub>3</sub>(b<sub>1</sub>, b<sub>2</sub>) (depending on b<sub>1</sub>, b<sub>2</sub>), and so on, such that for any such sequence of b<sub>i</sub>, 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.}\n}\n\n\n
\n
\n\n\n
\n The Dense Hindman's Theorem states that, in any finite coloring of the integers, one may find a single color and a \"dense\" set B1, for each b1∈ B1 a \"dense\" set B2(b1) (depending on b1), for each b2∈ B2(b1) a \"dense\" set B3(b1, b2) (depending on b1, b2), and so on, such that for any such sequence of bi, 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.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hindman's theorem: an ultrafilter argument in second order arithmetic.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n J. Symbolic Logic, 76(1): 353–360. 2011.\n \n\n\n\n
\n\n\n\n \n \n \"Hindman'sJournal\n  \n \n \n \"Hindman'sArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 56 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2791353,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {Hindman's theorem: an ultrafilter argument in second order\n              arithmetic},\n   JOURNAL = {J. Symbolic Logic},\n  FJOURNAL = {Journal of Symbolic Logic},\n    VOLUME = {76},\n      YEAR = {2011},\n    NUMBER = {1},\n     PAGES = {353--360},\n      ISSN = {0022-4812},\n     CODEN = {JSYLA6},\n   MRCLASS = {03F35 (54D80)},\n  MRNUMBER = {2791353 (2012b:03165)},\nMRREVIEWER = {M. Yasuhara},\n       DOI = {10.2178/jsl/1294171005},\n       URLJOURNAL= {http://dx.doi.org/10.2178/jsl/1294171005},\nurlarxiv={http://arxiv.org/abs/0906.3882},\nabstract={Hindman's Theorem is a prototypical example of a combinatorial theorem with a proof that uses the topology of the ultrafilters. We show how the methods of this proof, including topological arguments about ultrafilters, can be translated into second order arithmetic.},\n}\n\n\n\n
\n
\n\n\n
\n Hindman's Theorem is a prototypical example of a combinatorial theorem with a proof that uses the topology of the ultrafilters. We show how the methods of this proof, including topological arguments about ultrafilters, can be translated into second order arithmetic.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2010\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Metastability in the Furstenberg-Zimmer tower.\n \n \n \n \n\n\n \n Avigad, J.; and Towsner, H.\n\n\n \n\n\n\n Fund. Math., 210(3): 243–268. 2010.\n \n\n\n\n
\n\n\n\n \n \n \"MetastabilityJournal\n  \n \n \n \"MetastabilityArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 23 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2733051,\n    AUTHOR = {Avigad, Jeremy and Towsner, Henry},\n     TITLE = {Metastability in the {F}urstenberg-{Z}immer tower},\n   JOURNAL = {Fund. Math.},\n  FJOURNAL = {Fundamenta Mathematicae},\n    VOLUME = {210},\n      YEAR = {2010},\n    NUMBER = {3},\n     PAGES = {243--268},\n      ISSN = {0016-2736},\n   MRCLASS = {37A05 (03E15 03F03 28D05 37A25)},\n  MRNUMBER = {2733051 (2012b:37003)},\nMRREVIEWER = {Michael H. Schraudner},\n       DOI = {10.4064/fm210-3-2},\n       URLJOURNAL= {http://dx.doi.org/10.4064/fm210-3-2},\nurlarxiv={http://arxiv.org/abs/0902.0356},\nabstract={According to the Furstenberg-Zimmer structure theorem, every measure-preserving system has a maximal distal factor, and is weak mixing relative to that factor. Furstenberg and Katznelson used this structural analysis of measure-preserving systems to provide a perspicuous proof of Szemer&eacute;di's theorem. Beleznay and Foreman showed that, in general, the transfinite construction of the maximal distal factor of a separable measure-preserving system can extend arbitrarily far into the countable ordinals. Here we show that the Furstenberg-Katznelson proof does not require the full strength of the maximal distal factor, in the sense that the proof only depends on a combinatorial weakening of its properties. We show that this combinatorially weaker property obtains fairly low in the transfinite construction, namely, by the &\\omega;<sup>&\\omega;<sup>&\\omega;</sup></sup>th level.}\n}\n\n
\n
\n\n\n
\n According to the Furstenberg-Zimmer structure theorem, every measure-preserving system has a maximal distal factor, and is weak mixing relative to that factor. Furstenberg and Katznelson used this structural analysis of measure-preserving systems to provide a perspicuous proof of Szemerédi's theorem. Beleznay and Foreman showed that, in general, the transfinite construction of the maximal distal factor of a separable measure-preserving system can extend arbitrarily far into the countable ordinals. Here we show that the Furstenberg-Katznelson proof does not require the full strength of the maximal distal factor, in the sense that the proof only depends on a combinatorial weakening of its properties. We show that this combinatorially weaker property obtains fairly low in the transfinite construction, namely, by the &ω;&ω;&ω;th level.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Priority arguments and epsilon substitution.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n In Proofs, categories and computations, volume 13, of Tributes, pages 251–266. Coll. Publ., London, 2010.\n \n\n\n\n
\n\n\n\n \n \n \"PriorityArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 24 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@incollection {MR2856914,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {Priority arguments and epsilon substitution},\n BOOKTITLE = {Proofs, categories and computations},\n    SERIES = {Tributes},\n    VOLUME = {13},\n     PAGES = {251--266},\n PUBLISHER = {Coll. Publ., London},\n      YEAR = {2010},\n   MRCLASS = {03F30 (03D25 03D30 03F03)},\n  MRNUMBER = {2856914 (2012i:03165)},\nurlarxiv={http://arxiv.org/abs/0812.3434},\nabstract={Kreisel has observed that the termination proof for Hilbert's epsilon-substitution method bears a resemblance to the priority arguments used in recursion theory. We make this precise by proving the termination using a framework for priority arguments due to Lerman and Lempp.},\n}\n\n
\n
\n\n\n
\n Kreisel has observed that the termination proof for Hilbert's epsilon-substitution method bears a resemblance to the priority arguments used in recursion theory. We make this precise by proving the termination using a framework for priority arguments due to Lerman and Lempp.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Local stability of ergodic averages.\n \n \n \n \n\n\n \n Avigad, J.; Gerhardy, P.; and Towsner, H.\n\n\n \n\n\n\n Trans. Amer. Math. Soc., 362(1): 261–288. 2010.\n \n\n\n\n
\n\n\n\n \n \n \"LocalJournal\n  \n \n \n \"LocalArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 23 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2550151,\n    AUTHOR = {Avigad, Jeremy and Gerhardy, Philipp and Towsner, Henry},\n     TITLE = {Local stability of ergodic averages},\n   JOURNAL = {Trans. Amer. Math. Soc.},\n  FJOURNAL = {Transactions of the American Mathematical Society},\n    VOLUME = {362},\n      YEAR = {2010},\n    NUMBER = {1},\n     PAGES = {261--288},\n      ISSN = {0002-9947},\n     CODEN = {TAMTAM},\n   MRCLASS = {03F60 (28D05)},\n  MRNUMBER = {2550151 (2011e:03082)},\nMRREVIEWER = {Josef Berger},\n       DOI = {10.1090/S0002-9947-09-04814-4},\n       URLJOURNAL= {http://dx.doi.org/10.1090/S0002-9947-09-04814-4},\nurlarxiv={http://arxiv.org/abs/0706.1512},\nabstract={The mean ergodic theorem is equivalent to the assertion that for every function K and every epsilon, there is an n with the property that the ergodic averages A<sub>m</sub> f are stable to within epsilon on the interval [n,K(n)]. We show that even though it is not generally possible to compute a bound on the rate of convergence of a sequence of ergodic averages, one can give explicit bounds on n in terms of K and || f || / epsilon. This tells us how far one has to search to find an n so that the ergodic averages are "locally stable" on a large interval. We use these bounds to obtain a similarly explicit version of the pointwise ergodic theorem, and show that our bounds are qualitatively different from ones that can be obtained using upcrossing inequalities due to Bishop and Ivanov. Finally, we explain how our positive results can be viewed as an application of a body of general proof-theoretic methods falling under the heading of "proof mining."},\n}\n\n
\n
\n\n\n
\n The mean ergodic theorem is equivalent to the assertion that for every function K and every epsilon, there is an n with the property that the ergodic averages Am f are stable to within epsilon on the interval [n,K(n)]. We show that even though it is not generally possible to compute a bound on the rate of convergence of a sequence of ergodic averages, one can give explicit bounds on n in terms of K and || f || / epsilon. This tells us how far one has to search to find an n so that the ergodic averages are \"locally stable\" on a large interval. We use these bounds to obtain a similarly explicit version of the pointwise ergodic theorem, and show that our bounds are qualitatively different from ones that can be obtained using upcrossing inequalities due to Bishop and Ivanov. Finally, we explain how our positive results can be viewed as an application of a body of general proof-theoretic methods falling under the heading of \"proof mining.\"\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2009\n \n \n (4)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Metastability in the Furstenberg-Zimmer Tower II: Polynomial and Multidimensional Szemerédi's Theorem.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n 2009.\n draft\n\n\n\n
\n\n\n\n \n \n \"MetastabilityArxiv\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@Unpublished{towsner09:_metas_furst_zimmer_tower_ii,\n  author = \t {Towsner, Henry},\n  title = \t {Metastability in the {F}urstenberg-{Z}immer Tower II: Polynomial and Multidimensional {S}zemer\\'edi's Theorem},\n  note = \t {draft},\n  year = \t 2009,\nurlarxiv={http://arxiv.org/abs/0909.5668},\nabstract={The Furstenberg-Zimmer structure theorem for &integers;<sub>d,</sub> 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;<sup>&omega;<sup>&omega;<sup>&omega;</sup></sup></sup>).\n}\n}\n\n
\n
\n\n\n
\n The Furstenberg-Zimmer structure theorem for ℤ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édi's theorem, and Bergelson and Liebman further generalized to a polynomial Szemerédi'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, ωωωω). \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Functional interpretation and inductive definitions.\n \n \n \n \n\n\n \n Avigad, J.; and Towsner, H.\n\n\n \n\n\n\n J. Symbolic Logic, 74(4): 1100–1120. 2009.\n \n\n\n\n
\n\n\n\n \n \n \"FunctionalJournal\n  \n \n \n \"FunctionalArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 35 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2583811,\n    AUTHOR = {Avigad, Jeremy and Towsner, Henry},\n     TITLE = {Functional interpretation and inductive definitions},\n   JOURNAL = {J. Symbolic Logic},\n  FJOURNAL = {Journal of Symbolic Logic},\n    VOLUME = {74},\n      YEAR = {2009},\n    NUMBER = {4},\n     PAGES = {1100--1120},\n      ISSN = {0022-4812},\n     CODEN = {JSYLA6},\n   MRCLASS = {03F10 (03F15 03F35)},\n  MRNUMBER = {2583811 (2011c:03137)},\nMRREVIEWER = {H. Schwichtenberg},\n       DOI = {10.2178/jsl/1254748682},\n       URLJOURNAL= {http://dx.doi.org/10.2178/jsl/1254748682},\nurlarxiv={http://arxiv.org/abs/0802.1938},\nabstract={Extending G&ouml;odel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.},\n}\n\n
\n
\n\n\n
\n Extending Göodel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Convergence of diagonal ergodic averages.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Ergodic Theory Dynam. Systems, 29(4): 1309–1326. 2009.\n \n\n\n\n
\n\n\n\n \n \n \"ConvergenceJournal\n  \n \n \n \"ConvergenceArxiv\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 21 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2529651,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {Convergence of diagonal ergodic averages},\n   JOURNAL = {Ergodic Theory Dynam. Systems},\n  FJOURNAL = {Ergodic Theory and Dynamical Systems},\n    VOLUME = {29},\n      YEAR = {2009},\n    NUMBER = {4},\n     PAGES = {1309--1326},\n      ISSN = {0143-3857},\n   MRCLASS = {37A30 (28D15)},\n  MRNUMBER = {2529651 (2010f:37005)},\nMRREVIEWER = {Bryna Kra},\n       DOI = {10.1017/S0143385708000722},\n       URLJOURNAL= {http://dx.doi.org/10.1017/S0143385708000722},\nurlarxiv={http://arxiv.org/abs/0711.1180},\nabstract={Tao has recently proved that if T<sub>1</sub>,&hellip;,T<sub>l</sub> are commuting, invertible, measure-preserving transformations on a dynamical system then for any L<sub>&infin;</sub> functions f<sub>1</sub>,&hellip;f<sub>l</sub>, the average (1/N)&Sigma;<sub>n=0</sub><sup>N-1</sup>&Pi;<sub>i&leq;l</sub>f<sub>i</sub> o T<sup>in</sup> converges in the L<sub>2</sub> norm.  Tao's proof is unusual in that it translates the problem into a more complicated statement about the combinatorics of finite spaces by using the Furstenberg correspondence "backwards". In this paper, we give an ergodic proof of this theorem, essentially a translation of Tao's argument to the ergodic setting. In order to do this, we develop two new variations on the usual Furstenberg correspondence, both of which take recurrence-type statements in one dynamical system and give equivalent statements in a different dynamical system with desirable properties.\n},\n}\n\n
\n
\n\n\n
\n Tao has recently proved that if T1,…,Tl are commuting, invertible, measure-preserving transformations on a dynamical system then for any L functions f1,…fl, the average (1/N)Σn=0N-1Πi≤lfi o Tin converges in the L2 norm. Tao's proof is unusual in that it translates the problem into a more complicated statement about the combinatorics of finite spaces by using the Furstenberg correspondence \"backwards\". In this paper, we give an ergodic proof of this theorem, essentially a translation of Tao's argument to the ergodic setting. In order to do this, we develop two new variations on the usual Furstenberg correspondence, both of which take recurrence-type statements in one dynamical system and give equivalent statements in a different dynamical system with desirable properties. \n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Ordinal analysis by transformations.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Ann. Pure Appl. Logic, 157(2-3): 269–280. 2009.\n \n\n\n\n
\n\n\n\n \n \n \"OrdinalJournal\n  \n \n \n \"OrdinalPdf\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 36 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2499713,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {Ordinal analysis by transformations},\n   JOURNAL = {Ann. Pure Appl. Logic},\n  FJOURNAL = {Annals of Pure and Applied Logic},\n    VOLUME = {157},\n      YEAR = {2009},\n    NUMBER = {2-3},\n     PAGES = {269--280},\n      ISSN = {0168-0072},\n     CODEN = {APALD7},\n   MRCLASS = {03F05 (03F15 03F35)},\n  MRNUMBER = {2499713 (2010e:03069)},\nMRREVIEWER = {Thomas Strahm},\n       DOI = {10.1016/j.apal.2008.09.011},\n       URLJOURNAL= {http://dx.doi.org/10.1016/j.apal.2008.09.011},\nurlpdf={http://www.sas.upenn.edu/~htowsner/KPiMu.pdf},\nabstract={The technique of using infinitary rules in an ordinal analysis has been one of the\nmost productive developments in ordinal analysis. Unfortunately, one of the most\nadvanced variants, the Buchholz &Omega;<sub>&mu;</sub>-rule, does not apply to systems much stronger\nthan &Pi;<sup>1</sup><sub>1</sub>-comprehension. In this paper, we propose a new extension of the \n rule using game-theoretic quantifiers. We apply this to a system of inductive definitions\nwith the strength of a recursively inaccessible ordinal.},\n}\n\n
\n
\n\n\n
\n The technique of using infinitary rules in an ordinal analysis has been one of the most productive developments in ordinal analysis. Unfortunately, one of the most advanced variants, the Buchholz Ωμ-rule, does not apply to systems much stronger than Π11-comprehension. In this paper, we propose a new extension of the rule using game-theoretic quantifiers. We apply this to a system of inductive definitions with the strength of a recursively inaccessible ordinal.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2005\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Epsilon substitution for transfinite induction.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Arch. Math. Logic, 44(4): 397–412. 2005.\n \n\n\n\n
\n\n\n\n \n \n \"EpsilonJournal\n  \n \n \n \"EpsilonPdf\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 42 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2139689,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {Epsilon substitution for transfinite induction},\n   JOURNAL = {Arch. Math. Logic},\n  FJOURNAL = {Archive for Mathematical Logic},\n    VOLUME = {44},\n      YEAR = {2005},\n    NUMBER = {4},\n     PAGES = {397--412},\n      ISSN = {0933-5846},\n     CODEN = {AMLOEH},\n   MRCLASS = {03F05 (03F07 03F30)},\n  MRNUMBER = {2139689 (2006c:03083)},\nMRREVIEWER = {Christian Bennet},\n       DOI = {10.1007/s00153-004-0241-3},\n       URLJOURNAL= {http://dx.doi.org/10.1007/s00153-004-0241-3},\nurlpdf={http://www.sas.upenn.edu/~htowsner/esubTI.pdf},\nabstract = {We apply Mints' technique for proving the termination of the epsilon\nsubstitution method via cut-elimination to the system of Peano Arithmetic with Transfinite Induction given by Arai.},\n}\n\n
\n
\n\n\n
\n We apply Mints' technique for proving the termination of the epsilon substitution method via cut-elimination to the system of Peano Arithmetic with Transfinite Induction given by Arai.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2004\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n A realizability interpretation for classical analysis.\n \n \n \n \n\n\n \n Towsner, H.\n\n\n \n\n\n\n Arch. Math. Logic, 43(7): 891–900. 2004.\n \n\n\n\n
\n\n\n\n \n \n \"AJournal\n  \n \n \n \"APdf\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 58 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@article {MR2096140,\n    AUTHOR = {Towsner, Henry},\n     TITLE = {A realizability interpretation for classical analysis},\n   JOURNAL = {Arch. Math. Logic},\n  FJOURNAL = {Archive for Mathematical Logic},\n    VOLUME = {43},\n      YEAR = {2004},\n    NUMBER = {7},\n     PAGES = {891--900},\n      ISSN = {0933-5846},\n     CODEN = {AMLOEH},\n   MRCLASS = {03F35 (03F05)},\n  MRNUMBER = {2096140 (2005i:03070)},\nMRREVIEWER = {Thomas Strahm},\n       DOI = {10.1007/s00153-004-0233-3},\n       URLJOURNAL= {http://dx.doi.org/10.1007/s00153-004-0233-3},\nurlpdf={http://www.sas.upenn.edu/~htowsner/realize.pdf},\nabstract={We present a realizability interpretation for classical analysis&mdash;an association\nof a term to every proof so that the terms assigned to existential formulas represent witnesses to the truth of that formula. For classical proofs of &Pi;<sub>2</sub> sentences &forall; x &exist; y A(x,y), this provides a recursive type 1 function which computes the function given by f(x)=y iff y is the least number such that A(x,y).},\n}\n
\n
\n\n\n
\n We present a realizability interpretation for classical analysis—an association of a term to every proof so that the terms assigned to existential formulas represent witnesses to the truth of that formula. For classical proofs of Π2 sentences ∀ x ∃ y A(x,y), this provides a recursive type 1 function which computes the function given by f(x)=y iff y is the least number such that A(x,y).\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n\n\n \n\n \n \n \n \n\n
\n"}; document.write(bibbase_data.data);