Commonly used signatures

From Learning Logic for Computer Science

In the following, commonly used signatures are listed. To distinguish between symbols of a signature and symbols in the meta language of mathematics, dots are used.

Sets are structures with no additional structure: $$\Sigma_\text{set} = \{\}\enspace.$$

Relational signatures

Ordered sets are sets with an ordering relation on them: $$\Sigma_\text{ord} = \{{\dot <}/2\}\enspace.$$

Directed graphs are structures with a binary relation: $$\Sigma_\text{grph} = \{E/2\}\enspace.$$

There is no real difference between the signature for ordered sets and directed graphs except that in the tradition of mathematics different symbols have been used.

When a single point or two single points need to be marked, constant symbols are added: $$\Sigma = \{s, E/2\}\enspace, \qquad \Sigma = \{s, t, E/2\}\enspace.$$

When a subset of the set of vertices is marked, then the signature is augmented by a relation symbol: $$\Sigma = \{M/1, E/2\}\enspace.$$

Algebraic signatures

Groupoids are algebraic structures with a product: $$\Sigma_\text{grpd} = \{\dot{\cdot}\} \enspace.$$

When a neutral element (a unity) is around, then a constant symbol ist added: $$\Sigma = \{\dot 1, \dot{\cdot}/\!/2\}\enspace.$$

Groups are algebraic structures with a product, a neutral element, and inverses: $$\Sigma_\text{grp} = \{\dot 1, \dot{\cdot}/\!/2, \dot{{}^{-1}}/1\} \enspace.$$

Rings (with 1) are algebraic structures with addition and multiplication and neutral elements: $$\Sigma_\text{rng} = \{\dot 0, \dot 1, \dot +/\!/2, \dot \cdot/\!/2\}\enspace.$$

Ordered rings have an ordering as well: $$\Sigma_\text{orng} = \{\dot 0, \dot 1, \dot +/\!/2, \dot \cdot/\!/2, {\dot <}/2\}\enspace.$$