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 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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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})$.

See also Tarski's undefinability theorem.

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.

share|improve this answer
    
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

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.