# Difference between set of true sentences and deductive closure

I'm reading a chapter on first order arithmetic, and it lists the set of all true sentences (called complete first-order arithmetic and labelled $\Omega$) and the deductive closure of the empty set $\Lambda =_{df} \mathbf{Dc} \emptyset$ that is called "logic".

Are they different sets? I thought that since first-order logic systems are complete, any true sentence is deducible.

-
But this is not the same completeness. The completeness of the theory (in a particular model) is not the same as the completeness of the logic. –  Asaf Karagila Mar 30 '13 at 16:23
Yes, there are two forms of completeness. I am referring to the semantic completeness of first-order predicate calculus. Is every true sentence deducible? –  Darren Naylor Mar 31 '13 at 2:49

It depends what is meant by the set of all true sentences. Probably it refers to $Th(\mathcal{N})$, the set of arithmetic sentences that are true in $\mathcal{N}$ (the standard model). By Gödel's first incompleteness theorem we cannot construct an effectively generated consistent theory that would prove all these sentences, so the deductive closure of any consistent arithmetic system will be always a proper subset of $Th(\mathcal{N})$.

Update to clarify: Let $T$ be a consistent, effectively generated arithmetic theory. By Gödel's first incompleteness theorem there must be some true arithmetic formula $\phi\in Th(\mathcal{N})$ that is not provable in $T$, so $T\not\vdash\phi$.

However, by Gödel's completeness theorem we have for any $\psi$ that $T\vdash\psi$ iff $T\models\psi$. And because $T\not\vdash\phi$ we get that $T\not\models\phi$. In other words, there must exists a model $M$ of $T$ such that $M\models T$ and $M\not\models\phi$. Because $\phi$ is a true arithmetic formula ($\mathcal{N}\models\phi$), our model $M$ must be different from $\mathcal{N}$. Such models are called non-standard models of arithmetic. Formula $\phi$ is a true arithmetic formula, but isn's not true in all models of $T$!

So a corollary of Gödel's incompleteness theorem is that we cannot construct a consistent first-order theory of arithmetic that would have no other models than the standard one $\mathcal{N}$. Every theory must have a non-standard model in which some arithmetic truth is false.

-
I am struggling with how this fits in with semantic completeness? I thought that if a sentence is true (satisfied by every valuation), then we write $\models \alpha$, and by the semantic completeness it follows that $\vdash \alpha$, i.e. the sentence is deducible? –  Darren Naylor Mar 31 '13 at 15:37
@DarrenNaylor I updated the answer with an explanation how Gödel's completeness and incompleteness theorems go together. –  Petr Pudlák Mar 31 '13 at 16:59