Shiksha Nation
Skip to content

Signature (logic)

Description of non-logical symbols

  • 4 min read
  • 4 chapters

Related on Lably

Through Mathematical logic, Algebraic structure and Cardinality

Definition

Formally, a (single-sorted) signature can be defined as a 4-tuple σ=(Sfunc,Srel,Sconst,ar), where Sfunc and Srel are disjoint sets not containing any other basic logical symbols, called respectively

  • function symbols (examples: +,×),
  • relation symbols or predicates (examples: ≤,∈),
  • constant symbols (examples: 0,1),

and a function ar:Sfunc∪Srel→N which assigns a natural number called arity to every function or relation symbol. A function or relation symbol is called n-ary if its arity is n. Some authors define a nullary (0-ary) function symbol as constant symbol, otherwise constant symbols are defined separately.

A signature with no function symbols is called a relational signature, and a signature with no relation symbols is called an algebraic signature. A finite signature is a signature such that Sfunc and Srel are finite. More generally, the cardinality of a signature σ=(Sfunc,Srel,Sconst,ar) is defined as |σ|=|Sfunc|+|Srel|+|Sconst|.

The language of a signature is the set of all well formed sentences built from the symbols in that signature together with the symbols in the logical system.

Sign up free to read the rest

3 more chapters are free with a Lably account.

Already have an account?

More in Foundations