# Proof that the number of proofs is countably infinite

I think that the number of mathematical statements is countably infinite, since each statement is a finite string of finitely many symbols, but i am not sure how to prove it. Once i prove that, i can say that a every math proof with $n$ steps is a subset of the cartesian product $A^n$ where $A$ is the set of all mathematical statement, and each element in the resulting set is a statement that is a step in the proof. Since the cartesian product of countably infinite sets is countably infinite, then the set of all proofs with $n$ steps is countably infinite, for any $n$. How can i prove that the number of mathematical statements is countably infinite, and is the rest of the proof correct?

• Could you make more precise what you mean by a mathematical statement? – Adayah Jun 11 '18 at 16:00
• SInce there's an uncountable amount of real numbers, it would seem you can easily create an uncountable number of statements about those real numbers. – Carl Witthoft Jun 11 '18 at 19:09
• @CarlWitthoft But how do you enumerate over those reals? Also see this. – Quelklef Jun 11 '18 at 20:08
• @CarlWitthoft: Try it. It's easy to make one statement covering an uncountable number of reals (e.g. all reals between 0 and 1 are smaller than 2), but how would you construct the infinite set of statements which each cover one real from that range? Note that this set of statements can be ordered by the real number to which each statement applies, i.e "0.1 < 2" comes before "0.2<2". – MSalters Jun 11 '18 at 22:12
• I think Carl raises a good point in the following way: Currently the two highest voted answers start with the assertion that are there a finite number of symbols that can be used to construct a statement. My concern there is that couldn't we use a particular real number as a symbol? (perhaps my understanding of the term symbol is incorrect) If each real number would be considered a distinct symbol, then we have an uncountably infinite number of symbols. – Todd Wilcox Jun 12 '18 at 13:36

Let say we have a set of symbols symbols, $S=(s_0,...,s_{n-1})$, and $n$ elements in $S$.

We will now give every symbol a number between $0$ and $n-1$: $\forall i_{\in\Bbb N}<n(s_i\to i)$

For any arbitrary string $K=(k_0,...,k_m)$ of elements of $S$ we will look at the number in base $n$ created by its elements as digits: $k_m...k_1k_0(base~n)=k_mn^m+...+k_1n+k_0$, in other words I create a bijective function from the set of finite strings of $S$ to $\Bbb N$.

The number of proofs is subset of the above set hence it is also countable

As David point out this method has a problem: if I have at the start of the string $s_0$ it won't change the number but will change the string($s_0L\ne L$ but after converting to numbers they will be equal)

So instead of bijective I'll create the injective function $$K=(k_0,...,k_m)\mapsto 1k_m...k_1k_0(base~n)=n^{m+1}+k_mn^m+...+k_1n+k_0$$

• Side note: since the expression $k_m n^m + \ldots + k_1 n + k_0$ is not a sequence of digits, I think it doesn't make sense to specify that it's base $10$. – Adayah Jun 11 '18 at 16:07
• @Adayah why? I can change the digits in two forms, once at "digits" and once as "numbers" but I think it will make it less clear. I added that form just to make it clearer ( I think it is clearer with both forms at least) – ℋolo Jun 11 '18 at 16:13
• Because specifying base $10$ next to an expression like $k_m n^m + \ldots + k_1 n + k_0$ only makes sense if the same expression could be read e.g. in base $17$ and the outcome differs. Can you interpret the above expression once in base $10$ and once in base $17$ so that the results differ? Note that $m, n$ and $k_m$ stand for actual numbers, not sequences of digits representing numbers, so they don't depend on the choice of the base. – Adayah Jun 11 '18 at 16:23
• @Adayah I see. I understand, I'll delete that part – ℋolo Jun 11 '18 at 16:29
• Does this need a more rigorous assertion of the "given" that there are a finite number of symbols used for mathematical proofs? Does the set of symbols not include particular numbers? Is there a proof that does not rely on a finite or countable number of symbols? – Todd Wilcox Jun 12 '18 at 13:38

Regarding the proof that the number of statements is countably infinite

So suppose that the number of symbols $$S=\{s_1,\dots,s_n\}$$ is finite and equal to $$n$$. Then a statement is an element of the set $$S^{<\mathbb N}$$ of the finite sequences $$(s_{j_1},\dots, s_{j_k})$$ of elements of $$S$$.

You can create an injection from $$S^{<\mathbb N}$$ into $$\mathbb N$$ by setting $$(s_{j_1},\dots, s_{j_n}) \mapsto p_1^{j_1} \times \dots \times p_n^{j_n}$$, where $$p_i$$ is the $$i$$-th prime number. This is an injection according to the uniqueness factorization theorem.

• What do the $j_i$s mean? If they are how many times a symbol appear, then two different programs but with equal number of symbols appearing in different positions would be codified as the same program... – David Nov 7 '20 at 12:35
• $s_{j_i}$ is the element of $S$ that is at position $i$ in the sequence. Therefor the map is indeed one-to-one. – mathcounterexamples.net Nov 7 '20 at 13:01

Correct me if wrong:

Consider :

Let $S = \cup_{n \in \mathbb{Z^+}} E_n,$ where $E_n$ is countable, then $S$ is countable. (Rudin Theorem 2.12).

Consider a line length of $n$ characters .

The set $A_n$ of elements of line lengths of $n$ characters is finite.

