BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Alexandra Soskova (Sofia University) DTSTART:20201020T140000Z DTEND:20201020T150000Z DTSTAMP:20260423T024542Z UID:CTA/32 DESCRIPTION:Title: Eff ective embeddings and interpretations\nby Alexandra Soskova (Sofia Uni versity) as part of Computability theory and applications\n\n\nAbstract\nF riedman and Stanley introduced Borel embeddings as a way of comparing clas sification problems for different classes of structures. Many Borel embe ddings are actually Turing computable. The effective decoding is given by a uniform effective interpretation. Part of the effective interpretation is actually Medvedev reduction. \nThe class of undirected graphs and the class of linear orderings both lie on top under Turing computable embeddin gs. We give examples of graphs that are not Medvedev reducible to any lin ear ordering\, or to the jump of any linear ordering. For any graph\, the re is a linear ordering\, that the graph is Medvedev reducible to the seco nd jump of the linear ordering. Friedman and Stanley gave a Turing comput able embedding $L$ of directed graphs in linear orderings. We show that t here do not exist $L_{\\omega_1\\omega}$-formulas that uniformly interpret the input graph $G$ in the output linear ordering $L(G)$. This is joint w ork with Knight\, and Vatev.\n\nWe have also one positive result --- we pr ove that the class of fields is uniformly effectively interpreted without parameters in the class of Heisenberg groups.\nThe second part is joint w ork with Alvir\, Calvert\, Goodman\, Harizanov\, Knight\, Miller\, Moroz ov\, and Weisshaar.\n LOCATION:https://researchseminars.org/talk/CTA/32/ END:VEVENT END:VCALENDAR