@csj:
0-1 Laws in Finite Model Theory
Lunch is sandwiches from Jimmy John’s
We are looking for more presenters in 2020! Do you want to improve your speaking skills? Do you like computer science? Do you have a conference presentation to prepare for? The Student Seminar is a place where PhD students present to each other over a free lunch. Talks can be a chance to present something from your research of general interest, practice a conference presentation, or just tell us about something interesting.
This week Nathan Mull (@nmull) will present some beautiful mathematical facts, relevant to anyone who deals with very large computational objects,
0-1 Laws in Finite Model Theory
Abstract: Many natural graph properties hold for nearly all graphs in the sense that the fraction of n vertex graphs for which the property holds approaches 1 as n approaches infinity. For example, nearly all graphs contain a triangle. It turns out that this is an instance of a more general phenomenon that occurs in logic. We will prove that every first-order formula on a finite relational signature either holds for nearly all models or almost no models. Despite the finite nature of this result, the proof takes an interesting detour through classical results about infinite objects in logic such as the compactness theorem and the downward Löwenheim-Skolem theorem. No background in logic is assumed.