0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You'll have to find a source that's both in English and accessible; what you linked seems to be in Korean, and I can't open the book. In any case, the answers to your previous question apply: the universe contains exactly whatever it is defined to contain, and sometimes what it is defined as needs to be understood from context. It does seem reasonable to assume that in the context of graph coloring, the universe consists of the vertices. $\endgroup$
    – G. Bach
    Aug 8, 2014 at 1:36
  • $\begingroup$ Crossposted on CSTheory. Please don't do that. $\endgroup$
    – Juho
    Aug 8, 2014 at 10:54

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.