2
$\begingroup$

According to Wikipedia, every $\sigma$-structure $A$ is associated with a collection of atomic and negated atomic sentences called its diagram. Here's the precise definition.

For each σ-structure $A$, there are several associated theories in a larger signature σ' that extends σ by adding one new constant symbol for each element of the domain of A... The diagram of $A$ consists of all atomic or negated atomic σ'-sentences that are satisfied by $A$ and is denoted by $\mathrm{diag}_A$.

I was wondering. Since the diagram apparently captures everything about the structure, could we in principle define that a mathematical structure is its diagram? Or better yet, an ordered triple $(X,\sigma,D),$ where $D$ is the diagram in the larger signature $\sigma'$.

If so, then question: How do we define the notion that a structure satisfies a theory? In particular, how do we define $(X,\sigma,D) \models (T,\sigma),$ where $T$ is a deductively-closed first order theory in the language generated by $\sigma$?

Edit. To facilitate ease of expression, feel free to use the phrase literal sentence to mean 'a sentence that is either atomic, or the negation of a sentence that is atomic.'

Edit2. If it helps, here's some terminology we can use.

concept                    generic example

atomic          sentence   2<3
literal         sentence   not 3<2
quantifier-free sentence   if 2<3 and 3<4, then 2<4.
                sentence   For all x,y,z : if x<y and y<z, then x<z.

atomic          formula    2<x.
literal         formula    not 2<x.
quantifier-free formula    if x<y and y<z, then x<z.
                formula    For all x : if x<y and y<z, then x<z.
$\endgroup$
  • $\begingroup$ If you wanted to replace the talk of structures with that of diagrams, then you still need to have a definition for a structure, because the diagram is defined in terms of structures. $\endgroup$ – James Aug 9 '13 at 17:00
7
$\begingroup$

We could, if we liked, replace the notion of structure with the purely syntactic notion of diagram... but we'd have to be careful about what we meant by diagram.

Here's a reasonable definition. Given a language $\mathcal{L}$ and a set of constants $A$ (disjoint from $\mathcal{L}$), I'll denote by $\mathcal{L}(A)$ the language obtained by adding the constants in $A$ to $\mathcal{L}$. When I say a quantifier-free theory $T$ is complete, I just mean that for every quantifier free sentence $\phi$, $\phi\in T$ or $\lnot\phi\in T$.

Definition: In a language $\mathcal{L}$, a diagram on the set of constants $A$ is a complete consistent quantifier-free $\mathcal{L}(A)$-theory $T$ satisfying closure in the following sense:

  1. Given an $n$-ary function $f$ in $\mathcal{L}$ and constants $a_1,\dots,a_n$ from $A$, there is a constant $a$ from $A$ such that the sentence $f(a_1,\dots,a_n) = a$ is in $T$.
  2. Given a constant symbol $c$ in $\mathcal{L}$, there is a constant $a$ from $A$ such that the sentence $c = a$ is in $T$.

Now every $\mathcal{L}$-structure $A$ gives rise to a diagram in the usual way (taking the quantifier-free $\mathcal{L}(A)$-theory of $A$).

Conversely, given a diagram in the sense above, we can obtain a structure. I think this is where the previous answers (due to William and Alex Kocurek) misunderstood your question - it's true that a diagram doesn't have a unique model, but if it's closed in the sense above, it determines a canonical model.

Take the domain of the structure to be the quotient of the set $A$ by the equivalence relation $\sim$, where $a\sim b$ if and only if the sentence $a = b$ is in $T$. I'll denote by $[a]$ the equivalence class of $a$. Then interpret the constants and relations as dictated by the theory $T$ (of course, there's a well-definedness check to do):

  • $c^A = [a]$ if $c = a$ is in $T$ (using closure)
  • $f^A([a_1],\dots,[a_n]) = [a]$ if $f(a_1,\dots,a_n)=a\in T$ (using closure)
  • $R^A([a_1],\dots,[a_n])$ if and only if $R(a_1,\dots,a_n)\in T$

A few observations:

  1. This is the same "canonical model" construction appearing in Henkin's proof of the Completeness Theorem. There, too, we're interested in obtaining a structure from a suitable theory.

  2. If you want to avoid the quotient, you can additionally require in the definition of diagram that $\lnot a = b$ is in $T$ for all $a\neq b$. This has the advantage of making the constructions inverses - the diagram associated to the structure associated to a diagram is the original diagram and vice versa.

  3. This is all a little silly. We're just replacing the usual notion of structure, an arbitrary set together with interpretations of the symbols, with an arbitrary set of constants together with a syntactic description of how the symbols are to be interpreted.

But now for your last question: how do you define satisfaction in this setup? Given a diagram $D$ on the constants $A$, we'll define what it means for $D$ to satisfy $\phi(a_1,\dots,a_n)$, where $\phi$ is an $\mathcal{L}$-formula and the $a_i$ are constants from $A$.

An atomic formula should obviously be satisfied by $D$ if and only if it is in $D$. The definition for Boolean combinations is as usual. So we only need to worry about $\exists$. Well, since the constants in $A$ are the elements of the structure $D$ is describing, we say $D$ satisfies $\exists x\,\phi(x,a_1,\dots,a_n)$ if and only if there is a constant $a\in A$ such that $D$ satisfies $\phi(a,a_1,\dots,a_n)$.

