From Wikipedia, the free encyclopedia
Mathematics desk
< August 1 << Jul | August | Sep >> August 3 >
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.


August 2 Information

Unprovable Problems

Are there any problems in mathematics which are known for a fact to be unprovable (rather than merely currently unproven)? Futurist110 ( talk) 02:31, 2 August 2012 (UTC) reply

You can make a whole slew of them from things that aren't computable, there's a whole bunch of stuff like the word problem for groups, a whole bunch of set theory stuff, etc.* There's also trivial stuff: from the axioms of group theory, you can't decide if xy = yx for all x, y, etc. There's a whole bunch of other stuff, is there some specific type of statement you were looking for? Are you asking about modern "popular" problems? The continuum hypothesis is probably the best I can think of; although, if you're looking for things related to popular topics, you can cook up all sorts of boring stuff about primes and polynomials and what have you using the halting problem and a basic understanding of first order logic. Phoenixia1177 ( talk) 04:05, 2 August 2012 (UTC) *I'm not saying that the word problems/set theory/etc. is part of the slew of things, just listing three categories. reply
On a side note, I don't think being unprovable is nearly as interesting as it is made out to be. If something is unprovable from a list of axioms, it means that there are models in which it holds and ones in which its negation holds; this really isn't anymore remarkable than a lot of other stuff. As I pointed out above, you have models for group theory (groups) that are commutative and, then, those that aren't. Then again, I don't think any system is anymore important than any other for its own sake (I'm not a formalist, I do the opposite, I believe every theory describes an existing thing...yeah I'm a little liberal with my ontology.) Sorry to rant, I'm done now :-) Phoenixia1177 ( talk) 04:15, 2 August 2012 (UTC) reply
You've got to distinguish between three cases: Statements which are independent like the continuum hypothesis - it is perfectly okay to assume it is either true or false and we'd need a good case for a majority to go with an new axiom which supported one rather than the other. Or statements which are about a set of problems that there is no decision procedure, each one is always true or false as in the group theory example but one can't tell which ones are unprovable. Or statements which are definitely true but you can't prove them within some given axiom system like the basis for Gὃdel's undecidability result. It may be that something like the Collatz conjecture is unprovable but it is very unlikely to be provably undecidable with our current axioms - that would in fact also mean it was true and we would have a very interesting case for a new axiom of arithmetic. Dmcq ( talk) 08:35, 2 August 2012 (UTC) reply
OK, no, it is not "perfectly OK to assume" CH is true or false. Sorry, that's popularizer nonsense. Of course you can explore consequences of CH or ~CH, but that's a different thing.
The question of CH vs ~CH is related to very deep facts about the universe of sets. You can't just impose these by fiat. If you're not willing to commit to some argument supporting one or the other, then as regards questions that depend on CH, you pretty much just have to say CH implies one thing and ~CH implies the other, and leave it at that. -- Trovatore ( talk) 17:03, 7 August 2012 (UTC) reply
I absolutely agree. I don't think that it's not interesting, or can't be interesting, I'm just griping about the seeming fascination that a lot of people seem to have with it; at least online and in random pop-math books. I guess my point was that a lot of people seem to think that it's some rare unusual phenomena that always has deep implications or that it is some quasiphilosophical thing. As far as I'm concerned, there are tons of things that fit the bill, lots of them are entirely mundane. Then again, maybe it's just the discussions I happen to happen upon. Honestly, though, I'm grumbling more about the nine topic discussion above about odd perfect numbers, it just seems so random a thing to focus like that on (I just assumed this was a continuation of that same topic initially since the other just kept spawning new headings) Finally, does my response make sense to what you said? I'm not a 100% sure that you're replying to what I said, nor am I sure that you are replying to the points I think you are (my fault not yours, very sleepy) :-) Phoenixia1177 ( talk) 09:15, 2 August 2012 (UTC) reply
By the way, the cake cutting part on your website (linked from profile) The references look 12+ years old, is what you wrote recent? If not, have you ever worked out the case for 3? Or found anything interesting along those lines? If it is inappropriate to respond here and you feel like responding, please do so on my talk page, I'm very interested:-) Phoenixia1177 ( talk) 09:30, 2 August 2012 (UTC) reply
Sorry I haven't looked at that page of mine for a while, actually that bit would probably go I think as I'm more interested in quite different things these days. I didn't get anywhere with three and think it is more of a game theory business with probabilities, I guess one would really have to look at restricting things to get anywhere. Dmcq ( talk) 13:01, 2 August 2012 (UTC) reply
That's a shame, it seemed interesting. Phoenixia1177 ( talk) 03:41, 3 August 2012 (UTC) reply
A strong platonist would argue that your first and third cases are really the same. The continuum hypothesis can't be proven with the axiom system of ZFC, but (they would argue) that doesn't change the fact that it's definitely false.-- 121.73.35.181 ( talk) 10:09, 2 August 2012 (UTC) reply
And there's an offshoot of Platonism that would say both yield real existing universes, so that it's not really true/false in the usual way. Changing gears: is there a recursively enumerable collection of unprovables for number theory so that anything could be proven by adding a finite collection of them? I'm just curious if yes, what would these look like and how would human intuition feel about them (kind of like a loose analogy to large cardinals in set theory). Phoenixia1177 ( talk) 11:08, 2 August 2012 (UTC) reply
So to clarify: you're looking for a c.e. set A of first order sentences in the language of arithmetic, each individually independent of PA, such that for every sentence which is independent of PA, there is a subset X of A such that PA + X is consistent and implies . Hmm, not sure. Note that by Godel, PA + A would need to be inconsistent.-- 121.73.35.181 ( talk) 12:06, 2 August 2012 (UTC) reply
If you could add extra axioms in some straightforward automatic way you could turn that into an axiom fairly easily and then you're back to square one able to construct a definite theorem in arithmetic which is true but not provable in that axiom system. I don't see the point of confusing things which are definitely true by any normal standards with things which are just straightforwardly independent like the continuum hypothesis. There's been arguments for an axiom that puts another infinity between the countable and the continuum, but not being able to demonstrate a likely example makes for difficulty in accepting that. Dmcq ( talk) 13:01, 2 August 2012 (UTC) reply
I'll have to disagree with you about turning it into an axiom, for every p there would be subsets for both p and not p, so you couldn't build it into an axiom. However, it is still trivial since the set of all sentences would work and that's not very interesting. As for adding a set between countable and continuum, I have a problem with the idea of needing to "accept" it, or of its truth. If you say that there are no such sets in reality, that's all well and good. However, the system that has a thing between them has just as much claim to being something; the question is why should sets be more important than this other thing? And how do you know which is which? We don't talk about "the group", we just have groups; why should the arithmetic with the naturals have some special status as a model of PA? Sure, we may be most interested in talking about it, but does it really have some intrinsic preference? The same for the system with no cardnality between countable and continuum, it exists and things are true of it, but why does it have some special philosophical status? Sorry to ramble on, especially since I'm making my point poorly at the moment:-) Phoenixia1177 ( talk) 03:41, 3 August 2012 (UTC) reply

