Graph Connectivity is not First Order Definable
Perhaps, dear readers, I am mistaken in believing that many (or any) of you are interested in logic, but on the chance that you have arrived here through a search engine in desperate hope of finding a solution to some problem, I shall post a PDF for you, and for historical purposes.
How do you show that the connectivity of directed graphs is not first-order definable? There are at least two proofs in “Counting and Locality over Finite Structures”, a paper by Leonid Libkin and Juha Nurmonen. The first, on the fifth page of the PDF, is an informal one using an Ehrenfeucht-Fraisse game. The second, starting on the eleventh page, is more formal.
This was a question on an exam that I took last week, which (I believe) required more preparation on my part than any exam I’ve ever taken. If you’re doing logic of this sort, I wish you good luck.
Once again, here’s the PDF: https://whereofwecannotspeak.files.wordpress.com/2006/10/graphconnectivity.pdf.