Diagram (logic)

In mathematical logic , a diagram is a set of statements that can be used to express relationships between models . The use of such diagrams is known as the diagram method. It was introduced independently by AI Malzew and A. Robinson .

definition

Let it be a model for a language of first-order predicate logic . Is the carrier of , so is called ${\displaystyle {\mathcal {M}}}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$

${\displaystyle {\begin{aligned}D({\mathcal {M}})&=\{\varphi ({\vec {m}}):{\mathcal {M}}\models \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}\\&=\{\neg \varphi ({\vec {m}}):{\mathcal {M}}\models \neg \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}\end{aligned}}}$

the diagram, or also the atomic diagram of . Here stands for a tuple with elements of the appropriate length, so that the elements of the tuple replace the free variables of the formula . A formula is called atomic if it is a term equation or a relation . Accordingly, the diagram of consists of all term equations, term inequalities, relations and negated relations of elements that apply in the model . ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\vec {m}}}$ ${\displaystyle M}$ ${\displaystyle \varphi \in L}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$

Assuming means constant expansion of language over, so in the individual from each is added as a constant, so is the diagram, the amount of valid model in atomic or negated atomic -statements. ${\displaystyle L}$ ${\displaystyle L(M)}$ ${\displaystyle M}$ ${\displaystyle L(M)}$

Sample application

Certain relationships between models can be expressed using diagrams, which is shown here using a simple example. It applies

For two models and with carrier quantities are equivalent: ${\displaystyle L}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle M\subset N}$

• ${\displaystyle {\mathcal {M}}}$is sub-model of . ${\displaystyle {\mathcal {N}}}$
• ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$, that is, the model expanded by the constants is a model of the diagram of . ${\displaystyle M}$ ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {M}}}$

As a proof, let us first consider the sub-model of . Existing Term equations Termungleichungen, relations and the negative of these elements made will be reflected in larger model , ie for all atomic or negated atomic -formulae , for the true, that is the model for each GO indication from the graph of . ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {N}}\models \varphi ({\vec {m}})}$ ${\displaystyle L}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi ({\vec {m}})}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {M}}}$

If the reverse is true , it has to be shown that the -contains constants and that the -functions and -relations of are exactly the corresponding, restricted functions or relations of . We show this using the example of the functions. Be a function and or its interpretation in or . Is and , then is a statement from the diagram of . Since , follows , that is, is the restriction of . The constants and relations are treated the same way. ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle f^{\mathcal {M}}:M^{n}\rightarrow M}$ ${\displaystyle f^{\mathcal {N}}:N^{n}\rightarrow N}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\vec {m}}\in M^{n}}$ ${\displaystyle f^{\mathcal {M}}({\vec {m}})=m_{0}\in M}$ ${\displaystyle f({\vec {m}})=m_{0}}$ ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$ ${\displaystyle f^{\mathcal {N}}({\vec {m}})=m_{0}}$ ${\displaystyle f^{\mathcal {M}}}$ ${\displaystyle f^{\mathcal {N}}}$

This can be generalized by moving from the subset relationship to a monomorphic embedding (i.e., is an injective strong homomorphism ). They are equivalent (diagram lemma): ${\displaystyle M\subset N}$ ${\displaystyle F:M\rightarrow N}$ ${\displaystyle F}$

• ${\displaystyle {\mathcal {M}}}$can be embedded monomorphically in (isomorphic to a substructure). ${\displaystyle {\mathcal {N}}}$
• There is one - expansion of that is model of . ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle D({\mathcal {M}})}$

More diagrams

You can change the sets of statements that make up the diagram and thus come to further diagram terms.

Positive diagram

The positive diagram of a model is ${\displaystyle {\mathcal {M}}}$

${\displaystyle D_{+}({\mathcal {M}})=\{\varphi ({\vec {m}}):{\mathcal {M}}\models \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}.}$

So here only the atomic statements are considered, the negations of atomic statements, however, no longer. In analogy to the above use of the diagram for monomorphic embeddability, the positive diagram can be used to characterize homomorphic embeddability. Equivalent are:

• ${\displaystyle {\mathcal {M}}}$is homomorphically embeddable in . ${\displaystyle {\mathcal {N}}}$
• There is an expansion of , the model of . ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle D_{+}({\mathcal {M}})}$

Elementary diagram

While the positive diagram was obtained by restricting the statements considered, all statements are now allowed with the so-called elementary diagram . If there is a model with a set of carriers , then the totality of all valid formulas is nothing other than the theory of the extended model , in which every new constant is interpreted by itself. This theory is known as and is called the elementary diagram of . ${\displaystyle L}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle L(M)}$ ${\displaystyle \varphi ({\vec {m}})}$ ${\displaystyle ({\mathcal {M}},M)}$ ${\displaystyle m}$ ${\displaystyle \mathrm {Th} ({\mathcal {M}},M)}$ ${\displaystyle {\mathcal {M}}}$

This term can be used to characterize the elementary embeddability . For two and are equivalent: ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {N}}}$

• ${\displaystyle {\mathcal {M}}}$can be embedded in elementary. ${\displaystyle {\mathcal {N}}}$
• There is an expansion of which is the model of . ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \mathrm {Th} ({\mathcal {M}},M)}$

For two models and with carrier quantities are equivalent: ${\displaystyle L}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle M\subset N}$

• ${\displaystyle {\mathcal {M}}}$is an elementary substructure of . ${\displaystyle {\mathcal {N}}}$
• ${\displaystyle ({\mathcal {N}},M)\models \mathrm {Th} ({\mathcal {M}},M)}$, that is, the model expanded by the constants is a model of the elementary diagram of . ${\displaystyle M}$ ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {M}}}$

Individual evidence

1. ^ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , page 93
2. ↑ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , page 96
3. ↑ Philipp Rothmaler: Introduction to model theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , Lemma 6.1.2
4. ↑ Philipp Rothmaler: Introduction to the model theory , spectrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , section 7.1: Positive diagrams
5. ↑ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , Lemma 7.1.1: Positive diagrams
6. ^ CC Chang, HJ Keisler: Model Theory , Studies in Logic and the Foundations of Mathematics, Volume 73, Elsevier Science 1990, ISBN 0-444-88054-2 , sentence 2.1.12
7. ↑ Philipp Rothmaler: Introduction to the model theory , spectrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , section 8.2: Elementary images
8. ↑ CC Chang, HJ Keisler: Model Theory , Studies in Logic and the Foundations of Mathematics, Volume 73, Elsevier Science, 1990, ISBN 0-444-88054-2 , page 137
9. ↑ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , Lemma 8.2.1