Diagram (mathematical logic)

In model theory, a branch of mathematical logic, the diagram of a structure is the set of sentences with parameters from the structure that are true in the structure, denoted ${\displaystyle D({\mathfrak {A}})}$ or ${\displaystyle {\text{Diag}}({\mathfrak {A}})}$ for a structure ${\displaystyle {\mathfrak {A}}}$. Usually 'diagram' means the atomic diagram that contains only the atomic and negated atomics sentences which are true in the structure. We can also define the elementary diagram that contains all true sentences.

Diagrams are a simple but powerful tool for proving useful properties of a theory, for example the amalgamation property and the joint embedding property, among others. The name 'diagram' was introduced by Abraham Robinson, the first model theorist to make systematic use of diagrams.^[1]

Definition

Let ${\displaystyle {\mathcal {L}}}$ be a first-order language and ${\displaystyle T}$ be a theory over ${\displaystyle {\mathcal {L}}.}$ For a model ${\displaystyle {\mathfrak {A}}}$ of ${\displaystyle T}$ one expands ${\displaystyle {\mathcal {L}}}$ to a new language

${\displaystyle {\mathcal {L}}_{A}:={\mathcal {L}}\cup \{c_{i}:a_{i}\in A\}}$

by adding a new constant symbol ${\displaystyle c_{i}}$ for each element ${\displaystyle a_{i}}$ in ${\displaystyle A,}$ where ${\displaystyle A}$ is a (not necessarily proper) subset of the domain of ${\displaystyle {\mathfrak {A}}.}$ Now one may expand ${\displaystyle {\mathfrak {A}}}$ to the model ${\displaystyle {\mathfrak {A}}_{A}:=({\mathfrak {A}},a_{i})_{a_{i}\in A}.}$

The (atomic) diagram ${\displaystyle D({\mathfrak {A}})}$ of ${\displaystyle {\mathfrak {A}}}$ is the set of all atomic sentences and negations of atomic sentences of ${\displaystyle {\mathcal {L}}_{A}}$ that hold in ${\displaystyle {\mathfrak {A}}_{A}.}$^[2][3] Symbolically, ${\displaystyle D({\mathfrak {A}})=\{\phi$ :{\mathfrak {A}}\models \phi {\text{ where }}\phi {\text{ is an atomic }}{\mathcal {L}}_{A}{\text{-formula or a negation thereof}}\}} .

The elementary diagram ${\displaystyle D_{el}({\mathfrak {A}})}$ of ${\displaystyle {\mathfrak {A}}}$ is the set of all sentences of ${\displaystyle {\mathcal {L}}_{A}}$ that hold in ${\displaystyle {\mathfrak {A}}_{A}.}$^[4][5] Symbolically, ${\displaystyle D_{el}({\mathfrak {A}})=\{\phi$ :{\mathfrak {A}}\models \phi {\text{ where }}\phi {\text{ is a sentence of }}{\mathcal {L}}_{A}\}} . Equivalently, ${\displaystyle D_{el}({\mathfrak {A}})=\{\phi (c_{1},\ldots ,c_{n}):{\mathfrak {A}}\models \phi (c_{1},\ldots ,c_{n}){\text{ where }}\phi {\text{ is an }}{\mathcal {L}}{\text{-formula}}\}}$.^[6]

The positive diagram of ${\displaystyle {\mathfrak {A}}}$, sometimes denoted ${\displaystyle D^{+}({\mathfrak {A}})}$, is the set of all those atomic sentences which hold in ${\displaystyle {\mathfrak {A}}}$ while the negative diagram, denoted ${\displaystyle D^{-}({\mathfrak {A}}),}$ thereof is the set of all those atomic sentences which do not hold in ${\displaystyle {\mathfrak {A}}}$. The positive diagram and the negation of all of the formulas in the negative diagram combine to form the atomic diagram. Symbolically, ${\displaystyle D({\mathfrak {A}})=D^{+}({\mathfrak {A}})\cup \neg D^{-}({\mathfrak {A}})}$.