Re: Arithmetic with (only) exponentiation

On 27 Apr 2006 12:38:17 -0700, george wrote:

Bertie Reed wrote:
No, it was a clarification of an earlier post that you did not seem to
understand. I showed that from the function x^y, one can define 0 and 1.

We know.
Nobody, especially not me, seemed not to understand that.

I also noted that this was true for the function 2^x.

You can't just NOTE that. You have to GET *2* FROM
somewhere! 2 does NOT come built in to the langauge!

This refuted the implicit assertion in

"No, no, no!...How are you even getting "2" into this vocabulary if you
don't have a successor function AS WELL as an exponentiation function?"

It does NOT refute that. You still can't answer the question!
The TITLE of the thread is "arithmetic swith (only) exponentiation"!

x |-> 2^x is an exponential function.

Thus we are considering the theory of N together with (only) this function.

If you have 2 then you do NOT have ONLY exponentiation!

I am not sure what you mean by "have" in this context. The point being made
was that in any first order context where one can define (over the
emptyset) exponentiation on N, one can show that addition and
multiplication are also definable (over the emptyset) on N, and thus each
natural number is definable (over the emptyset).

You either have a successor function (so 2 can be s(1)) or you
define addition (so 2 can be 1+1), which would require you to define
addition WITHOUT USING 2 (otherwise your definition of 2 as 1+1
IS CIRCULAR).

You seem to be confused. We started with x |-> 2^x (or if you prefer x^y)
as the basic function. We did not start with 2.

The original treatment spoke in terms of definig 2^(whatever),
not of x^y.

No, it spoke, perfectly correctly, about multiplication and arithmetic
being definable from 2^x.

That is NOT "perfectly correct" IF you are trying to
do "Arithmetic with (only) exponentiation". YOU ALSO NEED
*2*, IF you are going to do it that way.

What do you mean by "need *2*? For what?

You defined
0 and 1 without using 2, with ONLY exponentiation.


Correct.

The actual question here is, simply, what axioms do you need,
if you are going to do this?

This is your question, perhaps. Do what?

Define arithmetic using ONLY exponentiation, THAT'S what.


I refer you to my previous post.


The original question was

"Does anyone know the status of arithmetic with just
exponentiation?

In that case it was incoherent.
Arithmetic by definition COMES with 0, +, *, and either
s(.) or 1.

Do you mean: Arithmetic is the first order structure of the natural numbers
with symbols for the above functions?

This is clearly not the definition that the Colin, A N Niel, quazi or I
were using. I refer you to the OP:

"Pressburger showed that arithmetic with just addition (i.e., the
first-order theory where addition is the only function) is a decidable
theory. Skolem showed that arithmetic with just multiplication is a
decidable theory."

He refers to "arithmetic with just addition (i.e., the
first-order theory where addition is the only function) and then ask about
"arithmetic with just exponentiation".

I think it's clear what he means.

It also, by definition, comes with either = or <
(< is preferable, since it avoids the question of whether
the underlying logic is FOL with equality xor FOL without
equality).

My guess is that it would not turn out to be decidable,
but I was hoping this matter might be settled and someone could clue me
in."

Whilst this is not entirely clear, the meaning that I (and A N Niel and
quazi) understood was the following:

I retract that, it was entirely clear from the outset.

"Is the theory of N with a function for exponentiation (either binary or
unary) decidable?"

Your claiming that three people understood something that is
meaningless is ridiculous. There Is No Such Thing As
"the theory of N with" any function.

I see: I am argueing with a crank.

And exponentiation ISN'T
unary. IT'S BINARY.

I handled the binary case in my first post. It should be clear that both
are biinterpretable once one shows that both define multiplication.

If you want to have unary exponentiation
THEN YOU HAVE TO HAVE A CONSTANT AS A BASE
for that unary exponentiation and THAT CONSTANT ISN'T
definable by exponentiation from ITSELF.

I am afraid I showed that it was. See my first post.

The answer was given by A N Niel,

It was not.
The title of the thread is about what you acn do
with ONLY exponentiation. And "The theory of N"
is meaningless.
A theory is a set of sentences.

consistent

Before you can have sentences, you have to have
a language. The prior QUESTION here is WHAT
language are we using?

I made that clear and explicit in my first post what language I was using.

Your responce was
"This whole approach is insufferably model-theoretic."

If it doesn't have any
constants and it only has exponentiation, then
it does NOT have 2.

Yes, the language does not contain a constant symbol that refers to 2. In
fact it contains no constant symbol. 2 is never the less definable over the
emptyset.

If it has 2 then it has more
than just exponentiation.


and clarified by me because you did not
seem to understand it.

The secondary question is, can you do it without = ?

Do what?

Define a theory of arithmetic.


Well, on any totally ordered set, = is definable from the order. One could
certainly set out 1st order Peano (or Presburger) Arithmetic without the
symbol =. I am not sure why one would want to however.

PA is doable without = at all, let alone without = in the logic.

I am afraid you have completely lost me.

PA is, among other things, a formal theory of arithmetic.
It has axiomatizations. The good ones do not have any
occurrences of =. Should you ever Truly Need to use =
in PA, a=b is definable as ~(a<b v b<a).

I agree: one can rephrase the axoims of without refering to =.

PA has a fairly big signature (a constant 0, a unary successor
function, binary addition and multiplication, and a binary
predicate <). And that's the small version (bigger ones
have 1 and = ). The question was, could you formalize
a theory at least as strong as PA using a smaller signature,
e.g. one that just had one binary function (exponentiation).
If so, WHAT DO THE AXIOMS look like?

Ahh, I see what you are geting at.

The answer is no. With no relations in the language, one can not form any
formulas.

Bertie
.

Relevant Pages

  • Re: Arithmetic with (only) exponentiation
    ... "Is the theory of N with a function for exponentiation (either binary or ... (Or am I missing something? ... Well, given any language L and L-structure M, the "theory of M" is the set ... of true formulae) would be inconsistent because these 2 true formulae ...
    (sci.logic)
  • Re: Arithmetic with (only) exponentiation
    ... "Is the theory of N with a function for exponentiation (either binary or ... Well, given any language L and L-structure M, the "theory of M" is the set ... This was for the binary function situation. ... The unary situation is not ...
    (sci.logic)
  • Re: Arithmetic with (only) exponentiation
    ... quazi) understood was the following: ... "Is the theory of N with a function for exponentiation (either binary or ... Well, given any language L and L-structure M, the "theory of M" is the set ... of true formulae) would be inconsistent because these 2 true formulae ...
    (sci.logic)
  • Re: Arithmetic with (only) exponentiation
    ... "Is the theory of N with a function for exponentiation (either ... Well, given any language L and L-structure M, the "theory of M" is the ... of true formulae) would be inconsistent because these 2 true formulae ... I was assumeing the usual interpretation for S in M (indeed the usual ...
    (sci.logic)