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:20200811T140000Z DTEND:20200811T150000Z DTSTAMP:20260423T005723Z UID:CTA/17 DESCRIPTION:Title: Com puting descending sequences in linear orderings\nby Jun Le Goh (Univer sity of Wisconsin) as part of Computability theory and applications\n\n\nA bstract\nLet DS be the problem of computing a descending sequence in a giv en ill-founded linear ordering. We investigate the uniform computational c ontent of DS from the point of view of Weihrauch reducibility\, in particu lar its relationship with the analogous problem of computing a path in a g iven ill-founded tree (known as choice on Baire space).\n\nFirst\, we show that DS is strictly Weihrauch reducible to choice on Baire space. Our tec hniques characterize the problems which have codomain N and are Weihrauch reducible to DS\, thereby identifying the so-called first-order part of DS .\n\nSecond\, we use the technique of inseparable $\\Pi^1_1$ sets (first u sed by Angles d'Auriac\, Kihara in this context) to study the strengthenin g of DS whose inputs are $\\Sigma^1_1$-codes for ill-founded linear orderi ngs. We prove that this strengthening is still strictly Weihrauch reducibl e to choice on Baire space.\n\nThis is joint work with Arno Pauly and Manl io Valenti.\n LOCATION:https://researchseminars.org/talk/CTA/17/ END:VEVENT END:VCALENDAR