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

  • Thread starter julypraise
  • Start date
  • #1
110
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
841
0
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.
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:
  • #3
110
0
@ramsey2879

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?
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
18
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".
 
  • #5
110
0
@Hurkyl

Thank you very much. Your solution is very elegant and careful by the way.
 

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

Replies
14
Views
4K
Replies
5
Views
2K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
2
Views
4K
  • Last Post
Replies
7
Views
5K
Replies
11
Views
1K
Replies
2
Views
795
Replies
4
Views
3K
Top