3
$\begingroup$

I have question considering example of complete formula, that was presented in Keisler/Chang - Model Theory:

2.3.1. EXAMPLES

(1). Let $T$ be a complete theory and let $c_0,c_1,c_2,\ldots$ be constant symbols of $\mathscr{L}$. Then any formula of $\mathscr{L}$ of the form $$x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n$$ is complete in $T$. If $\mathfrak{U}$ is a model of $T$ such that every element of $A$ is a constant, then $\mathfrak{U}$ is an atomic model.

Why so? Am I right, when I think, that if theory is complete than -> every of it's formulas is complete too? So that formula with conjunction too?

Also, I pin basic definitions about it:

Consider a complete theory $T$ in $\mathcal{L}$. A formula $\varphi(x_1\ldots x_n)$ is said to be complete (in $T$) iff for every formula $\psi(x_1,\ldots x_n)$ exactly one of $$T\vDash\varphi\rightarrow\psi,\quad T\vDash\varphi\rightarrow\neg\psi$$ holds. A formula $\theta(x_1\ldots x_n)$ is said to be completable (in T) iff there is a complete formula $\varphi(x_1\ldots x_n)$ with $T\vDash\varphi\rightarrow\theta$. If $\theta(x_1\ldots x_n)$ is not completable it is said to be incompletable.

A theory $T$ is said to be atomic iff every formula of $\mathcal{L}$ which is consistent with $T$ is completable in $T$. A model $\mathfrak{U}$ if is said to be an atomic model iff every $n$-tuple $a_1,\ldots,a_n\in A$ satisfies a complete formula in $\mathrm{Th}(\mathfrak{U})$.

$\endgroup$

2 Answers 2

1
$\begingroup$

$T$ is complete iff for every sentence $\phi$ either $T \models \phi$ or $T \models \lnot \phi$. This requirement only applies to sentences, i.e., closed formulas: if $\phi = \phi(x_1, \ldots, x_n)$ has free variables then $\phi$ might hold under some interpretations of $\phi$ but not under others. E.g., consider $\phi(x, y) = x < y$ in the theory of a dense linear order without endpoints.

The formula $x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n$ is complete in the sense of the definition you give, because for any $\phi$, $T \models x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n \to \phi$ iff $T \models \phi(c_1, \ldots, c_n)$. Now, $\phi(c_1, \ldots, c_n)$ is a sentence, so if $T$ is complete either $T \models \phi(c_1, \ldots, c_n)$ or $T \models \lnot\phi(c_1, \ldots, c_n)$ and so either $T \models x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n \to \phi$ or $T \models x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n \to \lnot\phi$.

If every element of a model $\mathfrak{A}$ is a constant, then every $n$-tuple, $a_1, \ldots a_n$ satisfies the formula $x_1\equiv a_1\wedge x_1\equiv a_2\wedge\cdots\wedge x_n\equiv a_n$, which we have just shown is complete. Hence such an $\mathfrak{A}$ is an atomic model according to the definition you have quoted.

$\endgroup$
15
  • $\begingroup$ Where did you get $$ T \models x_{0} \equiv c_{0}∧x_{1}\equiv c_{1}∧⋯∧x_{n}\equiv c_{n}\rightarrow\phi$$ iff$$ T \models\phi\left( c_{1},…,c_{n}\right) $$ string? Mustn't T be bounded for that? There are nothing in example about boundness. Or, maybe we can derive it from condition of complete T? $\endgroup$
    – Timur
    Feb 7, 2021 at 16:11
  • $\begingroup$ This is true in any structure. An assignment to the $x_i$ either makes $x_1 \equiv c_1 \land \ldots x_n \equiv c_n$ false or it assigns $c_i$ to $x_i$ for each $i$ reducing the implication to $\phi(c_1, \ldots, c_n)$. $\endgroup$
    – Rob Arthan
    Feb 7, 2021 at 16:16
  • $\begingroup$ But what about formulas, not sentences? Or we have, that every model of $T \cup x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n$ will also realize $\phi\left( c_1,...c_n \right)$ and, as consequence, $\phi\left( x_1,...x_n \right) $ ? $\endgroup$
    – Timur
    Feb 7, 2021 at 16:49
  • $\begingroup$ But no, then it's consequence won't be just $\phi\left( x_1,...x_n \right) $, it will be $\exists x_1...\exists x_n\phi\left( x_1,...x_n \right) $, won't it? $\endgroup$
    – Timur
    Feb 7, 2021 at 16:52
  • $\begingroup$ No, this just follows from the definition of $\models$: $T \models \alpha$ means that in every model $\mathfrak{M}$ of $T$ we have $\mathfrak{M} \models \alpha$ and this means that $\alpha$ holds under every assignment of elements of $M$ to the free variables of $\alpha$. $\endgroup$
    – Rob Arthan
    Feb 7, 2021 at 21:14
