Wikipedia:Reference desk/Archives/Mathematics/2012 October 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 5

Mathematics degrees

Is there any stand alone degree of Algebra, Analysis, Combinatoric, Geometry? In the same way that you can study computational science independently. — Preceding unsigned comment added by 83.41.157.164 (talk) 09:29, 5 October 2012 (UTC)

Well, there are certainly lots of postgraduate degrees covering specific branches of mathematics. Googling gave me this course for a "Bachelor of Arts in Mathematical Sciences - Combinatorics and Optimization" at the University of Montana (Googling for "degree geometry" turns out not to be very helpful). You might need to be a bit more specific about what kind of degrees you are interested in, and which countries. 130.88.99.231 (talk) 17:54, 5 October 2012 (UTC)

Combinatorics and Optimization is an emphasis at Montana, not a stand-alone degree. From their website: The department offers a Bachelor's Degree with emphases in Pure Math, Applied Mathematics, Mathematics Education, Combinatorics and Optimization, Combined Mathematical Sciences-Computer Science and Statistics.' [my bolding]. I strongly doubt that any American undergraduate department offers such a specialized degree as Combinatorics and Optimization, Algebra, etc.--to fill up the required in-major credit hours would require courses that get so deep that they would not be undergraduate level. But some do offer separate degrees in Pure Mathematics and in Applied Mathematics and in Statistics. Duoduoduo (talk) 18:14, 5 October 2012 (UTC)

The University of Waterloo offers several specialized undergraduate majors in mathematics, including Combinatorics and Optimization. See [1]. —Bkell (talk) 21:02, 5 October 2012 (UTC)

Incompleteness theorem

Once when I was feeling brave and tried to understand Godel's incompleteness theorem, I thought the essential result was that it is possible to formulate syntactically valid statements (in some applicable system) that can be neither proved nor disproved. However, in an article I'm currently reading, it says that the theorem "revealed that mathematics must contain true but unprovable propositions", and again in the intro to the Wikipedia article "there will always be statements about the natural numbers that are true, but that are unprovable within the system".

How does the notion of "true" get involved in this? How do we know that the statements that cannot be proved or disproved are "true"? Why is the theorem described in those terms rather than in my original terms? 86.176.210.107 (talk) 20:28, 5 October 2012 (UTC)

The crucial point is "... within the system". Thus, we may be able to prove the truth of a statement that is expressible in a given formal system (under some semantic model), but is not a theorem of the system. Meaning that using the axioms and rules of the system, the statement is not provable, but reasoning outside the rules of the system is not constrained in the same way. Any formal system of symbols and rules has no inherent meaning; it requires a semantic model to match an interpretation (and hence what a string expresses as we would understand it). — Quondum 21:08, 5 October 2012 (UTC)

I see, thanks. Is there any reason why it is important to emphasise the existence of true statements that are not provably true (within some system), rather than any other combination, such as false statements not provably false, or statements that we can never know the truth of (in any way) not provable one way or the other (in some particular system)? 86.176.210.107 (talk) 21:17, 5 October 2012 (UTC)

I would phrase things somewhat differently from the way Quondam did. The point, which is often obscured in popular treatments, is that the Goedel sentence of a formal theory is an assertion about a very clear collection of objects, the natural numbers. If you agree that (i) there are such things as natural numbers and (ii) it is well-specified what they are, then you must agree that the Goedel sentence of (say) Peano arithmetic is either really true or really false.

The Goedel sentence of a consistent theory T is necessarily true. This is because what the sentence asserts is of the form "for every natural number n, n is not the Goedel number of a proof of (something complicated that we don't need to worry about the details of here) within T ", and if that were false, then there would be such a natural number n, and it would follow, by the arguments of the proof of the incompleteness theorem, that T was inconsistent.

The reason it is important to emphasize the truth of the Goedel sentence of a consistent theory is that, otherwise, it is easy to make the mistake that many popularizers make, and suppose that the "choice" between adding the Goedel sentence as an axiom, and adding its negation as an axiom, is a neutral one. It is not neutral; it is very clear — the Goedel sentence of a consistent theory is true. --Trovatore (talk) 21:27, 5 October 2012 (UTC)

(i) When you say "the Goedel sentence", you mean a constructed statement that is not provable or disprovable within T, right? (ii) How do we know that things are really "true" about the natural numbers without invoking some other system that itself suffers from the flaw (or incompleteness) that Godel exposed? 81.159.104.36 (talk) 22:55, 5 October 2012 (UTC)

For your (i), yes, but something a bit more specific than that. I mean specifically a sentence that encodes "I am not provable in T".

For your (ii), it is easy to show, assuming very little, that if T is consistent, then the Goedel sentence of T (call it G_T) is true. Now, T itself does not prove that G_T is true, but that is only because T also does not prove that T is consistent (this is the second incompleteness theorem, and in fact that's basically how it's proved).

So as to how we know that G_T is true — well, we know that only to the extent that we know that T is consistent, which is a whole 'nother discussion. Depending on what T is, perhaps we don't know that T is consistent. But that doesn't change the fact that the Goedel sentence of any consistent theory is true. --Trovatore (talk) 01:22, 6 October 2012 (UTC)

