<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T10:57:36Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/67575" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/67575</identifier><datestamp>2026-05-15T19:44:28Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Goh, Jun Le</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair">Shore, Richard A.</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Halpern, Joseph Yehuda</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Nerode, Anil</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2019-10-15T16:48:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2019-10-15T16:48:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2019-08-30</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Submission ID: 11586</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Publication ID: 22587310</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/67575</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="doi">https://doi.org/10.7298/0h3c-x173</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">11050558</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="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 $\Sigma^1_1$ 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 $\Delta^1_1$ 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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en_US</dim:field>
   <dim:field mdschema="dc" element="subject">Mathematics</dim:field>
   <dim:field mdschema="dc" element="subject">Logic</dim:field>
   <dim:field mdschema="dc" element="subject">Arithmetical Transfinite Recursion</dim:field>
   <dim:field mdschema="dc" element="subject">Computable reducibility</dim:field>
   <dim:field mdschema="dc" element="subject">Hyperarithmetical theory</dim:field>
   <dim:field mdschema="dc" element="subject">Pseudohierarchy</dim:field>
   <dim:field mdschema="dc" element="subject">Reverse mathematics</dim:field>
   <dim:field mdschema="dc" element="subject">Weihrauch reducibility</dim:field>
   <dim:field mdschema="dc" element="title">Measuring the Relative Complexity of Mathematical Constructions and Theorems</dim:field>
   <dim:field mdschema="dc" element="type">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Mathematics</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph.D., Mathematics</dim:field>
   <dim:field mdschema="dcterms" element="license">https://hdl.handle.net/1813/59810</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Goh, Jun Le</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="d4af1558-8081-410e-bde6-a236a8c7124d">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>Measuring the Relative Complexity of Mathematical Constructions and Theorems&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2019-08-30&lt;/PublicationDate>
   	&lt;DOI>https://doi.org/10.7298/0h3c-x173&lt;/DOI>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Goh, Jun Le&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>Mathematics&lt;/Keyword>
    &lt;Keyword>Logic&lt;/Keyword>
    &lt;Keyword>Arithmetical Transfinite Recursion&lt;/Keyword>
    &lt;Keyword>Computable reducibility&lt;/Keyword>
    &lt;Keyword>Hyperarithmetical theory&lt;/Keyword>
    &lt;Keyword>Pseudohierarchy&lt;/Keyword>
    &lt;Keyword>Reverse mathematics&lt;/Keyword>
    &lt;Keyword>Weihrauch reducibility&lt;/Keyword>
   	&lt;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\&amp;quot;iss\&amp;apos;e&amp;apos;s conjecture restricted to well-orderings. We then turn our attention to K\&amp;quot;onig&amp;apos;s duality theorem, which generalizes K\&amp;quot;onig&amp;apos;s theorem about matchings and covers to infinite bipartite graphs. We show that the problem of constructing a K\&amp;quot;onig cover of a given bipartite graph is roughly as hard as the following ``two-sided&amp;apos;&amp;apos; 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 $\Sigma^1_1$ 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&amp;apos;s forcing with tagged trees, we show that it does not follow from $\Delta^1_1$ 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&amp;apos;s theorem is a theorem of hyperarithmetic analysis, making it only the second ``natural&amp;apos;&amp;apos; (i.e., not formulated using concepts from logic) theorem with this property.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>