Xrfgtjtk

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?!

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.

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.

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.

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.

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

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.

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.

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.)

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.

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.

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.)