Re: primitive recursive: obsolete?

MoeBlee wrote:
On May 17, 9:10 am, "Nam D. Nguyen" <namducngu...@xxxxxxx> wrote:

Then re-read what he wrote which is quoted above, the one that has
"Solely on basis of ... repeatedly applying the "add one"-operation ...".
If that doesn't sound like Presburger artihmetic to you then that's
your own reading, not mine!

No, Presburger arithmetic has the two axioms for addition:

x+0=x
x+(Sy)=S(x+y).

As far as "add one" is concerned Sn = n + 1, so how does that *refute*
my saying that his *informal* statement sound like Presburger arithmetic?

That is not what Aatu mentioned.

Typically, an informal statement doesn't have to refer to everything!
Would this be difficult to comprehend?

My point in questioning his statement is we've taken for granted that
the concept of the naturals is an intuitive concept, not a formalized
one. Because if it were, he could have easily stated the axioms for
the naturals, instead of saying it in a half-intuitive-half-formalized
way, as he did in the quoted statement.

The "add one" operation is the
successor operation. The "add one" operation in this sense is
characteristic of Peano systems,

You're making the same kind of mistake: if Presburger artihmetic alone
can't characterize PA, neither can the successor function!

from which we THEN go on to prove the
existence of certain functions such as addition (i.e., addition of two
natural numbers not JUST adding 1 to any given number), as Presburger
arithmetic axiomatizes.

As far as a formal system is concerned, "THEN go on to" simply means
we have to add more axioms. And as far as we don't mention any axioms
about multiplication, then our system couldn't characterize the
naturals. Which is my whole point here, and which is very simple to
understand!

I am asking what do you mean by 'arithmetic' as a THEORY. I.e., what
particular theory do you refer to when you say 'arithmetic' in the
phrase 'strong as arithmetic'.

Canonically it's an extension of Q, though in the thread
"Pseudo Negation - A Formal Definition of "As Strong as Arithmetic"
I did have a refined definition.

If you feel generous, you might mention that defintion here and
restate whatever point you were trying to make but now based on that
definiiton.

