38
$\begingroup$

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.

$\endgroup$
10
  • 7
    $\begingroup$ Gödel's incompleteness theorem is not a counting argument. It proves that one countable set which apriori is a subset of another countable set is a proper subset. The properness is not proved by showing they have different cardinality. $\endgroup$
    – Chad K
    Jun 26, 2023 at 8:41
  • 9
    $\begingroup$ what Yanofsky says is true but not remarkable. Godel's incompleteness theorem makes a far more interesting and informative assertion about actual statements that are true but not provable. see math.stackexchange.com/questions/4722030/… $\endgroup$ Jun 26, 2023 at 15:54
  • 1
    $\begingroup$ It could be expressed with reals. There are uncountably many reals, even just in an interval like $[0, 1]$. About any given real number $r$, there exist facts, ... and so it goes. $\endgroup$
    – Kaz
    Jun 26, 2023 at 17:59
  • 2
    $\begingroup$ Seeing as a mathematical truth may have infinitely many proofs or none at all, the significance of counting proofs is not clear. $\endgroup$
    – bof
    Jun 26, 2023 at 23:14
  • 4
    $\begingroup$ To quote Joel David Hamkins on MO: "The concept of definable real number, although seemingly easy to reason with at first, is actually laden with subtle metamathematical dangers... ." That answer is about real numbers but it applies equally well to this question if you replace "real number" by "subset of the naturals". I recommend giving it a read. $\endgroup$
    – Carmeister
    Jun 27, 2023 at 15:52

6 Answers 6

48
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Furthermore, if ZF is consistent, there are pointwise-definable models of ZF (models of ZF in which each object is the unique object satisfying some formula). $\endgroup$ Jun 26, 2023 at 21:27
14
$\begingroup$

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.

$\endgroup$
4
  • 15
    $\begingroup$ We can prove that $\forall S \subset \mathbb N: \pi \not \in S$, but such proof isn't proof of "$\pi$ isn't in set of odd natural numbers": to prove the second from the first, we need to add two extra lines - that set of odd natural numbers is subset of $\mathbb N$ and then use universal elimination. However, for most subsets we can't do this, because we can't define them in the first place to write statement that they are subsets of $\mathbb N$. $\endgroup$
    – mihaild
    Jun 26, 2023 at 23:53
  • 2
    $\begingroup$ "There are only countably many ways we can express a statement of the form π∉S for some S⊆N" Why? Do you mean there are only countable many ways in first-order logic? "The fallacy is that a single proof can prove uncountably many facts" Not in the formal logic sense of "proof". A proof is sequence of statements in which each statement is either an axiom or a statement derived from previous statements through the rules of logic, and the final statement is the statement being proved. So "proof(for all x in X, x has property P)" $\neq$ "all x in X, proof(x has property P)". $\endgroup$ Jun 28, 2023 at 0:12
  • 1
    $\begingroup$ @Acccumulation Despite not writing a proof for all x in X, you have an algorithm for generating one from the proof of for all x in X, which is just universal elimination. $\endgroup$
    – Passer By
    Jun 28, 2023 at 3:24
  • 3
    $\begingroup$ @PasserBy only if you accept some strong form of constructivism, that every x in X can be defined by formula. If you can't define x you can't use universal elimination. $\endgroup$
    – mihaild
    Jun 28, 2023 at 8:31
8
$\begingroup$

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.

$\endgroup$
10
  • 7
    $\begingroup$ I think most people would be more comfortable with the phrasing "for each real $x$, $f$ is continuous at $x$" rather than "for each real $x$, $f(x)$ is continuous" $\endgroup$
    – Stef
    Jun 27, 2023 at 7:52
  • 3
    $\begingroup$ It's more useful to view Yanofsky's argument as a flavor of Gödel's First Incompleteness, which in turn can be viewed as a specialization of Lawvere's fixed-point theorem. See e.g. Yanofsky 2003 for a holistic treatment. $\endgroup$
    – Corbin
    Jun 27, 2023 at 12:48
  • 5
    $\begingroup$ @Corbin But Yanofsky's argument has nothing to do with Godel's incompleteness theorem. It's not "a flavor" of it, it's just unrelated. $\endgroup$ Jun 27, 2023 at 15:14
  • $\begingroup$ @stef You are correct. That was a silly oversight from me haha. $\endgroup$ Jun 27, 2023 at 15:50
  • 1
    $\begingroup$ @NoahSchweber: This question is about whether there are more true sentences than provable sentences. Gödel constructed an unprovable-yet-true sentence. They're more closely related than one might think. Either way, I think we agree that it's not an instance of Zeno's paradox. $\endgroup$
    – Corbin
    Jun 27, 2023 at 15:55
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
-3
$\begingroup$

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 nothing1: 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.


1Adds 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .