The World

[as I find it]

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:


Written by whereofwecannotspeak

October 22, 2006 at 7:31 pm

2 Responses

Subscribe to comments with RSS.

  1. Good times. No really. BTW, that PDF is copyrighted. I got it from a journal.

    Daniel J Singer

    October 26, 2006 at 9:27 pm

  2. Booya. That exam rocked my socks.


    February 24, 2007 at 6:11 pm

Comments are closed.

%d bloggers like this: