28 reputation
2
bio website
location
age
visits member for 2 years
seen Dec 10 '12 at 2:23

Dec
6
awarded  Scholar
Dec
6
accepted Why can't reachability be expressed in first order logic?
Dec
4
comment Why can't reachability be expressed in first order logic?
What if, like you said, you express reachability in first order logic in the language of set theory, by quantifying over the paths in the graph - won't that also be just a first order (no quantifications over relations) sentence ϕ(a,b) in the vocabulary of set theory? If so, the proof should go through for it as well!
Dec
4
comment Why can't reachability be expressed in first order logic?
Ok, but where does your proof depend on the restriction that the only relations available in the language are graph and equality? If ϕ(a,b) is taken to be the first order expression for reachability that I gave in my original post (which is over a language that contains an additional relation symbol L), your proof would also seem to work for it. Or let's say you express reachability in FOL using set theory, which you said is possible. Then where would your proof break down for that expression?
Dec
4
awarded  Student
Dec
4
asked Why can't reachability be expressed in first order logic?