Are there more truths than proofs?

Question

Noson Yanofsky is a theoretical computer scientist at Brooklyn College. He presents the following argument on pages 329-330 of his book The Outer Limits of Reason, published by the MIT Press.

1. The set $\mathbb{N}$ of natural numbers has uncountably many subsets.

2. Let $x$ be a natural number and $S$ a subset of $\mathbb{N}$. Exactly one of the following statements expresses a mathematical fact: (a) $x \in S$, (b) $x \notin S$.

3. It follows from (1) and (2) that there are uncountably many mathematical facts.

4. Let $T$ be a first-order theory. Then $T$ has only countably many formulas.

5. It follows from (3) and (4) that there are more mathematical facts than formulas in $T$.

6. Therefore $T$ cannot express, much less prove, all mathematical facts.

For Yanofsky's own words, see the article: "Most truths cannot be expressed in language."

I have heard people say similar things on podcasts. They try to explain Gödel's first incompleteness theorem as stating that there are more truths than proofs.

---

Question.$\ \ $Is Yanofsky's argument valid? If not, why?

---

It seems to contradict the answers to the following questions: 1, 2, 3. However, Yanofsky seems to be an expert in this area, and his argument was published by the MIT Press.

Note that Yanofsky writes:

"This is all about mathematical facts – not about what can be stated. A mathematical statement is a mathematical fact that can be put into symbols. We saw above that... there are countably [many] mathematical statements. Hence there are massively more mathematical facts than mathematical statements."

Perhaps this could be made more precise by encoding mathematical facts as sets.

Answer 1

That's correct, but it is not very interesting: we don't have "access" to most mathematical facts. It is not even clear what a proof of an arbitrary mathematical fact would mean, because to ask for a proof of something we have to write it down, and there are only countably many strings we can write.

Gödel's theorem is much more interesting: it says that there is a formula that is independent of PA. So you can write some statement in arithmetic language (and it actually can be as simple as "this Diophantine equation has a solution") and neither it nor its negation can be proved in PA.

Compare it with, say Euclidean geometry. There are uncountably many lines and points, so there are an uncountable number of "facts" like "this point is / is not on this line". But Euclidean geometry is complete. So Gödel's theorem shows a difference between arithmetic and geometry.

And also there is (assuming consistency of ZF) a model of ZF where there are, from an outside point of view, only countably many sets.

Answer 2

The argument is fallacious.

We can use the same basic argument in an even simpler setup, which clearly indicates what goes wrong.

There are uncountably many subsets of the natural numbers. There are only countably many ways we can express a statement of the form $\pi\not\in S$ for some $S\subseteq \mathbb N$. So there are massively more true facts of the form $\pi\not\in S$ than we can even express, let alone prove.

But of course, we can prove all of them, since we can prove $\pi\not\in \mathbb N$ and hence $\pi\not\in S$ for every $S\subseteq \mathbb N$. The fallacy is that a single proof can prove uncountably many facts, so being able to state a fact is not a prerequisite to proving it.

The quote "most truths cannot be expressed in language" is correct, at least for this definition of "truth". But it doesn't follow that they can't be proved.

Answer 3

A slightly different perspective - Yes, there are uncountable (trivial) mathematical facts, but you don't need to individually prove each of those facts. What's much more interesting is the fact that you can, in most situations where it matters, formulate statements in the language of first order so that it expresses, in theory, uncountable number of facts.

For example, proving that some function function $f: \mathbb{R} \to \mathbb{R}$ is continous. Which is equivalent to the statement that for each real $x$ (clearly uncountable number of $x$), $f$ is continous at $x$. We can obviously prove statements such as this, and so this shows that not only can we, in effect, state uncountable number of "facts," but also prove such "facts" as "facts" in a finite number of steps.

In a nutshell, though, Yanofsky's argument is just a variation of zeno's paradox.

Answer 4

Nobody seems to have mentioned the following point. Let $\mathcal F$ be the principal ultrafilter on $\mathbb N$ generated by $1\in\mathbb N$. Then the assertion $(\forall A\in \mathcal F) (1\in A)$ includes uncountably many "truths". That's all Yanofsky's argument is saying. It is difficult to derive meaningful insights from such a platitude.

Since Zeno's paradox is far from a platitude, it is clear that Yanofsky's argument has nothing to do with Zeno's paradox.

Answer 5

I would say (and I'm aware of where I'm saying this) that there are no proofs.

There are only facts, and statements about facts which are true or false or perhaps undecidable; And for each of the (uncountably many) statements about facts it can be shown that they are true or false or undecidable, but that adds nothing¹: They have always been true or false or perhaps undecidable.

The opposition of "statement" and "proof" is a fallacy. Showing that a statement is true or false or undecidable doesn't change anything about the statement. There is always a 1:1 relation between the statement and its quality of being true or false or undecidable.

---

_{¹Adds nothing to the statement, or the facts. Of course it gives us certainty and with it the tools to discover more facts, and is very valuable in this respect.}

Answer 6

I slightly disagree with the assertion that there are uncountable many facts, as only a countable many of these facts can actually be stated. That is, we can only describe a countably amount of subsets of $\mathbb{N}$.