Speaker: Ben Rossman, Assistant Professor of Mathematics and Computer Science at U of T
Title: Ehrenfeucht-Fraïssé Games & The 0-1 Law of First Order Logic
Ehrenfeucht-Fraïssé games are a fun and useful tool for determining which properties of graphs (and other mathematical structures) are expressible in first-order logic. In this talk, I will introduce this class of games, describe their connection to first-order logic, and play through several examples which highlight thematic winning strategies. In the last part of the talk, I will present a simple proof using E.F. games of the 0-1 Law for First-Order Logic, a beautiful theorem of Fagin (1976) which states that every first-order property of graphs holds with probability o(1) or 1-o(1) in the uniform random graph G(n,0.5).
Visit E.F. games for more information.