BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Jun Le Goh (University of Wisconsin)
DTSTART:20220404T203000Z
DTEND:20220404T213000Z
DTSTAMP:20260423T024557Z
UID:CTA/84
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CTA/84/">Ext
 ensions of embeddings in the $\\Sigma^0_2$ enumeration degrees</a>\nby Jun
  Le Goh (University of Wisconsin) as part of Computability theory and appl
 ications\n\n\nAbstract\nIn order to \nmeasure the \nalgorithmic content of
  partial functions\, or the positive information \ncontent of subsets of t
 he natural numbers\, one can use the notion of \nenumeration reducibility.
  The associated degree structure\, known as the \nenumeration degrees (e-d
 egrees)\, forms a superstructure of the Turing \ndegrees. We present ongoi
 ng work with Steffen Lempp\, Keng Meng Ng and \nMariya Soskova on the alge
 braic properties of a countable substructure of \nthe e-degrees\, namely t
 he &Sigma\;<sup class="double">0</sup><sub \nclass="double">2</sub> e-degr
 ees.\n<br><br>\n\nThe &Sigma\;<sup class="double">0</sup><sub class="doubl
 e">2</sub> \ne-degrees are analogous to the \ncomputably enumerable (c.e.)
  \nTuring degrees but these structures are not elementarily equivalent as 
 \npartial orders. Indeed\, Ahmad showed that there are incomparable \n&Sig
 ma\;<sup class="double">0</sup><sub class="double">2</sub>\ne-degrees <i>a
 </i> and <i>b</i> such that if <i>c</i> < <i>a</i>\, then \n<i>c</i> < <i>
 b</i>\, implying that <i>a</i> cannot \nbe expressed as the join of two de
 grees below it. This stands in contrast \nto Sacks's splitting theorem for
  the c.e. Turing degrees.\n<br><br>\n\nOne can view Ahmad's result as a tw
 o-quantifier sentence in the language \nof partial orders which holds in t
 he &Sigma\;<sup \nclass="double">0</sup><sub class="double">2</sub> \ne-de
 grees. While it is easy \nto compute whether a given one-quantifier senten
 ce is true in the \n&Sigma\;<sup class="double">0</sup><sub class="double"
 >2</sub> \ne-degrees (because all finite partial orders embed)\, the \ncor
 responding task for two-quantifier sentences (which corresponds to an \nex
 tension of embeddings problem) is not known to be algorithmically \ndecida
 ble. Towards solving this problem\, we investigate the extent to \nwhich A
 hmad's result can be generalized. For instance\, we show that it \ndoes no
 t generalize to triples: For any incomparable \n&Sigma\;<sup class="double
 ">0</sup><sub class="double">2</sub> e-degrees \n<i>a</i>\, <i>b</i> and <
 i>c</i>\, there is some <i>x</i> such that one of \nthe following holds: <
 i>x</i> is \nbelow <i>a</i> but not below <i>b</i>\, or <i>x</i> is below 
 <i>b</i> but \nnot below <i>c</i>.\n<br><br>\n\nWe shall also discuss spec
 ulative generalizations of the above result\, and \nhow they may lead to a
 n algorithm which decides a class of two-quantifier \nsentences in the &Si
 gma\;<sup class="double">0</sup><sub \nclass="double">2</sub> e-degrees.\n
LOCATION:https://researchseminars.org/talk/CTA/84/
END:VEVENT
END:VCALENDAR