Godel's Theorem and Model Theory

1 view
Skip to first unread message

poopd...@gmail.com

unread,
Jul 25, 2007, 7:21:33 PM7/25/07
to
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.

What exactly is meant by 'true' in the above? 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"? 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. I'm afraid I
might have been mistaken. 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

Message has been deleted

LauLuna

unread,
Jul 25, 2007, 7:54:02 PM7/25/07
to
On Jul 26, 1:21 am, poopdevi...@gmail.com 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.


> What exactly is meant by 'true' in the above? 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"? Something completely different?

If the sentence P is undecidable in T neither G nor its negation can
be derived in T. In any model of T just one of them is true.


> 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. I'm afraid I
> might have been mistaken.

No, you weren't.


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


You can get a nonstandard model by adding 'nonstandard numbers'.

Think of Gödel's sentence G. G says there is no number being the
Gödel
number of a proof of G in T (or rather the arithmetical equivalent
property). T can typically prove for any particular n that n is not
the Gödel number of such proof . Add ~G. Then T+~G proves there is
some number which is the Gödel number of a proof of G in T (that is,
which has the equivalent arithmetical property). But since T+~G
proves
the opposite for all naturals, the nonstandard model of T+~G must
contain at least one nonstandard number.


Regards

Newberry

unread,
Jul 25, 2007, 8:42:02 PM7/25/07
to

Newberry

unread,
Jul 25, 2007, 8:47:07 PM7/25/07
to
On Jul 25, 4:21 pm, poopdevi...@gmail.com wrote:

Assume the standard model
Then T(G)
G [by T(G) <--> G]
this leads to a contradiction
Therefore the standard model is incorrect
That leaves the non-standard models
So let's assume a non-standard model
If I am not mistaken a contradiction can be derived as well
The liar strikes back

What is wrong with the above reasoning?

For one, Peano attempted to codify the standard model because that is
what we are interested in - that is arithmetic. But if we assume the
standard model we get a contradiction. Is arithmetic inconsistent?

MoeBlee

unread,
Jul 25, 2007, 9:36:10 PM7/25/07
to
On Jul 25, 5:47 pm, Newberry <newberr...@gmail.com> wrote:

> Assume the standard model

What do you intend "assume the standard model" to mean? A model is not
a statement or set of statements, so a model is not something that is
assumed.

> Then T(G)

What does 'T(G)' stand for? For "G is true in the standard model"?

If so, then yes, T(G).

> G [by T(G) <--> G]

> this leads to a contradiction

No it doesn't.

> Therefore the standard model is incorrect

What does "a model is incorrect mean"? A model is certain mathematical
object. How is it "incorrect"?

> That leaves the non-standard models
> So let's assume a non-standard model

Again, what does "assume a model" mean? A model is not a statement or
set of statements, so a model is not something that is assumed.

> If I am not mistaken a contradiction can be derived as well

Since "assume a model" doesn't have any apparent meaning, I wouldn't
worry about what you think are contradictions from "assuming" models.

> The liar strikes back

Your sloppiness strikes again.

> What is wrong with the above reasoning?

I just told you.

> For one, Peano attempted to codify the standard model because that is
> what we are interested in - that is arithmetic. But if we assume the
> standard model we get a contradiction.

Since "assume a model" doesn't have any apparent meaning, I wouldn't
worry about what you think are contradictions from "assuming" models.

> Is arithmetic inconsistent?

By ordinary mathematical reasoning (though not in PA itself) we prove
that PA is consistent. If you think PA might not be consistent, then
you might state from what principles you would start trying to prove
that PA is inconsistent.

MoeBlee

Rupert

unread,
Jul 26, 2007, 12:19:29 AM7/26/07
to
On Jul 26, 9:21 am, poopdevi...@gmail.com 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.

herbzet

unread,
Jul 26, 2007, 1:52:01 AM7/26/07
to

I was about to post this when I saw Rupert's response, which is
essentially the same as mine, but better. But what the hell:

poopd...@gmail.com 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.

Look at it this way:

For each [consistent] recursively enumerable theory containing PA,
there is an arithmetical statement P such that neither P not ~P
is provable in the theory.

Under any interpretation, one of P and ~P is true and one is
false, so under any interpretation there exists an arithmetical
statement that is true but not provable in the theory.

> What exactly is meant by 'true' in the above? 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.

Correct.

> Does 'true' mean merely "true in some model"? Or "true
> in the standard model"? Something completely different?

In any model, in fact in any interpretation (which may not
be a model), one of P or ~P will be true, but neither will
be true in all models.

The author of the sentence in the Wikipedia article probably
meant "true in the standard model" which is the usual convention.

PA has a standard model, but not all theories subject to
Godelian incompleteness have models that are agreed to be
standard.

So more generally, for any consistent recursively enumerable
theory T that includes PA there will exist sentences P such that
neither P not ~P is provable in T; that is, P will be false in
some model of T and ~P will be false in some model of T.

> For my own sanity, I've always re-interpreted Godel's theorem using
> the Soundness and Completeness theorems as essentially stating that
> for each

consistent

> recursively enumerable theory T containing PA, there exists a
> sentence P true in some model of T and false in others. I'm afraid I
> might have been mistaken.

I think you're ok here.

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

This was carefully explained to me a few months ago here by Chris
Menzel and Daryl McCullough. What remains in my memory is that
in a non-standard model of PA there are hyperfinite numbers out
"beyond" (following) the standard whole numbers. The structure
of the set of hyperfinite numbers is isomorphic to the set of
rationals, or to lots of (an infinite number of) sets of rationals.
It's a countably infinite, dense set in any non-standard model.

Probably googling "hyperfinite number" is better than trusting
my memory.

--
hz

Daryl McCullough

unread,
Jul 26, 2007, 10:08:00 AM7/26/07
to
Newberry says...

>Assume the standard model
>Then T(G)
>G [by T(G) <--> G]
>this leads to a contradiction
>Therefore the standard model is incorrect
>That leaves the non-standard models
>So let's assume a non-standard model
>If I am not mistaken a contradiction can be derived as well
>The liar strikes back
>
>What is wrong with the above reasoning?

Well, the key statement that is wrong is the
claim "...this leads to a contradiction". No,
it doesn't. I can't say what's wrong with your
reasoning since you didn't say why you think it
leads to a contradiction.

--
Daryl McCullough
Ithaca, NY

george

unread,
Jul 26, 2007, 12:01:30 PM7/26/07
to
On Jul 25, 7:21 pm, poopdevi...@gmail.com wrote:
> "an arithmetical statement that is true, but not
> provable in the theory, can be constructed." -- the quoted part is
> from wikipedia.
>
> What exactly is meant by 'true' in the above?

Good question.

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

All those models are non-standard.
In the case of PA, Godel sentences (and related things like
consistency sentences)
are true in the standard model.

> Does 'true' mean merely "true in some model"?

Not just SOME model.

> Or "true in the standard model"?

It definitely means that in things THAT HAVE a standard model.
PA and ZFC (the two most important classical 1st-order theories)
are at odds on this in that PA's standard model is in some sense its
"smallest" (inner) model, while ZFC's standard model is in some sense
its "biggest" model (the one with "full" powersets).

> Something completely different?

In this context it really would be smart to just STOP saying
"true(period)",period, and start ALWAYS talking about truth
IN A MODEL. Outside a model, what matters is what's provable,
NOT what's true. Of course, under this paradigm, things that are
provable are going to be in true in every model, so you might want
to still call them true. That would be a mistake. It would be like
calling
a human being an animal. Yes, people are animals, and yes, theorems
are true, but the point is, they are so MUCH MORE THAN JUST that.

> 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 true but it hardly counts as a REinterpretation!
Given that the completeness theorem was proved BEFORE the
incompleteness theorem, the incompleteness theorem HAS ALWAYS
meant this!

> I'm afraid I might have been mistaken.

Don't panic.
You may get semantic quibbles over whether that version or
the one in terms of "just plain" truth deserves to be CALLED
"Godel's Theorem" but the content is the same.

Newberry

unread,
Jul 26, 2007, 3:25:35 PM7/26/07
to
On Jul 26, 7:08 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

We have derived G, which says about itself that it is not derivable.


