Talk:Peano axioms/Archive 1

Please add new topics to the end of the page.

Older posts

I deleted this:

This was a proof using logic alone, but of course infinite. It gives an algorithm for simplifying a :possible proof of contradiction by a series of simple transformations, until it becomes very short. :To see that it becomes very short we need transfinite induction. Gentzen's proof has been :humorously called "assuming the dubious to prove the obvious".

since (a) it was not a proof using 'infinite logic' but a straightforward mathematical proof; (b) the procedure makes the proofs longer, not shorter; (c) whoever called the proof that doesn't understand it.

---

Someone was getting confused about Peano's axioms vs. first order Peano Arithmetic. I(different I than the above: this I's a PhD student who's area is models of PA) changed

Although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization.

to

Dedekind proved, in his 1888 book Was sind und was sollen die Zahlen, that any model of the second order Peano axioms is isomorphic to the natural numbers. On the other hand, the last axiom listed above, the mathematical induction axiom, is not itself expressible in the first order language of arithmetic.

If one replaces the last axiom with the schema:

1. If P(0) is true and for all n P(x) implies P(x+1)

for each first order property P(x) (an infinite number of axioms) then although natural numbers satisfy these axioms, there are other, nonstandard models of arbitrary large cardinality - by the Compactness theorem the existence of infinite natural numbers cannot be excluded in any axiomatization; by the Lowenheim-Skolem theorem there exist models of all cardinalities.

Thanks for the clear-up and help! Revolver 07:04, 30 Sep 2004 (UTC)

---

Presumably "For all n, P(x) implies P(x+1)" really means:

"For all x, P(x) implies P(x + 1)."

Michael Hardy 00:07, 25 Oct 2003 (UTC)

Peano system

Why is the name Peano system used in the article? The criteria are due to Dedekind. ---- Charles Stewart 11:30, 29 Sep 2004 (UTC)

This is the term that I seem to remember hearing/reading most often. You can certainly check the literature and see if you find Dedekind system to be more standard. Whether the criteria are due to Dedekind is worth noting for historical reasons but not really related to current standard usage — we all know how many things in math aren't named after the proper person. Revolver 07:04, 30 Sep 2004 (UTC)

No doubt you are right, I think that the structure is normally given an ad hoc name such as "numerical structure"; I don't think there is a standard name for it, but I think the name Peano system is doubly unfortunate, because, besides the historical point, one usually uses the term "structure" to talk about these things and not system.

FWIW, Google tells me that "Peano system" is not much used, 180 hits, the most common being for a Perl ORB on freshmeat, and most of the relevant links referrring to Peano'x axioms and not the number structure. ---- Charles Stewart 12:14, 30 Sep 2004 (UTC)

I can do a check of several set theory books over the next week or so, just as an initial look. I'm not sure how to interpret the google quote you give (180 hits) without comparison to an alternative (how many hits does "___" get?) Revolver 08:25, 1 Oct 2004 (UTC)

"Numerical structure" got about 1600 hits, but the very FIRST hit is some religious numerology babble, so I take these google hit-numbers with a few grains of salt. Revolver 08:31, 1 Oct 2004 (UTC)

