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?
Set Theory – Proof That the Number of Proofs is Countably Infinite
cardinalselementary-set-theory
Best Answer
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.