Re: Godel's Theorem and Model Theory

On Jul 26, 9:21 am, poopdevi...@xxxxxxxxx wrote:
Hi Everybody,

I've been thinking about non-standard models of PA lately, especially
with regards to Godel's Incompleteness theorem. To be clear, here is
the version I'm working from: For each recursively enumerable theory
containing PA, "an arithmetical statement that is true, but not
provable in the theory, can be constructed." -- the quoted part is
from wikipedia.


For each consistent recursively enumerable theory containing PA this
is true, yes.

What exactly is meant by 'true' in the above?

True in the standard model. However, this is not the usual formulation
of the theorem. The usual formulation of the theorem is "Given any
consistent recursively enumerable theory containing Q (Robinson
Arithmetic), there exists a pi-1 sentence which is neither provable
nor disprovable in the theory."

The completeness
theorem says that a sentence in a theory T can be proved iff it is
true in every model of T. So if PA can't prove this mysterious
sentence (I know, Godel demonstrates one), it must be false in some
model of PA. Does 'true' mean merely "true in some model"? Or "true
in the standard model"?

The latter.

Something completely different?

For my own sanity, I've always re-interpreted Godel's theorem using
the Soundness and Completeness theorems as essentially stating that
for each recursively enumerable theory T containing PA, there exists a
sentence P true in some model of T and false in others.

That's equivalent to the version I just gave above, except that I
reduced it down to Q rather than PA, and also I added the requirement
that the theory be consistent, which is necessary.

I'm afraid I
might have been mistaken.

No, that's pretty much right.

However, if I wasn't, is there any way to
characterize the class of P's? Put another way, what would a non-
standard (in this sense) model of PA look like? Countable ordinals?
Cars and boats thrown in?

Thanks,
Alex

The order type of any nonstandard model of PA is N followed by Q x Z.

.

Relevant Pages

  • Re: Godels Theorem and Model Theory
    ... I've been thinking about non-standard models of PA lately, ... For each recursively enumerable theory ... Assume the standard model ... If I am not mistaken a contradiction can be derived as well ...
    (sci.logic)
  • Godels Theorem and Model Theory
    ... with regards to Godel's Incompleteness theorem. ... For each recursively enumerable theory ... in the standard model"? ...
    (sci.logic)
  • Re: Godels Theorem and Model Theory
    ... with regards to Godel's Incompleteness theorem. ... For each recursively enumerable theory ... in the standard model"? ...
    (sci.logic)