I'll make a compromise: I'll only point it out it was posted on May 3rd;
you just have to go and read it (it isn't too long). And I don't have
any point here with the refined definition, other than answering your
own question about what I meant by "arithmetic" or "strong as arithmetic"!

There is the theory of
all true sentences of arithmetic in the language of PA.

Are you sure you'd know exactly what that theory is? For example,
what are some examples of its *non-trivial* theorems? [Hint: one
can actually define "true" sentences even for an inconsistent theory!]

I spent about two straight weeks explaining this to you already. It's
found in just about any textbook on mathematical logic.
Yeah you did. But I also spend 2-3 weeks in a row giving out my
counter-explanation to you.

There is no "counterexample" to the fact that in ordinary mathematical
logic we define the set of sentences true in the standard model of PA
and that that set is a consistent, negation complete theory, though
not a recursively axiomatizable one.

How would *you* know "that set" is consistent when you couldn't tell an example
of its non-trivial theorems?

Notwithstanding all that, I asked a very simple question: "what are some
examples of its *non-trivial* theorems?". Can't you just simply answer
that question, without going back to what was debated in the past?

What is the point of the question? Whether I can name "non-trivial
theorems" or not has no bearing on the fact that what I said is
correct: we define the set of sentences true in the standard model of
PA and that set is a consistent, negation complete theory, though not
a recursively axiomatizable one.

The point of the question is you *need* axioms and rule of inference
to *make sense of out _any_ truth definitions, including the standard
definition of true sentences*.

There are always more than one way of defining true sentences. Consequently,
there's no such a thing as a *genuinely* true sentence that everyone must
accept as true. It's all just a matter of defining - of mapping a sentence
to a binary value. The real question is how well such a mapping would rhyme
with the theorems of an axiom set (a formal system). In other words, to the
extend that you take one definition (of true sentence) and *assume* such is
a model of PA, you still don't know if such "model" would guarantee there's
not theorems of the form (F /\ ~F), because theorems are solely determined
by axioms and rules of inference, not by true sentences (or definition of)!

And you'd have to define "non-trivial" in this context, if you want a
formal answer. Is "1+1=2" trivial?

You seriously don't understand what a non-trivial theorem is? It seems
just a basic "abc" in getting to know formalism! Any rate, it's just
a theorem which is not an axiom! For one example in PA, SS0 = S0 + S0
is a non-trivial theorem. For another in PA, ExAy (x < (y+1)) is non-trivial.

Meanwhile, if you gave an example
of what you consider to be a non-trivial theorem (of some theory) in
the language of PA, then perhaps I can tell you whether it's also a
member of the set of sentences true in the standard model for the
language of PA.

Let cGC df= 'There are infinite counter examples of GC', then ~GC is
a non-trivial theorem of {cGC}. Perhaps you could tell us, as you seemed
eager to do so, if ~GC is "a member of the set of sentences true in the
standard model for the language of PA"?

It is the
theory that is the set of sentences true in the standard model of the
language of PA. It is not a decidable theory and not even recursively
axiomatizable. It is a consistent theory though, as I explained to you
several times several months ago.
And I've explained to you in many post of the past that one could
*only assume it's consistent*!

You're ill-informed. By definition, it can't be an inconsistent
theory. There is no such thing as both a sentence P and ~P being true
in any model.

But how do you know that formal system (that theory) is consistent so
that it would have "any model", to begin with? You're being circular
but don't realize it. Just defining a set of true sentences and *label*
it a model of a theory (i.e. a formal system) doesn't necessarily make
it a model of a theory.


Eiher GC or ~GC is provable in that theory, though it is not a recursively
axiomatized theory.
You wouldn't know "that theory" enough to assert this kind of provability
"fact"!
I don't know what you're trying to say.

What I said is simple: a theory is a formal system which must have *known*
axioms.

That's a another definition of 'theory', not the defintion of 'theory'
that I've been using. If you insist on using your defintion rather
than mine, then okay, I'll use 'set_closed_under_entailment' instead.
Then where I've used 'theory', just substitute
'set_closed_under_entailment', or better yet, just recognize, as
reasonable people do, that different authors use different definitions
and that in this context, by 'theory' I mean 'set of sentences closed
under entailment'.

All of this from you still doesn't make it wrong that a theory is still
a formal system, an axiom set, where it theorems must follow rules of inference,
and where if it's syntactically inconsistent, no amount of true-sentence
definitions could generate a model for it!


IF you don't *know* enough about these axioms you wouldn't necessarily
know if a particular F, say, GC or ~GC, is provable!

What are you so excited about? It's already been granted from the
start of this discussion that we do not know whether GC is a member of
ThN (where 'ThN' stands for the set of sentences true in the standard
model for the language of PA).

First of all, this seems to contradict to what you've stated above:

"if you gave an example...[of] a non-trivial theorem (of some theory)
in the language of PA, then perhaps I can tell you whether it's also a
member of the set of sentences true in the standard model for the
language of PA."

Secondly, you seem to have a problem in listening to what your opponent
said: I talked about "axioms" and "provable" which are syntactical and
you *kept* going back and forth about "true sentences", as if you ignored
what I had just said! No wondering why our conversation is going no
where!

What I got "excited" about is basically there's a loophole in the foundation
of FOL: on the one hand we must depend on finite syntactical to protect
our reasoning from inconsistent conclusions, but on the other hand we went
ahead and made *intuitive assumption* about the naturals number, at the
expense of rigidity of syntactical proofs, through rules of inference!

Also from the beginning it it
recognized that the notion of 'provability' as being recursive whether
a string of formulas is a proof does not apply to ThN since it is not
recursively axiomatizable. But, if GC is decided in, say, ZFC, then,
even though we might not know which way the decision goes, still, we
know that either GC or ~GC is a member of ThN.

How do you know if ZFC is not *syntactically inconsistent*? Anyone can
always say "If 'this' then 'that'" but that doesn't take away the fact we
sometimes would like the reasoning framework to determine whether or
not it is "this", or "that" that we could *infer for certain*! In other
words, what good is a mathematical logic framework if all we could assert
is "If 'this' then 'that'"? At least if such framework itself provides
a way to acknowledge such shortcoming, then chances are it'd be more
trustworthy.


And if GC is not
decided in ZFC, then there is something of a "puzzling" situation,
which I've discussed before and even as part of my reason for admiring
Hilbert's finitistic distinction between the contentual and the ideal.

Sorry, this Hilbert's "finitistic distinction..." sounds a bit philosophical
to me and I have no comment on this.

What I said is correct: The
set of sentences true in the standard model of the language of PA is
negation complete but not a recursively axiomatizable theory.
Is that "theory" is Q then?

Of course not!!! That you even ask that question, after I explained
over and over and over for about a month, shows that you weren't even
reading what I wrote back then.

If not, then I don't know what you meant by
"that theory", despite the fact that we have a canonical definition of
the set of true sentences.

You don't know, because you're an arrogant snot who doesn't LISTEN to
what other people say: I explained over and over and over, for about a
MONTH, that "that theory" is EXACTLY the set of sentences true in the
standard model for the language of PA. This is common mathematical
logic. Look at, e.g., Enderton's logic book in which he makes this
central to his treatment of the subject of incompleteness.

I'm not an arrogant "snot"; you're just a modern time Inquisitor, that's all.

You just didn't understand my questions (or mis-interpreted the questions) but
went ahead answered them! I most likely would ask questions about provability
from axioms which are *syntactical* in nature, and you have only one-mantra
kind of answer "... true sentences ...", which is intuitive in nature.

(It's hard to converse when you asked a guy something specifically about
an apple and he kept answering specially about an orange, wouldn't you think so?)

Meanwhile, if GC is true then there is a
recursively axiomatized theory in which GC is provable and true and if
GC is false then there is a recursively axiomatized theory in which
~GC is provable and true. We can devise such theories in two seconds,
just by taking either GC or ~GC as axioms.
You had "taking either GC or ~GC as axioms" but "axioms" is plural!
Thanks for the proof reading.
And I don't think you meant {GC} and {~GC} since they're not considered
as "arithmetic theories"! So, I don't really understand what you said above!
I mean take GC or ~GC as an axiom, but not both.
So what are the other axioms?

I said EXPLICITLY, over and over and over, for about a month, that I
am using 'theory' in the sense NOT of a set of axioms and its
consequences, but rather in the sense of a set of sentences closed
under entailment. ThN is not recursively axiomatizable. However,
trivially, one axiomatization of ThN, which is NOT recursive, is ThN
itself.

If your sense of 'theory' is "NOT of a set of axioms", then what in the name
of reasoning in FOL is your sense of *rules of inference*?

And - one more time - what are some examples
of *non-trivial* theorems? How would you know that syntactically GC /\ ~GC
is not a theorem?

How many times am I going to explain this while you DON'T even listen?
No contradiction is a theorem of ThN since no contradiction is true in
any model whatsoever.

Since to you a "theory" is not a formal systems where axioms and rules of
inference play the key role in reasoning, I very much am not interested
in what's being said here.


This challenges the notion that the set of FOL rules of inference is adequate
enough to make it possible to solve all the provability problems.
I don't know what you mean by "all the provability problems".
It should be simple: the collection of "all the provability problems"
would include the question about GC's provability in, say, Q!

Okay. But then I dont know what exact claim in mathematical logic you
read as "the set of FOL rules of inference is adequate enough to make
it possible to solve all the provability problems." Please cite for me
the exact claim, as found in ordinary mathematical logic or as posted
by someone, that needs to be "challenged" in this regard. For example,
it's well recognized that Q is incomplete and that there is no
decision procedure that determines whether GC is a theorem of Q. So I
don't know what exactly you wish to "challenge".

The shortcoming of FOL is that it doesn't even formally admit this shortcoming.
I didn't know that it is even within the scope of deductive calculus
to "admit" its own "shortcomings".
I hope that you do know that by now!

So, your mathematical point is...?

To make it simple for you to comprehend, my point is there's no way
you could know if Q is consistent. The best you could do is assuming
it be consistent, by assuming that the "naturals" be one of its model!



MoeBlee





.

Relevant Pages

  • Re: Question about first-order arithmetic
    ... a properly axiomatized formal system whose axioms can use the language ... of first-order arithmetic such that its theorems are precisely the ... function symbols, S a unary function symbol, 0 a constant and epsilon a ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... from ZF + other axioms. ... are all theorems of pure ZF or ZFC. ... language, in this case, of course, the language of set theory. ...
    (sci.logic)
  • Re: Question about first-order arithmetic
    ... of first-order arithmetic such that its theorems are precisely the ... If we ask, as seems to have been lugita15's intention, whether there exists a finite number of schemata in the language of arithmetic axiomatizing the set of arithmetical consequences of ZFC, the question is an interesting one, and the solution far from obvious. ... theoretical formalization in the language of the assertion that the conjunction of the usual axioms of second order Peano arithmetic logically imply Q, and + and * are taken to be binary function symbols, S a unary function symbol, 0 a constant and epsilon a binary relation. ...
    (sci.logic)
  • Re: Is peano arithmetic inconsistent under the intended interpretation?
    ... We're talking about the language of first order PA, ... we know what the standard model is. ... where F= that theory whose axioms consist of all the ... formula as a well formed formula of the language of PA extended by ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... are all theorems of pure ZF or ZFC. ... first-order language, in this case, of course, the language of set ... there is one set theory text whose proofs are all expressed ... carried out using only the ZF axioms. ...
    (sci.logic)