george

unread,
Jul 26, 2007, 3:43:58 PM7/26/07
to

> On Jul 26, 7:08 am, stevendaryl3...@yahoo.com (Daryl McCullough)
> > Well, the key statement that is wrong is the
> > claim "...this leads to a contradiction". No,
> > it doesn't. I can't say what's wrong with your
> > reasoning since you didn't say why you think it
> > leads to a contradiction.

On Jul 26, 3:25 pm, Newberry <newberr...@gmail.com> wrote:
> We have derived G,

Not in PA you haven't.
The reason why G is not derivable is that
it is NOT EVEN TRUE, in SOME models of PA.

> which says about itself that it is not derivable

NOthing "says anything about" itself, inherently.
Godel numbers are (almost) arbitrary.
Godel sentences (and consistency sentences)
are true under some interpretations and false under
others. The one you want to privilege (the natural
numbers) is NOT even DEFINABLE AT ALL at in the
context (r.e.classical first-order theories) that "derivability"
is about.

Basically, by "we have derived G", you meant,
"we have used ZFC to prove the existence of a model
of PA in which G is true". The far more interesting question
is actually about the models where it is false.


Daryl McCullough

unread,
Jul 26, 2007, 4:09:58 PM7/26/07
to
Newberry says...

G is constructed for a specific theory. For example, Peano
Arithmetic. For PA we can construct a sentence G such that

G is true (in the standard model of arithmetic)
<-> G is not provable in PA

That's not a contradiction.

MoeBlee

unread,
Jul 26, 2007, 4:41:29 PM7/26/07
to
On Jul 26, 12:25 pm, Newberry <newberr...@gmail.com> wrote:
> On Jul 26, 7:08 am, stevendaryl3...@yahoo.com (Daryl McCullough)

> > I can't say what's wrong with your


> > reasoning since you didn't say why you think it
> > leads to a contradiction.
>
> We have derived G, which says about itself that it is not derivable.

Are you SERIOUS? Do you REALLY not understand such basics or are you
trolling?

We derive that G is true in the standard model of PA, but we don't do
that derivation IN PA (or in whatever system is being shown
incomplete). G is not equivalent to the statement "G is not derivable
in any system whatsoever".

Wow, you really are hopeless!

Though, I have to admire your nerve in thinking that you've no
intellectual obligation (to yourself even) to LEARN the subject on
which you are spouting as you engage the likes of such informed and
lucid posters such as Daryl to correct your ignorant pronouncements.

MoeBlee

Newberry

unread,
Jul 26, 2007, 9:00:09 PM7/26/07
to
On Jul 26, 1:09 pm, stevendaryl3...@yahoo.com (Daryl McCullough)

When you say "G is true in the standard model" is it not the same as
"if we assume the standard model then G"? .

>
> --
> Daryl McCullough
> Ithaca, NY- Hide quoted text -
>
> - Show quoted text -


Newberry

unread,
Jul 26, 2007, 9:13:17 PM7/26/07
to
On Jul 26, 12:43 pm, george <gree...@cs.unc.edu> wrote:
> > On Jul 26, 7:08 am, stevendaryl3...@yahoo.com (Daryl McCullough)
> > > Well, the key statement that is wrong is the
> > > claim "...this leads to a contradiction". No,
> > > it doesn't. I can't say what's wrong with your
> > > reasoning since you didn't say why you think it
> > > leads to a contradiction.
>
> On Jul 26, 3:25 pm, Newberry <newberr...@gmail.com> wrote:
>
> > We have derived G,
>
> Not in PA you haven't.
> The reason why G is not derivable is that
> it is NOT EVEN TRUE, in SOME models of PA.
>
> > which says about itself that it is not derivable
>
> NOthing "says anything about" itself, inherently.
> Godel numbers are (almost) arbitrary.
> Godel sentences (and consistency sentences)
> are true under some interpretations and false under
> others. The one you want to privilege (the natural
> numbers) is NOT even DEFINABLE AT ALL at in the
> context (r.e.classical first-order theories) that "derivability"
> is about.

