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?
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.
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 C1,C2, 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 C1, 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 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” Proc. Cambridge Philos. Soc. 72 (1972) 179–183.