nLab structure in model theory

Redirected from "first-order structure".
Contents

Contents

Idea

A structure in mathematics (also “mathematical structure”) is often taken to be a set equipped with some choice of elements, with some operations and some relations. Such as for instance the “structure of a group”. In model theory this concept of mathematical structure is formalized by way of formal logic.

Notice however that by far not every concept studied in mathematics fits as an example of a mathematical structure in the sense of classical first order model theory, described below. For instance a concept as basic as that of topological spaces fails to be a structure in the sense of classical model theory (see here).

In category theory there is a more flexible concept of structure, see there.

Definition

Given a first-order language LL, which consists of symbols (variable symbols, constant symbols, function symbols and relation symbols including ϵ\epsilon) and quantifiers; a structure for LL, or “LL-structure”, is a set MM with an interpretation for symbols:

  • if RLR\in L is an nn-ary relation symbol, then its interpretation R MM nR^M\subset M^n

  • if fLf\in L is an nn-ary function symbol, then f M:M nMf^M:M^n\to M is a function

  • if cLc\in L is a constant symbol, then c MMc^M\in M

The underlying set MM of the structure is referred to as (universal) domain of the structure (or the universe of the structure).

Interpretation for an LL-structure inductively defines an interpretation for well-formed formulas in LL. We say that a sentence ϕL\phi\in L is true in MM if ϕ M\phi^M is true. Given a theory (L,T)(L,T), which is a language LL together with a given set TT of sentences in LL (axioms), the interpretation in a structure MM makes those sentences true or false; if all the sentences in TT are true in MM we say that MM is a model of (L,T)(L,T).

In model theory, given a language LL, a structure for LL is the same as a model of LL as a theory with an empty set of axioms. Conversely, a model of a theory is a structure of its underlying language that satisfies the axioms demanded by that theory.

There is a generalization of structure for languages/theories with multiple domains or sorts, called multi-sorted languages/theories.

Properties

Elementary classes of structures

A class KK of structures of a given signature is an elementary class if there is a first-order theory TT such that KK consists precisely of all models of TT.

There is a vast generalizations for higher-order theories (and more), see at abstract elementary class and metric abstract elementary class.

Categories of structures

Every algebraic category whose forgetful functor preserves filtered colimits is the category of models for some first-order theory. The converse is false.

A detailed discussion of characterizations of categories of structures in the sense of model theory is in (Beke-Rosciky 11).

Interpretation in categorical logic

Every first-order language LL gives rise to a first-order hyperdoctrine with equality freely generated from LL. Denoting this by T(L)T(L), the base category C T(L)C_{T(L)} consists of sorts (which are products of basic sorts) and functional terms between sorts; the predicates are equivalence classes of relations definable in the language. The construction of T(L)T(L) depends to some extent on the logic we wish to impose; for example, we could take the free Boolean hyperdoctrine generated from LL if we work in classical logic.

There is also a “tautological” first order hyperdoctrine whose base category is SetSet, and whose predicates are given by the power set functor

P:Set opBoolP \colon Set^{op} \to Bool

and then an interpretation of LL, as described above, amounts to a morphism of hyperdoctrines T(L)Taut(Set)T(L) \to Taut(Set).

This observation opens the door to a widened interpretation of “interpretation” in categorical logic, where we might for instance generalize Set to any other topos EE, and use instead Sub:E opHeytSub \colon E^{op} \to Heyt (taking an object of EE to its Heyting algebra of subobjects) as the receiver of interpretations. This of course is just one of many possibilities.

References

Standard textbook accounts include

  • Wilfrid Hodges, section 1 of A shorter model theory, Cambridge University Press (1997)

  • Chen Chung Chang, H. Jerome Keisler, Model Theory. Studies in Logic and the Foundations of Mathematics. 1973, 1990, Elsevier.

Characterizations of categories of model-theoretic structures and homomorphisms between them (certain accessible categories) is discussed in

Online discussion includes

category: model theory

Last revised on May 6, 2023 at 11:40:26. See the history of this page for a list of all contributions to it.