Signature (logic)

In mathematical logic (also: Language ) is a signature from the set of symbols, which is added in the considered language to the usual, purely logical symbols, and a map that clearly assigns to each symbol of arity a signature. While the logical symbols, as always, as "for all", "there is a ", "and ", "or ", "follow", " equivalent to" or "not " interpreted, can the semantic interpretation of the symbols of signature different structures ( in particular models of propositions of logic) are distinguished. The signature is the specific part of an elementary language.

For example, the entire Zermelo -Fraenkel set theory in the language of first-order predicate logic and the single symbol formulate ( in addition to the purely logical symbols); In this case, the set of symbols of the signature is the same.

  • 4.1 structures
  • 4.2 Notes
  • 4.3 interpretations

Motivation

If statements can be formalized through a particular area, it is first to decide which objects and relations which statements are to be taken. For every nameable object a constant is introduced and for each relation a relation symbol. For example, to talk about the arrangement of the natural numbers, a constant is introduced for each number and relation symbols < (less than) and > (greater than).

Usually you still need additional functions, with which one can count on the constants, eg symbol ( ) for addition of natural numbers.

Thus, there are three types of symbols, which may occur in signatures:

  • Constant symbols: they stand for exactly one value.
  • Function symbols: they stand for an unambiguous assignment of values ​​to each other.
  • Relation symbols ( predicates ): You are each to each other for a relationship, so for an assignment of values ​​that might not be unique. A relationship is often expressed as the subset of tuples ( ordered sets ) for the predicate true.

Classification and delimitation

Not for signature include variable symbols whose value is not interpreted in the formula, and other characters, which serve the construction of a statement or formula. All these signs together form generated by the signature " basic language." A language thus includes more characters than the corresponding signature

The permitted to form logical statements and formulas characters can thus be roughly divided into

  • Characters that define the structure ( the structure ) of the statement or the formula: Junktorensymbole, for example
  • Quantorensymbole, for example
  • Variables, such as
  • Symbols of the signature Constant symbols, for example
  • Function symbols, for example
  • Relations symbols ( predicates ), for example

Terms do not belong to the signature, but they are composed of the logical symbols, the variables and the functions and constant symbols of the signature and of variables according to fixed rules education.

Are terms used as arguments in the relation symbols, atomic propositions arise predicate logic. Comparisons of terms valid in the predicate logic as atomic propositions. From these composite statements can be formed by links.

Definition

Let and pairwise disjoint sets of non- logical symbols. It then calls each character in a symbol and a symbol set, if by a picture each character in arity as follows a called number is uniquely associates:

  • For all
  • For all and
  • For all

Then called a signature, and each is referred as a constant symbol, each as a function symbol, and each as a relation symbol.

A signature is called finite if is a finite set. If a signature has no relation symbols, it is called an algebraic signature, whereas if it has no constants and no function symbols, a relational signature.

Comments

Semantics of a signature

Structures

Is a signature and there was the amount of all constant symbols, the set of all function symbols and the set of all relation symbols Further denote a non-empty set and then is a picture, so

  • Is a constant for each
  • A function for each and
  • A relation for each

It is called a structure of signature or just a structure. is then the basic set, the amount of carrier or short of the support of and if is a finite set, so called as finite, otherwise infinite.

Comments

Interpretations

The signature is replaced by a structure and an interpretation or interpretation of variables in a specific semantic meaning:

A picture with is called an assignment of the structure. then called an interpretation of the signature or a short interpretation.

de