Proof that the number of proofs is countably infinite

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.