<p>I'm looking for a reference for Exercise 6.11 from Libkin's FMT <a href="https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf" rel="nofollow noreferrer">book</a>:</p>
<blockquote>
<p>Prove that an order-invariant conjunctive query is FO-definable without the order relation.</p>
</blockquote>
<p>All help is appreciated.</p>

CC BY-SA 4.0
2020-08-22T13:16:54.383Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-08-22T14:13:34.430Z
I'm looking for the reference. I agree that the proof is quite easy (if I get it right).
Bartosz Bednarczyk
CC BY-SA 4.0
2020-08-22T14:44:23.780Z
A reference to some super-theorem from which Ex. 6.11 follows would be ok too.
Bartosz Bednarczyk
<reference-request><lo.logic><db.databases><finite-model-theory><first-order-logic>
Order-invariant conjunctive queries are FO-definable without the order
Bartosz Bednarczyk
# Order-invariant conjunctive queries are FO-definable without the order

(Asked by: username_0 on 2020-08-20)

I'm looking for a reference for Exercise 6.11 from Libkin's FMT [book](https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf):

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

All help is appreciated.

**Tags:** reference-request, lo.logic, db.databases, finite-model-theory, first-order-logic

> **Comments:**
> **username_1**: 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.  
> **username_0**: I'm looking for the reference. I agree that the proof is quite easy (if I get it right).  
> **username_0**: A reference to some super-theorem from which Ex. 6.11 follows would be ok too.  

---

## 0 answers

