What is a simple example of an unprovable statement?












67












$begingroup$


Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.



I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: https://math.stackexchange.com/a/453764/197692.



The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.



My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?



My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.



Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?



Update:
There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.



Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:43










  • $begingroup$
    Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
    $endgroup$
    – Najib Idrissi
    Dec 6 '14 at 9:14












  • $begingroup$
    Please note my comment here.
    $endgroup$
    – user21820
    Feb 26 '17 at 6:38










  • $begingroup$
    I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:01










  • $begingroup$
    For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:10
















67












$begingroup$


Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.



I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: https://math.stackexchange.com/a/453764/197692.



The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.



My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?



My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.



Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?



Update:
There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.



Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:43










  • $begingroup$
    Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
    $endgroup$
    – Najib Idrissi
    Dec 6 '14 at 9:14












  • $begingroup$
    Please note my comment here.
    $endgroup$
    – user21820
    Feb 26 '17 at 6:38










  • $begingroup$
    I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:01










  • $begingroup$
    For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:10














67












67








67


51



$begingroup$


Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.



I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: https://math.stackexchange.com/a/453764/197692.



The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.



My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?



My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.



Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?



Update:
There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.



Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.










share|cite|improve this question











$endgroup$




Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.



I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: https://math.stackexchange.com/a/453764/197692.



The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.



My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?



My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.



Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?



Update:
There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.



Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.







logic incompleteness provability






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Apr 4 '18 at 16:08







Michael Harris

















asked Dec 5 '14 at 1:09









Michael HarrisMichael Harris

4451510




4451510








  • 2




    $begingroup$
    Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:43










  • $begingroup$
    Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
    $endgroup$
    – Najib Idrissi
    Dec 6 '14 at 9:14












  • $begingroup$
    Please note my comment here.
    $endgroup$
    – user21820
    Feb 26 '17 at 6:38










  • $begingroup$
    I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:01










  • $begingroup$
    For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:10














  • 2




    $begingroup$
    Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:43










  • $begingroup$
    Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
    $endgroup$
    – Najib Idrissi
    Dec 6 '14 at 9:14












  • $begingroup$
    Please note my comment here.
    $endgroup$
    – user21820
    Feb 26 '17 at 6:38










  • $begingroup$
    I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:01










  • $begingroup$
    For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
    $endgroup$
    – user21820
    Dec 13 '17 at 6:10








2




2




$begingroup$
Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
$endgroup$
– MJD
Dec 5 '14 at 1:43




$begingroup$
Related: Examples of statements which are true but not provable / Do we know if there exist true mathematical statements that can not be proven?
$endgroup$
– MJD
Dec 5 '14 at 1:43












$begingroup$
Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
$endgroup$
– Najib Idrissi
Dec 6 '14 at 9:14






