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:20260408T121822Z
END:VEVENT
END:VCALENDAR