Representing a $\sigma$ - structure using a signature-$\sigma$ in Mathematical Logic.

Question

In mathematical logic, I have a question regarding how a signature-$\sigma$ relates to a corresponding $\sigma$ structure which interprets the signature-$\sigma$

In Chiswell and Hodges book "Mathematical Logic", on page 11 of the Quantifer Free Logic chapter, they introduce a language LR (Language of relations) which has a signature defined as the following:

[Signature (First order)-$\sigma$]: A first order signature is a 4-tuple $(Co, Fu, Re, r)$ where:

(1) $Co$ is a set (possibly empty) of symbols called the constant symbols;

(2) $Fu$ is a set (possibly empty) of symbols called the function symbols;

(3) $Re$ is a set (possibly empty) of symbosl called the relation symbols;

(4) $Co, Fu, Re$ are pairwise disjoint;

(5) The function $r$ takes each symbol $s$ in $Fu \cup Re$ to a positive integer $r(s)$ called the rank (or *arity) of $s$. We say a symbol is $n-ary$ if it has arity $n$.

Now of course in conjunction with this signature-$\sigma$, if we provide a structure-$\sigma$, we can then interpret the symbols of the signature $\sigma$.

From Definition 5.5.2 (a) on page 129 of chapter five, it is stipulated that every $\sigma$-structure $A$ consists of a domain which is a non-empty set. The elements of such a domain are the elements of $A$.

Shouldn't this mean, whatever symbols we choose to use in our $\sigma$ signature, the elements in the domain of $A$ should be represented using the symbols of the $\sigma$ signature? However, in the example below, im confused as to how this rule is being respected.

The $\sigma_{diagraph}$ structure Image

In the example in the image, it says that the signature $\sigma_{digraph}$ has just one symbol: the binary relation $E(x,y)$.

If this is the case, how are you able to represent the elements in the domain of the structure $\sigma$ (The set $\left\{{1,2,3,4,5}\right\}$) using the signature $\sigma_{digraph}$? Since the elements of the set have no corresponding expressions in the signature $\sigma_{digraph}$ as there are no constant symbols for the elements in A how does this work?

At first I thought perhaps that the binary relation $E(x,y)$ represented all the edges of the digraph as there is no worry about representing the vertices necessarily for this example. But even if this is the case, how can the the signature $\sigma_{digraph}$ represent the ordered pair elements of $E(x,y)$ when the x and y variables are substituted for elements in the domain $\left\{{1,2,3,4,5}\right\}$ and we have no corresponding symbols in our signature $\sigma_{digraph}$?

I'd really appreciate the help thanks!

Answer 1

Every $σ$-structure $A$ consists of a domain which is a non-empty set. The elements of such a domain are the elements of $A$.

Shouldn't this mean, whatever symbols we choose to use in our $σ$ signature, the elements in the domain of $A$ should be represented using the symbols of the $σ$ signature?

Not exactly; the symbols of the signature should be interpreted by way of the elements of $A$ :

a constant symbol $c \in CO$ will be interpreted assigning to it an element $c^A \in A$ as its denotation (a constant symbol is like a "name")

a relation symbol $R \in Re$ with arity $n=r(R)$ will be interpreted as a set $R^A \subseteq A^n$, i.e. a subset of the cartesian product $A \times \ldots \times A$ ($n$ times)

and so on.

---

Regarding the $\sigma_{diagraph}$ example :

Suppose $G$ is a directed graph. The elements of the domain of $G$ are called its vertices. The binary relation $E_G$ is called the edge relation of $G$, and the ordered pairs in this relation are called the edges of $G$.

Thus, the elements of the domain of $G$ are the vertices and the (binary) relation symbol $E$ (the only symbol of the signature) will be interpreted through $E_G \subseteq G \times G$, i.e. as a set of couples.

Two vertices $a, b \in G$ will be "related" by $E$ iff $(a,b) \in E_G$, i.e. iff they are connected by an edge.

Being the relation symbol $E$ the only symbol of the signature, we have :

$Co=Fu=\emptyset$

$Re= \{ E \}$

and :

$r(E)=2$

because $E$ is a binary relation symbol.