Can anyone offer me a book I can purchase that explains this in terms that someone with my limited intelligence can understand? Joefromrandb ( talk) 23:34, 2 August 2012 (UTC) reply

Nope. -- COVIZAPIBETEFOKY ( talk) 23:59, 2 August 2012 (UTC) reply
I was afraid of that. I should say that I'm not looking for something that jumps off the page and gives me a "eureka" moment. I'd simply like to be able to begin to digest some of it, and what I've read so far may as well have been written in Cantonese. Joefromrandb ( talk) 00:11, 3 August 2012 (UTC) reply
It depends, I guess, on how limited your intelligence is, about which I haven't a clue. There are some possibilities, for example the article cites Invitation to the Mathematics of Fermat-Wiles by Yves Hellegouarch, which claims to require only "modest undergraduate level math". Looie496 ( talk) 00:21, 3 August 2012 (UTC) reply
I was perhaps being a bit too self-deprecating about my intelligence; it is fairly high. But there's quite a difference between "fairly high" and "off the charts", which would be someone like an Andrew Wiles or a Stephen Hawking. I understand Fermat's Last Theorem and I understand to some degree what Wiles' aim was. I basically have very little understanding of the jargon. Joefromrandb ( talk) 00:32, 3 August 2012 (UTC) reply
I think the main limiting factor is how much time you're willing to invest in this endeavor. I don't know much about the proof myself, but from my understanding it uses some pretty heavy-duty machinery. If you want to really understand each detail you're going to need a lot of background, which takes a lot of study, probably on the order of years depending on what you know already. Rckrone ( talk) 01:37, 3 August 2012 (UTC) reply
The article actually mentions a book [1]. I'm curious what background it assumes. Rckrone ( talk) 01:44, 3 August 2012 (UTC) reply
It's not intelligence, so much as mathematical education, that matters (of course, you need to be intelligent to study maths at a high level). To what level have you studied maths? -- Tango ( talk) 17:34, 3 August 2012 (UTC) reply
Simon Singh wrote a book on FLT that covers Wiles's proof (as well as a lot of the history of the problem), but (as far as I remember) not in any great depth. AndrewWTaylor ( talk) 09:25, 3 August 2012 (UTC) reply

