The Sexy Primes (Undergrad Math Club) Presents: Ehrenfeucht–Fraïssé Games and First-Order Expressibility

Reed Sarney ’12 would like to have a chat with you:

A math major is admiring a sculpture of two graphs in Zilkha. Another math major passes by the sculpture and spits in disgust. “Vulgar and common! These two graphs are different!” The first math major, reluctant but ultimately willing to engage the clearly abrasive philistine, responds. “They look the same to me.” The two go back and forth, pointing at different parts of the graph and shouting in math as the humanities majors look on in confusion. After a minute of this, they are asked to leave for creating a disturbance.

First-order logic provides a formal language with which to describe the properties of structures, but not every property is expressible using first-order logic. Amazingly, the question of whether certain properties of structures are expressible using first-order logic amounts, with a little bit of reframing, to the question of which math major as above has a winning argument. Using graphs as a simple jumping-off point, I will develop all of the theory necessary to
understand and appreciate the talk. There will be Thai food. You should come.

Date: Feb. 21
Time: Noon – 1:00 PM
Place: Exley 141
Cost: nada