Finite structures of a theory have finite atomic diagram.

Question

Given a languaje $\mathcal{L}=(\mathcal{C},\mathcal{F},\mathcal{R})$ and $\mathcal{M}=(M,\mathcal{C}^\mathcal{M},\mathcal{F}^\mathcal{M},\mathcal{R}^\mathcal{M})$ an $\mathcal{L}$-structure. We can define a new lenguage $\mathcal{L}_\mathcal{M}$ by adjoining to $\mathcal{L}$ de elements of $M$ as constants, and we can consider the set $\text{Diag}(\mathcal{M})$ of sentences of $\mathcal{L}_\mathcal{M}$ corresponding to the atomic formulas or negation of atomic formulas of $\mathcal{M}$ that are true in this model. If I am not mistaken, this set is called the atomic diagram of $\mathcal{M}$.

I have read some times that $\text{Diag}(\mathcal{M})$ is a finite set when $M$ is finite, or some times this set is refered as a single formula $\phi(m_1,...,m_n)$. Why is this true?

As there are infinitely many terms in $\mathcal{M}$, so there are infinitely many atomic formulas. So probably this finitude refers to a subset of $\text{Diag}(\mathcal{M})$ that have the entire set as logical consequence (and if this set is finite, we can consider just one sentence using the conjunction of the finite set). If that is the case, why this finite subset exist?

Answer 1

You're absolutely right that according to the usual definition, if there are any function symbols in the language, then the atomic diagram of any nonempty structure $M$ is infinite.

But it's not hard to see that if $M$ is finite, then the atomic diagram of $M$ is actually equivalent to a finite set of $\mathcal{L}_M$-sentences (and hence to a single sentence by taking the conjunction). I think the cleanest way is to consider the following set of $\mathcal{L}_M$ sentences:

• $m\neq m'$ for all distinct $m$ and $m'$ in $M$.
• $R(m_1,\dots,m_n)$ for every $n$-ary relation symbol $R$ and every $n$-tuple $(m_1,\dots,m_n)\in R^M$.
• $\lnot R(m_1,\dots,m_n)$ for every $n$-ary relation symbol $R$ and every $n$-tuple $(m_1,\dots,m_n)\notin R^M$.
• $c = m$ for every constant symbol $c$, where $m = c^M$.
• $f(m_1,\dots,m_n) = m$ for each $n$-ary function symbol $f$ and every $n$-tuple $m_1,\dots,m_n$ from $M$, where $m = f^M(m_1,\dots,m_n)$.

This set of sentences is sometimes called the "flat diagram" of $M$: "flat" since there is no nesting of terms. The flat diagram is finite when $M$ is finite, by construction. I'll leave it as an exercise for you to show that every atomic formula which is true in $M$ is a consequence of the flat diagram of $M$. The flat diagram generalizes the notion of the multiplication table of a group more directly than the atomic diagram does.

Answer 2

An atomic formula is a formula that has no logical structure, so it does not contain any of the logical symbols $\land,\lor,\neg, \forall,\exists$.

Thus if $\mathcal L$ is finite and relational and $\mathcal M$ is a finite $\mathcal L$-structure the atomic diagram, which you defined correctly in your post, is finite. The same is true if $\mathcal L$ has function symbols, as there are only finitely many non equivalent terms.

The atomic diagram is usually viewed as the (possibly infinite) conjunction of atomic sentences and negations thereof true of $\mathcal M$ in the language $\mathcal L_{\mathcal M}$, that is $\mathcal L$ expanded by a constant symbol for every element in the universe of $\mathcal M$. So your statement that it is viewed as a single formula having variables $m_1,\dots, m_n$ is not quite correct as it does not contain any variables at all.

As an example consider the complete graph $K_3$ on three vertices with universe $\{1,2,3\}$ then its atomic diagram is $$ Diag(K_3)=\{ E(1,2),E(2,1),E(1,3), E(3,1),E(2,3),E(3,2), \neg E(1,1), \neg E(2,2),\neg E(3,3)\}.$$

It does not make a difference if we view $Diag(K_3)$ as a set or a single conjunction as we usually say that a set of sentences is true in a structure if all sentences in the set are true which is the case if and only if the conjunction of all sentences is true.