Re: Arithmetic with (only) exponentiation

On Mon, 01 May 2006 22:57:44 GMT, Nam Nguyen wrote:

Nam Nguyen wrote:

Nam Nguyen wrote:


Let M be the structure N and L be (0,S,+,*,<). Both ExAy(!(y = x))

Sorry for the typo, the formula should have been ExAy(!(x = Sy)).

and its negation can be true over N. So the "theory of M" (the set
of true formulae) would be inconsistent because these 2 true formulae
are in it? If we'dlike to make the "theory of M" consistent, which
of the formulae would you think we throw away and which one we
would keep - or *axiomatize*?

<Note>
For some reason I couldn't see your reply in my newsreader, so I
got your response from the internet.
</Note>

Bertie Reed wrote:

>Well, to specify a structure, one must say how one interprets each
>of the symbols in the language.
>
>I was assumeing the usual interpretation for S in M (indeed the usual
>interpretation for each of the symbols). Thus S names the function N->N
>x|->x+1
>
>Then the sentence above is satisfied by M, and it's negation is not.

I'm sorry that won't do it. Your ultimate question is whether or not
a certain *formal system* T is incomplete. So "the usual
interpretation" is not formal enough to determine that question.

I think we are talking at cross purposes:

First a couple of definitions I have been using:

I am using the word "interpretation" in the following, model theoretic,
way: An L-structure is any set S together with an "interpretation" of each
function, constant or relation symbol in L.

As an example, an interretation of a "binary function symbol" is a binary
function ie. any function f:S^2 -> S.

Fact: Given an L-structure M and a sentence s, either M satisfies s or M
satisfies not(s) [and not both!]

The theory of M is the defined to be the set of _all_ sentences satisfied
by M. Thus, by the above it is complete. The question I answer is whether
it is decidable (the completion of a recursive set of axioms).

What I am doing:
I am taking the model M to be the pair
(set of naturals, the function (x,y)|->x^y)
I then show that any recursive subtheory of the theory of M axioms is
incomplete.
You point out the fact that we don't know which sentences are in T. True,
but it is not necessary for this argument. Further if we did know, then it
would show that the result was wrong (well, given a bitmore anyway).

What I am not doing is the following:
Exhibiting a certain set of axioms A (which are true for naturals with exp)
so that any recursive set of axioms containing A is not complete.

I realize that an answer from your (and I think georges) point of view, i.e
from below, would be satisfying and instructing. However the approach I
use, from above, does answer the origional question (or at least my
interpretation of it).


Let me
give an example. Shoenfield defined a system TN (he called in "N")
that "formalizes a classical system for the natural numbers."; this
system is over the language L(0,S,+,*,<) and has 9 axioms: but no axiom
from the Induction Schema. In some chapters later, over the same
language he specified the normal PA system which is just TN above plus
the Induction Schema (minus TN's 9th axiom). The long and short of it is
that N is a model of both TN and PA, and yet there exists a formula F
that is provable from PA and yet undecidable in TN.

Thus, in my language TN is a subset of PA which is a subset of the theory
of N.

So given the
structure N, with the "usual arithmetic interpretation", we couldn't
determine if the "theory of N" is PA or TN; then how could it make sense
to question about the potential incompleteness of the "theory of N"?

I don't think I used this term, I am sorry if I did. It is, as you point
out nonsence. The theory of N is, by definition, complete.

(I meant there is at least one formula from the Schema that we'd have
no clue whether or not it should be interpreted as true or false!)

I think you're probably overlooking a subtlety here: axioms are
independent provability-wise, but *not* formulation-wise. When we
state "arithmetic without multiplication" that makes sense, without
much qualification that needs to go into the statement: Addition
axioms in both TN and PA *depend only* on Successor axioms, so
Multiplication is "expendable"! But for the other way around, you
can not simply throw away Addition and expect that out of N we could
have a Multiplication interpretation *without Multiplication axioms".
(Interpretation after all *needs axioms* to decide whether or not a
formula is true, or false!).
It goes without saying that Exponentiation
is also in the same boat with Multiplication!

I don't really understand that. I don't think I am sure what you an
interpretation is for you.


Bertie
.

Relevant Pages

  • Re: Skolems Paradox and why is math the way it is?
    ... > This is not a job the axioms were ever meant to do. ... other person's interpretation require a winning strategy, no more, no ... I'm pretty sure than any model of set theory is intuitively ... figuring out how I tell what is real in mathematics. ...
    (sci.math)
  • Re: Technique and Foundation
    ... axioms always carry any interpretation as far as the proof allows. ... It is co-referent. ... Also please explain which sign it is that makes the goedel sentence, referencing and self referencing. ...
    (sci.logic)
  • Re: Technique and Foundation
    ... axioms always carry any interpretation as far as the proof allows. ... Negation, for example, only works with a particular class of objects. ... Frege also declared that functions could not be described because they were fundamentals, ...
    (sci.logic)
  • Re: Goedel - interesting problem?
    ... Saying that a statement is "true in that set of axioms" is merely evidence ... The language of arithmetic, for example, is an interpreted language---by ... One could take the constant "0" to refer to Paul ... English interpretation), because John Lennon was, in fact, born in ...
    (sci.logic)
  • Re: countability of reals
    ... >>as one takes increasingly long lists of integers, the ratio ... >>don't seem to be accepting your interpretation. ... > Any kind of OBJECTIVE statement about naturals in progression is about the natural ordering. ... Its based on an infinite set of partial halt functions. ...
    (sci.math)