Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to state fundamental theorem of arithmetic in a formal way?

  1. Nov 16, 2011 #1
    I think a best informal way to state the theorem is Hardy's:
    every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes

    But clearly, this statement does not reveal the structure of the statement in the formal language the first order theory. Can you re-state this theorem by only using the first order language elements such as "for all" "there exists" and variable and so on? You can obviously use sets.

    I'm having trouble especially on stating the concepts of "a product" and "rearrangement" in the formal language.
  2. jcsd
  3. Nov 16, 2011 #2
    I don't see what is informal about Hardy's statement of the theorem, unless you can't view a prime to be a product of one prime. But your objections could be circumvented by language such as "either as a prime or the product of two or more prime numbers apart from the rearrangement of the order of the primes". IMHO Hardy's statement of the theorm is concise and formal though since it clearly defines a prime to be a product and "product" and "rearrangement" have clear meaning in their context.
    Last edited: Nov 16, 2011
  4. Nov 17, 2011 #3

    Basically, my intention is to clarify all the elements by translating to the first order theory language. As you know any (mathematical) statement can be translated to a statement such as "[itex]\forall x\in S \forall y \in K \exists b\dots[/itex] as the fist order theory is implemented set theoretic elements.

    In my level of mathematical maturity, I don't directly see this first order language structure of the Hardy's, i.e., I can't directly translate this Hardy's statement into the pure first order theory sentence in my mind, therby the meaning is not clarified to perfection but rather is possessed within a some intuition level vague to some extent.

    It'd be burdensome to translate the statement into the pure first order one, but I think it might be that the translation can be shortend if some set theoretic definitions are properly applied. Anyway I can't do it myself. Especially, the concpet of 'rearrangement' and 'product(multiplication)', I can't dare to think of the first order language structure of them.

    Note: obviosuly translation into the pure first order language will be really long, but as you know it can be shortened by using proper definitions (summariziation of some sentences or parts of a sentence). Right?
  5. Nov 17, 2011 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For every positive integer n, there exists a prime factorization of n. If [itex]n = \prod_{i=1}^s p_i^{e_i} = \prod_{j=1}^t q_j^{f_j}[/itex] are two prime factorizations, then [itex]s=t[/itex], and there is a permutation [itex]\sigma[/itex] on {1, ..., s} such that [itex]q_i = p_{\sigma(i)}[/itex] and [itex]f_i = e_{\sigma(i)}[/itex].

    By the way, there's no need to exclude 1; you just need to relax "one or more primes" to "zero or more primes".
  6. Nov 17, 2011 #5

    Thank you very much. Your solution is very elegant and careful by the way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook