Can two distinct formulae (or series of formulae) have the same Gödel number?

Question

As I am studying Gödel's incompleteness theorem I am wondering if two distinct formulae or series of formulae can have the same Gödel number? Or the function mapping each formula or series of formulae to a Gödel number is not invertible?

Answer 1

The function is injective (i.e. one-to-one), that is the principle of an encoding. So no two formula can have the same number. This is guaranteeing by the fundamental theorem of arithmetic: there is only one decomposition of a number in product of primes, and that is what is used by Gödel to do this encoding.

More precisely, each sign of a formula is encoded by a number, so a formula becomes a sequence $(a_1,\dots, a_k)$, and then we map to it the unique number $2^{a_1}3^{a_2}\dots p_k^{a_k}$ where $p_k$ is the $k^{th}$ prime number.

Answer 2

Two different formulas, or strings of formulas, cannot have the same index (Gödel number).

In the usual indexing schemes, not every natural number is an index. So the function is one to one but not onto.