Talk:Second-order arithmetic

From Wikipedia, the free encyclopedia

Contents 1 Criticizing the move from reverse mathematics 2 Changes as of 2006-3-20 3 Planned style changes 4 Induction axiom

[edit] Criticizing the move from reverse mathematics

(Preliminary remark: I wrote essentially all of the reverse mathematics article, including the section that was moved to form this new article.) While I agree that it is, at least in principle, a very good idea to split the article (something I should have done from the start), I think the way it was done is hasty at best, and a lot of things now don't make much sense. To start with, second order arithmetic is not a number of systems, it is one system, “classical analysis”, here described as “the full system”, and the others, which reverse mathematics studies, are merely subsystems of second-order arithmetic. The content is the same, but the emphasis is entirely different. So the comments about “the base system” and “stronger systems” don't make much sense here: they should have remained in the article on reverse mathematics or, better, be rewritten in a more sensible way to account for the new setting. Conversely, the article on reverse mathematics should be updated to at least summarize what is said here: for example, recursive comprehension should be defined there, not here (though it may be mentioned in both), since one may know all there is to know about second-order arithmetic without knowing what “recursive comprehension” means. And so on: I don't have the time to make the changes myself, unfortunately, so I hope the initiator of the split can do it. --Gro-Tsen 00:32, 7 February 2006 (UTC)

[edit] Changes as of 2006-3-20

Please excuse any mistakes I have made in formatting, as I am new to wikipedia.

I have thoroughly edited reverse mathematics and second-order arithmetic. I am very familiar with reverse math; I received my PhD with Simpson as my advisor. I tried to keep as much as I could, while removing things that were either false or disagreed with the terminology in the literature.

One key distinction, unspoken but observed in the literature:

1. Arithmetical comprehension is an axiom scheme, but it doesn't include the basic axioms or any induction
2. ACA_0 is arithmetical comprehension, arithmetical induction, and the base axioms
3. ACA is ACA_0 plus full induction (this was studied in the 1960s and 1970s until they realized ACA_0 is more amenable). Some authors, however, use ACA as an abbreviation for arithmetical comprehension axiom, meaning the arithemtical comprehension scheme.

You can say that a theorem is equivalent to ACA_0 over RCA_0, or to arithmetical comprehension over RCA_0, because these are equivalent statements. But it doesn't match the terminology in the literature to say that RCA_0 is the same as recursive comprehension or that the subsystem ACA_0 is called arithmetical comprehension

A more subtle point is that it is going out of fashion to use the word recursive in mathematical logic; the word computable is usually used except in fixed abbreviations like r.e., DNR, or RCA. In particular, almost the entire community of computability theorists now use the term computable instead of recursive. Simpson is hold-out.

--CMummert 02:08, 20 March 2006 (UTC)

That's all right, I wrote the article initially, but mathematical logic is not at all my domain (I'm in algebraic geometry and number theory), so in case you disagree with what I wrote you are obviously the one who's right, and I'm sorry if I made any bad mistakes (I just glanced over the diff, so I don't know). I also plead guilty for the metonymy of using the term "Weak König's Lemma" to designate the whole system KWL₀ (rather than just the axiom) and so on: basically that's because I'm of the old-fashioned school which believes that any interesting mathematical theorem should be expressible in English without any formalism whatsoever (i.e., no "kay-double-u-ell-zero"); if that's not the case in reverse mathematics, it is most unfortunate, but there's nothing I (or even you) can do about it. :-) (But if there is some standard English phrase which can be used rather than "kay-double-u-ell-zero" to refer to the system, please mention it. Also, I would be mildly of the opinion of letting the English names stand for the section titles, unless you think even that is abhorrent.) --Gro-Tsen 22:04, 20 March 2006 (UTC)

There weren't any really false statements. Simpson's book has a narrow focus and so doesn't mention things like second-order semantics that are important to the general study of second-order arithemtic but not to reverse math. In my changes to the second-order arithmetic page, I tried to give it a broader viewpoint than just reverse math. Over on the reverse math page, I have now changed the section titles back to English, which is indeed more attractive. I also added a paragraph explaining the difference between WKL_0 and weak Konig's lemma. The English-only phrase for WKL_0 is “The subsystem (of second-order arithmetic) consisting of Delta^0_1 comprehension, Sigma^0_1 induction, the base axioms, and weak Konig's lemma” which is why everybody uses the abbreviation. I would appreciate any changes you would like to make to make the exposition clearer for nonlogicans; my motivation in editing the pages at all is to have some sort of accessible introduction online. When a nonlogican hears the term reverse mathematics and looks it up on wikipedia, I would like the page to be informative and understandable. --CMummert 02:55, 21 March 2006 (UTC)

[edit] Planned style changes

I plan to make the following changes to improve the exposition:

• Consistently refer to first order variables as number variables and second order variables as set variables.
• Remove first-person phrasing (we define ...) to make the tone encyclopedic.

Are there any serious objections to this? CMummert 16:00, 28 June 2006 (UTC)

[edit] Induction axiom

Looks like the first arrow in the induction axiom should be "and". (I don't have time to play with the mathematical wikinotation now, so I'm leaving it alone.) HFuruseth 19:37, 16 November 2006 (UTC)

Well, it is a tautology that , and means in some circles, so the axioms were stated correctly. The version with only avoids some parentheses. But I changed the article to the more usual version that uses for clarity. CMummert 20:00, 16 November 2006 (UTC)

Oooh, I see. I've been reading as shorthand for , resulting in quite a bit of head-scratching. (In some other math articles too, I think. Will check.) HFuruseth 16:40, 20 November 2006 (UTC)