`Meaning' of 180 hits: the structure is obviously very fundamental, so 180 hits is low, especially since Wikipedia has quite a few syndicates. By comparison "Hopf algebra" gets 12700 hits, despite being an obviously less fundamental concept. I think there is no standard way of talking about this structure; given this, it looks to me that we should call the structure something non-misleading. Dedekind structure, gets only one relevant hit, but it is for exactly this item, and it is what I would call it. ---- Charles Stewart 12:09, 1 Oct 2004 (UTC)

It may be more "fundamental" in the foundational sense, but my guess is that more people study Hopf algebras than Dedekind structures. There does seem to be no standard terminology. I googled "Peano structure" and found at least half a dozen relevant hits. I admit I have no real knowledge on the history of the situation. Since both "Dedekind" and "Peano" seem to be in use, why not use "Dedekind-Peano structure" (which I have seen), and make some comments about other terminology? Note: I have also seen "Dedekind-Peano axioms" for "Peano axioms". Revolver 01:30, 3 Oct 2004 (UTC)

I'd guess the structure of positive integers sees as much study and more application than Hopf Algebras; however everytime you see a Hopf algebra applied you will see the fact advertised using the standard name. I have no objection to Dedekind-Peano structure. I think the name Dedekind-Peano axioms is generally used for second-order Peano arithmetic, but saying "second-order Peano axioms" I think is more suggestive. Should we add a terminology section? ---- Charles Stewart 09:27, 3 Oct 2004 (UTC)

first order?

The article claims that "Peano axioms (or Peano postulates) are a set of first-order axioms" can someone please tell how is it possible to postulate: "if a property is possessed by 0 and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers." in a first order logic? i think you will have two use second order for that claim.(it seems to quantify over properties(definition of second order logic))

(post moved to bottom of page)

As an axiom, induction is second-order. However it can be formulated in a first-order manner by adding not a single axiom, but an axiom schema with infinitely many instances. Since the schema defines a(primitive) recursive set, from the point of view of proof theory, it is acceptable. ---- Charles Stewart 07:46, 26 Jan 2005 (UTC)

I see, for example we can get around induction by using no-cycles claim, (no size 1 cycle, no size 2 cycle..etc up to infinity).Still, In this case the text of the artcile should be changed to this particular(infinitary) axiomatization, because as it stands it is confusing as to why is it first-order.--Hq3473 08:02, 26 Jan 2005 (UTC)

If I'm not mistakened, forbidding cycles is both too weak and can't be captured by a first-order axiomatisation. I agree the text needs (much) improvement, but I guess the issue won't be clear until we give an actual axiomatisation in a Hilbert-style proof theory - then we can talk about this point properly. I'll put it on my overburdened to do list ---- Charles Stewart 10:22, 26 Jan 2005 (UTC)

i see, cycles will not rule out higher orders. Any way, can you maybe give me link or a refernce to riogorous first order peano axiomatization? i want to see how is the deduction overcome.--Hq3473 21:44, 26 Jan 2005 (UTC)

Discardng induction?

I asked a vague question at Talk:Preintuitionism ... are there any examples of systems in which the first four axioms are kept, the fifth (induction) is intentionally broken or discarded, and yet are not finite, and somehow manage to achieve some sort of "infinity"? (By "intentionally broken", I mean, are there different set of axioms, in which induction is a theorem that may be proven false?) (By requiring "infinity", I want to exclude "obvious" systems like finite groups and fields (and finite state machines?) which seem like they might not need induction as an axiom). linas 05:50, 7 September 2005 (UTC)

Yes, this is an active area of study. If you limit the induction schema to formulas all of whose quantifiers are bounded, you get a theory called IΔ₀, which is insufficient to prove that the exponential function (the function that sends n to 2ⁿ) is total. (No warranties on the exact definition of IΔ₀). There's a whole hierarchy of theories weaker than PA. --Trovatore 20:49, 16 October 2005 (UTC)

Looks like I didn't read your question carefully enough; this isn't what you were after. But it still might be of interest to you.... --Trovatore 23:24, 16 October 2005 (UTC)

definition of PA

The most glaring deficiency of this article in its current form is that it does not give any explicit definition of first-order PA, which makes the introduction to the article seem almost a misrepresentation. PA is alluded to in the third paragraph of the "Metamathematical discussion" section (a section which has serious POV flaws as well), but an actual precise characterization of PA is never given. It should be mentioned that the language needs to include multiplication--this isn't necessary for the second-order Peano axioms, but it is for first-order PA; otherwise you get something much weaker, and I believe actually decidable. --Trovatore 20:56, 16 October 2005 (UTC)