I agree with COVIZAPIBETEFOKY. There is no royal road to geometry. Bo Jacoby ( talk) 10:01, 3 August 2012 (UTC). reply

Singh's and Amir Aczel's books are popularisations, and will give you an overview of Wiles' proof, but not much in the way of details. Hellegouarch covers the mathematical background in depth, and is written as a textbook for a graduate or upper-end undergraduate course, but it only sketches out the proof itself. Another textbook is Stewart and Tall's Algenraic Number Theory and Fermat's Last Theorem. Charles Daney's web site The Mathematics of Fermat's Last Theorem is a useful reference. Gandalf61 ( talk) 11:20, 3 August 2012 (UTC) reply
From Wikipedia, the free encyclopedia
Mathematics desk
< August 1 << Jul | August | Sep >> August 3 >
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.


August 2 Information

Unprovable Problems

Are there any problems in mathematics which are known for a fact to be unprovable (rather than merely currently unproven)? Futurist110 ( talk) 02:31, 2 August 2012 (UTC) reply

You can make a whole slew of them from things that aren't computable, there's a whole bunch of stuff like the word problem for groups, a whole bunch of set theory stuff, etc.* There's also trivial stuff: from the axioms of group theory, you can't decide if xy = yx for all x, y, etc. There's a whole bunch of other stuff, is there some specific type of statement you were looking for? Are you asking about modern "popular" problems? The continuum hypothesis is probably the best I can think of; although, if you're looking for things related to popular topics, you can cook up all sorts of boring stuff about primes and polynomials and what have you using the halting problem and a basic understanding of first order logic. Phoenixia1177 ( talk) 04:05, 2 August 2012 (UTC) *I'm not saying that the word problems/set theory/etc. is part of the slew of things, just listing three categories. reply
On a side note, I don't think being unprovable is nearly as interesting as it is made out to be. If something is unprovable from a list of axioms, it means that there are models in which it holds and ones in which its negation holds; this really isn't anymore remarkable than a lot of other stuff. As I pointed out above, you have models for group theory (groups) that are commutative and, then, those that aren't. Then again, I don't think any system is anymore important than any other for its own sake (I'm not a formalist, I do the opposite, I believe every theory describes an existing thing...yeah I'm a little liberal with my ontology.) Sorry to rant, I'm done now :-) Phoenixia1177 ( talk) 04:15, 2 August 2012 (UTC) reply
You've got to distinguish between three cases: Statements which are independent like the continuum hypothesis - it is perfectly okay to assume it is either true or false and we'd need a good case for a majority to go with an new axiom which supported one rather than the other. Or statements which are about a set of problems that there is no decision procedure, each one is always true or false as in the group theory example but one can't tell which ones are unprovable. Or statements which are definitely true but you can't prove them within some given axiom system like the basis for Gὃdel's undecidability result. It may be that something like the Collatz conjecture is unprovable but it is very unlikely to be provably undecidable with our current axioms - that would in fact also mean it was true and we would have a very interesting case for a new axiom of arithmetic. Dmcq ( talk) 08:35, 2 August 2012 (UTC) reply
OK, no, it is not "perfectly OK to assume" CH is true or false. Sorry, that's popularizer nonsense. Of course you can explore consequences of CH or ~CH, but that's a different thing.
The question of CH vs ~CH is related to very deep facts about the universe of sets. You can't just impose these by fiat. If you're not willing to commit to some argument supporting one or the other, then as regards questions that depend on CH, you pretty much just have to say CH implies one thing and ~CH implies the other, and leave it at that. -- Trovatore ( talk) 17:03, 7 August 2012 (UTC) reply
I absolutely agree. I don't think that it's not interesting, or can't be interesting, I'm just griping about the seeming fascination that a lot of people seem to have with it; at least online and in random pop-math books. I guess my point was that a lot of people seem to think that it's some rare unusual phenomena that always has deep implications or that it is some quasiphilosophical thing. As far as I'm concerned, there are tons of things that fit the bill, lots of them are entirely mundane. Then again, maybe it's just the discussions I happen to happen upon. Honestly, though, I'm grumbling more about the nine topic discussion above about odd perfect numbers, it just seems so random a thing to focus like that on (I just assumed this was a continuation of that same topic initially since the other just kept spawning new headings) Finally, does my response make sense to what you said? I'm not a 100% sure that you're replying to what I said, nor am I sure that you are replying to the points I think you are (my fault not yours, very sleepy) :-) Phoenixia1177 ( talk) 09:15, 2 August 2012 (UTC) reply
By the way, the cake cutting part on your website (linked from profile) The references look 12+ years old, is what you wrote recent? If not, have you ever worked out the case for 3? Or found anything interesting along those lines? If it is inappropriate to respond here and you feel like responding, please do so on my talk page, I'm very interested:-) Phoenixia1177 ( talk) 09:30, 2 August 2012 (UTC) reply
Sorry I haven't looked at that page of mine for a while, actually that bit would probably go I think as I'm more interested in quite different things these days. I didn't get anywhere with three and think it is more of a game theory business with probabilities, I guess one would really have to look at restricting things to get anywhere. Dmcq ( talk) 13:01, 2 August 2012 (UTC) reply
That's a shame, it seemed interesting. Phoenixia1177 ( talk) 03:41, 3 August 2012 (UTC) reply
A strong platonist would argue that your first and third cases are really the same. The continuum hypothesis can't be proven with the axiom system of ZFC, but (they would argue) that doesn't change the fact that it's definitely false.-- 121.73.35.181 ( talk) 10:09, 2 August 2012 (UTC) reply
And there's an offshoot of Platonism that would say both yield real existing universes, so that it's not really true/false in the usual way. Changing gears: is there a recursively enumerable collection of unprovables for number theory so that anything could be proven by adding a finite collection of them? I'm just curious if yes, what would these look like and how would human intuition feel about them (kind of like a loose analogy to large cardinals in set theory). Phoenixia1177 ( talk) 11:08, 2 August 2012 (UTC) reply
So to clarify: you're looking for a c.e. set A of first order sentences in the language of arithmetic, each individually independent of PA, such that for every sentence which is independent of PA, there is a subset X of A such that PA + X is consistent and implies . Hmm, not sure. Note that by Godel, PA + A would need to be inconsistent.-- 121.73.35.181 ( talk) 12:06, 2 August 2012 (UTC) reply
If you could add extra axioms in some straightforward automatic way you could turn that into an axiom fairly easily and then you're back to square one able to construct a definite theorem in arithmetic which is true but not provable in that axiom system. I don't see the point of confusing things which are definitely true by any normal standards with things which are just straightforwardly independent like the continuum hypothesis. There's been arguments for an axiom that puts another infinity between the countable and the continuum, but not being able to demonstrate a likely example makes for difficulty in accepting that. Dmcq ( talk) 13:01, 2 August 2012 (UTC) reply
I'll have to disagree with you about turning it into an axiom, for every p there would be subsets for both p and not p, so you couldn't build it into an axiom. However, it is still trivial since the set of all sentences would work and that's not very interesting. As for adding a set between countable and continuum, I have a problem with the idea of needing to "accept" it, or of its truth. If you say that there are no such sets in reality, that's all well and good. However, the system that has a thing between them has just as much claim to being something; the question is why should sets be more important than this other thing? And how do you know which is which? We don't talk about "the group", we just have groups; why should the arithmetic with the naturals have some special status as a model of PA? Sure, we may be most interested in talking about it, but does it really have some intrinsic preference? The same for the system with no cardnality between countable and continuum, it exists and things are true of it, but why does it have some special philosophical status? Sorry to ramble on, especially since I'm making my point poorly at the moment:-) Phoenixia1177 ( talk) 03:41, 3 August 2012 (UTC) reply