-1
$\begingroup$

I changed my answer to myself:

Thus $T$ is complete, therefore it's consistent therefore it has model. So, it's sufficient to show, that $T \cup x_0\equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n$ also will be consistent (and from that complete).

Suppose it isn't true.

Then, $T \models \forall x_0...\forall x_n \neg(x_0 \equiv c_0\wedge x_1\equiv c_1\wedge\cdots\wedge x_n\equiv c_n)$ or $T \models \forall x_0...\forall x_n (\neg x_0 \equiv c_0\vee \neg x_1\equiv c_1 \vee \cdots\vee \neg x_n\equiv c_n)$

Interpretation $I^{\mathfrak{A}}_{}$ of $c_{i} := t_{2i}$, as a term from signature in the model $\mathfrak{A} = <A,I^{\mathfrak{A}}_{}>$ is $I^{\mathfrak{A}}_{}[c_i] = a_{i}$.

Some labeling $\gamma_{j}$ of $x_{i} := t_{1i}$, as a term, in model $\mathfrak{A} =<A,I^{\mathfrak{A}}_{}>$ is $t^{\mathfrak{A}}_{1i}[\gamma_{j}] = \gamma_{j} x_{i} = a_{1i}$.

So, thus in the last formula with all variables bounded, it's must be true on all labelings $\gamma_{j}$ and on all of our variables.

But for all $i \in {0,...,n}$, $x_{i}$ takes all values from $A$, and eventually it takes $a_i$ in some labeling $\gamma_{j}$.

The resulting contradiction completes the proof.

$\endgroup$
13
  • 1
    $\begingroup$ In 1. if $T$ models every sentence, then $T$ is inconsistent - a much stronger property than completeness, which mens that $T$ either proves or disproves every sentence. Likewise in 2. it should read "or the same for $\lnot \phi$. An example of a formula that is not complete is $\phi = x < y \lor x = y$ in the theory of a dense linear order without endpoints: with $\psi = x < y$, $DLO \not\models \phi \to \psi$ and $DLO \not\models \phi \to \lnot \psi$. $\endgroup$
    – Rob Arthan
    Feb 8, 2021 at 15:12
  • $\begingroup$ So, where did you explain, in your answer, steps with that "forall" symbols? $\endgroup$
    – Timur
    Feb 8, 2021 at 15:49
  • $\begingroup$ There are no forall symbols involved in the question or in my answer. It is certainly not the case that $T \cup x_0 \equiv c_0 \land\ldots \models \phi$ implies that $T \models \forall x_0, \ldots \phi(x_0, \ldots)$. $\endgroup$
    – Rob Arthan
    Feb 8, 2021 at 15:54
  • 1
    $\begingroup$ I take $\mathfrak{M} \models \phi$ where $\phi $ has free variables to mean that $\mathfrak{M} \models \phi$ for every interpretation of the free variables in $\mathfrak{M}$. You can state this in terms of a universal quantifier. You are not manipulating the quantifiers correctly. $\endgroup$
    – Rob Arthan
    Feb 8, 2021 at 16:08
  • 1
    $\begingroup$ No, the correct definition is this: A theory $T$ is complete if for every sentence $\varphi$, $T\models \varphi$ or $T\models \lnot \varphi$. Sentences have no free variables. Rob Arthan's answer is correct. I was going to post another answer to help you understand it, but I can already tell that that won't be productive. $\endgroup$ Feb 9, 2021 at 22:24

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.