Re: Formalizing the Fundamental Theorem of Arithmetic

On May 23, 6:13 pm, Aatu Koskensilta <aatu.koskensi...@xxxxxxxxx>
wrote:
There is no sentence in the language of first order arithmetic that
expresses the fundamental theorem of arithmetic without some coding. This
holds for any sentence that involves the notion of a finite sequence or set
of naturals.

Indeed. What a "factorization" "really is" is a multiset.
You could write it is a list but that would be TOO much information
since there would be n! different permutations of that list if
the number had n factors. To get down to representing the
thing you are trying to represent, you have to throw away the
order. You could also map the primes completely down
to the naturals, aliasing every prime to its position in their natural
ordering (I guess you would still have to start with 0 and 1,
even though they are not "technically" prime, in order to
get a factorization for 0 and a factorization for 1).
If you do that, then "a prime factorization" simply becomes
"a multiset of natural numbers".

In the language of PA, finite natural numerals are all you have
to work with, so rather than doing anything without encoding,
you can ONLY do things that can be encoded as natural numbers.

In other words, the best answer to the original question
is another question, namely, "What is the most natural
and straightforward encoding of a multiset of natural numbers
as a natural number"? And you DON'T get to say
"the product of multiplying the nth prime to the mth
power for every n in the multiset" -- that is precisely the
encoding we are trying to INVERT (i.e., if you do that, then
every number's prime factorization is best represented by the
number that is ITSELF; somehow I DOUBT that that COULD COUNT
as "a proof of the fundamental theorem of arithmetic").

.

Relevant Pages
Loading