I'm looking for a reference for Exercise 6.11 from Libkin's FMT book:

Prove that an order-invariant conjunctive query is FO-definable without the order relation.

All help is appreciated.

  • $\begingroup$ Are you really looking for a reference, or just for a proof? If you need a reference to put in a paper, I don’t know any, but I wouldn’t hesitate to directly cite the Exercise in Libkin’s book. If you need a proof of the fact, it’s fairly simple. $\endgroup$ Aug 22 '20 at 13:16
  • 1
    $\begingroup$ I'm looking for the reference. I agree that the proof is quite easy (if I get it right). $\endgroup$ Aug 22 '20 at 14:13
  • 1
    $\begingroup$ A reference to some super-theorem from which Ex. 6.11 follows would be ok too. $\endgroup$ Aug 22 '20 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.