nLab
structure (model theory)

A structure on a set XX consists of a collection

𝒮 nP(X n)\mathcal{S}_n \subseteq P(X^n)

for each natural number nn such that

  • 𝒮 n\mathcal{S}_n is a Boolean subalgebra of P(X n)P(X^n),

  • If A𝒮 nA \in \mathcal{S}_n, then A×XA \times X and X×AX \times A belong to 𝒮 n+1\mathcal{S}_{n+1},

  • The set Δ={(x 1,,x n): 1inx i=x 1}\Delta = \{(x_1, \ldots, x_n): \forall_{1 \leq i \leq n} x_i = x_1\} belongs to 𝒮 n\mathcal{S}_n,

  • If π:X n+1X n\pi: X^{n+1} \to X^n denotes the projection onto the first nn coordinates, then the image π(A)\pi(A) belongs to 𝒮 n\mathcal{S}_n whenever A𝒮 n+1A \in \mathcal{S}_{n+1}.

Morally, a structure on a set is the collection of subsets of a finite power of XX which are definable with respect to a first-order language that has been interpreted in XX (such an interpretation being called a structure of the language). Indeed, the definable sets of such a language do form a structure in the present sense. Conversely, to any structure in this sense, we may introduce a relational language whose nn-ary relation symbols are named by the elements of 𝒮 n\mathcal{S}_n, and then the tautological structure of this language on XX, where each relation is interpreted as the set that names it, is a structure of this language.

Each structure 𝒮\mathcal{S} on XX induces a bicategory of relations: the objects are natural numbers, and 1-cells mnm \to n are triples (m,n,R)(m, n, R) where R𝒮 m+nR \in \mathcal{S}_{m+n}, ordered by inclusion. (It is indeed not difficult to show that 1-cells are closed under set-theoretic relational composition.)

Revised on August 11, 2011 01:38:53 by Toby Bartels (71.31.222.2)