Descriptive complexity: 3-colorability example

Question

So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed as following: $\exists R \exists Y \exists B \forall x \left[(R(x) \vee Y(x) \vee B(x)) \wedge (\forall y) (E(x,y) \rightarrow \neg(R(x) \wedge R(y)) \wedge \neg(Y(x) \wedge Y(y)) \wedge \neg (B(x) \wedge B(y))) \right]$.

My previous question seems to have been misunderstood - I was not asking about what first-order or second-order logic is, but rather on the use of quantifier. Here $\forall x$ seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding? If so, why is it the case? Is it pre-defined rule of descriptive complexity usage of logic?

Also for any similar graph problems, is universe of sets restricted to vertices only, or are we allowed to add sensible sets to universe?

Answer 1

The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.

Answer 2

To expand a bit on Yuval Filmus' answer:

Here ∀x seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding?

Yes.

Implicitly, descriptive complexity is querying a model(?). Here's a quote from the beginning of the book:

"A structure with vocabulary τ is a tuple, A = ⟨|A|,R1A,...,RrA,cA1 ,...,cAs ,f1A,...,ftA⟩ whose universe is the nonempty set |A|"

The model is |A|.

When you're dealing with graphs, usually the model is the set of vertices. For the edges there would be a binary relation E, which you see in your query.

Although I suppose you could encode the graph differently, if you wanted.