2
$\begingroup$

A graph $G$ is said to be a model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x_1,...,x_r)$ be a first order formula with free variables $x_1,...,x_r$. What is the standard terminology for a tuple of vertices $(v_1,...,v_r)$ of $G$ such that $G$ satisfies the formula $\varphi(v_1,...,v_r)$ obtained by substituting $x_i$ with $v_i$?

What I'm having trouble is to find the right terminology to connect $G$ to the assignment. The only thing I can think now is the following.

"$(v_1,...,v_r)$ is a satisfying assignment for $\varphi$ in $G$."

But maybe there is a shorter way.

|cite|improve this question
$\endgroup$
3
$\begingroup$

I think that's often called a "variable assignment", since it assigns to each variable a value (a vertex in the graph, in your case).

If the graph is equipped with a set of such tuples, these might be considered to be hyperedges, i.e. edges connected to an arbitrary number of vertices (not necessarily two of them).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I'm fine with the fact that it is an assignment. What I'm having trouble is to find the right terminology to connect $G$ to the assignment. For instance, would the standard be to say that $(v_1,...,v_r)$ is a satisfying assignment for $\varphi$ in $G$? $\endgroup$ – verifying Mar 1 at 20:28
  • $\begingroup$ @verifying I would understand that. You could even say that $(v_1,\ldots,v_r)$ satisfies $\varphi$ for short. I can't guarantee that's the most standard way, but I find that very reasonable and clear. $\endgroup$ – chi Mar 1 at 23:00

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.