What is a simple example of an unprovable statement?
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” Proc. Cambridge Philos. Soc. 72 (1972) 179–183.
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?!
Any statement which is not logically valid (read: always true) is unprovable. The statement $\exists x\exists 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 "$f\colon\Bbb{R\to 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.