# Re: Fitch's paradox and OWA

From: Barb Knox <Barbara_at_LivingHistory.co.uk>
Date: Fri, 01 Jan 2010 10:08:23 +1300

In article
<a3f061ed-3838-4be9-b73a-836141dc640f_at_u7g2000yqm.googlegroups.com>,  Marshall <marshall.spight_at_gmail.com> wrote:

> On Dec 30, 8:16 pm, Barb Knox <s..._at_sig.below> wrote:
> >  Marshall <marshall.spi..._at_gmail.com> wrote:
> >
> > By the nature of the construction of predicate logic, every arithmetic
> > formula must be either true or false in the standard model of the
> > natural numbers.
> >
> > But, we have no satisfactory way to fully characterise that standard
> > model!  We all think we know what the natural numbers are, but Goedel
> > showed that there is no first-order way to define them, and I don't know
> > of *any* purely formal (i.e., syntactic) way to do do.
>
> I was more under the impression that Goedel showed there
> was no complete finite theory of them, rather than no
> way to define them. Are you saying those are equivalent?

Yes, in this context. Since we are finite beings we need to use finite systems.

> > (The usual ways
> > to define them are not fully syntactic, but rely on "the full semantics"
> > of 2nd-order logic, or "a standard model" of set theory, both of which
> > are more complicated than just relying on "the Standard Model" of
> > arithmetic in the first place.)
>
> Here's a possible definition:
>
> nat := 0 | succ nat
>
> x + 0 = x
> x + succ y = succ x+y
>
> x * 0 = 0
> x * succ y = x + (x * y)
>
> Is there some way this definition is not fully syntactic?
> It uses no quantifying over predicates, so it can't be
> using second order logic.

> It certainly seems to me that the above is fully syntactic,
> and is a complete definition of basic arithmetic. Are
> there statements that are true of this definition that
> can't be captured by any finite theory? Sure there
> are, but that has nothing to do with whether it's
> a proper syntactic definition. To say it's not a syntactic
> definition, you have to point out something about
> it that's not syntactic, or not correct as a model
> of the naturals.

This is the usual first-order initial-algebra definition, and with the addition of "succ x = succ y -> x=y" and an induction schema gives first-order Peano Arithmetic. First-order logic is indeed formal (i.e., syntactic) in that all inferencing activities consist of finite operations on finite strings. But, via Goedel and others, the Peano axioms do NOT fully characterise the natural numbers N. N is indeed a model (the Standard Model) which satisfies these axioms, but there are also *non-standard models* which satisfy these axioms -- these models contain infinite elements in addition to the usual naturals.

You can get some of the flavour of non-standard models by considering the following non-standard model for just succ, where every element has a unique successor and predecessor:

0, 1, 2, ... ..., w-2, w-1, w, w+1, w+2, ...

So, we can readily produce purely formal systems that are satisfied by N, but all of them (as far as I know) are also satisfied by other, non-standard, models. Try as we might, those pesky infinite non-standard integers keep cropping up. That is the sense in which I mean that we apparently can not formally fully characterise N.

(Note that we similarly cannot formally define "finite", so the dodge of saying something like "the naturals are defined by the Peano axioms plus the restriction that everything is finite" can not be expressed purely formally.)

> > > If it's actually the case (that every statement of basic arithmetic
> > > is either true or false) then it's not a shortcoming to say so.
> > > On the contrary, that would be a virtue.
> >
> > Speaking philosophically (since I'm posting from sci.philoisophy.tech),
> > entities which in some sense exist but are thoroughly inaccessible seem
> > to be of little value.  This applies to the truth values of any
> > statements which can never be known to be true or false.
>
> While I have sympathy for that position, I don't think it's
> tenable in the long run. Or anyway, it's not tenable to go
> from "of little value" to suggesting that we should, say,
> not attend to the real numbers because of the existence
> of uncomputable numbers,

I am not an expert in that field, but I believe that almost all of real analysis can be reconstructed using just computable numbers, e.g. the work of Bishop.

> or suggest that statements
> that are undecidable one way or the other are somehow
> neither true nor false. What they are is undecidable.

They are true or false in any *particular* model. Since we apparently cannot formally pin down arithmetic to have just one particular model (the Standard one) then there will always be some arithmetic statements, the undecidable ones, which are true in some models and false in others. Thus it is unreasonable to say that an undecidable statement is simply "true" or "false" -- we need to specify a particular model, almost always the Standard one, which we can not fully characterise formally.

This doesn't prevent doing interesting number theory, but it is at least somewhat bothersome from a foundational perspective. Received on Thu Dec 31 2009 - 22:08:23 CET

Original text of this message