1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! However, I still have one negging problem. As you said, a constant symbol $c$ is like a 'name' which refers to an object, which is an element in the domain of set $A$ in this case. How then, is it possible to express an edge relation of $G$ using the signature $\sigma_{digraph}$, when the binary relation $E(x,y)$ has subterms $t_1$ and $t_2$ which are the elements of domain $A$ but don't have any constant symbols or 'names' to represent them in the signature $\sigma_{digraph}$? $\endgroup$ – Cp3Shadow Dec 30 '15 at 16:36
  • $\begingroup$ Don't we have to introduce a set of constant symbols like $\overline{1}$ for the element '$1$' in set $A$, $\overline{2}$ for the element '$2$' etc. so that we can then represent the edge relations using the signature $\sigma_{digraph}$ correctly as $E(\overline{1},\overline{2})$ How can we say that edge relations can be effectively represented in the signature just using that one binary relation, when that binary relation includes subterms which have no corresponding 'name' in the signature? $\endgroup$ – Cp3Shadow Dec 30 '15 at 16:40
  • 1
    $\begingroup$ @GavanC - $1,2,3,4$ are not terms, i.e. constant of the language; they are the "names" of the vertices used in the meta-language. If you want to name them in the language, as you say, you have to add constant symbols (see Ex.5.5.2 page 132). $\endgroup$ – Mauro ALLEGRANZA Dec 30 '15 at 16:43
  • 1
    $\begingroup$ @GavanC - an example of a "property" of a graph that you can express also without constants : $E(x,y) \to E(y,x)$. $\endgroup$ – Mauro ALLEGRANZA Dec 30 '15 at 18:53

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.