2
$\begingroup$

I'm working on the following problem which is exercise 3.5.1 in Rothmaler's Model Theory book. Show that theory $T$ is complete iff $\phi \vee \psi \in T$ implies $\phi \in T$ or $\psi \in T$ (keep in mind that in his book, a theory is deductively closed)

My forward direction looks like this: Let $\mathcal{M}$ be a model of T, if $\mathcal{M} \models \phi \vee \psi$ then $\mathcal{M} \models \phi$ or $\mathcal{M} \models \psi$. $\mathcal{M} \models \phi$ means $\phi \in Th(M)$ but because $T$ is complete, $T=Th(M)$ so $\phi \in T$. Similarly for $\psi$. Is this correct?

For a counter example of the forward direction, I was thinking something along the line of: Let $T$ be PA (which is incomplete), and consider non-standard model $\mathcal{M}$ of $T$, then in $\mathcal{M}$, the sentence "$x \neq x$ or there's a biggest elt" is true, but neither $x \neq x$ or "there's a biggest elt" is in PA. Does this make sense?

I'm not sure about the backward direction.

  • 0
    @nullgraph: You need not rely on models for the forward direction. Let $\phi, \psi$ be formulas and $\phi\lor\psi\in T$. Because $T$ is complete, $\phi\in T$ or $\lnot\phi\in T$. If $\lnot\phi\in T$, then by $\phi\lor\psi, \lnot\phi \vdash \psi$ (because of “elimination of disjunction”, “ex falso quodlibet”, S, K are in $T$) and because $T$ is closed we obtain $\psi\in T$.2011-08-25

1 Answers 1

2

Your argument for the forward direction is fine.

However, the sentence you suggest is not true in any model of $T$, be it nonstandard or not. This is because PA proves both that $x=x$ and that for any number there is a larger number. But then this holds in any model of PA, be it nonstandard or the standard one.

If you insist on $T$ being PA, an example is the sentence "PA is consistent or PA is inconsistent" formalized in the usual way (it is irrelevant for the moment what "the usual way" is, it would distract us to actually go through the formalization here). This sentence is obviously true (because $\phi\lor\lnot\phi$ is always true). However, "PA is consistent" is only true in certain models (such as the standard model) while "PA is inconsistent" is true in some nonstandard models (by the incompleteness theorem, this sentence is neither provable nor refutable in PA so, by the completeness theorem, it holds in some model of PA).

It is much simpler to take $T$ to be, say, the theory of graphs, and consider the assertion "there is exactly one element of the universe, or there is more than one."

As suggested by Lin, the backward direction of the equivalence follows from taking $\psi=\lnot\phi$. Note that $\phi\lor\lnot\phi$ is a theorem, and in fact it is a propositional tautology (i.e., it can be proved in first order logic using only propositional axioms). So it follows from any theory. In particular, it follows from $T$. The assumption on $T$ gives that either $\phi\in T$ or else $\lnot\phi\in T$. Hence $T$ is complete.