$\endgroup$
  • $\begingroup$ Yes, that's a much better answer. :) $\endgroup$ – Alex Kocurek Aug 10 '13 at 1:34
  • $\begingroup$ Alex thanks for your answer. I'm curious, why are you basing everything around quantifier-free sentences? Note that 'quantifier-free sentence' is a less stringent condition than 'atomic sentence'. $\endgroup$ – goblin Aug 10 '13 at 3:00
  • $\begingroup$ Actually, I have just noticed we're probably interested in 'atomic or negated atomic' sentences, rather than just the atomic ones. Anyway, note that this is still more stringent condition than just 'quantifier-free sentence' For instance, $((2<3) \wedge (3<4)) \rightarrow (2<3)$ is a quantifier free sentence, but is it neither an atomic sentence nor a negated atomic sentence. $\endgroup$ – goblin Aug 10 '13 at 3:11
  • $\begingroup$ P.S. I edited the question, stating that: "To facilitate ease of expression, feel free to use the phrase literal sentence to mean a sentence that is either atomic, or the negation of a sentence that is atomic." $\endgroup$ – goblin Aug 10 '13 at 3:19
  • $\begingroup$ @user18921 Ah yes, I had forgotten that the diagram of a structure usually consists of all literal sentences in its theory, not all quantifier free sentences. It's reasonable that I had forgotten this, because the two notions of diagram are equivalent: Every literal is quantifier free, and if you know the truth value of every atomic sentence, then you know the truth value of every quantifier free sentence, since a quantifier free sentence is just a boolean combination of atomic sentences, i.e. the "literal diagram" generates the "quantifier free diagram". $\endgroup$ – Alex Kruckman Aug 10 '13 at 17:08
0
$\begingroup$

The diagram does not determine the structure. Even stronger, the full theory of a structure does not determine a structure.

There are elementarily equivalent structures that are not isomorphic. In fact, if you take any structure of uncountable cardinality in a countable language, by the downward Lowenheim Skolem, you can get a countable elementary substructure. Hence the two structure has the same diagram (in fact full theory), but there are no isomorphism between the two just by cardinality consideration.

$\endgroup$
  • 3
    $\begingroup$ William I think you have misread the definition! The diagram is written in the extended language generated by $\sigma'$; this means that, in particular, we have a constant symbol for each element of $X$. $\endgroup$ – goblin Aug 9 '13 at 11:24
  • $\begingroup$ Yes, but there is no guarantee that every element in a model of the diagram is the interpretation of a constant! $\endgroup$ – Zhen Lin Aug 9 '13 at 11:24
  • $\begingroup$ @ZhenLin Then for such a model $\mathfrak M$ of the diagram $D$ in a language $\mathcal L$, wouldn't we have $D \subsetneq \mathrm{diag}_{\mathfrak M}$ in the language $\mathcal L_M$ (extended language with constant for each element of the base $M$ of $\mathfrak M$) ? If so, William's argument doesn't hold. $\endgroup$ – Pece Aug 9 '13 at 11:35
  • 1
    $\begingroup$ I think everyone is misunderstanding the question... see my answer. $\endgroup$ – Alex Kruckman Aug 9 '13 at 17:50
  • 4
    $\begingroup$ To say that the diagram $D$ of a structure $\mathfrak A$ determines the structure does not mean that $\mathfrak A$ is the only model of $D$ (which is in fact false) but rather than $\mathfrak A$ is the only structure (up to isomorphism) whose diagram is $D$ (which is true). $\endgroup$ – Andreas Blass Aug 9 '13 at 17:56
0
$\begingroup$

As William has correctly noted, the diagram certainly does not determine the structure in question. True, it tells you every atomic thing that's true or false about the element of the original model (say $\cal{A}$), but there are other models with more structure which could satisfy that diagram (for instance, by including elements which aren't named in the diagram). In fact, it's a theorem of model theory that if $\cal{A},\cal{B}$ are models, with $A \subseteq B$, then $\cal{A}$ is a substructure of $\cal{B}$ if and only if $\cal{B}$ satisfies the diagram of $\cal{A}$. Hence, all superstructures of $\cal{A}$ will satisfy the diagram as well, but they certainly need not be isomorphic.

For instance, take a simple model where you have two elements $a,b \in A$, and let's say we have a unary predicate $P$ whose interpretation in $\cal{A}$ is $P^\mathcal{A} = \{a,b\}$. Then, $\mathcal{A} \vDash \forall x P(x)$. But now consider an extension of $\cal{A}$, $\cal{B}$ with one extra element $c \in B - A$, but with the interpretation of $P$ the same. Then $\mathcal{B} \vDash \text{diag}(\mathcal{A})$ (when you extend the language of $\cal{B}$ to what you're calling $\sigma'$), so $\cal{A} \subseteq \cal{B}$, and yet $\mathcal{B} \vDash \neg\forall x P(x)$ since $\mathcal{B} \vDash \neg P[c]$. So $\cal{A}$ and $\cal{B}$ aren't even elementarily equivalent!

Also, to answer your last question, a structure satisfies a theory just in case it satisfies each sentence of a theory. Satisfaction of sentences in models is defined in the usual inductive way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.