Structure (mathematical logic)

From Wikipedia, the free encyclopedia

In mathematical logic, a structure is an object that gives semantic meanings to the symbols in a logical language. The most common setting is with first-order languages, but structures for typed and higher-order languages are also important.

Contents

[edit] One-sorted first-order structures

An untyped first-order language consists of constant symbols, and relation symbols and function symbols of various arities. A structure \mathcal{M} for such a language consists of a set |\mathcal{M}|, which will be the domain of discourse for \mathcal{M}, and interpretations of the symbols in the first order language:

  • The constant symbols are interpreted as specific elements of \mathcal{M}. Thus for each constant symbol c in the language there is a specific element m_c \in |\mathcal{M}|.
  • Each n-ary relation symbol R is interpreted as a specific subset of the Cartesian product |\mathcal{M}|^n.
  • Each n-ary function symbol f is interpreted as a specific function from |\mathcal{M}|^n to |\mathcal{M}|.

Thus a structure for a language gives complete semantic meaning to all the symbols of the language.

[edit] Examples

A language for rings consists of three binary functions +, -, and ×, along with equality. Thus a structure for this language consists of a set of elements R together with interpretations of the +, -, and × functions. This structure may or may not satisfy the ring axioms, as discussed below.

The ordinary language for set theory includes a single binary relation ∈ and equality. A structure for this language consists of a set of elements and an interpretation of the ∈ relation as a binary relation on these elements.

[edit] The satisfaction relation and models of first-order theories

Each first-order structure \mathcal{M} has a satisfaction relation \mathcal{M} \vDash \phi defined for all formulas φ in the language consisting of the language of \mathcal{M} together with a constant symbol for each element of M, which is interpreted as that element. This relation is defined inductively using Tarski's T-schema.

A structure \mathcal{M} is said to be a model of a theory T if the language of \mathcal{M} is the same as the language of T and every sentence in T is satisfied by \mathcal{M}. Thus, for example, a "ring" is a structure for the language of rings that satisfies each of the ring axioms, and a model of ZFC set theory is a structure in the language of set theory that satisfies each of the ZFC axioms.

[edit] Generalizations

[edit] Many-sorted structures

A many sorted language includes more than one domain of discourse. For example, the first-order axiomatization of second-order logic includes a sort for natural numbers and a sort for sets of natural numbers. A structure \mathcal{M} for a many sorted language is defined as for a one-sorted language, but instead of a single universe |\mathcal{M}| there are several universes, one for each sort.

[edit] Higher-order languages

Main article: Second-order logic

There is more than one possible semantics for higher-order logic, as discussed in the article on second-order logic. When using full higher-order semantics, a structure need only have a universe for objects of type 0, and the T-schema is extended so that a quantifier over a higher-order type is satisfied by the model if and only if it is disquotationally true. When using first-order semantics, an additional sort is added for each higher-order type, as in the case of a many sorted first order language.

[edit] Definability over a structure

An n-ary relation R on the universe |\mathcal{M}| of a structure \mathcal{M} is said to be definable (or explicitly definable) if there is a formula \phi(x_1,\ldots.x_n) such that

R = \{ (a_1,\ldots,a_n ) \in |\mathcal{M}|^n : \mathcal{M} \vDash \phi(a_1,\ldots,a_n)\}

In other words, R is definable if and only if there is a formula φ such that

(a_1,\ldots,a_n ) \in R \Leftrightarrow \mathcal{M} \vDash \phi(a_1,\ldots,a_n)

is correct.

An important special case is the definability of specific elements. An element m \in |\mathcal{M}| is definable over \mathcal{M} if and only if there is a formula φ(x) such that

\mathcal{M}\vDash \forall x ( x = m \Leftrightarrow \phi(x)).

[edit] Definability with parameters

A relation R is said to be definable from parameters if there is a sentence φ with parameters from \mathcal{M} such that R is definable using φ. Every element of a structure is definable using the element itself as a parameter.

[edit] Implicit definability

Recall from above that an n-ary relation R on the universe \mathcal{M} of a structure \mathcal{M} is explicitly definable if there is a formula \phi(x_1,\ldots.x_n) such that

R = \{ (a_1,\ldots,a_n ) \in |\mathcal{M}|^n : \mathcal{M} \vDash \phi(a_1,\ldots,a_n)

Here the formula φ used to define a relation R must be in the language of \mathcal{M} and so φ may not mention R itself, since R is not in the language of \mathcal{M}. If there is a formula φ in the extended language containing the language of \mathcal{M} and a new symbol R, and the relation R is the only relation on \mathcal{M} such that \mathcal{M} \vDash \phi, then R is said to be implicitly definable over \mathcal{M}.

There are many examples of implicitly definable relations that are not explicitly definable.

[edit] References

  • Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0. 

[edit] External links

Retrieved from "http://en.wikipedia.org../../../s/t/r/Structure_%28mathematical_logic%29.html"
In other languages