BEGIN:VCALENDAR
METHOD:PUBLISH
VERSION:2.0
PRODID:-//Cornell U. Department of Computer Science//Brown Bag Seminar//EN
BEGIN:VEVENT
SUMMARY:Brown bag: Dexter Kozen
DESCRIPTION:Title: Borel Coalgebras and Non-wellfounded Logic\nSpeaker:
Dexter Kozen\nAbstract: I will introduce Borel coalgebras and Borel
automata as a computational approach to basic descriptive set theory. We
show that over any Polish space\, Borel automata accept exactly the
coanalytic sets\, and total Borel automata (those that halt on all
inputs) accept exactly the Borel sets. The latter result is a
computational version of the Kleene--Suslin theorem. The ordinal rank of
a Borel set is characterized as the running time of a Borel automaton.
We show how these ideas lead to a general notion of non-wellfounded
logic in which syntactic objects such as terms and formulas are elements
of a final coalgebra. We relate these notions to the categorical theory
of recursion schemes (Adamek\, Milius\, and Velebil 2006\, Milius and
Moss 2006) to provide a foundation for non-wellfounded logic.
LOCATION:Gates 122
UID:2018-02-06
STATUS:CONFIRMED
DTSTART:20180206T170000Z
DTEND:20180206T180000Z
LAST-MODIFIED:20180206T183550Z
ORGANIZER;CN=Jonathan Shi:http://www.cs.cornell.edu/~jshi/brownbag/
DTSTAMP:20240723T052141Z
END:VEVENT
END:VCALENDAR