$begingroup$
Relevant talk notes by Patrick Dehornoy that I suggest you read (there's even a joke in there).
$endgroup$
– Najib Idrissi
Dec 6 '14 at 9:14














$begingroup$
Please note my comment here.
$endgroup$
– user21820
Feb 26 '17 at 6:38




$begingroup$
Please note my comment here.
$endgroup$
– user21820
Feb 26 '17 at 6:38












$begingroup$
I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
$endgroup$
– user21820
Dec 13 '17 at 6:01




$begingroup$
I fixed the answer that you had accepted, since it had not been fixed despite my comments months ago and was thoroughly misleading to every reader. This incident (and many other similar incidents such as here) shows that you cannot assume answers you receive on Math SE are correct or meaningful.
$endgroup$
– user21820
Dec 13 '17 at 6:01












$begingroup$
For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
$endgroup$
– user21820
Dec 13 '17 at 6:10




$begingroup$
For this particular issue, go and look up the arithmetical hierarchy, and see also this computability theorist's blog.
$endgroup$
– user21820
Dec 13 '17 at 6:10










12 Answers
12






active

oldest

votes


















65












$begingroup$

Here's a nice example that I think is easier to understand than the usual examples of Goodstein's theorem, Paris-Harrington, etc. Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors $C_1, C_2, $ and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.



Now ask the question: Are there four real numbers $a,b,c,d$, all painted the same color, and not all zero, such that $$a+b=c+d?$$



It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color $C_1$, then obviously there are $a,b,c,d$ satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with $a+b=c+d$; perhaps a sufficiently clever painter could arrange that for any four numbers with $a+b=c+d$ there would always be at least one of a different color than the rest.



So now you can ask the question: Must such $a,b,c,d$ exist regardless of how cleverly the numbers are actually colored?



And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics.





The result is mentioned in




  • Fox, Jacob “An infinite color analogue of Rado's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.


Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over $Bbb Q$, which is proved in:




  • Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.


A proof for the $a+b=c+d$ situation, originally proved by Erdős, is given in:




  • Davies, R.O. “Partitioning the plane into denumerably many sets without repeated distance” Porc. Cambridge Philos. Soc. 72 (1972) 179–183.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
    $endgroup$
    – MJD
    Dec 5 '14 at 2:35








  • 1




    $begingroup$
    Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:14






  • 7




    $begingroup$
    Thanks all for consistently correct spelling Erdős and Gödel.
    $endgroup$
    – Hagen von Eitzen
    Dec 6 '14 at 12:28






  • 3




    $begingroup$
    ^ It takes one person to start a good thing. The rest copy and paste.
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:55






  • 1




    $begingroup$
    I assume you mean "four distinct real numbers".
    $endgroup$
    – DanielV
    Nov 23 '16 at 13:47



















19












$begingroup$

The one I find most intuitive, as an unprovable statement from ZF without Axiom of Choice, is that for any two sets X and Y, either there's an injective function from X to Y, or there's one from Y to X.



Roughly, and informally, I read this as: either X is at least as big as Y, or Y is at least as big as X.



I mean, what's the alternative? They're both bigger than each other?!






share|cite|improve this answer









$endgroup$









  • 4




    $begingroup$
    There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
    $endgroup$
    – murray
    Dec 7 '14 at 17:46










  • $begingroup$
    @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
    $endgroup$
    – Ant
    Dec 9 '14 at 16:44










  • $begingroup$
    Why is this statement unprovable?
    $endgroup$
    – Marco Flores
    Dec 27 '14 at 5:13






  • 2




    $begingroup$
    @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
    $endgroup$
    – chiastic-security
    Dec 27 '14 at 8:09



















18












$begingroup$

In $mathsf{ZF}$ (i.e. Zermelo–Fraenkel's set theory axioms, without the Axiom of Choice) the following statements (among many many others) are unprovable:




  1. Countable union of countable sets is countable.

  2. Every surjective function has a right-inverse.

  3. Every vector space has a basis.

  4. Every ring has a maximal ideal.


These statements are not exactly "intuitively true to the layperson", but seem natural to many mathematicians. In particular, (2) is probably taught in every math university during the first week of the first year.



If you are interested in models of $mathsf{ZF}$ in which (1),(2),(3) or (4) don't hold, you can start taking a look at Axiom of Choice, by Horst Herrlich. It has a very nice and well organised Appendix where you can look for models depending on which (main) statements they satisfy.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:20






  • 2




    $begingroup$
    @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:07












  • $begingroup$
    And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:09





















18












$begingroup$

Any statement which is not logically valid (read: always true) is unprovable. The statement $exists xexists y(x>y)$ is not provable from the theory of linear orders, since it is false in the singleton order. On the other hand, it is not disprovable since any other order type would satisfy it.



The statement $exists x(x^2-2=0)$ is not provable from the axioms of the field, since $Bbb Q$ thinks this is false, and $Bbb C$ thinks it is true.



The statement "$G$ is an Abelian group" is not provable since given a group $G$ it can be Abelian and it could be non-Abelian.



The statement "$fcolonBbb{Rto R}$ is continuous/differentiable/continuously differentiable/smooth/analytic/a polynomial" and so on and so forth, are all unprovable, because just like that given an arbitrary function we don't know anything about it. Even if we know it is continuous we can't know if it is continuously differentiable, or smooth, or anything else. So these are all additional assumptions we have to make.



Of course, given a particular function, like $f(x)=e^x$ we can sit down and prove things about it, but the statement "$f$ is a continuous function" cannot be proved or disproved until further assumptions are added.



And that's the point that I am trying to make here. Every statement which cannot be always proved will be unprovable from some assumptions. But you ask for an intuitive statement, and that causes a problem.



The problem with "intuitive statement" is that the more you work in mathematics, the more your intuition is decomposed and reconstructed according to the topic you work with. The continuum hypothesis is perfectly intuitive and simple for me, it is true that understanding how it can be unprovable is difficult, but the statement itself is not very difficult once you cleared up the basic notions like cardinality and power sets.



Finally, let me just add that there are plenty of theories which are complete and consistent and we work with them. Some of them are even recursively enumerable. The incompleteness theorem gives us three conditions from which incompleteness follows, any two won't suffice. (1) Consistent, (2) Recursively enumerable, (3) Interprets arithmetics.



There are complete theories which satisfy the first two, and there are complete theories which are consistent and interpret arithmetics, and of course any inconsistent theory is complete.






share|cite|improve this answer









$endgroup$









  • 13




    $begingroup$
    I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 8:19










  • $begingroup$
    I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
    $endgroup$
    – David Z
    Dec 5 '14 at 8:49






  • 1




    $begingroup$
    @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
    $endgroup$
    – Turion
    Dec 5 '14 at 15:18






  • 1




    $begingroup$
    @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 15:28






  • 1




    $begingroup$
    I am starting to suspect there is something personal about these downvotes.
    $endgroup$
    – Asaf Karagila
    Dec 8 '14 at 7:02



















17












$begingroup$

Most laypersons will understand the following. If you have a file containing random data that is larger than 1 GB in size, then it's unlikely that it could be compressed to a self-extracting file of size less than 1 MB. The probability is astronomically small that such a self-extracting program could generate your file.



But while the vast majority of such files cannot be compressed to under 1 MB in size, you can never have a mathematical proof of that fact for any specific file. This is because you can generate all such proofs recursively using a small program. Have this program stop at the first proven theorem that says that such and such a file larger than 1 GB cannot be compressed, and output that large file. If the program outputs, that means the program is the small self-extracting program (compressed) version of its output, the very output that the theorem says cannot be compressed, which is a contradiction.






share|cite|improve this answer











$endgroup$









  • 4




    $begingroup$
    Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
    $endgroup$
    – wchargin
    Dec 6 '14 at 17:19










  • $begingroup$
    How does one know that the theorem itself will be small?
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:59










  • $begingroup$
    @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
    $endgroup$
    – Gordon Davisson
    Dec 7 '14 at 8:54










  • $begingroup$
    Um, how do we know it will?
    $endgroup$
    – Soham Chowdhury
    Dec 7 '14 at 12:59










  • $begingroup$
    I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
    $endgroup$
    – Count Iblis
    Dec 8 '14 at 3:32



















13












$begingroup$

The problem with your goal is this:
There are conjectures that are currently unknown (i.e., with our current knowledge, they could be provably right, or provably wrong, or undecidable from the generally accepted axiom systems) and simple enough to formulate so that a layperson can understands their underlying concepts. Some examples are




  • Goldbach's conjecture

  • Twin prime conjecture

  • The $3n+1$ problem

  • All perfect numbers are even

  • $pi$ is a normal number

  • $e+pi$ is irrational


For most such conjectures there is numerical evidence for them to hold up to the very limits of computational search - but does that make them "intuitively true" for the layperson?
If any of these should ever turn out to be undecidable, we'd be in the position to add one of two conflicting axioms to our inventory, e.g., one of "There exists a natural number $N$ that cannot be written as sum of two primes" or "Goldbach is true". When picking the first choice, we'd know that $N$ cannot be reached in finite time by counting $1,2,3,ldots$ as for any number reachable this way in finite time can also be checked in finite time if it can or cannot be written as sum of two primes. Therefore, we'd know intuitively that the "real-life" natural numbers do not contain such $N$, i.e. the only "correct" extension of our axiom system is that Goldbach is true. This argument works for some others: If "all perfect numbers are even" is independent, then it is true. In general, any independent $Π_1$-sentence is true in the natural numbers. This fact is equivalent to the $Σ_1$-completeness of first-order Peano Arithmetic. Currently, the twin prime conjecture and Collatz conjecture and irrationality of $e+π$ are only known to be equivalent to $Π_2$-sentences, so we cannot apply this argument to them.



Besides the above possibilities, other possibly independent statements include:




  • Those specifically constructed to be independent (of the "I am unprovable" kind) that are totally dull and unrelated to any real-life mathematics.

  • Those that worthy of being added (positively or negatively) to $mathsf{ZFC}$ without there being a very natural preference in one direction or the other (such as the Continuum Hypothesis; or already the Axiom of Choice if you start with $mathsf{ZF}$). I doubt that any of these could be considered intuitively clear for the layperson.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
    $endgroup$
    – Lehs
    Dec 6 '14 at 17:57










  • $begingroup$
    So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
    $endgroup$
    – Michael Harris
    Dec 6 '14 at 20:29






  • 1




    $begingroup$
    @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
    $endgroup$
    – Hagen von Eitzen
    Dec 7 '14 at 18:47










  • $begingroup$
    I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
    $endgroup$
    – Steven Stadnicki
    Dec 8 '14 at 1:11






  • 1




    $begingroup$
    @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
    $endgroup$
    – user21820
    Feb 24 '17 at 13:40





















8












$begingroup$

There is no natural number, $n$, such that $n$'s interpretation as an ASCII string is a proof of this statement.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Ah, simplicity! Elegance, too! +1
    $endgroup$
    – TobiMcNamobi
    Dec 8 '14 at 14:11





















6












$begingroup$

You asked




Can someone give a good example you can point to and say "That's what Godel's incompleteness theorems are talking about"?




I think you can cut right to the heart of the matter by explaining the Peano axioms, which anyone can understand and which seem as self-evidently true as anything in mathematics. And you can explain how one can use the Peano axioms to prove theorems that are true of the natural numbers, such as $forall a,b. a+b = b+a$ and the like.



Now, we might like some assurance that these axioms are sound; that is, how do we know that the Peano axioms don't somehow allow us to “prove” something that is actually false?



Perhaps we could prove that using the Peano axioms themselves, some sort of self-bootstrapping demonstration of the soundness of the axioms?
Mathematicians at the beginning of the 20th century hoped for just such a demonstration, and their hope was dashed in 1931.



Gödel's second incompleteness theorem says that the axioms themselves might indeed be able to prove that the axioms were sound—but that if they do, it is only because they are not sound and can prove anything at all, true or false. Sound axioms cannot prove their own soundness.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:45






  • 1




    $begingroup$
    If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
    $endgroup$
    – MJD
    Dec 6 '14 at 0:15



















5












$begingroup$

Luckily Gödels proof is constructive and so provides an example itself. This is nicely explained in "Gödel, Escher, Bach".



In short (from what I humbly understand and remember): You can assign a number to every logical statement in your formal context, let's call this the Gödel number of that statement. Then you can construct statements that make propositions about other statements (by referencing the Gödel number, e.g. "the statement with the number xyz is true"). Those statements of course have associated Gödel numbers, too. Now construct a statement "The statement with Gödel number xyz is unprovable" so that the Gödel number of the statement is xyz.



The Wikipedia entry for this (here) is more detailed but maybe still considered popular science.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:36






  • 1




    $begingroup$
    @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
    $endgroup$
    – TobiMcNamobi
    Dec 6 '14 at 12:48



















2












$begingroup$

The parallel postulate can't proved from the other axioms of Euclid's geometry.



You don't even have to drag in Gödel's theorem when you explain this, because it's not relevant. That's a big plus.





Similarly, there are plenty of incomplete axiom systems. Take the Peano axioms for arithmetic, and leave one out, say the axiom that says that there's no $n$ of which zero is the successor. This axiom can't be proved from the other four axioms.



Or take the axioms for the real numbers and leave out the well-ordering principle.



Or take the axioms for set theory and delete one, say the axiom of regularity. You can't prove the deleted axiom from the remaining ones. (There are a few exceptions to this; you can prove the axiom of the empty set from the others.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    This is not really what the question is about.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:44










  • $begingroup$
    @Andres What do you see in the question to suggest that?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:44










  • $begingroup$
    The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:50










  • $begingroup$
    In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
    $endgroup$
    – MJD
    Dec 5 '14 at 1:52












  • $begingroup$
    If you wish.${}$
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:54



















2












$begingroup$

This is certainly not an direct answer but a perspective on the topic of the question. The quadrangular parts in the picture below could be empty or joined depending on the approach to the issue.



Topological model of proofs and statements



Suppose there was a topology on a space of statements. Then the concept of proof perhaps could be generalized so that some of the unprovable statements could be interpreted as limits of sequences of logical steps that converges to statements in C, D or E?



Without topology and when only regarding finite proofs the unprovable statements must be considered as a single class of undecidable statements.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
    $endgroup$
    – draks ...
    Jan 23 at 20:10










  • $begingroup$
    What do the numbers mean and where is that figure from?
    $endgroup$
    – draks ...
    Jan 24 at 22:25










  • $begingroup$
    @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
    $endgroup$
    – Lehs
    Jan 24 at 23:04










  • $begingroup$
    I see. Sorry for being late, my interest in that topic just started...
    $endgroup$
    – draks ...
    Jan 25 at 7:36










  • $begingroup$
    @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
    $endgroup$
    – Lehs
    Jan 25 at 9:56



















2












$begingroup$

An example of a problem that in general cannot be solved is the existence of solutions to Diophantine equations http://en.wikipedia.org/wiki/Diophantine_equation. Hilbert's 10th problem was to find an "effective method" (that is, a computer program) to solve Diophantine equations. It was shown in work by Yuri Matiyasevich and Julia Robinson that there is no such effective method. (As I recall, Julia did most of the work, leaving one lemma that needed to be proved. Yuri then proved the lemma. Yuri's paper is rather short, and you need to read Julia's paper to get the full picture.)






share|cite|improve this answer









$endgroup$












    protected by user99914 Nov 19 '17 at 2:18



    Thank you for your interest in this question.
    Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



    Would you like to answer one of these unanswered questions instead?














    12 Answers
    12






    active

    oldest

    votes








    12 Answers
    12






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    65












    $begingroup$

    Here's a nice example that I think is easier to understand than the usual examples of Goodstein's theorem, Paris-Harrington, etc. Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors $C_1, C_2, $ and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.



    Now ask the question: Are there four real numbers $a,b,c,d$, all painted the same color, and not all zero, such that $$a+b=c+d?$$



    It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color $C_1$, then obviously there are $a,b,c,d$ satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with $a+b=c+d$; perhaps a sufficiently clever painter could arrange that for any four numbers with $a+b=c+d$ there would always be at least one of a different color than the rest.



    So now you can ask the question: Must such $a,b,c,d$ exist regardless of how cleverly the numbers are actually colored?



    And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics.





    The result is mentioned in




    • Fox, Jacob “An infinite color analogue of Rado's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.


    Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over $Bbb Q$, which is proved in:




    • Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.


    A proof for the $a+b=c+d$ situation, originally proved by Erdős, is given in:




    • Davies, R.O. “Partitioning the plane into denumerably many sets without repeated distance” Porc. Cambridge Philos. Soc. 72 (1972) 179–183.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
      $endgroup$
      – MJD
      Dec 5 '14 at 2:35








    • 1




      $begingroup$
      Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:14






    • 7




      $begingroup$
      Thanks all for consistently correct spelling Erdős and Gödel.
      $endgroup$
      – Hagen von Eitzen
      Dec 6 '14 at 12:28






    • 3




      $begingroup$
      ^ It takes one person to start a good thing. The rest copy and paste.
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:55






    • 1




      $begingroup$
      I assume you mean "four distinct real numbers".
      $endgroup$
      – DanielV
      Nov 23 '16 at 13:47
















    65












    $begingroup$

    Here's a nice example that I think is easier to understand than the usual examples of Goodstein's theorem, Paris-Harrington, etc. Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors $C_1, C_2, $ and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.



    Now ask the question: Are there four real numbers $a,b,c,d$, all painted the same color, and not all zero, such that $$a+b=c+d?$$



    It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color $C_1$, then obviously there are $a,b,c,d$ satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with $a+b=c+d$; perhaps a sufficiently clever painter could arrange that for any four numbers with $a+b=c+d$ there would always be at least one of a different color than the rest.



    So now you can ask the question: Must such $a,b,c,d$ exist regardless of how cleverly the numbers are actually colored?



    And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics.





    The result is mentioned in




    • Fox, Jacob “An infinite color analogue of Rado's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.


    Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over $Bbb Q$, which is proved in:




    • Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.


    A proof for the $a+b=c+d$ situation, originally proved by Erdős, is given in:




    • Davies, R.O. “Partitioning the plane into denumerably many sets without repeated distance” Porc. Cambridge Philos. Soc. 72 (1972) 179–183.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
      $endgroup$
      – MJD
      Dec 5 '14 at 2:35








    • 1




      $begingroup$
      Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:14






    • 7




      $begingroup$
      Thanks all for consistently correct spelling Erdős and Gödel.
      $endgroup$
      – Hagen von Eitzen
      Dec 6 '14 at 12:28






    • 3




      $begingroup$
      ^ It takes one person to start a good thing. The rest copy and paste.
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:55






    • 1




      $begingroup$
      I assume you mean "four distinct real numbers".
      $endgroup$
      – DanielV
      Nov 23 '16 at 13:47














    65












    65








    65





    $begingroup$

    Here's a nice example that I think is easier to understand than the usual examples of Goodstein's theorem, Paris-Harrington, etc. Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors $C_1, C_2, $ and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.



    Now ask the question: Are there four real numbers $a,b,c,d$, all painted the same color, and not all zero, such that $$a+b=c+d?$$



    It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color $C_1$, then obviously there are $a,b,c,d$ satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with $a+b=c+d$; perhaps a sufficiently clever painter could arrange that for any four numbers with $a+b=c+d$ there would always be at least one of a different color than the rest.



    So now you can ask the question: Must such $a,b,c,d$ exist regardless of how cleverly the numbers are actually colored?



    And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics.





    The result is mentioned in




    • Fox, Jacob “An infinite color analogue of Rado's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.


    Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over $Bbb Q$, which is proved in:




    • Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.


    A proof for the $a+b=c+d$ situation, originally proved by Erdős, is given in:




    • Davies, R.O. “Partitioning the plane into denumerably many sets without repeated distance” Porc. Cambridge Philos. Soc. 72 (1972) 179–183.






    share|cite|improve this answer











    $endgroup$



    Here's a nice example that I think is easier to understand than the usual examples of Goodstein's theorem, Paris-Harrington, etc. Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors $C_1, C_2, $ and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.



    Now ask the question: Are there four real numbers $a,b,c,d$, all painted the same color, and not all zero, such that $$a+b=c+d?$$



    It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color $C_1$, then obviously there are $a,b,c,d$ satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with $a+b=c+d$; perhaps a sufficiently clever painter could arrange that for any four numbers with $a+b=c+d$ there would always be at least one of a different color than the rest.



    So now you can ask the question: Must such $a,b,c,d$ exist regardless of how cleverly the numbers are actually colored?



    And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics.





    The result is mentioned in




    • Fox, Jacob “An infinite color analogue of Rado's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.


    Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over $Bbb Q$, which is proved in:




    • Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.


    A proof for the $a+b=c+d$ situation, originally proved by Erdős, is given in:




    • Davies, R.O. “Partitioning the plane into denumerably many sets without repeated distance” Porc. Cambridge Philos. Soc. 72 (1972) 179–183.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 31 '18 at 9:23


























    community wiki





    6 revs, 2 users 98%
    MJD













    • $begingroup$
      @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
      $endgroup$
      – MJD
      Dec 5 '14 at 2:35








    • 1




      $begingroup$
      Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:14






    • 7




      $begingroup$
      Thanks all for consistently correct spelling Erdős and Gödel.
      $endgroup$
      – Hagen von Eitzen
      Dec 6 '14 at 12:28






    • 3




      $begingroup$
      ^ It takes one person to start a good thing. The rest copy and paste.
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:55






    • 1




      $begingroup$
      I assume you mean "four distinct real numbers".
      $endgroup$
      – DanielV
      Nov 23 '16 at 13:47


















    • $begingroup$
      @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
      $endgroup$
      – MJD
      Dec 5 '14 at 2:35








    • 1




      $begingroup$
      Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:14






    • 7




      $begingroup$
      Thanks all for consistently correct spelling Erdős and Gödel.
      $endgroup$
      – Hagen von Eitzen
      Dec 6 '14 at 12:28






    • 3




      $begingroup$
      ^ It takes one person to start a good thing. The rest copy and paste.
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:55






    • 1




      $begingroup$
      I assume you mean "four distinct real numbers".
      $endgroup$
      – DanielV
      Nov 23 '16 at 13:47
















    $begingroup$
    @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
    $endgroup$
    – MJD
    Dec 5 '14 at 2:35






    $begingroup$
    @Andres I hope you like this answer better, although I feel that it falls foul of the same criticism you leveled at the other one: it has nothing at all to do with Gödel's theorems.
    $endgroup$
    – MJD
    Dec 5 '14 at 2:35






    1




    1




    $begingroup$
    Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:14




    $begingroup$
    Wonderful. I really like this example. Although it seems like to really get this you have to understand some of the subtleties of Reals vs Integers and countable vs uncountable. That's probably straining the attention span of my audience (my family/friends) a bit.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:14




    7




    7




    $begingroup$
    Thanks all for consistently correct spelling Erdős and Gödel.
    $endgroup$
    – Hagen von Eitzen
    Dec 6 '14 at 12:28




    $begingroup$
    Thanks all for consistently correct spelling Erdős and Gödel.
    $endgroup$
    – Hagen von Eitzen
    Dec 6 '14 at 12:28




    3




    3




    $begingroup$
    ^ It takes one person to start a good thing. The rest copy and paste.
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:55




    $begingroup$
    ^ It takes one person to start a good thing. The rest copy and paste.
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:55




    1




    1




    $begingroup$
    I assume you mean "four distinct real numbers".
    $endgroup$
    – DanielV
    Nov 23 '16 at 13:47




    $begingroup$
    I assume you mean "four distinct real numbers".
    $endgroup$
    – DanielV
    Nov 23 '16 at 13:47











    19












    $begingroup$

    The one I find most intuitive, as an unprovable statement from ZF without Axiom of Choice, is that for any two sets X and Y, either there's an injective function from X to Y, or there's one from Y to X.



    Roughly, and informally, I read this as: either X is at least as big as Y, or Y is at least as big as X.



    I mean, what's the alternative? They're both bigger than each other?!






    share|cite|improve this answer









    $endgroup$









    • 4




      $begingroup$
      There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
      $endgroup$
      – murray
      Dec 7 '14 at 17:46










    • $begingroup$
      @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
      $endgroup$
      – Ant
      Dec 9 '14 at 16:44










    • $begingroup$
      Why is this statement unprovable?
      $endgroup$
      – Marco Flores
      Dec 27 '14 at 5:13






    • 2




      $begingroup$
      @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
      $endgroup$
      – chiastic-security
      Dec 27 '14 at 8:09
















    19












    $begingroup$

    The one I find most intuitive, as an unprovable statement from ZF without Axiom of Choice, is that for any two sets X and Y, either there's an injective function from X to Y, or there's one from Y to X.



    Roughly, and informally, I read this as: either X is at least as big as Y, or Y is at least as big as X.



    I mean, what's the alternative? They're both bigger than each other?!






    share|cite|improve this answer









    $endgroup$









    • 4




      $begingroup$
      There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
      $endgroup$
      – murray
      Dec 7 '14 at 17:46










    • $begingroup$
      @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
      $endgroup$
      – Ant
      Dec 9 '14 at 16:44










    • $begingroup$
      Why is this statement unprovable?
      $endgroup$
      – Marco Flores
      Dec 27 '14 at 5:13






    • 2




      $begingroup$
      @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
      $endgroup$
      – chiastic-security
      Dec 27 '14 at 8:09














    19












    19








    19





    $begingroup$

    The one I find most intuitive, as an unprovable statement from ZF without Axiom of Choice, is that for any two sets X and Y, either there's an injective function from X to Y, or there's one from Y to X.



    Roughly, and informally, I read this as: either X is at least as big as Y, or Y is at least as big as X.



    I mean, what's the alternative? They're both bigger than each other?!






    share|cite|improve this answer









    $endgroup$



    The one I find most intuitive, as an unprovable statement from ZF without Axiom of Choice, is that for any two sets X and Y, either there's an injective function from X to Y, or there's one from Y to X.



    Roughly, and informally, I read this as: either X is at least as big as Y, or Y is at least as big as X.



    I mean, what's the alternative? They're both bigger than each other?!







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 6 '14 at 19:35









    chiastic-securitychiastic-security

    625312




    625312








    • 4




      $begingroup$
      There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
      $endgroup$
      – murray
      Dec 7 '14 at 17:46










    • $begingroup$
      @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
      $endgroup$
      – Ant
      Dec 9 '14 at 16:44










    • $begingroup$
      Why is this statement unprovable?
      $endgroup$
      – Marco Flores
      Dec 27 '14 at 5:13






    • 2




      $begingroup$
      @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
      $endgroup$
      – chiastic-security
      Dec 27 '14 at 8:09














    • 4




      $begingroup$
      There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
      $endgroup$
      – murray
      Dec 7 '14 at 17:46










    • $begingroup$
      @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
      $endgroup$
      – Ant
      Dec 9 '14 at 16:44










    • $begingroup$
      Why is this statement unprovable?
      $endgroup$
      – Marco Flores
      Dec 27 '14 at 5:13






    • 2




      $begingroup$
      @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
      $endgroup$
      – chiastic-security
      Dec 27 '14 at 8:09








    4




    4




    $begingroup$
    There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
    $endgroup$
    – murray
    Dec 7 '14 at 17:46




    $begingroup$
    There's a second alternative: neither $X$ nor $Y$ is bigger than the other!
    $endgroup$
    – murray
    Dec 7 '14 at 17:46












    $begingroup$
    @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
    $endgroup$
    – Ant
    Dec 9 '14 at 16:44




    $begingroup$
    @murray At least as big.. if $X$ and $Y$ are "of the same size", then it is true that $X$ is at least as big as $Y$ and the viceversa is also true
    $endgroup$
    – Ant
    Dec 9 '14 at 16:44












    $begingroup$
    Why is this statement unprovable?
    $endgroup$
    – Marco Flores
    Dec 27 '14 at 5:13




    $begingroup$
    Why is this statement unprovable?
    $endgroup$
    – Marco Flores
    Dec 27 '14 at 5:13




    2




    2




    $begingroup$
    @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
    $endgroup$
    – chiastic-security
    Dec 27 '14 at 8:09




    $begingroup$
    @MarcoFlores it's provably equivalent to the axiom of choice, which is provably independent of the axioms of ZF.
    $endgroup$
    – chiastic-security
    Dec 27 '14 at 8:09











    18












    $begingroup$

    In $mathsf{ZF}$ (i.e. Zermelo–Fraenkel's set theory axioms, without the Axiom of Choice) the following statements (among many many others) are unprovable:




    1. Countable union of countable sets is countable.

    2. Every surjective function has a right-inverse.

    3. Every vector space has a basis.

    4. Every ring has a maximal ideal.


    These statements are not exactly "intuitively true to the layperson", but seem natural to many mathematicians. In particular, (2) is probably taught in every math university during the first week of the first year.



    If you are interested in models of $mathsf{ZF}$ in which (1),(2),(3) or (4) don't hold, you can start taking a look at Axiom of Choice, by Horst Herrlich. It has a very nice and well organised Appendix where you can look for models depending on which (main) statements they satisfy.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:20






    • 2




      $begingroup$
      @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:07












    • $begingroup$
      And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:09


















    18












    $begingroup$

    In $mathsf{ZF}$ (i.e. Zermelo–Fraenkel's set theory axioms, without the Axiom of Choice) the following statements (among many many others) are unprovable:




    1. Countable union of countable sets is countable.

    2. Every surjective function has a right-inverse.

    3. Every vector space has a basis.

    4. Every ring has a maximal ideal.


    These statements are not exactly "intuitively true to the layperson", but seem natural to many mathematicians. In particular, (2) is probably taught in every math university during the first week of the first year.



    If you are interested in models of $mathsf{ZF}$ in which (1),(2),(3) or (4) don't hold, you can start taking a look at Axiom of Choice, by Horst Herrlich. It has a very nice and well organised Appendix where you can look for models depending on which (main) statements they satisfy.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:20






    • 2




      $begingroup$
      @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:07












    • $begingroup$
      And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:09
















    18












    18








    18





    $begingroup$

    In $mathsf{ZF}$ (i.e. Zermelo–Fraenkel's set theory axioms, without the Axiom of Choice) the following statements (among many many others) are unprovable:




    1. Countable union of countable sets is countable.

    2. Every surjective function has a right-inverse.

    3. Every vector space has a basis.

    4. Every ring has a maximal ideal.


    These statements are not exactly "intuitively true to the layperson", but seem natural to many mathematicians. In particular, (2) is probably taught in every math university during the first week of the first year.



    If you are interested in models of $mathsf{ZF}$ in which (1),(2),(3) or (4) don't hold, you can start taking a look at Axiom of Choice, by Horst Herrlich. It has a very nice and well organised Appendix where you can look for models depending on which (main) statements they satisfy.






    share|cite|improve this answer









    $endgroup$



    In $mathsf{ZF}$ (i.e. Zermelo–Fraenkel's set theory axioms, without the Axiom of Choice) the following statements (among many many others) are unprovable:




    1. Countable union of countable sets is countable.

    2. Every surjective function has a right-inverse.

    3. Every vector space has a basis.

    4. Every ring has a maximal ideal.


    These statements are not exactly "intuitively true to the layperson", but seem natural to many mathematicians. In particular, (2) is probably taught in every math university during the first week of the first year.



    If you are interested in models of $mathsf{ZF}$ in which (1),(2),(3) or (4) don't hold, you can start taking a look at Axiom of Choice, by Horst Herrlich. It has a very nice and well organised Appendix where you can look for models depending on which (main) statements they satisfy.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 5 '14 at 3:35









    aerdna91aerdna91

    716314




    716314












    • $begingroup$
      Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:20






    • 2




      $begingroup$
      @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:07












    • $begingroup$
      And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:09




















    • $begingroup$
      Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 19:20






    • 2




      $begingroup$
      @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:07












    • $begingroup$
      And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
      $endgroup$
      – aerdna91
      Dec 5 '14 at 22:09


















    $begingroup$
    Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:20




    $begingroup$
    Great list. #2 and #3 I especially like. They are all great examples, but like you pointed out not necessarily accessible to the layperson. Most people who have taken a university math class could get #2, but to see it's relationship to incompleteness you would have to understand the Axiom of Choice pretty well, and therefore set theory and how integers and reals are built from sets, right?
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 19:20




    2




    2




    $begingroup$
    @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:07






    $begingroup$
    @MichaelHarris It depends on what you meen by "relationship". Look at Proof 1 here: proofwiki.org/wiki/Surjection_iff_Right_Inverse. It is a very simple proof, and it's easy to understand why it relies on the Axiom of Choice. So it's clear that $mathsf{ZFC}$ can prove (2). Of course now you might ask a different question: are we sure that it is impossible to prove (2) in $mathsf{ZF}$? The answer is YES, but the proof of this fact is all but easy, since it uses quite an advanced tool from set theory, namely forcing.
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:07














    $begingroup$
    And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:09






    $begingroup$
    And to understand how forcing works is much more difficult than understanding the axioms of $mathsf{ZF}$. Or how $mathbb Z$ and $mathbb R$ are built (which I actually think is not even strictly needed to understand forcing).
    $endgroup$
    – aerdna91
    Dec 5 '14 at 22:09













    18












    $begingroup$

    Any statement which is not logically valid (read: always true) is unprovable. The statement $exists xexists y(x>y)$ is not provable from the theory of linear orders, since it is false in the singleton order. On the other hand, it is not disprovable since any other order type would satisfy it.



    The statement $exists x(x^2-2=0)$ is not provable from the axioms of the field, since $Bbb Q$ thinks this is false, and $Bbb C$ thinks it is true.



    The statement "$G$ is an Abelian group" is not provable since given a group $G$ it can be Abelian and it could be non-Abelian.



    The statement "$fcolonBbb{Rto R}$ is continuous/differentiable/continuously differentiable/smooth/analytic/a polynomial" and so on and so forth, are all unprovable, because just like that given an arbitrary function we don't know anything about it. Even if we know it is continuous we can't know if it is continuously differentiable, or smooth, or anything else. So these are all additional assumptions we have to make.



    Of course, given a particular function, like $f(x)=e^x$ we can sit down and prove things about it, but the statement "$f$ is a continuous function" cannot be proved or disproved until further assumptions are added.



    And that's the point that I am trying to make here. Every statement which cannot be always proved will be unprovable from some assumptions. But you ask for an intuitive statement, and that causes a problem.



    The problem with "intuitive statement" is that the more you work in mathematics, the more your intuition is decomposed and reconstructed according to the topic you work with. The continuum hypothesis is perfectly intuitive and simple for me, it is true that understanding how it can be unprovable is difficult, but the statement itself is not very difficult once you cleared up the basic notions like cardinality and power sets.



    Finally, let me just add that there are plenty of theories which are complete and consistent and we work with them. Some of them are even recursively enumerable. The incompleteness theorem gives us three conditions from which incompleteness follows, any two won't suffice. (1) Consistent, (2) Recursively enumerable, (3) Interprets arithmetics.



    There are complete theories which satisfy the first two, and there are complete theories which are consistent and interpret arithmetics, and of course any inconsistent theory is complete.






    share|cite|improve this answer









    $endgroup$









    • 13




      $begingroup$
      I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 8:19










    • $begingroup$
      I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
      $endgroup$
      – David Z
      Dec 5 '14 at 8:49






    • 1




      $begingroup$
      @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
      $endgroup$
      – Turion
      Dec 5 '14 at 15:18






    • 1




      $begingroup$
      @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 15:28






    • 1




      $begingroup$
      I am starting to suspect there is something personal about these downvotes.
      $endgroup$
      – Asaf Karagila
      Dec 8 '14 at 7:02
















    18












    $begingroup$

    Any statement which is not logically valid (read: always true) is unprovable. The statement $exists xexists y(x>y)$ is not provable from the theory of linear orders, since it is false in the singleton order. On the other hand, it is not disprovable since any other order type would satisfy it.



    The statement $exists x(x^2-2=0)$ is not provable from the axioms of the field, since $Bbb Q$ thinks this is false, and $Bbb C$ thinks it is true.



    The statement "$G$ is an Abelian group" is not provable since given a group $G$ it can be Abelian and it could be non-Abelian.



    The statement "$fcolonBbb{Rto R}$ is continuous/differentiable/continuously differentiable/smooth/analytic/a polynomial" and so on and so forth, are all unprovable, because just like that given an arbitrary function we don't know anything about it. Even if we know it is continuous we can't know if it is continuously differentiable, or smooth, or anything else. So these are all additional assumptions we have to make.



    Of course, given a particular function, like $f(x)=e^x$ we can sit down and prove things about it, but the statement "$f$ is a continuous function" cannot be proved or disproved until further assumptions are added.



    And that's the point that I am trying to make here. Every statement which cannot be always proved will be unprovable from some assumptions. But you ask for an intuitive statement, and that causes a problem.



    The problem with "intuitive statement" is that the more you work in mathematics, the more your intuition is decomposed and reconstructed according to the topic you work with. The continuum hypothesis is perfectly intuitive and simple for me, it is true that understanding how it can be unprovable is difficult, but the statement itself is not very difficult once you cleared up the basic notions like cardinality and power sets.



    Finally, let me just add that there are plenty of theories which are complete and consistent and we work with them. Some of them are even recursively enumerable. The incompleteness theorem gives us three conditions from which incompleteness follows, any two won't suffice. (1) Consistent, (2) Recursively enumerable, (3) Interprets arithmetics.



    There are complete theories which satisfy the first two, and there are complete theories which are consistent and interpret arithmetics, and of course any inconsistent theory is complete.






    share|cite|improve this answer









    $endgroup$









    • 13




      $begingroup$
      I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 8:19










    • $begingroup$
      I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
      $endgroup$
      – David Z
      Dec 5 '14 at 8:49






    • 1




      $begingroup$
      @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
      $endgroup$
      – Turion
      Dec 5 '14 at 15:18






    • 1




      $begingroup$
      @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 15:28






    • 1




      $begingroup$
      I am starting to suspect there is something personal about these downvotes.
      $endgroup$
      – Asaf Karagila
      Dec 8 '14 at 7:02














    18












    18








    18





    $begingroup$

    Any statement which is not logically valid (read: always true) is unprovable. The statement $exists xexists y(x>y)$ is not provable from the theory of linear orders, since it is false in the singleton order. On the other hand, it is not disprovable since any other order type would satisfy it.



    The statement $exists x(x^2-2=0)$ is not provable from the axioms of the field, since $Bbb Q$ thinks this is false, and $Bbb C$ thinks it is true.



    The statement "$G$ is an Abelian group" is not provable since given a group $G$ it can be Abelian and it could be non-Abelian.



    The statement "$fcolonBbb{Rto R}$ is continuous/differentiable/continuously differentiable/smooth/analytic/a polynomial" and so on and so forth, are all unprovable, because just like that given an arbitrary function we don't know anything about it. Even if we know it is continuous we can't know if it is continuously differentiable, or smooth, or anything else. So these are all additional assumptions we have to make.



    Of course, given a particular function, like $f(x)=e^x$ we can sit down and prove things about it, but the statement "$f$ is a continuous function" cannot be proved or disproved until further assumptions are added.



    And that's the point that I am trying to make here. Every statement which cannot be always proved will be unprovable from some assumptions. But you ask for an intuitive statement, and that causes a problem.



    The problem with "intuitive statement" is that the more you work in mathematics, the more your intuition is decomposed and reconstructed according to the topic you work with. The continuum hypothesis is perfectly intuitive and simple for me, it is true that understanding how it can be unprovable is difficult, but the statement itself is not very difficult once you cleared up the basic notions like cardinality and power sets.



    Finally, let me just add that there are plenty of theories which are complete and consistent and we work with them. Some of them are even recursively enumerable. The incompleteness theorem gives us three conditions from which incompleteness follows, any two won't suffice. (1) Consistent, (2) Recursively enumerable, (3) Interprets arithmetics.



    There are complete theories which satisfy the first two, and there are complete theories which are consistent and interpret arithmetics, and of course any inconsistent theory is complete.






    share|cite|improve this answer









    $endgroup$



    Any statement which is not logically valid (read: always true) is unprovable. The statement $exists xexists y(x>y)$ is not provable from the theory of linear orders, since it is false in the singleton order. On the other hand, it is not disprovable since any other order type would satisfy it.



    The statement $exists x(x^2-2=0)$ is not provable from the axioms of the field, since $Bbb Q$ thinks this is false, and $Bbb C$ thinks it is true.



    The statement "$G$ is an Abelian group" is not provable since given a group $G$ it can be Abelian and it could be non-Abelian.



    The statement "$fcolonBbb{Rto R}$ is continuous/differentiable/continuously differentiable/smooth/analytic/a polynomial" and so on and so forth, are all unprovable, because just like that given an arbitrary function we don't know anything about it. Even if we know it is continuous we can't know if it is continuously differentiable, or smooth, or anything else. So these are all additional assumptions we have to make.



    Of course, given a particular function, like $f(x)=e^x$ we can sit down and prove things about it, but the statement "$f$ is a continuous function" cannot be proved or disproved until further assumptions are added.



    And that's the point that I am trying to make here. Every statement which cannot be always proved will be unprovable from some assumptions. But you ask for an intuitive statement, and that causes a problem.



    The problem with "intuitive statement" is that the more you work in mathematics, the more your intuition is decomposed and reconstructed according to the topic you work with. The continuum hypothesis is perfectly intuitive and simple for me, it is true that understanding how it can be unprovable is difficult, but the statement itself is not very difficult once you cleared up the basic notions like cardinality and power sets.



    Finally, let me just add that there are plenty of theories which are complete and consistent and we work with them. Some of them are even recursively enumerable. The incompleteness theorem gives us three conditions from which incompleteness follows, any two won't suffice. (1) Consistent, (2) Recursively enumerable, (3) Interprets arithmetics.



    There are complete theories which satisfy the first two, and there are complete theories which are consistent and interpret arithmetics, and of course any inconsistent theory is complete.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 5 '14 at 8:04









    Asaf KaragilaAsaf Karagila

    305k33435766




    305k33435766








    • 13




      $begingroup$
      I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 8:19










    • $begingroup$
      I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
      $endgroup$
      – David Z
      Dec 5 '14 at 8:49






    • 1




      $begingroup$
      @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
      $endgroup$
      – Turion
      Dec 5 '14 at 15:18






    • 1




      $begingroup$
      @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 15:28






    • 1




      $begingroup$
      I am starting to suspect there is something personal about these downvotes.
      $endgroup$
      – Asaf Karagila
      Dec 8 '14 at 7:02














    • 13




      $begingroup$
      I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 8:19










    • $begingroup$
      I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
      $endgroup$
      – David Z
      Dec 5 '14 at 8:49






    • 1




      $begingroup$
      @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
      $endgroup$
      – Turion
      Dec 5 '14 at 15:18






    • 1




      $begingroup$
      @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
      $endgroup$
      – Asaf Karagila
      Dec 5 '14 at 15:28






    • 1




      $begingroup$
      I am starting to suspect there is something personal about these downvotes.
      $endgroup$
      – Asaf Karagila
      Dec 8 '14 at 7:02








    13




    13




    $begingroup$
    I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 8:19




    $begingroup$
    I'm not a fan of "Everything should be explainable to the layperson". If everything was explainable to the layperson, why do we have to spend so many years studying before we can understand something correctly, even at the intuitive level? Why is it that when someone explains to me the gist of something in my own field I know that there's a good chance that I have no idea what it really does? Thinking that a few examples make it clearer is wishful thinking. From both parties involved.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 8:19












    $begingroup$
    I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
    $endgroup$
    – David Z
    Dec 5 '14 at 8:49




    $begingroup$
    I agree with that, but I do still think there is considerable value in trying to explain complex concepts in a manner accessible to laypeople - not just to the laypeople it is being explained to, but also to the experts doing the explaining.
    $endgroup$
    – David Z
    Dec 5 '14 at 8:49




    1




    1




    $begingroup$
    @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
    $endgroup$
    – Turion
    Dec 5 '14 at 15:18




    $begingroup$
    @AsafKaragila, there is a considerable difference in explaining something to a layperson in such a way that they are satisfied and understand why we are doing it, and explaining it so that they understand it in the same rigor like us, or in your words, "correctly". The latter requires a maths degree. But the former is something I do on a regular basis to people without mathematical background, and I do quantum gravity and category theory. And it's not an 'inferior' or 'worse' way of explaining, it's just explaining less.
    $endgroup$
    – Turion
    Dec 5 '14 at 15:18




    1




    1




    $begingroup$
    @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 15:28




    $begingroup$
    @Turion: I find that explaining in very broad strokes and skipping the details you end up either giving the wrong impression or lying through your nose. I do that too, of course, and I tell people that I'm currently misleading them and there is a lot more to it. But I often feel that the oversimplification is running against the ultimate cause, which is to get people interested more in whatever you're telling them.
    $endgroup$
    – Asaf Karagila
    Dec 5 '14 at 15:28




    1




    1




    $begingroup$
    I am starting to suspect there is something personal about these downvotes.
    $endgroup$
    – Asaf Karagila
    Dec 8 '14 at 7:02




    $begingroup$
    I am starting to suspect there is something personal about these downvotes.
    $endgroup$
    – Asaf Karagila
    Dec 8 '14 at 7:02











    17












    $begingroup$

    Most laypersons will understand the following. If you have a file containing random data that is larger than 1 GB in size, then it's unlikely that it could be compressed to a self-extracting file of size less than 1 MB. The probability is astronomically small that such a self-extracting program could generate your file.



    But while the vast majority of such files cannot be compressed to under 1 MB in size, you can never have a mathematical proof of that fact for any specific file. This is because you can generate all such proofs recursively using a small program. Have this program stop at the first proven theorem that says that such and such a file larger than 1 GB cannot be compressed, and output that large file. If the program outputs, that means the program is the small self-extracting program (compressed) version of its output, the very output that the theorem says cannot be compressed, which is a contradiction.






    share|cite|improve this answer











    $endgroup$









    • 4




      $begingroup$
      Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
      $endgroup$
      – wchargin
      Dec 6 '14 at 17:19










    • $begingroup$
      How does one know that the theorem itself will be small?
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:59










    • $begingroup$
      @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
      $endgroup$
      – Gordon Davisson
      Dec 7 '14 at 8:54










    • $begingroup$
      Um, how do we know it will?
      $endgroup$
      – Soham Chowdhury
      Dec 7 '14 at 12:59










    • $begingroup$
      I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
      $endgroup$
      – Count Iblis
      Dec 8 '14 at 3:32
















    17












    $begingroup$

    Most laypersons will understand the following. If you have a file containing random data that is larger than 1 GB in size, then it's unlikely that it could be compressed to a self-extracting file of size less than 1 MB. The probability is astronomically small that such a self-extracting program could generate your file.



    But while the vast majority of such files cannot be compressed to under 1 MB in size, you can never have a mathematical proof of that fact for any specific file. This is because you can generate all such proofs recursively using a small program. Have this program stop at the first proven theorem that says that such and such a file larger than 1 GB cannot be compressed, and output that large file. If the program outputs, that means the program is the small self-extracting program (compressed) version of its output, the very output that the theorem says cannot be compressed, which is a contradiction.






    share|cite|improve this answer











    $endgroup$









    • 4




      $begingroup$
      Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
      $endgroup$
      – wchargin
      Dec 6 '14 at 17:19










    • $begingroup$
      How does one know that the theorem itself will be small?
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:59










    • $begingroup$
      @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
      $endgroup$
      – Gordon Davisson
      Dec 7 '14 at 8:54










    • $begingroup$
      Um, how do we know it will?
      $endgroup$
      – Soham Chowdhury
      Dec 7 '14 at 12:59










    • $begingroup$
      I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
      $endgroup$
      – Count Iblis
      Dec 8 '14 at 3:32














    17












    17








    17





    $begingroup$

    Most laypersons will understand the following. If you have a file containing random data that is larger than 1 GB in size, then it's unlikely that it could be compressed to a self-extracting file of size less than 1 MB. The probability is astronomically small that such a self-extracting program could generate your file.



    But while the vast majority of such files cannot be compressed to under 1 MB in size, you can never have a mathematical proof of that fact for any specific file. This is because you can generate all such proofs recursively using a small program. Have this program stop at the first proven theorem that says that such and such a file larger than 1 GB cannot be compressed, and output that large file. If the program outputs, that means the program is the small self-extracting program (compressed) version of its output, the very output that the theorem says cannot be compressed, which is a contradiction.






    share|cite|improve this answer











    $endgroup$



    Most laypersons will understand the following. If you have a file containing random data that is larger than 1 GB in size, then it's unlikely that it could be compressed to a self-extracting file of size less than 1 MB. The probability is astronomically small that such a self-extracting program could generate your file.



    But while the vast majority of such files cannot be compressed to under 1 MB in size, you can never have a mathematical proof of that fact for any specific file. This is because you can generate all such proofs recursively using a small program. Have this program stop at the first proven theorem that says that such and such a file larger than 1 GB cannot be compressed, and output that large file. If the program outputs, that means the program is the small self-extracting program (compressed) version of its output, the very output that the theorem says cannot be compressed, which is a contradiction.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 6 '14 at 3:19









    Dan Getz

    1032




    1032










    answered Dec 5 '14 at 18:20









    Count IblisCount Iblis

    8,30421533




    8,30421533








    • 4




      $begingroup$
      Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
      $endgroup$
      – wchargin
      Dec 6 '14 at 17:19










    • $begingroup$
      How does one know that the theorem itself will be small?
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:59










    • $begingroup$
      @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
      $endgroup$
      – Gordon Davisson
      Dec 7 '14 at 8:54










    • $begingroup$
      Um, how do we know it will?
      $endgroup$
      – Soham Chowdhury
      Dec 7 '14 at 12:59










    • $begingroup$
      I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
      $endgroup$
      – Count Iblis
      Dec 8 '14 at 3:32














    • 4




      $begingroup$
      Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
      $endgroup$
      – wchargin
      Dec 6 '14 at 17:19










    • $begingroup$
      How does one know that the theorem itself will be small?
      $endgroup$
      – Soham Chowdhury
      Dec 6 '14 at 18:59










    • $begingroup$
      @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
      $endgroup$
      – Gordon Davisson
      Dec 7 '14 at 8:54










    • $begingroup$
      Um, how do we know it will?
      $endgroup$
      – Soham Chowdhury
      Dec 7 '14 at 12:59










    • $begingroup$
      I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
      $endgroup$
      – Count Iblis
      Dec 8 '14 at 3:32








    4




    4




    $begingroup$
    Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
    $endgroup$
    – wchargin
    Dec 6 '14 at 17:19




    $begingroup$
    Interesting. Though, of course, practically, this would take $mathcal{O}(text{way too long})$ time to execute.
    $endgroup$
    – wchargin
    Dec 6 '14 at 17:19












    $begingroup$
    How does one know that the theorem itself will be small?
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:59




    $begingroup$
    How does one know that the theorem itself will be small?
    $endgroup$
    – Soham Chowdhury
    Dec 6 '14 at 18:59












    $begingroup$
    @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
    $endgroup$
    – Gordon Davisson
    Dec 7 '14 at 8:54




    $begingroup$
    @SohamChowdhury The size of the theorem doesn't matter, as long as the program to search for it is under 1 MB.
    $endgroup$
    – Gordon Davisson
    Dec 7 '14 at 8:54












    $begingroup$
    Um, how do we know it will?
    $endgroup$
    – Soham Chowdhury
    Dec 7 '14 at 12:59




    $begingroup$
    Um, how do we know it will?
    $endgroup$
    – Soham Chowdhury
    Dec 7 '14 at 12:59












    $begingroup$
    I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
    $endgroup$
    – Count Iblis
    Dec 8 '14 at 3:32




    $begingroup$
    I think there are proof checker algorithms that are just a few hundred lines of codes long, so it should be doable using a lot less than 1 MB.
    $endgroup$
    – Count Iblis
    Dec 8 '14 at 3:32











    13












    $begingroup$

    The problem with your goal is this:
    There are conjectures that are currently unknown (i.e., with our current knowledge, they could be provably right, or provably wrong, or undecidable from the generally accepted axiom systems) and simple enough to formulate so that a layperson can understands their underlying concepts. Some examples are




    • Goldbach's conjecture

    • Twin prime conjecture

    • The $3n+1$ problem

    • All perfect numbers are even

    • $pi$ is a normal number

    • $e+pi$ is irrational


    For most such conjectures there is numerical evidence for them to hold up to the very limits of computational search - but does that make them "intuitively true" for the layperson?
    If any of these should ever turn out to be undecidable, we'd be in the position to add one of two conflicting axioms to our inventory, e.g., one of "There exists a natural number $N$ that cannot be written as sum of two primes" or "Goldbach is true". When picking the first choice, we'd know that $N$ cannot be reached in finite time by counting $1,2,3,ldots$ as for any number reachable this way in finite time can also be checked in finite time if it can or cannot be written as sum of two primes. Therefore, we'd know intuitively that the "real-life" natural numbers do not contain such $N$, i.e. the only "correct" extension of our axiom system is that Goldbach is true. This argument works for some others: If "all perfect numbers are even" is independent, then it is true. In general, any independent $Π_1$-sentence is true in the natural numbers. This fact is equivalent to the $Σ_1$-completeness of first-order Peano Arithmetic. Currently, the twin prime conjecture and Collatz conjecture and irrationality of $e+π$ are only known to be equivalent to $Π_2$-sentences, so we cannot apply this argument to them.



    Besides the above possibilities, other possibly independent statements include:




    • Those specifically constructed to be independent (of the "I am unprovable" kind) that are totally dull and unrelated to any real-life mathematics.

    • Those that worthy of being added (positively or negatively) to $mathsf{ZFC}$ without there being a very natural preference in one direction or the other (such as the Continuum Hypothesis; or already the Axiom of Choice if you start with $mathsf{ZF}$). I doubt that any of these could be considered intuitively clear for the layperson.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
      $endgroup$
      – Lehs
      Dec 6 '14 at 17:57










    • $begingroup$
      So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
      $endgroup$
      – Michael Harris
      Dec 6 '14 at 20:29






    • 1




      $begingroup$
      @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
      $endgroup$
      – Hagen von Eitzen
      Dec 7 '14 at 18:47










    • $begingroup$
      I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
      $endgroup$
      – Steven Stadnicki
      Dec 8 '14 at 1:11






    • 1




      $begingroup$
      @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
      $endgroup$
      – user21820
      Feb 24 '17 at 13:40


















    13












    $begingroup$

    The problem with your goal is this:
    There are conjectures that are currently unknown (i.e., with our current knowledge, they could be provably right, or provably wrong, or undecidable from the generally accepted axiom systems) and simple enough to formulate so that a layperson can understands their underlying concepts. Some examples are




    • Goldbach's conjecture

    • Twin prime conjecture

    • The $3n+1$ problem

    • All perfect numbers are even

    • $pi$ is a normal number

    • $e+pi$ is irrational


    For most such conjectures there is numerical evidence for them to hold up to the very limits of computational search - but does that make them "intuitively true" for the layperson?
    If any of these should ever turn out to be undecidable, we'd be in the position to add one of two conflicting axioms to our inventory, e.g., one of "There exists a natural number $N$ that cannot be written as sum of two primes" or "Goldbach is true". When picking the first choice, we'd know that $N$ cannot be reached in finite time by counting $1,2,3,ldots$ as for any number reachable this way in finite time can also be checked in finite time if it can or cannot be written as sum of two primes. Therefore, we'd know intuitively that the "real-life" natural numbers do not contain such $N$, i.e. the only "correct" extension of our axiom system is that Goldbach is true. This argument works for some others: If "all perfect numbers are even" is independent, then it is true. In general, any independent $Π_1$-sentence is true in the natural numbers. This fact is equivalent to the $Σ_1$-completeness of first-order Peano Arithmetic. Currently, the twin prime conjecture and Collatz conjecture and irrationality of $e+π$ are only known to be equivalent to $Π_2$-sentences, so we cannot apply this argument to them.



    Besides the above possibilities, other possibly independent statements include:




    • Those specifically constructed to be independent (of the "I am unprovable" kind) that are totally dull and unrelated to any real-life mathematics.

    • Those that worthy of being added (positively or negatively) to $mathsf{ZFC}$ without there being a very natural preference in one direction or the other (such as the Continuum Hypothesis; or already the Axiom of Choice if you start with $mathsf{ZF}$). I doubt that any of these could be considered intuitively clear for the layperson.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
      $endgroup$
      – Lehs
      Dec 6 '14 at 17:57










    • $begingroup$
      So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
      $endgroup$
      – Michael Harris
      Dec 6 '14 at 20:29






    • 1




      $begingroup$
      @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
      $endgroup$
      – Hagen von Eitzen
      Dec 7 '14 at 18:47










    • $begingroup$
      I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
      $endgroup$
      – Steven Stadnicki
      Dec 8 '14 at 1:11






    • 1




      $begingroup$
      @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
      $endgroup$
      – user21820
      Feb 24 '17 at 13:40
















    13












    13








    13





    $begingroup$

    The problem with your goal is this:
    There are conjectures that are currently unknown (i.e., with our current knowledge, they could be provably right, or provably wrong, or undecidable from the generally accepted axiom systems) and simple enough to formulate so that a layperson can understands their underlying concepts. Some examples are




    • Goldbach's conjecture

    • Twin prime conjecture

    • The $3n+1$ problem

    • All perfect numbers are even

    • $pi$ is a normal number

    • $e+pi$ is irrational


    For most such conjectures there is numerical evidence for them to hold up to the very limits of computational search - but does that make them "intuitively true" for the layperson?
    If any of these should ever turn out to be undecidable, we'd be in the position to add one of two conflicting axioms to our inventory, e.g., one of "There exists a natural number $N$ that cannot be written as sum of two primes" or "Goldbach is true". When picking the first choice, we'd know that $N$ cannot be reached in finite time by counting $1,2,3,ldots$ as for any number reachable this way in finite time can also be checked in finite time if it can or cannot be written as sum of two primes. Therefore, we'd know intuitively that the "real-life" natural numbers do not contain such $N$, i.e. the only "correct" extension of our axiom system is that Goldbach is true. This argument works for some others: If "all perfect numbers are even" is independent, then it is true. In general, any independent $Π_1$-sentence is true in the natural numbers. This fact is equivalent to the $Σ_1$-completeness of first-order Peano Arithmetic. Currently, the twin prime conjecture and Collatz conjecture and irrationality of $e+π$ are only known to be equivalent to $Π_2$-sentences, so we cannot apply this argument to them.



    Besides the above possibilities, other possibly independent statements include:




    • Those specifically constructed to be independent (of the "I am unprovable" kind) that are totally dull and unrelated to any real-life mathematics.

    • Those that worthy of being added (positively or negatively) to $mathsf{ZFC}$ without there being a very natural preference in one direction or the other (such as the Continuum Hypothesis; or already the Axiom of Choice if you start with $mathsf{ZF}$). I doubt that any of these could be considered intuitively clear for the layperson.






    share|cite|improve this answer











    $endgroup$



    The problem with your goal is this:
    There are conjectures that are currently unknown (i.e., with our current knowledge, they could be provably right, or provably wrong, or undecidable from the generally accepted axiom systems) and simple enough to formulate so that a layperson can understands their underlying concepts. Some examples are




    • Goldbach's conjecture

    • Twin prime conjecture

    • The $3n+1$ problem

    • All perfect numbers are even

    • $pi$ is a normal number

    • $e+pi$ is irrational


    For most such conjectures there is numerical evidence for them to hold up to the very limits of computational search - but does that make them "intuitively true" for the layperson?
    If any of these should ever turn out to be undecidable, we'd be in the position to add one of two conflicting axioms to our inventory, e.g., one of "There exists a natural number $N$ that cannot be written as sum of two primes" or "Goldbach is true". When picking the first choice, we'd know that $N$ cannot be reached in finite time by counting $1,2,3,ldots$ as for any number reachable this way in finite time can also be checked in finite time if it can or cannot be written as sum of two primes. Therefore, we'd know intuitively that the "real-life" natural numbers do not contain such $N$, i.e. the only "correct" extension of our axiom system is that Goldbach is true. This argument works for some others: If "all perfect numbers are even" is independent, then it is true. In general, any independent $Π_1$-sentence is true in the natural numbers. This fact is equivalent to the $Σ_1$-completeness of first-order Peano Arithmetic. Currently, the twin prime conjecture and Collatz conjecture and irrationality of $e+π$ are only known to be equivalent to $Π_2$-sentences, so we cannot apply this argument to them.



    Besides the above possibilities, other possibly independent statements include:




    • Those specifically constructed to be independent (of the "I am unprovable" kind) that are totally dull and unrelated to any real-life mathematics.

    • Those that worthy of being added (positively or negatively) to $mathsf{ZFC}$ without there being a very natural preference in one direction or the other (such as the Continuum Hypothesis; or already the Axiom of Choice if you start with $mathsf{ZF}$). I doubt that any of these could be considered intuitively clear for the layperson.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 13 '17 at 5:51









    user21820

    39.2k543154




    39.2k543154










    answered Dec 6 '14 at 13:20









    Hagen von EitzenHagen von Eitzen

    281k23272505




    281k23272505












    • $begingroup$
      I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
      $endgroup$
      – Lehs
      Dec 6 '14 at 17:57










    • $begingroup$
      So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
      $endgroup$
      – Michael Harris
      Dec 6 '14 at 20:29






    • 1




      $begingroup$
      @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
      $endgroup$
      – Hagen von Eitzen
      Dec 7 '14 at 18:47










    • $begingroup$
      I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
      $endgroup$
      – Steven Stadnicki
      Dec 8 '14 at 1:11






    • 1




      $begingroup$
      @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
      $endgroup$
      – user21820
      Feb 24 '17 at 13:40




















    • $begingroup$
      I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
      $endgroup$
      – Lehs
      Dec 6 '14 at 17:57










    • $begingroup$
      So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
      $endgroup$
      – Michael Harris
      Dec 6 '14 at 20:29






    • 1




      $begingroup$
      @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
      $endgroup$
      – Hagen von Eitzen
      Dec 7 '14 at 18:47










    • $begingroup$
      I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
      $endgroup$
      – Steven Stadnicki
      Dec 8 '14 at 1:11






    • 1




      $begingroup$
      @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
      $endgroup$
      – user21820
      Feb 24 '17 at 13:40


















    $begingroup$
    I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
    $endgroup$
    – Lehs
    Dec 6 '14 at 17:57




    $begingroup$
    I just wonder, if the statement is about natural numbers and of the kind that a counterexample in principle is possible, wouldn't then "no possible proof" be equivalent with true? Since no possible proof means no counterexample? As a natural and necessary assignment?
    $endgroup$
    – Lehs
    Dec 6 '14 at 17:57












    $begingroup$
    So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
    $endgroup$
    – Michael Harris
    Dec 6 '14 at 20:29




    $begingroup$
    So I take this to mean that an open question can go three ways: unprovable, true, or false. If true or false then no problem. If it turns out to be unprovable, then we will likely adopt it as axiomatic in some new system or branch of systems. But whatever that question is, the very fact that it remains an open question means it is likely too complicated for easy understanding. And once something has been shown to be unprovable in the current system, it ceases to be unprovable because mathematicians immediately shift focus to taking it as a new assumtion (axiom) in one direction or another.
    $endgroup$
    – Michael Harris
    Dec 6 '14 at 20:29




    1




    1




    $begingroup$
    @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
    $endgroup$
    – Hagen von Eitzen
    Dec 7 '14 at 18:47




    $begingroup$
    @MichaelHarris I doubt anyone would want axioms like "Goldbach is true" (or false) if G. should turn out unprovable. An axiom should never be so tailored to a specific problem. Also, once CH was shown independent, this didn't caus either $CH$ or $neg CH$ to be adopted as axiom. Instead, people tend to formulate results relying on either of these statements as $If CH then (my result)" or "If not CH then (my result)", thus somwhat keeping the "open" status of CH. But I indeed guess that known to be unprovable in ZF(C) (witout being tailored to be unprovable) implies not suiable for laypersons.
    $endgroup$
    – Hagen von Eitzen
    Dec 7 '14 at 18:47












    $begingroup$
    I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
    $endgroup$
    – Steven Stadnicki
    Dec 8 '14 at 1:11




    $begingroup$
    I think the point about Goldbach should be reinforced: this is a case, and essentially all other number-theory conjectures will behave likewise, where 'unprovable' implies 'functionally true' because any counterexamples would have to be non-standard numbers. This is a problem with almost all natural unprovable statements.
    $endgroup$
    – Steven Stadnicki
    Dec 8 '14 at 1:11




    1




    1




    $begingroup$
    @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
    $endgroup$
    – user21820
    Feb 24 '17 at 13:40






    $begingroup$
    @StevenStadnicki: My above comment contradicts your implicit claim that undecidable universal sentences are true (in the standard model). We can only make that claim for $Π_1$-sentences. For instance, if "every even number greater than $2$ is the sum of two primes" (a $Π_1$-sentence) is undecidable, then it is true and hence "for every natural $n ge 2$ there is an even number greater than $n$ that is not the sum of two primes" (a $Π_2$-sentence) is also undecidable but false. (Note that I accidentally used "unprovable" in my earlier comment but should have used "undecidable".)
    $endgroup$
    – user21820
    Feb 24 '17 at 13:40













    8












    $begingroup$

    There is no natural number, $n$, such that $n$'s interpretation as an ASCII string is a proof of this statement.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Ah, simplicity! Elegance, too! +1
      $endgroup$
      – TobiMcNamobi
      Dec 8 '14 at 14:11


















    8












    $begingroup$

    There is no natural number, $n$, such that $n$'s interpretation as an ASCII string is a proof of this statement.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Ah, simplicity! Elegance, too! +1
      $endgroup$
      – TobiMcNamobi
      Dec 8 '14 at 14:11
















    8












    8








    8





    $begingroup$

    There is no natural number, $n$, such that $n$'s interpretation as an ASCII string is a proof of this statement.






    share|cite|improve this answer









    $endgroup$



    There is no natural number, $n$, such that $n$'s interpretation as an ASCII string is a proof of this statement.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 8 '14 at 6:54









    Aaron GoldenAaron Golden

    796310




    796310












    • $begingroup$
      Ah, simplicity! Elegance, too! +1
      $endgroup$
      – TobiMcNamobi
      Dec 8 '14 at 14:11




















    • $begingroup$
      Ah, simplicity! Elegance, too! +1
      $endgroup$
      – TobiMcNamobi
      Dec 8 '14 at 14:11


















    $begingroup$
    Ah, simplicity! Elegance, too! +1
    $endgroup$
    – TobiMcNamobi
    Dec 8 '14 at 14:11






    $begingroup$
    Ah, simplicity! Elegance, too! +1
    $endgroup$
    – TobiMcNamobi
    Dec 8 '14 at 14:11













    6












    $begingroup$

    You asked




    Can someone give a good example you can point to and say "That's what Godel's incompleteness theorems are talking about"?




    I think you can cut right to the heart of the matter by explaining the Peano axioms, which anyone can understand and which seem as self-evidently true as anything in mathematics. And you can explain how one can use the Peano axioms to prove theorems that are true of the natural numbers, such as $forall a,b. a+b = b+a$ and the like.



    Now, we might like some assurance that these axioms are sound; that is, how do we know that the Peano axioms don't somehow allow us to “prove” something that is actually false?



    Perhaps we could prove that using the Peano axioms themselves, some sort of self-bootstrapping demonstration of the soundness of the axioms?
    Mathematicians at the beginning of the 20th century hoped for just such a demonstration, and their hope was dashed in 1931.



    Gödel's second incompleteness theorem says that the axioms themselves might indeed be able to prove that the axioms were sound—but that if they do, it is only because they are not sound and can prove anything at all, true or false. Sound axioms cannot prove their own soundness.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:45






    • 1




      $begingroup$
      If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
      $endgroup$
      – MJD
      Dec 6 '14 at 0:15
















    6












    $begingroup$

    You asked




    Can someone give a good example you can point to and say "That's what Godel's incompleteness theorems are talking about"?




    I think you can cut right to the heart of the matter by explaining the Peano axioms, which anyone can understand and which seem as self-evidently true as anything in mathematics. And you can explain how one can use the Peano axioms to prove theorems that are true of the natural numbers, such as $forall a,b. a+b = b+a$ and the like.



    Now, we might like some assurance that these axioms are sound; that is, how do we know that the Peano axioms don't somehow allow us to “prove” something that is actually false?



    Perhaps we could prove that using the Peano axioms themselves, some sort of self-bootstrapping demonstration of the soundness of the axioms?
    Mathematicians at the beginning of the 20th century hoped for just such a demonstration, and their hope was dashed in 1931.



    Gödel's second incompleteness theorem says that the axioms themselves might indeed be able to prove that the axioms were sound—but that if they do, it is only because they are not sound and can prove anything at all, true or false. Sound axioms cannot prove their own soundness.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:45






    • 1




      $begingroup$
      If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
      $endgroup$
      – MJD
      Dec 6 '14 at 0:15














    6












    6








    6





    $begingroup$

    You asked




    Can someone give a good example you can point to and say "That's what Godel's incompleteness theorems are talking about"?




    I think you can cut right to the heart of the matter by explaining the Peano axioms, which anyone can understand and which seem as self-evidently true as anything in mathematics. And you can explain how one can use the Peano axioms to prove theorems that are true of the natural numbers, such as $forall a,b. a+b = b+a$ and the like.



    Now, we might like some assurance that these axioms are sound; that is, how do we know that the Peano axioms don't somehow allow us to “prove” something that is actually false?



    Perhaps we could prove that using the Peano axioms themselves, some sort of self-bootstrapping demonstration of the soundness of the axioms?
    Mathematicians at the beginning of the 20th century hoped for just such a demonstration, and their hope was dashed in 1931.



    Gödel's second incompleteness theorem says that the axioms themselves might indeed be able to prove that the axioms were sound—but that if they do, it is only because they are not sound and can prove anything at all, true or false. Sound axioms cannot prove their own soundness.






    share|cite|improve this answer











    $endgroup$



    You asked




    Can someone give a good example you can point to and say "That's what Godel's incompleteness theorems are talking about"?




    I think you can cut right to the heart of the matter by explaining the Peano axioms, which anyone can understand and which seem as self-evidently true as anything in mathematics. And you can explain how one can use the Peano axioms to prove theorems that are true of the natural numbers, such as $forall a,b. a+b = b+a$ and the like.



    Now, we might like some assurance that these axioms are sound; that is, how do we know that the Peano axioms don't somehow allow us to “prove” something that is actually false?



    Perhaps we could prove that using the Peano axioms themselves, some sort of self-bootstrapping demonstration of the soundness of the axioms?
    Mathematicians at the beginning of the 20th century hoped for just such a demonstration, and their hope was dashed in 1931.



    Gödel's second incompleteness theorem says that the axioms themselves might indeed be able to prove that the axioms were sound—but that if they do, it is only because they are not sound and can prove anything at all, true or false. Sound axioms cannot prove their own soundness.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    answered Dec 5 '14 at 2:44


























    community wiki





    MJD













    • $begingroup$
      This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:45






    • 1




      $begingroup$
      If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
      $endgroup$
      – MJD
      Dec 6 '14 at 0:15


















    • $begingroup$
      This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:45






    • 1




      $begingroup$
      If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
      $endgroup$
      – MJD
      Dec 6 '14 at 0:15
















    $begingroup$
    This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:45




    $begingroup$
    This explains the idea of incompleteness very well (as far as I understand it), but it doesn't give a concrete example of what a particular statement that is unprovable is or what it looks like. I could certainly see using this as an introduction to explain the concept, followed up by a concrete example. I suppose what I'm asking might be impossible. By it's very nature, incompleteness seems to only apply to more complex examples, otherwise it wouldn't have taken so long for mathematicians to figure it out.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:45




    1




    1




    $begingroup$
    If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
    $endgroup$
    – MJD
    Dec 6 '14 at 0:15




    $begingroup$
    If you want a concrete example of incompleteness, very simple examples are available. Take the axioms of Euclid's geometry. Remove the parallel postulate, which says that if $L$ is a line and $p$ is a point not on $L$, there is exactly one line $L'$ through $p$ that is parallel to $L$. The parallel postulate is not provable from the remaining axioms. Or: Take the Peano axioms for the natural numbers. Delete the axiom that says that 0 is not the successor of any natural number. This axiom is not provable from the remaining axioms.
    $endgroup$
    – MJD
    Dec 6 '14 at 0:15











    5












    $begingroup$

    Luckily Gödels proof is constructive and so provides an example itself. This is nicely explained in "Gödel, Escher, Bach".



    In short (from what I humbly understand and remember): You can assign a number to every logical statement in your formal context, let's call this the Gödel number of that statement. Then you can construct statements that make propositions about other statements (by referencing the Gödel number, e.g. "the statement with the number xyz is true"). Those statements of course have associated Gödel numbers, too. Now construct a statement "The statement with Gödel number xyz is unprovable" so that the Gödel number of the statement is xyz.



    The Wikipedia entry for this (here) is more detailed but maybe still considered popular science.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:36






    • 1




      $begingroup$
      @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
      $endgroup$
      – TobiMcNamobi
      Dec 6 '14 at 12:48
















    5












    $begingroup$

    Luckily Gödels proof is constructive and so provides an example itself. This is nicely explained in "Gödel, Escher, Bach".



    In short (from what I humbly understand and remember): You can assign a number to every logical statement in your formal context, let's call this the Gödel number of that statement. Then you can construct statements that make propositions about other statements (by referencing the Gödel number, e.g. "the statement with the number xyz is true"). Those statements of course have associated Gödel numbers, too. Now construct a statement "The statement with Gödel number xyz is unprovable" so that the Gödel number of the statement is xyz.



    The Wikipedia entry for this (here) is more detailed but maybe still considered popular science.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:36






    • 1




      $begingroup$
      @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
      $endgroup$
      – TobiMcNamobi
      Dec 6 '14 at 12:48














    5












    5








    5





    $begingroup$

    Luckily Gödels proof is constructive and so provides an example itself. This is nicely explained in "Gödel, Escher, Bach".



    In short (from what I humbly understand and remember): You can assign a number to every logical statement in your formal context, let's call this the Gödel number of that statement. Then you can construct statements that make propositions about other statements (by referencing the Gödel number, e.g. "the statement with the number xyz is true"). Those statements of course have associated Gödel numbers, too. Now construct a statement "The statement with Gödel number xyz is unprovable" so that the Gödel number of the statement is xyz.



    The Wikipedia entry for this (here) is more detailed but maybe still considered popular science.






    share|cite|improve this answer











    $endgroup$



    Luckily Gödels proof is constructive and so provides an example itself. This is nicely explained in "Gödel, Escher, Bach".



    In short (from what I humbly understand and remember): You can assign a number to every logical statement in your formal context, let's call this the Gödel number of that statement. Then you can construct statements that make propositions about other statements (by referencing the Gödel number, e.g. "the statement with the number xyz is true"). Those statements of course have associated Gödel numbers, too. Now construct a statement "The statement with Gödel number xyz is unprovable" so that the Gödel number of the statement is xyz.



    The Wikipedia entry for this (here) is more detailed but maybe still considered popular science.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Feb 21 '16 at 16:41









    Fornost

    335




    335










    answered Dec 5 '14 at 9:05









    TobiMcNamobiTobiMcNamobi

    165410




    165410












    • $begingroup$
      Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:36






    • 1




      $begingroup$
      @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
      $endgroup$
      – TobiMcNamobi
      Dec 6 '14 at 12:48


















    • $begingroup$
      Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
      $endgroup$
      – Michael Harris
      Dec 5 '14 at 23:36






    • 1




      $begingroup$
      @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
      $endgroup$
      – TobiMcNamobi
      Dec 6 '14 at 12:48
















    $begingroup$
    Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:36




    $begingroup$
    Isn't this exactly the same as saying "This statement is false."? It's not a problem if it is, but that's what I understand.
    $endgroup$
    – Michael Harris
    Dec 5 '14 at 23:36




    1




    1




    $begingroup$
    @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
    $endgroup$
    – TobiMcNamobi
    Dec 6 '14 at 12:48




    $begingroup$
    @MichaelHarris Well, Gödel built a statement (in a formal language!) that could be interpreted as "This statement is false". Still there are two important points here I think: First, Gödels proof does not only show the pure existence of such a statement, and second the simple natural language sentence can indeed be formally expressed to serve as the wanted example.
    $endgroup$
    – TobiMcNamobi
    Dec 6 '14 at 12:48











    2












    $begingroup$

    The parallel postulate can't proved from the other axioms of Euclid's geometry.



    You don't even have to drag in Gödel's theorem when you explain this, because it's not relevant. That's a big plus.





    Similarly, there are plenty of incomplete axiom systems. Take the Peano axioms for arithmetic, and leave one out, say the axiom that says that there's no $n$ of which zero is the successor. This axiom can't be proved from the other four axioms.



    Or take the axioms for the real numbers and leave out the well-ordering principle.



    Or take the axioms for set theory and delete one, say the axiom of regularity. You can't prove the deleted axiom from the remaining ones. (There are a few exceptions to this; you can prove the axiom of the empty set from the others.)






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This is not really what the question is about.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:44










    • $begingroup$
      @Andres What do you see in the question to suggest that?
      $endgroup$
      – MJD
      Dec 5 '14 at 1:44










    • $begingroup$
      The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:50










    • $begingroup$
      In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
      $endgroup$
      – MJD
      Dec 5 '14 at 1:52












    • $begingroup$
      If you wish.${}$
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:54
















    2












    $begingroup$

    The parallel postulate can't proved from the other axioms of Euclid's geometry.



    You don't even have to drag in Gödel's theorem when you explain this, because it's not relevant. That's a big plus.





    Similarly, there are plenty of incomplete axiom systems. Take the Peano axioms for arithmetic, and leave one out, say the axiom that says that there's no $n$ of which zero is the successor. This axiom can't be proved from the other four axioms.



    Or take the axioms for the real numbers and leave out the well-ordering principle.



    Or take the axioms for set theory and delete one, say the axiom of regularity. You can't prove the deleted axiom from the remaining ones. (There are a few exceptions to this; you can prove the axiom of the empty set from the others.)






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      This is not really what the question is about.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:44










    • $begingroup$
      @Andres What do you see in the question to suggest that?
      $endgroup$
      – MJD
      Dec 5 '14 at 1:44










    • $begingroup$
      The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:50










    • $begingroup$
      In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
      $endgroup$
      – MJD
      Dec 5 '14 at 1:52












    • $begingroup$
      If you wish.${}$
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:54














    2












    2








    2





    $begingroup$

    The parallel postulate can't proved from the other axioms of Euclid's geometry.



    You don't even have to drag in Gödel's theorem when you explain this, because it's not relevant. That's a big plus.





    Similarly, there are plenty of incomplete axiom systems. Take the Peano axioms for arithmetic, and leave one out, say the axiom that says that there's no $n$ of which zero is the successor. This axiom can't be proved from the other four axioms.



    Or take the axioms for the real numbers and leave out the well-ordering principle.



    Or take the axioms for set theory and delete one, say the axiom of regularity. You can't prove the deleted axiom from the remaining ones. (There are a few exceptions to this; you can prove the axiom of the empty set from the others.)






    share|cite|improve this answer











    $endgroup$



    The parallel postulate can't proved from the other axioms of Euclid's geometry.



    You don't even have to drag in Gödel's theorem when you explain this, because it's not relevant. That's a big plus.





    Similarly, there are plenty of incomplete axiom systems. Take the Peano axioms for arithmetic, and leave one out, say the axiom that says that there's no $n$ of which zero is the successor. This axiom can't be proved from the other four axioms.



    Or take the axioms for the real numbers and leave out the well-ordering principle.



    Or take the axioms for set theory and delete one, say the axiom of regularity. You can't prove the deleted axiom from the remaining ones. (There are a few exceptions to this; you can prove the axiom of the empty set from the others.)







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 5 '14 at 14:12


























    community wiki





    4 revs
    MJD













    • $begingroup$
      This is not really what the question is about.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:44










    • $begingroup$
      @Andres What do you see in the question to suggest that?
      $endgroup$
      – MJD
      Dec 5 '14 at 1:44










    • $begingroup$
      The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:50










    • $begingroup$
      In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
      $endgroup$
      – MJD
      Dec 5 '14 at 1:52












    • $begingroup$
      If you wish.${}$
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:54


















    • $begingroup$
      This is not really what the question is about.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:44










    • $begingroup$
      @Andres What do you see in the question to suggest that?
      $endgroup$
      – MJD
      Dec 5 '14 at 1:44










    • $begingroup$
      The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:50










    • $begingroup$
      In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
      $endgroup$
      – MJD
      Dec 5 '14 at 1:52












    • $begingroup$
      If you wish.${}$
      $endgroup$
      – Andrés E. Caicedo
      Dec 5 '14 at 1:54
















    $begingroup$
    This is not really what the question is about.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:44




    $begingroup$
    This is not really what the question is about.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:44












    $begingroup$
    @Andres What do you see in the question to suggest that?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:44




    $begingroup$
    @Andres What do you see in the question to suggest that?
    $endgroup$
    – MJD
    Dec 5 '14 at 1:44












    $begingroup$
    The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:50




    $begingroup$
    The question is made in the context of the incompleteness theorem(s). It is not about whether every set of first order axioms is deductively complete.
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:50












    $begingroup$
    In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
    $endgroup$
    – MJD
    Dec 5 '14 at 1:52






    $begingroup$
    In that case, why did you bring up Goodstein sequences, the Paris-Harrington theorem, and so on? These have nothing to do with Gödel's incompleteness theorems; they are results that are interesting only because they are independent of certain particular sets of axioms.
    $endgroup$
    – MJD
    Dec 5 '14 at 1:52














    $begingroup$
    If you wish.${}$
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:54




    $begingroup$
    If you wish.${}$
    $endgroup$
    – Andrés E. Caicedo
    Dec 5 '14 at 1:54











    2












    $begingroup$

    This is certainly not an direct answer but a perspective on the topic of the question. The quadrangular parts in the picture below could be empty or joined depending on the approach to the issue.



    Topological model of proofs and statements



    Suppose there was a topology on a space of statements. Then the concept of proof perhaps could be generalized so that some of the unprovable statements could be interpreted as limits of sequences of logical steps that converges to statements in C, D or E?



    Without topology and when only regarding finite proofs the unprovable statements must be considered as a single class of undecidable statements.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
      $endgroup$
      – draks ...
      Jan 23 at 20:10










    • $begingroup$
      What do the numbers mean and where is that figure from?
      $endgroup$
      – draks ...
      Jan 24 at 22:25










    • $begingroup$
      @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
      $endgroup$
      – Lehs
      Jan 24 at 23:04










    • $begingroup$
      I see. Sorry for being late, my interest in that topic just started...
      $endgroup$
      – draks ...
      Jan 25 at 7:36










    • $begingroup$
      @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
      $endgroup$
      – Lehs
      Jan 25 at 9:56
















    2












    $begingroup$

    This is certainly not an direct answer but a perspective on the topic of the question. The quadrangular parts in the picture below could be empty or joined depending on the approach to the issue.



    Topological model of proofs and statements



    Suppose there was a topology on a space of statements. Then the concept of proof perhaps could be generalized so that some of the unprovable statements could be interpreted as limits of sequences of logical steps that converges to statements in C, D or E?



    Without topology and when only regarding finite proofs the unprovable statements must be considered as a single class of undecidable statements.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
      $endgroup$
      – draks ...
      Jan 23 at 20:10










    • $begingroup$
      What do the numbers mean and where is that figure from?
      $endgroup$
      – draks ...
      Jan 24 at 22:25










    • $begingroup$
      @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
      $endgroup$
      – Lehs
      Jan 24 at 23:04










    • $begingroup$
      I see. Sorry for being late, my interest in that topic just started...
      $endgroup$
      – draks ...
      Jan 25 at 7:36










    • $begingroup$
      @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
      $endgroup$
      – Lehs
      Jan 25 at 9:56














    2












    2








    2





    $begingroup$

    This is certainly not an direct answer but a perspective on the topic of the question. The quadrangular parts in the picture below could be empty or joined depending on the approach to the issue.



    Topological model of proofs and statements



    Suppose there was a topology on a space of statements. Then the concept of proof perhaps could be generalized so that some of the unprovable statements could be interpreted as limits of sequences of logical steps that converges to statements in C, D or E?



    Without topology and when only regarding finite proofs the unprovable statements must be considered as a single class of undecidable statements.






    share|cite|improve this answer











    $endgroup$



    This is certainly not an direct answer but a perspective on the topic of the question. The quadrangular parts in the picture below could be empty or joined depending on the approach to the issue.



    Topological model of proofs and statements



    Suppose there was a topology on a space of statements. Then the concept of proof perhaps could be generalized so that some of the unprovable statements could be interpreted as limits of sequences of logical steps that converges to statements in C, D or E?



    Without topology and when only regarding finite proofs the unprovable statements must be considered as a single class of undecidable statements.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 6 '14 at 17:24

























    answered Dec 6 '14 at 11:44









    LehsLehs

    7,03231664




    7,03231664












    • $begingroup$
      Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
      $endgroup$
      – draks ...
      Jan 23 at 20:10










    • $begingroup$
      What do the numbers mean and where is that figure from?
      $endgroup$
      – draks ...
      Jan 24 at 22:25










    • $begingroup$
      @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
      $endgroup$
      – Lehs
      Jan 24 at 23:04










    • $begingroup$
      I see. Sorry for being late, my interest in that topic just started...
      $endgroup$
      – draks ...
      Jan 25 at 7:36










    • $begingroup$
      @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
      $endgroup$
      – Lehs
      Jan 25 at 9:56


















    • $begingroup$
      Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
      $endgroup$
      – draks ...
      Jan 23 at 20:10










    • $begingroup$
      What do the numbers mean and where is that figure from?
      $endgroup$
      – draks ...
      Jan 24 at 22:25










    • $begingroup$
      @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
      $endgroup$
      – Lehs
      Jan 24 at 23:04










    • $begingroup$
      I see. Sorry for being late, my interest in that topic just started...
      $endgroup$
      – draks ...
      Jan 25 at 7:36










    • $begingroup$
      @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
      $endgroup$
      – Lehs
      Jan 25 at 9:56
















    $begingroup$
    Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
    $endgroup$
    – draks ...
    Jan 23 at 20:10




    $begingroup$
    Interesting, I have a question about the "topology on the space of statements", and would be happy to read your opinion here...
    $endgroup$
    – draks ...
    Jan 23 at 20:10












    $begingroup$
    What do the numbers mean and where is that figure from?
    $endgroup$
    – draks ...
    Jan 24 at 22:25




    $begingroup$
    What do the numbers mean and where is that figure from?
    $endgroup$
    – draks ...
    Jan 24 at 22:25












    $begingroup$
    @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
    $endgroup$
    – Lehs
    Jan 24 at 23:04




    $begingroup$
    @draks... I wrote this 4 years ago and I don't fully understand that point of view today. The figures is about topology, how one could put the area together to a torus.
    $endgroup$
    – Lehs
    Jan 24 at 23:04












    $begingroup$
    I see. Sorry for being late, my interest in that topic just started...
    $endgroup$
    – draks ...
    Jan 25 at 7:36




    $begingroup$
    I see. Sorry for being late, my interest in that topic just started...
    $endgroup$
    – draks ...
    Jan 25 at 7:36












    $begingroup$
    @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
    $endgroup$
    – Lehs
    Jan 25 at 9:56




    $begingroup$
    @draks... I wouldn't formulate this today, but there is something about topology in proving theorems. Or should be.
    $endgroup$
    – Lehs
    Jan 25 at 9:56











    2












    $begingroup$

    An example of a problem that in general cannot be solved is the existence of solutions to Diophantine equations http://en.wikipedia.org/wiki/Diophantine_equation. Hilbert's 10th problem was to find an "effective method" (that is, a computer program) to solve Diophantine equations. It was shown in work by Yuri Matiyasevich and Julia Robinson that there is no such effective method. (As I recall, Julia did most of the work, leaving one lemma that needed to be proved. Yuri then proved the lemma. Yuri's paper is rather short, and you need to read Julia's paper to get the full picture.)






    share|cite|improve this answer









    $endgroup$


















      2












      $begingroup$

      An example of a problem that in general cannot be solved is the existence of solutions to Diophantine equations http://en.wikipedia.org/wiki/Diophantine_equation. Hilbert's 10th problem was to find an "effective method" (that is, a computer program) to solve Diophantine equations. It was shown in work by Yuri Matiyasevich and Julia Robinson that there is no such effective method. (As I recall, Julia did most of the work, leaving one lemma that needed to be proved. Yuri then proved the lemma. Yuri's paper is rather short, and you need to read Julia's paper to get the full picture.)






      share|cite|improve this answer









      $endgroup$
















        2












        2








        2





        $begingroup$

        An example of a problem that in general cannot be solved is the existence of solutions to Diophantine equations http://en.wikipedia.org/wiki/Diophantine_equation. Hilbert's 10th problem was to find an "effective method" (that is, a computer program) to solve Diophantine equations. It was shown in work by Yuri Matiyasevich and Julia Robinson that there is no such effective method. (As I recall, Julia did most of the work, leaving one lemma that needed to be proved. Yuri then proved the lemma. Yuri's paper is rather short, and you need to read Julia's paper to get the full picture.)






        share|cite|improve this answer









        $endgroup$



        An example of a problem that in general cannot be solved is the existence of solutions to Diophantine equations http://en.wikipedia.org/wiki/Diophantine_equation. Hilbert's 10th problem was to find an "effective method" (that is, a computer program) to solve Diophantine equations. It was shown in work by Yuri Matiyasevich and Julia Robinson that there is no such effective method. (As I recall, Julia did most of the work, leaving one lemma that needed to be proved. Yuri then proved the lemma. Yuri's paper is rather short, and you need to read Julia's paper to get the full picture.)







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 9 '14 at 19:45









        Stephen Montgomery-SmithStephen Montgomery-Smith

        17.8k12247




        17.8k12247

















            protected by user99914 Nov 19 '17 at 2:18



            Thank you for your interest in this question.
            Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



            Would you like to answer one of these unanswered questions instead?



            Popular posts from this blog

            Bressuire

            Cabo Verde

            Gyllenstierna