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?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

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