Re: Fitch's paradox and OWA

On Dec 31, 1:08 pm, Barb Knox <Barb..._at_LivingHistory.co.uk> wrote:

I have no disagreement with the point about finiteness, but I don't see how that point leads to saying that a theory is the same thing as a definition. That is rather tantamount to saying that theories are all there are, and that's just not true. There are things such as computational models, for examples. It seems entirely appropriate to me to use a computational model as the definition of something, which is why I gave a computational model of the naturals as a definition.

Perhaps worse, if it's not possible to have a definition of anything, then I don't see how you can have any theories, either. Theory of what? If you have no definition, I don't see how you can even claim to have an object under discussion.

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

Small points:

First of all, I claim "succ x = succ y -> x=y" is necessarily the case via the definition of =.

Secondly, I claim we don't need to explicitly add any induction schema, because induction on the naturals in this case is merely a special case of structural induction, which is itself merely a special case of case analysis on the constructors for nat, and case analysis is always available, as it were.

These are perhaps just quibbles.

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

I can see how your above set could be a model for PA, but I don't see how it's supposed to be something that conforms to the definition I gave.

For one thing, addition on the naturals is supposed to be total. What is the result of "2 + w" under my definition of +? It does not terminate, because you have introduced elements with infinite descending deconstruction. That my addition operator is total over (nat, nat) is provable; if there is some value for which it is not total that value must therefor not belong to nat.

For another thing, my definition doesn't have any "w" in it, so you don't get to insert them in to the process. We are supposed to be being syntactical here; recall that you wanted to keep out second order logic and set theory, so no "w".

Perhaps most importantly, I defined "nat" as those things that are constructed via one of the two specified constructors. Your w-elements are not so constructed, so they cannot meet the definition I gave.

I have noticed in the past that logicians and set theorists don't necessarily buy the idea that the universe consists only of those objects that can be constructed using explicitly defined construction rules. I am rather inclined to say "tough," but perhaps I'll get better results if I just say that's fine, but anything that isn't so constructed isn't a natural, by definition.

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

It seems to me that syntax is necessarily finite, but again this is perhaps just a quibble.

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

I'd accept "almost all" but note that "almost all" isn't the same as "all". For example, the order relation on computable numbers is not itself computable, sadly. Also isn't it the case that the least-upper-bound property is lost if we limit ourselves to computables?

Regardless, the bigger issue, it seems to me, is that any such system is going be be distinctly more complex than the reals, and that complexity has a nontrivial cost.

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

Even if we can pin it down, we still have statements that we don't know if they are true or false. It might require an infinite amount of computation to decide. Or just more than we will ever have.

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

Sure, but whatever those statements do evaluate to, we can narrow it down to one of two possibilities, even if we can't narrow it any further.

> This doesn't prevent doing interesting number theory, but it is at least
> somewhat bothersome from a foundational perspective.

I agree that it is bothersome!

Marshall Received on Fri Jan 01 2010 - 00:27:01 CET