Can anyone offer me a book I can purchase that explains this in terms that someone with my limited intelligence can understand? Joefromrandb ( talk) 23:34, 2 August 2012 (UTC) reply

Nope. -- COVIZAPIBETEFOKY ( talk) 23:59, 2 August 2012 (UTC) reply
I was afraid of that. I should say that I'm not looking for something that jumps off the page and gives me a "eureka" moment. I'd simply like to be able to begin to digest some of it, and what I've read so far may as well have been written in Cantonese. Joefromrandb ( talk) 00:11, 3 August 2012 (UTC) reply
It depends, I guess, on how limited your intelligence is, about which I haven't a clue. There are some possibilities, for example the article cites Invitation to the Mathematics of Fermat-Wiles by Yves Hellegouarch, which claims to require only "modest undergraduate level math". Looie496 ( talk) 00:21, 3 August 2012 (UTC) reply
I was perhaps being a bit too self-deprecating about my intelligence; it is fairly high. But there's quite a difference between "fairly high" and "off the charts", which would be someone like an Andrew Wiles or a Stephen Hawking. I understand Fermat's Last Theorem and I understand to some degree what Wiles' aim was. I basically have very little understanding of the jargon. Joefromrandb ( talk) 00:32, 3 August 2012 (UTC) reply
I think the main limiting factor is how much time you're willing to invest in this endeavor. I don't know much about the proof myself, but from my understanding it uses some pretty heavy-duty machinery. If you want to really understand each detail you're going to need a lot of background, which takes a lot of study, probably on the order of years depending on what you know already. Rckrone ( talk) 01:37, 3 August 2012 (UTC) reply
The article actually mentions a book [1]. I'm curious what background it assumes. Rckrone ( talk) 01:44, 3 August 2012 (UTC) reply
It's not intelligence, so much as mathematical education, that matters (of course, you need to be intelligent to study maths at a high level). To what level have you studied maths? -- Tango ( talk) 17:34, 3 August 2012 (UTC) reply
Simon Singh wrote a book on FLT that covers Wiles's proof (as well as a lot of the history of the problem), but (as far as I remember) not in any great depth. AndrewWTaylor ( talk) 09:25, 3 August 2012 (UTC) reply

I agree with COVIZAPIBETEFOKY. There is no royal road to geometry. Bo Jacoby ( talk) 10:01, 3 August 2012 (UTC). reply

Singh's and Amir Aczel's books are popularisations, and will give you an overview of Wiles' proof, but not much in the way of details. Hellegouarch covers the mathematical background in depth, and is written as a textbook for a graduate or upper-end undergraduate course, but it only sketches out the proof itself. Another textbook is Stewart and Tall's Algenraic Number Theory and Fermat's Last Theorem. Charles Daney's web site The Mathematics of Fermat's Last Theorem is a useful reference. Gandalf61 ( talk) 11:20, 3 August 2012 (UTC) reply

Videos

Youtube | Vimeo | Bing

Websites

Google | Yahoo | Bing

Encyclopedia

Google | Yahoo | Bing

Facebook