Back to search

Cornell University

Measuring the Relative Complexity of Mathematical Constructions and Theorems

Abstract

dc:description.abstract

We investigate the relative complexity of mathematical constructions and theorems using the frameworks of computable reducibilities and reverse mathematics. First, we study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (\mathsf{ATR}0) from the point of view of computable reducibilities, in particular Weihrauch reducibility. We show that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. We obtain a similar result for Fra\"iss\'e's conjecture restricted to well-orderings. We then turn our attention to K\"onig's duality theorem, which generalizes K\"onig's theorem about matchings and covers to infinite bipartite graphs. We show that the problem of constructing a K\"onig cover of a given bipartite graph is roughly as hard as the following ``two-sided'' version of the aforementioned jump hierarchy problem: given a \emph{linear} ordering $L$, construct either a jump hierarchy on $L$ (which may be a pseudohierarchy), or an infinite $L$-descending sequence. We also obtain several results relating the above problems with choice on Baire space (choosing a path on a given ill-founded tree) and unique choice on Baire space (given a tree with a unique path, produce said path). Next, we investigate three known ways to formalize the notion of solving a problem by applying other problems in series: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general. Next, we turn our attention to the parallel product. In joint work with Dzhafarov, Hirschfeldt, Patey and Pauly, we investigate the infinite pigeonhole principle for different numbers of colors and how these problems behave under Weihrauch reducibility with respect to parallel products. Finally, we leave the setting of computable reducibilities for the setting of reverse mathematics. First, we define a \Sigma11 axiom of finite choice and investigate its relationships with other theorems of hyperarithmetic analysis. For one, we show that it follows from Arithmetic Bolzano-Weierstrass. On the other hand, using an elaboration of Steel's forcing with tagged trees, we show that it does not follow from \Delta11 comprehension. Second, in joint work with James Barnes and Richard A.\ Shore, we analyze a theorem of Halin about disjoint rays in graphs. Our main result shows that Halin's theorem is a theorem of hyperarithmetic analysis, making it only the second ``natural'' (i.e., not formulated using concepts from logic) theorem with this property.

Degree

thesis:*
Name thesis:degree_name
Ph.D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Goh, Jun Le
Chair dc:contributor.chair
  • Shore, Richard A.
Committee members dc:contributor.committeemember
  • Halpern, Joseph Yehuda
  • Nerode, Anil

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
11050558
Dc Identifier Other
ProQuest Submission ID: 11586
ProQuest Publication ID: 22587310

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Goh, Jun Le. Measuring the Relative Complexity of Mathematical Constructions and Theorems. Doctor of Philosophy thesis, Cornell University, 2019. https://hdl.handle.net/1813/67575