Diagram (mathematical logic)

In mathematical logic, a diagram is a formal structure representing a model of a first-order language. More specifically, a diagram encodes information about the individuals and relations within a particular model. There are two main types of diagrams: the elementary diagram and the basic diagram (sometimes simply called the diagram).

The basic diagram (or simply diagram) of a structure M in a language L is a set of all atomic sentences and negations of atomic sentences that are true in M when the individual constants in L are interpreted as elements of the domain of M. To form the diagram, the language L is augmented with a new constant symbol c_a for each element a in the domain of M. These constants are then interpreted as referring to their corresponding elements. For each relation symbol R in L, and for all elements a₁,...,a_n in the domain of M, if R^M(a₁,...,a_n) holds (meaning the relation R holds for a₁,...,a_n in the model M), then the atomic formula R(c_a1,...,c_an) is added to the diagram. If R^M(a₁,...,a_n) does not hold, then the negation ¬R(c_a1,...,c_an) is added to the diagram. Similarly, for each function symbol f in L, and for all elements a₁,...,a_n, b in the domain of M, if f^M(a₁,...,a_n) = b, then the atomic formula f(c_a1,...,c_an) = c_b is added to the diagram. If the equality a = b holds in M, then c_a = c_b is added; otherwise, ¬(c_a = c_b) is added. The basic diagram thus provides a complete description of the atomic facts that are true in the model M.

The elementary diagram of a structure M is the set of all sentences in the language augmented with constants for elements of M that are true in M. This is a much larger set than the basic diagram, as it includes quantified sentences, implications, and other complex formulas, not just atomic formulas and their negations. The elementary diagram completely characterizes the elementary properties of the model M.

Diagrams are a key tool in model theory. They are used in proofs of embedding theorems, such as the downward Löwenheim–Skolem theorem, and in demonstrating the existence of models with specific properties. The diagram method allows us to express properties of a specific model M in a logical theory, which can then be used to prove the existence of other models related to M in some way (e.g., elementary extensions). The basic diagram is useful for showing that a structure can be embedded into another structure, while the elementary diagram is used to show that a structure can be elementarily embedded into another structure.