Multi-Graph Logic Exercise: Describe as First-Order Structure

[Andrei1]

Here is an exercise from a book of logic:

Suppose we are presented with a graph $G$ that has multiple edges.This means that there may be more than one edge between two vertices of $G$ (so, by our strict definition of "graph", a graph with multiple edges is not a graph). Describe $G$ as a first-order $\nu$-structure for a suitable vocabulary $\nu.$

I thought about the following structure: $G=(U,\,\mathbb{N}\cup\{0\}\mid R)$, where $U$ is the set of vertices, and $R(a,n)$ means that vertice $a$ has $n$ adjacent edges. This looks suspicious: I learned that a structure has a single underlying set.
How do you understand this exercise?

 

[Evgeny.Makarov]

I apologize for taking forever to respond to this question.

I thought about the following structure: $G=(U,\,\mathbb{N}\cup\{0\}\mid R)$, where $U$ is the set of vertices, and $R(a,n)$ means that vertice $a$ has $n$ adjacent edges.

Knowing the degree of each vertex does not uniquely determine the graph even for simple graphs. Imagine two disjoint triangles, on the one hand, and a hexagon, on the other hand. These two graphs have the same number of vertices and each vertex has degree 2, but they are not isomorphic.

As Wikipedia describes, there are two flavors of multigraphs. In the first one, we can only say how many edges there are between two given vertices, but we cannot distinguish or identify individual edges. In the second flavor, we can refer to individual edges. The problem probably talks about the first kind. In this case, you can describe a multigraph if instead of a relation $R(a,n)$ between vertices and numbers you have a function $f:V\times V\to\mathbb{N}$ where V is the set of vertices. Then $f(a,b)$ says how many edges there are between $a$ and $b$.

This looks suspicious: I learned that a structure has a single underlying set.

You are right: a structure as defined in the book has a single underlying set, or, domain. However, first, it is easy to generalize first-order logic into many-sorted logic, where structures have several domains and each function or predicate symbol in the vocabulary is assigned not only the number of arguments, but also types of those arguments, which signify from which domain a given argument comes. This extension of first-order logic is routine and does not raise any significant problems.

Alternatively, we can consider an underlying set $U$ to be a disjoint union of two or more sets, in this case, the set of vertices and the set of natural numbers. Of course, the function $f$ that assigns the number of edges to a pair of vertices, like any function in a structure, must be total on $U\times U$. We can make $f$ return some fixed element of $U$, e.g., 0, when one or both arguments of $f$ are numbers rather than vertices.

Recall that not every structure with one binary predicate defines a graph: we need the axioms saying that the relation is irreflexive and symmetric. Similarly, we need axioms for multigraphs. It is convenient to introduce two unary predicate symbols $V$ and $N$ that are true only on vertices and numbers, respectively. Then we can make an axioms saying that $f$ returns a number for any two vertices and that the order of vertices does not matter.

For the second flavor of multigraphs, we can again have (a disjoint union of) two sets: vertices and edges and two functions that return the two ends of a given edge.

 

[Andrei1]

At this moment I am looking for a sort of final answer, so let me just summarize. I highlighted where I somewhat doubt.

Let $\nu=\{f,\,V,\,N\}$ where $f$ is a binary function, $V$ and $N$ are unary relations. Then $G=(U\mid f,\,V,\,N)$ denotes a $\nu$-structure. The universe $U$ of $G$ is the union of the set of vertices and the set $\{x\in\mathbb{Z}\mid x\geqslant -1\}.$ The structure interprets $f$ as the edge function. That is, for elements $a$, $b$, and $n$ of $U$, $G\models f(a,b)=n$ iff the graph has $n$ edges between vertices $a$ and $b.$ $G$ interprets:
$V(x)$ as "$x$ is a vertex", and
$N(x)$ as "$x$ is a number from $\{x\in\mathbb{Z}\mid x>-1\}$".

$G$ models the sentences:
$\forall x\forall y(N(x)\vee N(y)\vee x=-1\vee y=-1\to f(x,y)=-1)$;
$\forall x\forall y(V(x)\wedge V(y)\to N(f(x,y)))$;
$\forall x\forall y\forall z(f(x,y)=f(y,x)).$

 

[Evgeny.Makarov]

Seems OK. I would write, "For all a, b ∈ U, if a and b are vertices, then f(a, b) equals the number of edges between a and b; otherwise, f(a, b) = -1."

 

[blue_raver22]

I understand this exercise as a way to explore and understand the concept of multiple edges in a graph using first-order logic. The exercise is asking us to describe a graph with multiple edges as a first-order structure, which means representing the graph using a set of objects and a set of relations between those objects.

In this case, the structure $G=(U,\,\mathbb{N}\cup\{0\}\mid R)$ is a valid representation of the graph $G$ with multiple edges. The set $U$ represents the vertices of the graph, and the relation $R(a,n)$ represents the number of adjacent edges for a specific vertex $a$. This structure allows us to define and reason about the properties of the graph using first-order logic.

However, it is important to note that this structure may not be the most efficient or elegant way to represent a graph with multiple edges. As noted in the exercise, a graph with multiple edges does not fit the strict definition of a graph, so it may be better to use a different structure that better captures the properties of a graph with multiple edges. Overall, this exercise is a useful way to practice and explore the use of first-order logic in representing complex structures such as graphs.