# A graph in descriptive complexity - is $x$ already a vertex?

So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use relation like $v(x)$ to say that $x$ is a vertex?

• Strictly speaking, no, though the universe (vertices, in your case) is often clear from context and might be omitted. Commented Aug 6, 2014 at 16:56
• How is universe defined? Is it dependent on the graph input given? So like if a graph is 5-vertex graph, then there is only 5 elements in universe?
– DES
Commented Aug 6, 2014 at 17:01
• Or are we allowed to form any structure out of a graph then form a language/universe?
– DES
Commented Aug 6, 2014 at 17:02
• What are you doing or trying to express?
– Juho
Commented Aug 6, 2014 at 18:00
• Yes, when describing graph properties, the universe consists of all vertices, and there's an edge predicate. Commented Aug 8, 2014 at 3:19

(First-order logic) formulae are independent of structures; you just have variables, predicates and possibly functions (in addition to the syntactical symbols). To decide whether a formula $\varphi$ is true in a given structure $S$ (consisting of a universe of individuals $U$ and an interpretation of predicates $I$), i.e. whether $S$ is a model of $\varphi$, you apply the semantic rules of first order logic.

Concerning your specific question: if you have $\varphi = \forall x: F$ where $F$ is some formula, then $x$ denotes exactly all vertices iff you defined your structure $S = (U,I)$ such that $U$ contains exactly all vertices. Note that if you do that and want access to the edges, then you'll need to define some predicate $e(x,y)$ such that $e(x,y) \Leftrightarrow \text{there is an edge between } x \text{ and } y$.

More generally: the quantifiers do not differentiate between elements of your universe, the predicates will have to do that. If you want to check $F$ only for all vertices but your universe contains elements that are not vertices, then you do what you suggested: introduce a predicate $v(x)$ and use $\varphi' = \forall x: (v(x) \rightarrow F)$

• If you're interested in slides, this set seems to do a good job of explaining first-order logic. Commented Aug 6, 2014 at 18:17

Let me quote from Immerman's survey on descriptive complexity: In Descriptive Complexity we view the input as a finite logical structure. A graph is a logical structure whose universe is the set of vertices and $E_G$ is the binary edge relation.

So when describing graph properties, qualifiers quantify over all vertices, and edges are encoded by a binary relation. This is the convention in descriptive complexity. If you follow some other convention then you might get different behavior.

Typically, when referring to vertices in a graph, one does by the following. Let $G=(V,E)$ be a graph such that $V$ is the set of vertices and $E$ is the set of edges. Then you would proceed $\forall x \in V$ etcetera.

• I'd add - $E \subset V \times V$ Commented Aug 6, 2014 at 21:22