Structure (mathematical logic)

In universal algebra and model theory, a structure is a set together with finitary operations and relations defined on it. Universal algebra focuses on structures that generalize algebraic systems like groups, rings, fields, and vector spaces, and it deals with first-order theories that have no relation symbols. Model theory covers a broader range of first-order theories, including foundational ones like models of set theory. From the model-theoretic perspective, structures provide the semantics for first-order logic, as seen in Tarski's theory of truth. A structure that satisfies every sentence of a given theory is called a model. Logicians sometimes use the term "interpretation" for structures, though "interpretation" has a related but distinct meaning in model theory.

The word "model" in mathematical logic was first used by philosopher Willard Van Orman Quine in 1940, referencing mathematician Richard Dedekind, an early figure in set theory. Alfred Tarski, from the Lwów–Warsaw school, coined the phrase "theory of models" in 1954. Since the 1800s, a key method for proving the consistency of a set of axioms has been to find a model for it.

Formally, a structure is a triple \(\mathcal{A} = (A, \sigma, I)\), consisting of a domain \(A\), a signature \(\sigma\), and an interpretation function \(I\) that shows how the signature is interpreted on the domain. A structure with a particular signature \(\sigma\) is called a \(\sigma\)-structure.

The domain is an arbitrary set, also called the underlying set, carrier (especially in universal algebra), universe (especially in model theory), or domain of discourse. In classical first-order logic, the empty domain is not allowed. The domain may be denoted \(\operatorname{dom}(\mathcal{A})\) or \(|\mathcal{A}|\), but often the same symbol \(\mathcal{A}\) refers to both the structure and its domain.

The signature \(\sigma = (S, \operatorname{ar})\) consists of a set \(S\) of function and relation symbols, along with a function \(\operatorname{ar}: S \to \mathbb{N}_0\) that assigns each symbol \(s\) a natural number \(n = \operatorname{ar}(s)\), called its arity. A signature with no relation symbols is called an algebraic signature, and a structure with such a signature is called an algebra (not to be confused with an algebra over a field).

The interpretation function \(I\) of \(\mathcal{A}\) assigns functions and rel