Here is the standard interpretation:
(Ex)(P(x, #("A")) --> A (1)
When you add this to PA you get an immediate contradiction. (1) is
equivalent to assuming the standard model. If (1) is not the case then
it leaves the non-standard models.
What is wrong with this reasoning?

MoeBlee

unread,
Jul 26, 2007, 9:20:08 PM7/26/07
to

No! There is no "we assume the standard model". What do you think a
model IS? What we assume or don't assume are sentences or sets of
sentences. A model is not a sentence and not a set of sentences. Of
course, for each model M, there is the set of set sentences that are
true in that model (that is called 'the theory of model M'), but to
say that a sentence S is true in a model M is NOT equivalent (not even
CLOSE to be equivalent) to assuming all the sentences that are members
of the theory of the model M.

How can you be so opinionated about this subject, posting all kinds of
pronouncements on it, when you don't even know its basics?

MoeBlee


MoeBlee

unread,
Jul 26, 2007, 9:31:11 PM7/26/07
to
On Jul 26, 6:13 pm, Newberry <newberr...@gmail.com> wrote:
> is
> equivalent to assuming the standard model.

It makes no sense to say we "assume a model" in the manner you are
doing. A model is not a sentence or set of sentences that we assume or
reject assuming. A model is a mathematical object (usually a certain
kind of function on symbols of a language or a tuple that arranges the
range of such a function). So it makes about as much sense to say
"assume model M" as it does to say "assume the number 2" or to say
"assume this triangle". Sure, one might speak of assuming that a
certain set of sentences has a model, but that is much different from
saying such a silly thing as "assuming the standard model" in the
sense you are doing. And we do refer to the set of sentences that are
true in a model M and we may choose to assume or reject assuming that
set of sentences, but that is not expressed by saying "assuming the
model M" as you are and it does not bear upon this discussion in the
way you would have it.

You are confused as to even such a basic thing as what a model IS.
What makes you think then that you are in a position to tell other
well informed people (and I'm not even including myself) anything
about this subject?

MoeBlee

Keith Ramsay

unread,
Jul 27, 2007, 3:42:00 AM7/27/07
to

On Jul 26, 10:01 am, george <gree...@cs.unc.edu> wrote:
|In this context it really would be smart to just STOP saying
|"true(period)",period, and start ALWAYS talking about truth
|IN A MODEL. Outside a model, what matters is what's provable,
|NOT what's true. Of course, under this paradigm, things that are
|provable are going to be in true in every model, so you might want
|to still call them true. That would be a mistake. It would be like
|calling
|a human being an animal. Yes, people are animals, and yes, theorems
|are true, but the point is, they are so MUCH MORE THAN JUST that.

I wouldn't recommend this advice. I mean, if the
original poster finds it helpful, by all means go
ahead and think this way.

It seems to be a common problem, however, to get
stuck imagining that the concept of truth is
dependent on the concept of "model". If one then
tries to retrace one's steps, to work out a
logical sequence of definitions of terms, one
keeps getting stuck wondering how it's possible
to specify a model while being unable to talk
about truth of any kind (but only provability).

One always knows what integers are long before one
has any of these concepts of mathematical logic in
mind. This isn't just a quirk of human psychology
or of the educational system either; the concepts
of mathematical logic are dependent on the concept
of integer (or natural number at least), or some
equivalent stand-in, like the concept of a finite
string of characters.

Once one knows what natural numbers are, what
addition and multiplication of them are, and so on,
one can then understand what this kind of number-
theoretic sentence being referred to means, and
what it means for it to be true, without having
any notion of what a "model" is.

Later on, if one learns some mathematical logic,
one can then realize that there is such a thing as
the set of all natural numbers, which together
with the basic relations and functions on it forms
a model N of various theories like PA. One can then
point out that what one understood by the truth of
one of these sentences of number theory can be
rephrased in terms of a model-relative concept of
truth: the truth of that sentence "in N". But this
is only a rephrasing. Unless one already knows
what a natural number is, and what various
sentences referring to natural numbers mean,
there's no way that one could've gotten to that
point.

Goedel foresaw the troubles that could arise if he
stated his incompleteness theorems or their proofs
using such concepts as "truth". (He wrote a letter
in which he mentioned this.) People could wonder
whether there was some subtle problem with the
way he was using it. So he carefully stated
it all in "syntactic" terms, using concepts like
formal provability in a system. He had no problem
with speaking of the truth of the sentences,
however, when he wasn't trying to occupy a
defensive position, and it's only natural to think
in such terms as one considers the theorems.

Keith Ramsay

Daryl McCullough

unread,
Jul 27, 2007, 10:34:54 AM7/27/07
to
Newberry says...

>On Jul 26, 1:09 pm, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:

>> G is constructed for a specific theory. For example, Peano


>> Arithmetic. For PA we can construct a sentence G such that
>>
>> G is true (in the standard model of arithmetic)
>> <-> G is not provable in PA
>>
>> That's not a contradiction.
>
>When you say "G is true in the standard model" is it not the same as
>"if we assume the standard model then G"? .

It only makes sense to assume *statements*. A model is not
a statement. So I don't know what you mean by assuming the
standard model.

Anyway, whatever you mean by "assume the standard model", the
question is: what contradiction are you claiming to have discovered?
A contradiction in a set of assumptions (plus inference rules)
occurs when both a statement and its negation are both provable
from those assumptions together with those inference rules.
What contradiction do you think you have discovered?

Daryl McCullough

unread,
Jul 27, 2007, 10:57:43 AM7/27/07
to
Newberry says...

>Here is the standard interpretation:
>(Ex)(P(x, #("A")) --> A (1)
>When you add this to PA you get an immediate contradiction. (1) is
>equivalent to assuming the standard model. If (1) is not the case then
>it leaves the non-standard models.
>What is wrong with this reasoning?

For one thing, your statement (1) doesn't say anything
about the standard model. So stop saying that.

For the second problem: no, it's not true that if you add
(1) to PA you get an immediate contradiction. The proof
predicate P(x,y) is defined for a specific set of axioms,
the axioms of PA. If you add *new* axioms, you have to
make a corresponding change to the proof predicate.

So let's make the dependence on axioms explicit. Instead
of P(x,y), let's introduce a three-place predicate
P(z,x,y) with the interpretation:

P(z,x,y) holds if A is a code for an r.e. set of axioms A,
y is a code for a statement Phi, and x is a code for
a proof of Phi using the axioms in A.

Let #PA be the code for the axioms of PA. Then your
statement (1) becomes:

(1) (Ex)(P(#PA, x, #("A")) --> A

Godel's theorem shows that if PA is consistent, then
PA cannot prove a specific instance of (1), namely
there is a sentence G_PA such that

G_PA <-> not (Ex)P(#PA, x, #G_PA)

is provable in PA. It follows that if PA is consistent,
then PA cannot prove the instance of (1) in which A is
replace by G; PA cannot prove

(Ex) (P(#PA,x,#G_PA)) --> G_PA

Now, you ask what happens if we add all instances of
schema (1) to PA? Well, that means that we are *changing*
the axioms. We are defining a *new* theory, which we can
call PA_2 whose axioms include all axioms of PA plus all
instances of

(Ex) (P(#PA,x,#A)) --> A

Is this new theory consistent? Yes (the proof that it
is consistent can be done in ZFC, for example). Note
that what PA_2 cannot prove is this:

(Ex) (P(#PA_2,x,#A)) --> A

If you want, you can add those as axioms to PA_2 to
get yet another theory PA_3, but then PA_3 will be
unable to prove

(Ex) (P(#PA_3,x,#A)) --> A

There is no way to construct an inconsistent theory
by starting with a theory that is true in the standard
model and adding more statements that are also true
in the standard model.

--
Daryl McCullough
Ithaca, NY

Daryl McCullough

unread,
Jul 27, 2007, 11:05:17 AM7/27/07
to
Keith Ramsay says...

>It seems to be a common problem, however, to get
>stuck imagining that the concept of truth is
>dependent on the concept of "model". If one then
>tries to retrace one's steps, to work out a
>logical sequence of definitions of terms, one
>keeps getting stuck wondering how it's possible
>to specify a model while being unable to talk
>about truth of any kind (but only provability).

Very good point. Actually, even if you want to
be a formalist about it and say that the only
meaningful statements are of the form "Phi is
provable in theory T", you are still relying on
the *truth* (not just provability) of statements
of the form "X is a proof of Y from axioms Z".

george

unread,
Jul 27, 2007, 2:35:33 PM7/27/07
to
On Jul 26, 9:13 pm, Newberry <newberr...@gmail.com> wrote:
> Here is the standard interpretation:

NO, dumbass, what you have "here" IS NOT
"the standard interpretation". The standard interpretation is
"Everything in the domain is a natural number".
You caNOT even SAY that "here", i.e., using the
first-order language of PA.

> (Ex)(P(x, #("A")) --> A

You can't say THAT in the language under consideration
(the first-order language of PA) EITHER, because even though
you didn't write the universal quantifier, THAT is universally
quantified
OVER A. You are trying to say that FOR ALL A. Not only that,
the way you have phrased it above is not even grammatical because it
has "A" in it. NOrmally, quotes mean "do NOT evaluate the thing
inside
the quotes". But you are NOT looking for -- with #("A") -- the
godel-number of the 1-character string "A".

EVEN *SAYING* this stuff AT ALL is HARD!
The proof of Godel's theorem makes a prior contribution (prior to
its negative result about proving truths in the standard model) in
forcing people to focus on the DIFFERENCE between the object-
language AND THE META-LANGUAGE. Most of what people actually
want to say IS IN THE META-LANGUAGE. ONLY SOME of it is
re-translatable down into the object language, and even there,
ESPECIALLY in the case of PA vs. the natural numbers, THE TRANSLATIONS
ARE IMPERFECT. Provability in particular simply cannot be translated
at all,
BECAUSE PROOFS HAVE TO BE FINITE, but PA has to have models where
MOST THINGS AREN'T FINITE.

> When you add this to PA you get an immediate contradiction.

You CANNOT add (1) to PA in THAT form.
You basically have to migrate from 'A' to 'a' where 'a' is the godel-
numeral of an arbitrary statement and try something like
Apa[Ppa --> Ta]
where Ta is true if a is true. But by a much easier
diagonal theorem, T(.) cannot even exist.
The point is, you can't quantify over sentences of a first-
order language in the same first-order language, if it is this
rich. You have to settle for quantifying over their Godel-numbers and
that is NOT the same thing.

> (1) is equivalent to assuming the standard model.

(1) IS NOT one thing. (1) is at best AN AXIOM-SCHEMA (like
induction except that this is 0-ary instead of unary).
You have to add the whole infinity of instances of (1).

> What is wrong with this reasoning?

There is no such thing as "assuming" a model.
You instead allege that you are INTERPRETING
the axioms (along with everything else in their same
language) in the model. You can't use the object-
language of the theory to say this sort of thing.
You HAVE to use a meta-language.
Even when it is the same language. In that
case you have to take PAINS to keep them STRAIGHT.

> > Basically, by "we have derived G", you meant,
> > "we have used ZFC to prove the existence of a model
> > of PA in which G is true". The far more interesting question
> > is actually about the models where it is false.

Since you quoted that part but then COMPLETELY IGNORED
it, it had to be repeated. THIS is the part you have to address, if
you are going to keep thinking "we have derived G".
We have NOT derived G in PA, unless you include
"PA is consistent" as a hypothesis of G.
And EVEN then the encoding of "PA is consistent" is
not necessarily reasonably DESCRIBABLE as that in natural
language (since it gives the wrong answer in most models).


Newberry

unread,
Jul 27, 2007, 9:24:23 PM7/27/07
to
On Jul 27, 7:57 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

> Newberry says...
>
> >Here is the standard interpretation:
> >(Ex)(P(x, #("A")) --> A (1)
> >When you add this to PA you get an immediate contradiction. (1) is
> >equivalent to assuming the standard model. If (1) is not the case then
> >it leaves the non-standard models.
> >What is wrong with this reasoning?
>
> For one thing, your statement (1) doesn't say anything
> about the standard model. So stop saying that.

It says that there are no hyperinfinite numbers.
BTW, how would formalize the argument that leads to the conclusion
that "G is true in the standard model"?


Newberry

unread,
Jul 27, 2007, 9:41:22 PM7/27/07
to
On Jul 27, 7:57 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

OK, let's start with PA and let's introduce
(Ex)(P(x, #("G")) --> G (1)
as an assumption. Do we get a contradiction then i.e. do we get
~[(Ex)(P(x, #("G")) --> G]
by RAA?

Nam D. Nguyen

unread,
Jul 27, 2007, 11:06:12 PM7/27/07
to

Not so. "Truth" here as you emphasized is arithmetic
truth. But arithmetical truth or model truth must necessarily
be associated with a formula. (Can one state a truth without
a formula?). And once a truth can't escape its syntactical
embodiment (its formula), the entire model-provability of FOL
will come right at us immediately.

In other words, what we assume as "arithmetic" is equivalent
to the assumption that a certain arithmetical formal system
"Ar" is consistent. So if G(PA) is arithmetically true, then
the arithmetic formula F encoding G(PA) is arithmetically
provable, in "Ar".

herbzet

unread,
Jul 28, 2007, 1:06:33 AM7/28/07
to

george wrote:

> In this context it really would be smart to just STOP saying
> "true(period)",period, and start ALWAYS talking about truth
> IN A MODEL. Outside a model, what matters is what's provable,
> NOT what's true. Of course, under this paradigm, things that are
> provable are going to be in true in every model, so you might want
> to still call them true. That would be a mistake. It would be like
> calling
> a human being an animal. Yes, people are animals, and yes, theorems
> are true, but the point is, they are so MUCH MORE THAN JUST that.

I'm curious as to what sort of stuff you're thinking about in
this intriguing last remark.



> poopdeville wrote:
> >
> > 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 true but it hardly counts as a REinterpretation!
> Given that the completeness theorem was proved BEFORE the
> incompleteness theorem, the incompleteness theorem HAS ALWAYS
> meant this!

Yes, but ... you pointed out to me awhile back that the completeness
theorem was proved prior to the establishment of model theory as
a discipline. I've since read an english translation of the
original completeness theorem, and I don't recall much discussion
of models (although the theorem does rely heavily on previous results
by Skolem, some of which is, I think, now considered fundamental to
model theory). The heart of the original proof seems to be in
observing the relationship between first-order validities and
propositional tautologies, which seems to me to be a very good
thing to do.

I didn't really follow the proof all that well. I think a
nice dumbed-down cleaned-up version would be a nice thing
to have. I just discovered Wikipedia is working on one:

http://tinyurl.com/2b6ngc

--
hz

herbzet

unread,
Jul 28, 2007, 1:06:41 AM7/28/07
to

Keith Ramsay wrote:
>
> On Jul 26, 10:01 am, george <gree...@cs.unc.edu> wrote:
> |In this context it really would be smart to just STOP saying
> |"true(period)",period, and start ALWAYS talking about truth
> |IN A MODEL. Outside a model, what matters is what's provable,
> |NOT what's true. Of course, under this paradigm, things that are
> |provable are going to be in true in every model, so you might want
> |to still call them true. That would be a mistake. It would be like
> |calling
> |a human being an animal. Yes, people are animals, and yes, theorems
> |are true, but the point is, they are so MUCH MORE THAN JUST that.
>
> I wouldn't recommend this advice. I mean, if the
> original poster finds it helpful, by all means go
> ahead and think this way.
>
> It seems to be a common problem, however, to get
> stuck imagining that the concept of truth is
> dependent on the concept of "model". If one then
> tries to retrace one's steps, to work out a
> logical sequence of definitions of terms, one
> keeps getting stuck wondering how it's possible
> to specify a model while being unable to talk
> about truth of any kind (but only provability).

Kind of all going past me. Is (Ax)(Fx -> Gx) true
or false? Doesn't that depend on how we interpret
"F" and "G"?

[...]

> Goedel foresaw the troubles that could arise if he
> stated his incompleteness theorems or their proofs
> using such concepts as "truth". (He wrote a letter
> in which he mentioned this.) People could wonder
> whether there was some subtle problem with the
> way he was using it. So he carefully stated
> it all in "syntactic" terms, using concepts like
> formal provability in a system. He had no problem
> with speaking of the truth of the sentences,
> however, when he wasn't trying to occupy a
> defensive position, and it's only natural to think
> in such terms as one considers the theorems.

Good stuff, but doesn't it undermine your argument
somewhat? It seems that we don't need no stinkin'
"truth" concept to go a long way.

--
hz

LauLuna

unread,
Jul 28, 2007, 4:46:06 PM7/28/07
to
> We have derived G, which says about itself that it is not derivable.- Hide quoted text -

>
> - Show quoted text -

It seems that you are conflating derivation in the system with
deduction in general. What G says, under the standard interpretation,
is equivalent to the statement that G cannot be derived in the system;
G does not say G is absolutely unprovable.

Regards

Newberry

unread,
Jul 30, 2007, 10:20:59 AM7/30/07
to

Where exactly did I conflate them?

>
> Regards- Hide quoted text -

LauLuna

unread,
Jul 30, 2007, 10:31:37 AM7/30/07
to
On Jul 30, 4:20 pm, Newberry <newberr...@gmail.com> wrote:

> > It seems that you are conflating derivation in the system with
> > deduction in general. What G says, under the standard interpretation,
> > is equivalent to the statement that G cannot be derived in the system;
> > G does not say G is absolutely unprovable.
>
> Where exactly did I conflate them?

It seems you did when you wrote:

> Assume the standard model
> Then T(G)
> G [by T(G) <--> G]
> this leads to a contradiction

Regards

george

unread,
Jul 30, 2007, 11:28:26 AM7/30/07
to
> > Newberry says...
>
> > >Here is the standard interpretation:
> > >(Ex)(P(x, #("A")) --> A (1)
> > >When you add this to PA

You CANNOT add THIS to PA!
"This" is NOT IN THE LANGUAGE of PA!
"This" is not a wff of PA until AFTER *A* is!
And if A is just 1 wff then obviously you are not going to
get a contradiction from adding ONE new axiom.
You have to add ALL instances of this as SEPARATE axioms.

Moreover, under YOUR framework, we're going to have the
following much BIGGER problem: a lot of these are going
to be VACUOUSLY true because in PA, for a great many
things true in the standard model, there is NOT any proof of
them from PA. If A is G, for example, then
Ex[Pxg] --> G
is vacuously true. So while it might've helped to add
it classically, you yourself will wind up excluding it
right after you add it.

george

unread,
Jul 30, 2007, 11:31:02 AM7/30/07
to
On Jul 27, 9:41 pm, Newberry <newberr...@gmail.com> wrote:
> OK, let's start with PA and let's introduce
> (Ex)(P(x, #("G")) --> G (1)
> as an assumption.

You DON'T GET to introduce it as an ASSUMPTION.
If you mean as an AXIOM then SAY *Axiom*!

Before we do anything else with this new axiom,
the first thing we need to notice about it is that since
there is in fact NOT, under PA itself, any x such that
P(x,#"G"), this is going to be vacuously true, unless you
are amending your proof-predicate P to be the proof-
predicate for the new expanded theory instead of just for PA.

Daryl McCullough

unread,
Jul 30, 2007, 11:59:47 AM7/30/07
to
Newberry says...

>OK, let's start with PA and let's introduce
>(Ex)(P(x, #("G")) --> G (1)
>as an assumption. Do we get a contradiction then

Didn't I just go over that? No, you don't get
a contradiction. You get a new, consistent theory
with a new proof predicate P' and a new Godel statement
G'. This new theory can prove

(Ex)(P(x, #G)) --> G

but it cannot prove

(Ex)(P'(x, #G')) --> G'

george

unread,
Jul 30, 2007, 12:02:22 PM7/30/07
to
On Jul 27, 10:34 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

> Anyway, whatever you mean by "assume the standard model", the
> question is: what contradiction are you claiming to have discovered?

I think his problem is that he has not figured out yet that you could
ADD "PA is INconsistent" as an AXIOM and still NOT get a
contradiction (or even an inconsistency).

george

unread,
Jul 30, 2007, 12:05:46 PM7/30/07
to
On Jul 27, 11:05 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

> Keith Ramsay says...
>
> >It seems to be a common problem, however, to get
> >stuck imagining that the concept of truth is
> >dependent on the concept of "model".

Oh, shut up.
It seems to be a common problem to be wedded to the
existence of "the concept of truth".
I am not "imagining" that anything is "Dependent" on anything.
I am DEFINING everything.
Down to characters, anyway.

Daryl McCullough

unread,
Jul 30, 2007, 12:13:24 PM7/30/07
to
Newberry says...

>
>On Jul 27, 7:57 am, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:
>> Newberry says...
>>
>> >Here is the standard interpretation:
>> >(Ex)(P(x, #("A")) --> A (1)
>> >When you add this to PA you get an immediate contradiction. (1) is
>> >equivalent to assuming the standard model. If (1) is not the case then
>> >it leaves the non-standard models.
>> >What is wrong with this reasoning?
>>
>> For one thing, your statement (1) doesn't say anything
>> about the standard model. So stop saying that.
>
>It says that there are no hyperinfinite numbers.

No, it doesn't say that. Just as there are nonstandard
models of PA, there are also nonstandard models of (1).

>BTW, how would formalize the argument that leads to
>the conclusion that "G is true in the standard model"?

You show that if PA proves G, then PA is inconsistent.
Therefore, if PA is consistent, then PA does not prove
G. Then you show that PA is consistent (because all of
its axioms are true in the standard model). From this,
it follows that

PA does not prove G

Now, you show that there is a one-to-one correspondence
between proofs in PA and naturals in the standard model.
Then you show, using that correspondence, that G is true in the
standard model if and only if PA does not prove G.
Since you've already shown that PA does not prove G,
it follows that G is true in the standard model.

george

unread,
Jul 30, 2007, 12:16:12 PM7/30/07
to
On Jul 27, 3:42 am, Keith Ramsay <kram...@aol.com> wrote:
> It seems to be a common problem, however, to get
> stuck imagining that the concept of truth is
> dependent on the concept of "model".

Come on. THat is just plain ridiculous.
If you believe in the existence of models at all
then you believe that their raison d'etre is to TO TELL
everybody which statements are true and which aren't.
It is NOT like truth has been somehow "demoted" or diminished
by being associated with models. That's what models ARE FOR.

Outside a model one simply does not NEED mere truth. One needs MORE
than that.
Outside a model, one cares NOT so much WHETHER anything is
true, as, rather, HOW YOU KNOW. Outside a model one needs
JUSTIFICATION as OPPOSED to mere truth. Outside a model,
truth is dependent on the concept of PROOF!

> If one then
> tries to retrace one's steps, to work out a
> logical sequence of definitions of terms, one
> keeps getting stuck wondering how it's possible
> to specify a model while being unable to talk
> about truth of any kind (but only provability).

Well, obviously one has to stop somewhere.
It's called AN AXIOM, dumbass. One does not have to
call one's axioms "true" in order to insist that their proofs
are entitled to be of length 0,at least locally.


> One always knows what integers are long before one
> has any of these concepts of mathematical logic in
> mind.

That is just ridiculous. Natnums, maybe.
Integers, definitely not. In any case this question is
begged in our framework by the fact that the language is
constructed PRESUMING the natnums. That has implications
that aren't generally conceded their proper parentage.

> This isn't just a quirk of human psychology
> or of the educational system either; the concepts
> of mathematical logic are dependent on the concept
> of integer (or natural number at least),

Well, as I said, the concept of a first-order
language as we define it is of course (explicitly)
dependent on the natnums, but that threatens to moot
the whole enterprise if you take it seriously.

> or some
> equivalent stand-in, like the concept of a finite
> string of characters.

The operative word there is "finite'.

It turns out that that is not first-order definable.

But what that means is (arguably) that you have to
take 2nd-order logic rather than first as primary.
Then you CAN define natnums.

> Once one knows what natural numbers are, what
> addition and multiplication of them are, and so on,
> one can then understand what this kind of number-
> theoretic sentence being referred to means, and
> what it means for it to be true, without having
> any notion of what a "model" is.

Au contraire, to have understood those things is
to have understood the model already, or at least to
be thinking in terms of it.


> Later on, if one learns some mathematical logic,
> one can then realize that there is such a thing as
> the set of all natural numbers, which together
> with the basic relations and functions on it forms
> a model N of various theories like PA. One can then
> point out that what one understood by the truth of
> one of these sentences of number theory can be
> rephrased in terms of a model-relative concept of
> truth: the truth of that sentence "in N". But this
> is only a rephrasing. Unless one already knows
> what a natural number is, and what various
> sentences referring to natural numbers mean,
> there's no way that one could've gotten to that
> point.

How anyone got to anything is irrelevant.
For someone who started with "this is not just a quirk
of human psychology", you sure are brining in a lot of it
anyway, in a most irrelevant and unwelcome fashion.


> Goedel foresaw the troubles that could arise if he
> stated his incompleteness theorems or their proofs
> using such concepts as "truth". (He wrote a letter
> in which he mentioned this.) People could wonder
> whether there was some subtle problem with the
> way he was using it. So he carefully stated
> it all in "syntactic" terms, using concepts like
> formal provability in a system. He had no problem
> with speaking of the truth of the sentences,
> however, when he wasn't trying to occupy a
> defensive position, and it's only natural to think
> in such terms as one considers the theorems.

That is ridiculous. Especially if we are in the language
of PA, a lot of these first-order truths (all the unprovable
ones, all the consistency statements) simply ARE NOT true.
They are true in some models AND FALSE IN OTHERS.
The question is not what "the concept of truth" may or may
not be dependent on. The question IS why you think you
get to discriminate against all but one of the models.

MoeBlee

unread,
Jul 30, 2007, 1:02:54 PM7/30/07
to
On Jul 27, 6:24 pm, Newberry <newberr...@gmail.com> wrote:

> how would formalize the argument that leads to the conclusion
> that "G is true in the standard model"?

One obvious method (and I do not claim that there are not methods
using weaker systems) is just to pove it in a formal set theory. What
do you find in ordinary textbooks on mathematical logic that you can't
formalize in set theory?

MoeBlee


poopd...@gmail.com

unread,
Jul 30, 2007, 6:10:18 PM7/30/07
to
On Jul 27, 12:42 am, Keith Ramsay <kram...@aol.com> wrote:
> On Jul 26, 10:01 am, george <gree...@cs.unc.edu> wrote:
> |In this context it really would be smart to just STOP saying
> |"true(period)",period, and start ALWAYS talking about truth
> |IN A MODEL. Outside a model, what matters is what's provable,
> |NOT what's true. Of course, under this paradigm, things that are
> |provable are going to be in true in every model, so you might want
> |to still call them true. That would be a mistake. It would be like
> |calling
> |a human being an animal. Yes, people are animals, and yes, theorems
> |are true, but the point is, they are so MUCH MORE THAN JUST that.
>
> I wouldn't recommend this advice. I mean, if the
> original poster finds it helpful, by all means go
> ahead and think this way.
>
> It seems to be a common problem, however, to get
> stuck imagining that the concept of truth is
> dependent on the concept of "model". If one then
> tries to retrace one's steps, to work out a
> logical sequence of definitions of terms, one
> keeps getting stuck wondering how it's possible
> to specify a model while being unable to talk
> about truth of any kind (but only provability).

This is a metaphysical and epistemological issue. I am sympathetic to
model relativism, as it is a natural consequence of a solipsistic
epistemology. (Allow me to be flaky: we can think of sense
impressions as being analogous to syntactical forms. The "real world"
is one of many non-isomorphic "models" of the "theory" formed from
these syntactical forms. While everything in quotation marks must be
fleshed out, this is a tidy, unifying description of my
understanding.)

>
> One always knows what integers are long before one
> has any of these concepts of mathematical logic in
> mind. This isn't just a quirk of human psychology
> or of the educational system either; the concepts
> of mathematical logic are dependent on the concept
> of integer (or natural number at least), or some
> equivalent stand-in, like the concept of a finite
> string of characters.

I'm not so sure about this. In particular, I think it is not
logically necessary for the standard integers (or naturals) to be the
first structure we become familiar with.

This is tricky to phrase. The standard K-12 curriculum introduces
arithmetic. As a child struggles to understand it, he might try to
come up with a "mental model" of the numbers. But there is no a
priori reason why it must be isomorphic (in principle) to the standard
model. Indeed, it seems that many people have non-standard models of
arithmetic in mind, though without the tools of mathematical logic,
they are unable to understand the consequences. Notice how many
people claim that "infinity" is a number.

My objection comes from two aspects of Wittgensteinian thought: his
thoughts on "rule-following considerations" and the Private Language
Argument. At the very least, at the K12 level, the standard and non-
standard models are linguistically indistinguishable.

>
> Once one knows what natural numbers are, what
> addition and multiplication of them are, and so on,
> one can then understand what this kind of number-
> theoretic sentence being referred to means, and
> what it means for it to be true, without having
> any notion of what a "model" is.

I agree with this. Everyone who's been through the K-12 system will
know a natural when they see it. But it isn't clear that they can't
throw hyperfinite numbers into their conception of the numbers.

'cid 'ooh

Newberry

unread,
Aug 2, 2007, 10:22:41 AM8/2/07
to
On Jul 30, 9:13 am, stevendaryl3...@yahoo.com (Daryl McCullough)

wrote:
> Newberry says...
>
>
>
>
>
>
>
> >On Jul 27, 7:57 am, stevendaryl3...@yahoo.com (Daryl McCullough)
> >wrote:
> >> Newberry says...
>
> >> >Here is the standard interpretation:
> >> >(Ex)(P(x, #("A")) --> A (1)
> >> >When you add this to PA you get an immediate contradiction. (1) is
> >> >equivalent to assuming the standard model. If (1) is not the case then
> >> >it leaves the non-standard models.
> >> >What is wrong with this reasoning?
>
> >> For one thing, your statement (1) doesn't say anything
> >> about the standard model. So stop saying that.
>
> >It says that there are no hyperinfinite numbers.
>
> No, it doesn't say that. Just as there are nonstandard
> models of PA, there are also nonstandard models of (1)

What does a non-standard model of (1) look like?

>
> >BTW, how would formalize the argument that leads to
> >the conclusion that "G is true in the standard model"?
>
> You show that if PA proves G, then PA is inconsistent.
> Therefore, if PA is consistent, then PA does not prove
> G. Then you show that PA is consistent (because all of
> its axioms are true in the standard model). From this,
> it follows that
>
> PA does not prove G
>
> Now, you show that there is a one-to-one correspondence
> between proofs in PA and naturals in the standard model.
> Then you show, using that correspondence, that G is true in the
> standard model if and only if PA does not prove G.
> Since you've already shown that PA does not prove G,
> it follows that G is true in the standard model.
>
> --
> Daryl McCullough

> Ithaca, NY- Hide quoted text -

Newberry

unread,
Aug 2, 2007, 11:00:44 AM8/2/07
to
On Jul 30, 9:13 am, stevendaryl3...@yahoo.com (Daryl McCullough)

How do you express "in the standard model"?

george

unread,
Aug 2, 2007, 11:28:00 AM8/2/07
to
On Aug 2, 10:22 am, Newberry <newberr...@gmail.com> wrote:
> On Jul 30, 9:13 am, stevendaryl3...@yahoo.com (Daryl McCullough)
> > No, it doesn't say that. Just as there are nonstandard
> > models of PA, there are also nonstandard models of (1)
>
> What does a non-standard model of (1) look like?

Given that there is ("up to isomorphism") only 1 standard model,
there are (obviously) MANY different ways in which EVERY other
model might be non-standard. The first thing to note is that there
are by definition only countably many counting numbers, and since
we are in a countable first-order language, there is (downward LST)
always going to be a countable model if there is a model at all.
In other words, the most basic way in which a model could be non-
standard is by being bigger than countable. It is important to just
exclude all those from consideration immediately.
After that, among the countable models, there is a usual
way of getting a non-standard model. The standard model
is an initial subsequence of it.


In other words, there is NOT a nonstandard model of 1.
The 1 that occurs in non-standard models is THE SAME 1
that occurs in the standard model. The standard model is
a submodel of all the nonstandard ones.

Daryl McCullough

unread,
Aug 2, 2007, 1:00:33 PM8/2/07
to
Newberry says...

>On Jul 30, 9:13 am, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:

>> >> >Here is the standard interpretation:


>> >> >(Ex)(P(x, #("A")) --> A (1)
>>

>> >> For one thing, your statement (1) doesn't say anything
>> >> about the standard model. So stop saying that.
>>
>> >It says that there are no hyperinfinite numbers.
>>
>> No, it doesn't say that. Just as there are nonstandard
>> models of PA, there are also nonstandard models of (1)
>
>What does a non-standard model of (1) look like?

It has the finite naturals plus infinitely many
hyperfinite naturals, each of which is larger than
any finite natural.

Daryl McCullough

unread,
Aug 2, 2007, 1:03:44 PM8/2/07
to
Newberry says...

>
>On Jul 30, 9:13 am, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:

>> >BTW, how would formalize the argument that leads to


>> >the conclusion that "G is true in the standard model"?
>>
>> You show that if PA proves G, then PA is inconsistent.
>> Therefore, if PA is consistent, then PA does not prove
>> G. Then you show that PA is consistent (because all of
>> its axioms are true in the standard model). From this,
>> it follows that
>>
>> PA does not prove G
>>
>> Now, you show that there is a one-to-one correspondence
>> between proofs in PA and naturals in the standard model.
>> Then you show, using that correspondence, that G is true in the
>> standard model if and only if PA does not prove G.
>> Since you've already shown that PA does not prove G,
>> it follows that G is true in the standard model.
>
>How do you express "in the standard model"?

If you are working in ZFC, then you can take the
set of finite Von Neumann ordinals to be the standard
model.

george

unread,
Aug 2, 2007, 1:27:47 PM8/2/07
to
Newberry says...

> >> >> >Here is the standard interpretation:
> >> >> >(Ex)(P(x, #("A")) --> A (1)
>
> >> >> For one thing, your statement (1) doesn't say anything
> >> >> about the standard model. So stop saying that.
>
> >> >It says that there are no hyperinfinite numbers.

On Aug 2, 1:00 pm, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
> >> No, it doesn't say that. Just as there are nonstandard
> >> models of PA, there are also nonstandard models of (1)

That is misleading. (1) was intended to be ADDED AS AN AXIOM-
schema, TO PA. So ALL models of (1), standard OR nonstandard,
are models of PA, in *this* context. Although (1) is not one of them,
there are plenty of new axioms one could add to PA such that ALL
models of them would necessarily be nonstandard models of the ORIGINAL
PA. It is hopelessly ambiguous and confusing to ask for
"the standard model of PA+~Con(PA)", for example.
But it is just plain stupid to ask for "models of (1)".
(1) has a P(,) in it and that P doesn't even make sense outside
BUNCHES OF OTHER axioms that would enable the provability
predicate to be defined.


> >What does a non-standard model of (1) look like?
>
> It has the finite naturals plus infinitely many
> hyperfinite naturals, each of which is larger than
> any finite natural.

That is true of countable non-standard models of *just* PA, BY ITSELF,
generically, and is therefore completely useless as a reply about (1)
specifically. His obvious point is that
THE USUAL Godel-numbering of sentences and proofs will, along
with this schema, cause EVERY sentence, INCLUDING DENIALS
OF THEOREMS OF PA, and, thus, INCLUDING CONTRADICTIONS,
to have a proof. It would cause there not to exist a model at all.
You could not, for example, consistently apply this schema to
any nonstandard model of PA that you got by adding ~Con(PA) as an
axiom.

Daryl McCullough

unread,
Aug 2, 2007, 2:07:21 PM8/2/07
to
george says...

>
>Newberry says...
>> >> >> >Here is the standard interpretation:
>> >> >> >(Ex)(P(x, #("A")) --> A (1)
>>
>> >> >> For one thing, your statement (1) doesn't say anything
>> >> >> about the standard model. So stop saying that.
>>
>> >> >It says that there are no hyperinfinite numbers.
>
>On Aug 2, 1:00 pm, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
>> >> No, it doesn't say that. Just as there are nonstandard
>> >> models of PA, there are also nonstandard models of (1)
>
>That is misleading. (1) was intended to be ADDED AS AN AXIOM-
>schema, TO PA. So ALL models of (1), standard OR nonstandard,
>are models of PA, in *this* context. Although (1) is not one of them,
>there are plenty of new axioms one could add to PA such that ALL
>models of them would necessarily be nonstandard models of the ORIGINAL
>PA. It is hopelessly ambiguous and confusing to ask for
>"the standard model of PA+~Con(PA)", for example.
>But it is just plain stupid to ask for "models of (1)".
>(1) has a P(,) in it and that P doesn't even make sense outside
>BUNCHES OF OTHER axioms that would enable the provability
>predicate to be defined.

Well, I'm not sure what Newberry meant by P, but what
I meant was the proof predicate for PA, via some Godel
coding. In that case, every instance of the schema

(Ex)(P(x, #A)) --> A

is true in the standard model, so if you add all such
statements to PA, then the resulting theory still has
the standard model as a model.

>> >What does a non-standard model of (1) look like?
>>
>> It has the finite naturals plus infinitely many
>> hyperfinite naturals, each of which is larger than
>> any finite natural.
>
>That is true of countable non-standard models of *just* PA, BY ITSELF,
>generically, and is therefore completely useless as a reply about (1)
>specifically. His obvious point is that
>THE USUAL Godel-numbering of sentences and proofs will, along
>with this schema, cause EVERY sentence, INCLUDING DENIALS
>OF THEOREMS OF PA, and, thus, INCLUDING CONTRADICTIONS,
>to have a proof.

It depends on what the meaning of P is. If it is provability
in *PA*, then the resulting theory is still consistent, it still
is satisfied by the standard model, and it still has nonstandard
models.

>It would cause there not to exist a model at all.
>You could not, for example, consistently apply this schema to
>any nonstandard model of PA that you got by adding ~Con(PA) as an
>axiom.

That's true, but you don't have to add any *false* statements
to PA to get a nonstandard model for PA. It is possible to get
a nonstandard model of the *complete* theory of arithmetic.

Newberry

unread,
Aug 2, 2007, 8:46:20 PM8/2/07
to
On Aug 2, 10:00 am, stevendaryl3...@yahoo.com (Daryl McCullough)

Can #("A") ever produce a hyperfinite natural?

Daryl McCullough

unread,
Aug 2, 2007, 9:00:14 PM8/2/07
to
Newberry says...

>> >> >> >Here is the standard interpretation:
>> >> >> >(Ex)(P(x, #("A")) --> A (1)
>>
>> >> >> For one thing, your statement (1) doesn't say anything
>> >> >> about the standard model. So stop saying that.
>>
>> >> >It says that there are no hyperinfinite numbers.
>>
>> >> No, it doesn't say that. Just as there are nonstandard
>> >> models of PA, there are also nonstandard models of (1)
>>
>> >What does a non-standard model of (1) look like?
>>
>> It has the finite naturals plus infinitely many
>> hyperfinite naturals, each of which is larger than
>> any finite natural.
>
>Can #("A") ever produce a hyperfinite natural?

No, if A is a formula of PA, then #A is always
a standard natural. But what's the relevance of
that? My point is that (Ex)(P(x, #("A")) --> A
does not say "There are no hyperfinite numbers".

Newberry

unread,
Aug 2, 2007, 11:10:27 PM8/2/07
to

Well, it says that if a proof exists then it is a proof of a finite
number.

Daryl McCullough

unread,
Aug 3, 2007, 8:21:28 AM8/3/07
to
Newberry says...

>> >> >> >> >Here is the standard interpretation:
>> >> >> >> >(Ex)(P(x, #("A")) --> A (1)

>> >Can #("A") ever produce a hyperfinite natural?


>>
>> No, if A is a formula of PA, then #A is always
>> a standard natural. But what's the relevance of
>> that? My point is that (Ex)(P(x, #("A")) --> A
>> does not say "There are no hyperfinite numbers".
>
>Well, it says that if a proof exists then it is a proof of a finite
>number.

No, it doesn't say that.

I don't know where you are getting these interpretations,
because they bear very little relationship with the formula
you wrote down.

First: "There are no hyperfinite numbers". There is no way
to state this in first-order logic. The closest you can come
is the axiom schema of induction:

B(0) and Ax (B(x) -> B(x+1)) -> Ax B(x)

This *almost* says that there are no hyperfinite numbers,
because every nonstandard model of arithmetic violates
the second-order induction axiom. To see this, let S be
the set of standard naturals. Clearly, 0 is an element
of S, and if n is an element of S, then so is n+1. So
if we apply induction to the formula "x element of S"
we get "Ax x is an element of S", which says that all
numbers are standard. However, the first-order principle
of induction cannot say that induction holds for all
subsets of N, it can only say that induction holds for
all *definable* subsets of N. So in any nonstandard model,
it follows that the set of all standard elements is not
definable (by a formula).

Second, you want to say "Every proof is a proof of a finite
number". I assume you mean "Every proof is a proof of a finite
*formula*". You can't formalize that in first-order logic, either.

You can't add as an axiom "All y satisfying B(y) are finite", but
you can add the negation as an axiom schema. To say "No y satisfying B(y)
is finite", you can add the infinitely many axioms

not B(0)
not B(1)
not B(2)
...

From this infinite collection of axioms, it follows that if anything
satisfies B(x), then that object is *not* finite.

george

unread,
Aug 3, 2007, 9:28:52 AM8/3/07
to
> >Newberry says...
> >> >> >> >Here is the standard interpretation:
> >> >> >> >(Ex)(P(x, #("A")) --> A (1)

> >You could not, for example, consistently apply this schema to


> >any nonstandard model of PA that you got by adding ~Con(PA) as an
> >axiom.


On Aug 2, 2:07 pm, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
> That's true, but you don't have to add any *false* statements
> to PA to get a nonstandard model for PA. It is possible to get
> a nonstandard model of the *complete* theory of arithmetic.

Well, that is a pretty lame use of "non-standard", if it is going to
be
elementarily equivalent to the standard. I did make an effort at
PRIOR
exclusion of the models that were too big. There is a serious
linguistic
problem here in that the nonstandard models necessarily contain
elements
that necessarily HAVE NO NAMES in the standard language. You
arguably
DO have to add something like a false existential (or its
skolemization)
in order to be able to expand the language enough to be able to even
REFER to any of the nonstandard elements.

george

unread,
Aug 3, 2007, 9:44:07 AM8/3/07
to
> Newberry says...
> >> >> >> >Here is the standard interpretation:
> >> >> >> >(Ex)(P(x, #("A")) --> A (1)

He is surely basing this on Loeb's theorem.
If the above could somehow be made into an axiom
(as opposed to an axiom-schema), which would make it
provable, then contradictions would necessarily ensue.

He has sort of forgotten that formalizing
"PA is consistent" relativizes it in a very evil way; it is
consistent with PA for "PA is consistent" to be FALSE;
PA+"PA is inconsistent" IS consistent.


> >Can #("A") ever produce a hyperfinite natural?
>
> No, if A is a formula of PA, then #A is always
> a standard natural. But what's the relevance of
> that? My point is that (Ex)(P(x, #("A")) --> A
> does not say "There are no hyperfinite numbers".

Come on. It says that ~Con(PA) is false.
Even if it can't make the model standard, it at least narrows it
down to models of PA+Con(PA).
Your point that it could get the COMPLETE theory of true
arithmetic and STILL allow things nonstandard is one I
still don't appreciate.


george

unread,
Aug 3, 2007, 9:56:59 AM8/3/07
to

> Newberry says...

> >How do you express "in the standard model"?

On Aug 2, 1:03 pm, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
> If you are working in ZFC, then you can take the
> set of finite Von Neumann ordinals to be the standard
> model.

That is not the point; the point is that if you STAY in PA,
as OPPOSED to going up to something higher, then
YOU DON'T express "in the standard model". That NECESSARILY
MUST be expressed in a meta-language AND NOT in the object language.

There is, however, a sort of intermediate level of complexity
if you resort to axiom-schemata as opposed to axioms.
THen, "how far up" you are going DEPENDS on the kinds
of things that you allow to be substituted for the schematic/bound
variable[s]. THis is why he thought he could get there with an axiom-
schema.

Daryl McCullough

unread,
Aug 3, 2007, 9:57:01 AM8/3/07
to
george says...

>> >Can #("A") ever produce a hyperfinite natural?
>>
>> No, if A is a formula of PA, then #A is always
>> a standard natural. But what's the relevance of
>> that? My point is that (Ex)(P(x, #("A")) --> A
>> does not say "There are no hyperfinite numbers".
>
>Come on. It says that ~Con(PA) is false.
>Even if it can't make the model standard, it at least narrows it
>down to models of PA+Con(PA).

My point is just that "it can't make the model standard".

>Your point that it could get the COMPLETE theory of true
>arithmetic and STILL allow things nonstandard is one I
>still don't appreciate.

The key here is that completeness is with respect to a
particular *language*. If the language is the language
of PA, then let T_true be the theory of true arithmetic,
which is the set of formulas of PA that are true in the
standard model of PA. This theory is necessarily complete,
but it has nonstandard models. To see this, get a new
theory T' with a new constant symbol a and with infinitely many
axioms of the form

a > 0
a > 1
...

(for each numeral n, there is a corresponding axiom
a > n)

This new theory is consistent, but it is not satisfied
by the standard model. So let M be a model of this new
theory. Then since T_true is a subtheory of T', M is
also a model of T_true. So M is a nonstandard model of
the complete theory of arithmetic.

Daryl McCullough

unread,
Aug 3, 2007, 10:09:57 AM8/3/07
to
george says...

>On Aug 2, 2:07 pm, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
> > That's true, but you don't have to add any *false* statements
>> to PA to get a nonstandard model for PA. It is possible to get
>> a nonstandard model of the *complete* theory of arithmetic.
>
>Well, that is a pretty lame use of "non-standard", if it is going to
>be elementarily equivalent to the standard.

Well, the truth is sometimes lame, I guess. The usual meaning of
"nonstandard model of arithmetic" is a model that is not isomorphic
to the standard model.

>I did make an effort at PRIOR exclusion of the models that were too big.
>There is a serious linguistic problem here in that the nonstandard
>models necessarily contain elements that necessarily HAVE NO NAMES
>in the standard language. You arguably DO have to add something like
>a false existential (or its skolemization)
>in order to be able to expand the language enough to be able to even
>REFER to any of the nonstandard elements.

That's all true, but it is still the case that there exist nonstandard
models of the complete theory of arithmetic.

george

unread,
Aug 3, 2007, 1:54:15 PM8/3/07
to
On Aug 3, 9:57 am, stevendaryl3...@yahoo.com (Daryl McCullough) wrote:
> The key here is that completeness is with respect to a
> particular *language*.

THis point I DO appreciate. I basically raised it myself on the other
subthread.

> If the language is the language of PA,

Then it does not contain the new constant 'a' that you are introducing
below,
which makes this whole explanation a failure.

then let T_true be the theory of true arithmetic,
> which is the set of formulas of PA that are true in the
> standard model of PA. This theory is necessarily complete,
> but it has nonstandard models. To see this, get a new
> theory T' with a new constant symbol a and with infinitely many
> axioms of the form
>
> a > 0
> a > 1
> ...
>
> (for each numeral n, there is a corresponding axiom
> a > n)
>
> This new theory is consistent, but it is not satisfied
> by the standard model. So let M be a model of this new
> theory. Then since T_true is a subtheory of T', M is
> also a model of T_true.

NOT necessarily.
For sufficiently traditonal values of "subtheory", perhaps.
But this is sort of like the ZFC-vs.category-theory definition of
"domain" and "range" and "total" and "onto".
In ZFC, there is no such thing as a function that is partial
or that is not surjective. The domain and range of the function
are defined by the function ITSELF. From the perspective of
category theory or an other where the domain and range are
defined independently and in advance, it is possible for a function
to have a ZFC-range that is a proper subset of the INTENDED range
or a domain that is a proper subset of the INTENDED domain.

My point here is simply that a model of a theory typically involves
assigning interpretations to the linguistic components OF THE
PRIORLY-selected language that that theory is in.
No model of T' (with an 'a' on its "left" side) is therefore a
model (super, sub, or otherwise) of any model of ANY OTHER
language.

george

unread,
Aug 3, 2007, 2:28:51 PM8/3/07
to
On Aug 3, 10:09 am, stevendaryl3...@yahoo.com (Daryl McCullough)
wrote:

> That's all true, but it is still the case that there exist nonstandard
> models of the complete theory of arithmetic.

Your previous attempt to just add a bigger constant and call it 'a',
as in
a>0
a>1
a>2
etc.
is
humble.

The usual thing to add is ~Con(PA), e.g.,
Ex[P(x,#"0=1")]. If you skolemize THAT and call THAT x "a", then you
get all of
a>0
a>1
a>2,
etc. AS CONSEQUENCES of that. Of course, the question of what "P"
means after you
add a new axiom is problematic. But not completely. The new proof-
predicate and the old
one are going to agree on all finite arguments. Indeed, if you don't
skolemize, they are
going to agree on all terms you can form in the language, all of which
are necessarily
finite. So the question of expansion of the LANGUAGE to refer to the
supernatural
numbers IS RELEVANT.

The real question here is, how efficiently does "iterating consistency
assertions"
force us toward "standardness"?
I mean,
PA+Con(PA)
is "closer" to the standard in that models of PA+~Con(PA), ALL of
which are non-standard, have
now been excluded from the picture. But obviously, ^THAT^ has non-
standard models via
PA + Con(PA) + ~(Con(PA+Con(PA)).
Clearly, though, some successoring is going on here.
We can iterate this ordinally-TRANS-finitely.
The question is, HOW MANY, ordinally, times, do you have
to iterate the successor-operation of "add the consistency-statement
as a new axiom" --
PA
PA+Con(PA)
PA+Con(PA)+Con(PA+Con(PA))
PA+Con(PA)+Con(PA+Con(PA))+Con(PA+Con(PA)+Con(PA+Con(PA)))...
ad naus.,
or should that be ad inf.?
to get to "true" arithmetic?
Well, of COURSE it should be ad inf.,
but my question is,
WHICH inf.?
Is there some known countable limit ordinal up-to-which doing-this
will guarantee that you finally include all of true 1st-order
arithmetic?
My point being that if there were, then, obviously, all you would need
to
do to get a non-standard model of true arithmetic would then be, at
the successor
to THAT ordinal, add
~Con(PA+...).

Daryl McCullough

unread,
Aug 3, 2007, 2:59:18 PM8/3/07
to
george says...

>
>On Aug 3, 10:09 am, stevendaryl3...@yahoo.com (Daryl McCullough)
>wrote:
>> That's all true, but it is still the case that there exist nonstandard
>> models of the complete theory of arithmetic.
>
>Your previous attempt to just add a bigger constant and call it 'a',
>as in
>a>0
>a>1
>a>2
>etc.
>is
>humble.
>
>The usual thing to add is ~Con(PA),

But if you start with the complete theory of arithmetic,
then it already has Con(PA) as a theorem.

This subject has been investigated by (I think) Sol Feferman.
What I believe he proved is that for every statement of arithmetic,
it is possible to prove it by iterating such consistency statements.

Here's a link to his paper on the subject. It looks like you have
to pay to get the full paper, but you can look at the first page
for free

http://links.jstor.org/sici?sici=0022-4812%28196209%2927%3A3%3C259%3ATRPOAT%3E2.0.CO%3B2-R&size=LARGE&origin=JSTOR-enlargePage


>Is there some known countable limit ordinal up-to-which doing-this
>will guarantee that you finally include all of true 1st-order
>arithmetic?

I'm pretty sure that the magic ordinal is omega_1-CK, which is the
first nonrecursive ordinal.


>My point being that if there were, then, obviously, all you would need
>to
>do to get a non-standard model of true arithmetic would then be, at
>the successor
>to THAT ordinal, add
>~Con(PA+...).

--
Daryl McCullough
Ithaca, NY

Daryl McCullough

unread,
Aug 3, 2007, 3:49:05 PM8/3/07