1
$\begingroup$

First the statement as I understand it:

Given some consistent logic (axioms + rules of inference) which can encode enough arithmetic to do addition and multiplication, we can always find propositions for which neither the proposition itself nor its negation is provable.

But if the logic has two non-isomorphic models, then this is rather trivial, or? For then just choose a proposition which is true in one model, but false in the other...

Or does Gödel means by a true proposition a proposition that is true in every model of the logic?

$\endgroup$
24
  • 2
    $\begingroup$ If a statement is true in EVERY model, it is provable. $\endgroup$
    – Peter
    Commented Aug 3, 2017 at 20:04
  • 2
    $\begingroup$ In Gödel's completeness theorem (his dissertation), he proves that a statement true in every model is a theorem (provable statement) of the predicate calculus. Note that two non-isomorphic models can be elementarily equivalent, that is satisfying the same statements of first-order logic. $\endgroup$
    – hardmath
    Commented Aug 3, 2017 at 20:08
  • 1
    $\begingroup$ youtube.com/watch?v=O4ndIDcDSGc $\endgroup$
    – user451844
    Commented Aug 3, 2017 at 20:12
  • 1
    $\begingroup$ "But if the logic has two non-isomorphic models, then this is rather trivial, or?" Well yes (modulo pedantry about elementary equivalence), but then you're assuming the conclusion. It is not trivial to determine whether a particular theory has non-equivalent models or not; the incompleteness theorem gives a (surprising) sufficient condition for this to happen. $\endgroup$ Commented Aug 3, 2017 at 20:15
  • 1
    $\begingroup$ The incompleteness theorems apply in a more general context than just for Peano arithmetic, but this may add a bit to the confusion: In the context of arithmetic, to be "true in a model" is not the same as being "true", which in turn is not the same as being "true in every model". A sentence that is true in every model (of the appropriate theory) is provable, this is Gödel's completeness theorem. We say that a sentence is true to mean that it is "true in the standard model", that is, $\mathbb N$ with the usual interpretation of $+,\times$, etc. $\endgroup$ Commented Aug 3, 2017 at 20:16

1 Answer 1

7
$\begingroup$

In the question as asked, your mistake is the following:

if the logic has two non-isomorphic models, then this is rather trivial, or? For then just choose a proposition which is true in one model, but false in the other...

Just because $\mathcal{A}\not\cong\mathcal{B}$ does not mean that there is a sentence true in one and false in the other! There are non-isomorphic structures which are elementarily equivalent. One easy way to see this is just by a cardinality argument: in a given language $L$, there are only $2^{\vert L\vert+{\aleph_0}}$-many sets of sentences in the language $L$ but a proper class of structures, so we have to be able to find non-isomorphic structures with the same theory. More satisfyingly, the compactness theorem (or rather, its corollary the upwards Lowenheim-Skolem theorem) tells us that for any structure $\mathcal{A}$ there is a nonisomorphic, elementarily equivalent structure $\mathcal{B}$. And in particular, if $T$ is a complete theory with an infinite model, then $T$ has lots of nonisomorphic but elementarily equivalent models (since any two models of $T$ are elementarily equivalent since $T$ is complete). (Exercise: "has non-elementarily-equivalent models" is exactly the same as "is incomplete.")

So Godel's incompleteness theorem says far more than just that there are non-isomorphic models of any "reasonable" theory of arithmetic: it says that no reasonable theory of arithmetic even pins down the true natural numbers up to elementary equivalence!

It's worth considering, at this point, some examples of complete theories.

  • The theory of dense linear orders without endpoints is computably (indeed, finitely) axiomatizable and is complete; this is a standard exercise in most first-semester logic classes.

  • A more interesting example is the following. If we consider the structure $(\mathbb{N}; +)$, it turns out that Godel fails: the theory Presburger arithmetic is complete (it axiomatizes $Th(\mathbb{N}; +)$). It's also decidable, since Presburger arithmetic is computably axiomatized.

  • Similarly, it turns out that the theory of real closed fields is complete (and computably axiomatized); this is due to Tarski.


You also asked about truth (although truth doesn't even show up in your statement of Godel's theorem). The issue here - as in your other question - is that you are conflating two notions of truth. The truthy version of Godel's incompleteness theorem says

For any "reasonable" theory $T$, there is a true sentence $\varphi$ which is not provable in $T$.

"True" here means "true in the structure $(\mathbb{N}; +, \times)$;" this has nothing to do with truth in all models of $T$. A better statement of the "truthy" incompleteness theory is:

For any "reasonable" theory $T$, there is a sentence $\varphi$ such that $\varphi$ is not provable in $T$ but $(\mathbb{N}; +,\times)\models\varphi$.

This makes it very clear what's going on, and why Godel's completeness theorem is irrelevant. Again, it boils down to the fact that any reasonable theory of arithmetic $T$ will have lots of non-elementarily-equivalent models; the sentence $\varphi$ above is not true in all of them, hence (by Completeness) not provable in $T$, but is true in the standard model.

(Keep in mind that "reasonable" here means, among other things, "computably axiomatizable"; of course the set of all sentences true in $(\mathbb{N}; +,\times)$ is a complete theory, but Incompleteness doesn't apply to it since it's not computably axiomatizable.)

$\endgroup$
4
  • $\begingroup$ I realised for the first time that there are two notions of complete around, one meaning that logical validity and provability are the same, the other that for every statement either it or its negation is provable (quite a strong assertion I find), and Gödels incompleteness refers to the last, and Gödels completeness to the first (quite confusing that two notions of completeness are associated with two famous theorems of one person). $\endgroup$
    – StefanH
    Commented Aug 4, 2017 at 13:25
  • $\begingroup$ @StefanH See also Tarski's definition of truth and Tarski's theorem on the undefinability of truth! $\endgroup$ Commented Aug 4, 2017 at 13:43
  • $\begingroup$ Ok, I will check that out. But by the way, how you know there are $2^{|L| + \aleph_0}$ sentences and what does $2^{|L| + \aleph_0}$ mean? $\endgroup$
    – StefanH
    Commented Aug 4, 2017 at 15:18
  • $\begingroup$ @StefanH Whoops, that was a bad typo - there are $2^{\vert L\vert+\aleph_0}$-many sets of sentences (that is, theories) in the language $L$. This notation is cardinal exponentiation - if you're not familiar with cardinals (e.g. what "$\aleph_0$" means), start there and you'll quickly figure things out. The point is that there are only set-many sets of sentences, but class-many structures; so there will be lots of instances of structures which are non-isomorphic but elementarily equivalent. (In fact, we'll be able to find a proper class of elementarily equivalent non-isomorphic structures!) $\endgroup$ Commented Aug 4, 2017 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .