Thursday, November 20, 2025 4:30 pm
-
5:30 pm
EST (GMT -05:00)
Laindon Burnett, University of Waterloo
A definable criterion for definability
In 2001, A.A. Muchnik proved the surprising result that for any n, there is a formula within Presburger arithmetic which takes in a predicate A and is true if and only if A is definable in Presburger arithmetic; that is, within this setting, the property of being definable is itself definable. We will go over the proof of this result and, time permitting, discuss its applications to automata theory.
MC 5403