Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I don't think your third paragraph is correct. Your sentence is not a theorem of PA. Your forward direction is correct. For the backward direction, consider the sentence $\phi \lor \lnot \phi$. –  Zhen Lin Aug 23 '11 at 3:06
    
Yes I thought about $\phi \vee \neg\phi$ for the backward direction, but I'm not sure why that sentence is in T. If it is then by assumption, $\phi \in T$ or $\neg \phi \in T$, so $T$ would be complete. Can you help with a counter example for the forward direction? –  nullgraph Aug 23 '11 at 3:19
    
Wait, of course $\phi \vee \neg \phi \in T$ because it's a tautology. –  nullgraph Aug 23 '11 at 3:26
    
@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$. –  beroal Aug 25 '11 at 15:23
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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