For the set of proofs $E_n$ of line length of $n$ characters we have :

$E_n \subset A_n$ , i.e finite.

Hence

$S= \cup_{n \in \mathbb{Z^+}} E_n$ is countable.

• Let $P_x$ be the sentence "$x<0\Rightarrow 1+x<1$". Note that $P_x$ is a proof of "$1>1+x$" provided that $x<0$. Then, shouldn't the set $\{P_x\mid x\in(-\infty,0)\}$ be a subset of the set of proofs? Then, shouldn't the set of proofs be uncountable? – Pedro Jun 11 '18 at 12:40
• Pedro.I am certainly not a specialist on this.Let me try to put it in one line of length n: For all x<0 the statement P_x ( P_x: x <0 implies 1+x <1 ) implies 1>1+x.What do you think ? – Peter Szilas Jun 11 '18 at 13:30

The Curry–Howard correspondence tells us that there is an isomorphism between proofs and program's type (for each proof there is at least a program with the corresponding type and vice versa).

This means that if the number of programs is countably infinite, so will be the number of proofs. This gets us back to the number of characters... (but hopefully in an interesting way).

I think that the number of mathematical statements is countably infinite, since each statement is a finite string of finitely many symbols

Well, be careful here. Please note that for every number $n$ of symbols you have, you can generate a mathematical statement that contains more than $n$ variables (but is still of finite length). So, if each variable is given its own symbol ($x$, $y$, $z$ ,...) , we may need an infinite set of symbols. Indeed, this is exactly the assumption in formal logic.

Now, of course, in practice we write $x_1$, $x_2$, ..., $x_9$, $x_{10}$, $x_{11}$, i.e. we can separate variables using indices, and those indices only require finitely many digits. So ... the proofs as given (which all assume finitely many symbols) can stand.

Still, if you're worried about the set of symbols possibly having to be infinite, it is clear that it only needs to be countably infinite: To create any sentence, we sometimes need another variable, but we only introduce one of them at a time, and a different sentence can simply reuse those variables.

Even more interestingly, the number of finite strings you can generate using a countable set of symbols is still countable as well.

To see this, you can first show that the set $S_1$ of all strings of length $1$ is countable (and of course it is! This is basically the set of symbols themselves).

We can then show that the set $S_2$ of all strings of length $2$ are countable by concatenating two strings of length $1$. That is, we can take the Cartesian product of $S_1 \times S_1$, and regard each entry $(s_i, s_j)$ as the string $s_is_j$, and apparently you already know that

the cartesian product of countably infinite sets is countably infinite

With that, you can then also show the set of all strings of length $3$ to be countable, ... and indeed using induction you can show that for any $n$: the set $S_n$ of all finite strings of length $n$, as generated using a countable infinite set of symbols $S$, is countable. Finally, you need to show that the union of all those sets

$$U=\bigcup_{n=1}^\infty S_n$$

is countable, but that is easily done by putting all those entries in one big table as well ($S_{i,j}$ is the $j$-th entry of the enumeration of all strings in $S_i$), and zig-zagging through that table.

So finally, since all proofs are a subset of $U$, that set is countable as well.

• Note that "putting all of those in one big table" is very non trivial action, I think you should add this is assuming axiom of countable choice – ℋolo Jun 12 '18 at 4:52
• I know it seems clear that the set of symbols only need be countable, at most, but it's not at all clear to me. Can you add anything to that to explain why we would never need uncountably many symbols for proofs? – Todd Wilcox Jun 12 '18 at 13:41
• You're not from Europe, are you? – Asaf Karagila Jun 12 '18 at 14:14
• @AsafKaragila Why do you ask? – Bram28 Jun 12 '18 at 14:24
• Because most Europeans I know wouldn't use SS to denote things. – Asaf Karagila Jun 12 '18 at 14:25

You could construct, by induction, an infinite sequence of proofs out of many different schemas. This does not get you all proofs or all theorems in arithmetic, but it shows that there are at least a countably-infinite number of them, and you already showed that there are at most a countably-infinite number of proofs. For example, in Peano arithmetic, "The successor of any natural number is a natural number. 0 is a natural number. The successor of 0 is a natural number. QED." Then replace 0 by 1, 2, 3, and so on. You get a different proof for each natural number.

Another strategy would be to insert sound but redundant steps into the proof, giving you a longer, distinct proof. For example, if you’re proving a relation, adding and then subtracting 1 to both sides an arbitrary number of times.

That demonstrates that the number of proofs is at least countably infinite, and since proofs are a proper subset of well-formed formulas, which are countably infinite, they are at most countably infinite.

• The only proofs that the first paragraph covers are proofs that the successor of any natural number is a natural number (which is usually true by definition anyway). There are quite a few other mathematical statements that can be proven. The second paragraph only applies if you already have a proof, or collection of proofs, so It doesn't describe a systematic way to generate all proofs. You would pretty much need to start with a collection of all proofs for that to work anyway, which kind of defeats the purpose. – David Jun 11 '18 at 23:11
• @DavidYoung You don’t need to systematically generate all proofs to show that there are a countably-infinite number of them. The first paragraph shows that the set of all proofs is a proper superset of a countably-infinite set, and the last that it is a proper subset of a countably-infinite set. – Davislor Jun 11 '18 at 23:23