To the OP: I agree with the other people here, that it's possible to prove - outside the system - that the Goedel sentence is true. However, I think it's redundant to indicate that the Goedel sentence is true, i.e. Goedel's full discovery is not fully reflected by the fact that the Goedel sentence - not provable within the system - is true; Goedel's discovery (or rather Goedel-Rosser discovery) is fully reflected by the fact that the Goedel's sentence - not provable within the system - is also not disprovable within the system. It's really a stronger claim, because: on one hand, this version of Goedel's discovery entails also that there is a sentence (whether the Goedel sentence or its negation) - which is not provable within the system - and is true (assuming every sentence about natural numbers must be either true or false); On the other hand, the other version of Goedel's discovery - which only claims that the Geodel sentence (not provable within the system) is true - is a weaker version (of Goedel's discovery), because it may make us suspect that the (true) Goedel sentence may still be disproved within the consistent system, that may disprove true sentences and still stay consistent. HOOTmag (talk) 19:07, 6 October 2012 (UTC)

You're right, there is a small extra piece that is not captured by saying that the sentence is true. It is nevertheless important to emphasize that the sentence is true (given that the theory being studied is consistent). This is at least arguably really the main point, because the pre-Goedel incarnation of formalism hoped to be able to capture truth by formal provability, and this is the hope that was dashed. Moreover, without saying that loudly and explicitly, readers tend to come away with the impression that the sentence is "neither true nor false" or some such, an impression that many popularizers are guilty of spreading.

Certainly the point that the Goedel–Rosser sentence of a consistent theory can neither be proved nor refuted by the theory even if the theory proves false things, is also worth saying. But to me it's a little bit of a secondary point. --Trovatore (talk) 19:19, 6 October 2012 (UTC)

So we almost agree, and may disagree - a little bit. I agree that - from a historical point of view (as well as from an "anti-populistic" point of view) - Goedel's version for his discovery is more important than Rosser's one, because Goedel's version directly-refutes what was hoped (and what is still being claimed by many popularizers). However, in my opinion, from a purely mathematical point of view - Rosser's version is more important, because it's mathematically stronger - and not less aesthetical !!! it's not easy at all to conclude - Rosser's aesthetical version - from Goedel's version, whereas it's quite easy to conclude Goedel's version from Rosser's version - once we assume an (almost) obviuos (or definitely-obvious) assumption: "every sentence about natural numbers must be either true or false" (as opposed to what those popularizers think). Btw, also you indicated this assumption, by your stating: "If you agree that (i) there are such things as natural numbers and (ii) it is well-specified what they are, then you must agree that the Goedel sentence of (say) Peano arithmetic is either really true or really false". HOOTmag (talk) 20:27, 6 October 2012 (UTC)

Hmm — I guess I think the most important mathematical consequence of the theorems is the hierarchy of consistency strength, for the most part of theories that have wellfounded models (for example, various large cardinal assumptions). From this perspective, the non-arithmetically-sound theories for which Rosser closes a loophole are not all that interesting in the first place. From the perspective of a pure proof theorist, I can see your position might make sense. --Trovatore (talk) 20:34, 6 October 2012 (UTC)

If "the non-arithmetically-sound theories for which Rosser closes a loophole" hadn't been "all that interesting in the first place" (as you state), then also the inconsistent systems wouldn't have been all that interesting in the first place; However, Goedel did find it important to emphasize that the theories he was talking about - were the consistent ones - in order to exclude the inconsisent ones, although the inconsistent theories are not more interesting than the theories you claim to be "uninteresting", i.e. the consistent theories which prove false sentences too. Hence: since Goedel did find it important - to indicate that the theories he was talking about - were consistent, then he must also have found it important - to indicate that the consistent theories he was talking about - proved true sentences only. All of this shows, that Rosser's version is also important for "practical" purposes, because Goedel's version must assume that the Peano system - if consistent - proves true sentences only, whereas Rosser's version does not have to assume that. Note that this assumption is not more trivial/obvious than the assumption that the Peano system is consistent. HOOTmag (talk) 21:42, 6 October 2012 (UTC)

(OP) Thanks. I cannot pretend to understand all of that, but I appreciate your help. Moving away from the exact literal meaning of what Godel originally said, I thought I had read in some places that more complicated statements, not directly concerning the natural numbers, have been shown to be undecidable in Godel's sense, and that this implies that it might (or will) never be known whether those statements are true or false. Is that correct? 86.160.216.227 (talk) 20:36, 6 October 2012 (UTC)

Ah, this is much more subtle. All that has so far been shown is that certain such statements are undecidable in certain formal theories, or at best certain classes of formal theories. There has never been a mathematical proof that, for a given statement, we can never know in any way at all whether it is true or false, and it is unclear what a such a proof could even look like. There is an excellent paper on this question by Peter Koellner called On the question of absolute undecidability — you might google for it. Be warned that it's not light bedtime reading. --Trovatore (talk) 20:39, 6 October 2012 (UTC)