An introduction to the Ehrenfeucht-Fraïssé Games – From Game Theory to Models

Loading Map....

Date(s) - 29 Apr 2011
10:00 AM - 11:00 AM

Anfiteatro do CCET



Patrick Terrematte

Sanderson Molick

Abstract: The Ehrenfeucht-Fraïssé Games are a tool developed from the relationship between Mathematical Logic and Game Theory.  They consist in an interesting technique for comparing first-order structures and exploring some model-theoretic properties such as elementary equivalence, isomorphism and inexpressibility by FOL structures.  Their origin remounts to a method originated with Cantor, the so-called back-and-forth method.  Later on, Roland Fraïssé extended and discovered other properties about back-and-forth method.  However, Fraïssé’s treatment had a purely algebraic view.  Based on that, in 1960, Andrzej Ehrenfeucht reformulated Fraïssé’s treatment in a game-theoretical terminology.  In our lecture, we will make an expository introduction to the EF Games, showing their relevance, how Game Theory and Mathematical Logic are connected in its construction, and the main applications in Model Theory.

Leave a Reply