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.

1 One-sorted first-order structures
- 1.1 Examples
2 The satisfaction relation and models of first-order theories
3 Generalizations
- 3.1 Many-sorted structures
- 3.2 Higher-order languages
4 Definability over a structure
- 4.1 Definability with parameters
- 4.2 Implicit definability
5 References
6 External links

[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.

Marker, D. (2002). Model Theory: An Introduction, Graduate Texts in Mathematics 217, Springer. ISBN 0-387-98760-6.

[edit] External links

Semantics section in Classical Logic (an entry of Stanford Encyclopedia of Philosophy)

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

Category: Model theory

Structure (mathematical logic)

From Wikipedia, the free encyclopedia

Contents

[edit] One-sorted first-order structures

[edit] Examples

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

[edit] Generalizations

[edit] Many-sorted structures

[edit] Higher-order languages

[edit] Definability over a structure

[edit] Definability with parameters

[edit] Implicit definability

[edit] References

[edit] External links

Views

Navigation

interaction

Search

In other languages