A common statement of The Fundamental Theorem of Arithmetic goes:

Every integer greater than $1$ can be expressed as a product of powers of distinct prime numbers uniquely up to a reordering of the factors.

Now the statement makes a point of mentioning that factorization is unique up to reordering of the factors, saying basically that we don't have to worry about it because multiplication in the integers is commutative. But why not specify that it's also unique up to the choice in which order we multiply the factors? I.e, that we don't have to worry about it because multiplication in the integers is associative too? If we insist on multiplication being a binary operation, then we need to define some grouping when we have a product of more than two integers. Shouldn't there be a clause in the Fundamental Theorem that indicates, for example, that $30 = (2\times (3 \times 5))$ and $30 = ((2\times 3) \times 5)$ are not distinct factorizations?  

  • 17
    You seem to be mixing the issue of ordering the factors in a product (which the uniqueness statement of FTA allows you to do) with the question of associativity of multiplication of integers (it is associativity which guarantees that $a*b*c$ is a uniquely determined product, and that $(a*b)*c$ yields the same result as $a*(b*c)$). – Geoff Robinson Aug 22 '11 at 22:05
  • 6
    "But why not specify that it's also unique up to the choice in which order we multiply the factors?" -- because it is obvious? When you are at the stage where you are proving the FTA, certain background facts can simply be assumed. The only alternative is to weigh everything down by a layer of pedantry. – John Coleman Apr 21 at 13:46
  • 11
    @JohnColeman Commutativity is also "obvious" so why is there any need to state "up to reordering"? Why not just say "uniquely" full stop? – Derek Elkins Apr 21 at 23:22
  • 5
    @DerekElkins 3*5*7 looks different from 7*3*5. Furthermore, it is common for people to write down products in such different ways. Both forms that I wrote are natural. On the other hand, in most contexts nobody even bothers to write things like 2*(3*(7*7)) or (2*3)*(7*7) but would instead just write 2*3*7*7. The different ways of writing the product due to commutativity are visible in a way that the different forms of the product due to associativity are not. It makes sense to address the visibly different ways of writing the products, but is pedantic to bring up the invisible. – John Coleman Apr 22 at 0:07
  • 2
    @JohnColeman I agree with that. If you had said "visible" as Joffan did instead of "obvious" I would have had no issue. Incidentally, what about $2^12^1$? Does this constitute a "different" factorization of $4$? It's visibly different. – Derek Elkins Apr 22 at 0:18

10 Answers 10

up vote 32 down vote accepted

"Uniquely" means that there is exactly one way to write an integer as a $k$-ary product of primes (up to permutation of the factors).

Since thanks to associativity, all placements of parentheses give the same product, it does not matter which of the concatenations of binary operations one uses for the definition of the $k$-ary product.

One symmetric way to think about it, is to define it as an equivalence class of all these expressions.

If you insist on Polish notation, then we get, say, $30=*_3 2\ 3\ 5 $ where $*_3$ denotes the ternary multiplication operator.

  • 23
    This doesn't answer why commutativity is explicitly mentioned in the FTA, but associativity is taken implicitly. Consider this slightly modified excerpt from your answer: "Since thanks to commutativity, all reorderings of factors give the same product, it does not matter which of the reorderings of factors one uses for the definition of the $k$-ary product." If your answer explains why associativity isn't explicitly mentioned, then the excerpt should explain why commutativity isn't explicitly mentioned. Clearly, though, this isn't the case, because commutativity is explicitly mentioned. – Vaelus Apr 20 at 23:17
  • 4
    @Vaelus Note that this answer was actually written for another question (more than 6 years ago). – Arnaud D. Apr 21 at 0:23
  • 11
    @ArnaudD. Okay, thanks for pointing that out. That explains why none of the answers seem to address the question in it's current form. Any idea why the question seemingly doesn't have a complete history, and appears to have been asked only 5 hours ago? – Vaelus Apr 21 at 0:37
  • 4
    @Vaelus The question you see was asked 5 hours ago, but it has been merged with an older one; all the answers (and comments on them) were actually written for the other question (and it looks like this answer was not accepted by the new question asker, but by the old one). You can see this in the revision history (click on "edited 4 hours" (as of now) under the question) : there is some sort of blue banner which says " Post Merged (destination) from math.stackexchange.com/questions/59079/…". – Arnaud D. Apr 21 at 0:44
  • 2
    @Vaelus To add to what Arnaud said, this question is an attempt to salvage an old question that was very poorly written, but addressed an issue worth preserving for future users. The old question was a big mess, so cleaning up the comments and answers is still a work in progress. As such if you find discrepencies caused by the merge, please feel free to suggest an edit to improve consistency within its current context. – Alexander Gruber Apr 21 at 20:30
up vote 38 down vote
+250

Writing $a(bc)$ is not distinct from writing $(ab)c$, or any variant in this form.

What you talk about can occur abstractly, just not in $\mathbb{Z}$. Magmas and quasigroups do not insist upon associativity, and in such situations, a singular factorization cannot always occur. But associativity of multiplication (and also addition) holds for all rings - this is an axiom. So your conclusion that $abc$ factors to both $a(bc)$ and $(ab)c$ is not logical. Think of multiplication as a binary function, from $\mathbb{Z}$ to $\mathbb{Z}$, not as a formation of a word. Only notationally is $a(bc)$ in $\mathbb{Z}$, as it maps to an individual $z\in \mathbb{Z}$. But $a(bc)$ intrinsically, as a symbol, is a function waiting for valuation. This is why it is said that $(ab)c=a(bc)$; both form a map to synonymous locations.

I don't know if your complaint is with notion or notation, but if you follow what I'm saying, you should try to construct a ring without associativity of multiplication to assist you in grasping why this works in $\mathbb{Z}$. Try looking at octonions - polish notation (or any notation) won't fix factorization in that situation.

  • 53
    The bounty notice is gone, so I would like to note for posterity that the bounty was offered to the best answer that did not include the letter ‘e’, and this post was the brilliant result. – MJD Mar 18 '16 at 15:05

By the associativity and commutativity of multiplication we can normalize prime products by right-associating brackets and ordering primes least-first. Now unique factorization amounts to

$$\rm 2^{u_0} (3^{u_1} (5^{u_2} \cdots p_k^{u_k}))\ =\ 2^{v_0} (3^{v_1} (5^{v_2} \cdots p_k^{v_k}))\ \ \Rightarrow\ \ u_i = v_i,\ \ i = 0,\ldots,k $$

Equivalently, the multiplicative monoid of positive integers is freely generated by the primes, i.e. it is isomorphic to the free monoid of "exponent vectors" $\:\in \mathbb N^{\mathbb N}\:,\:$ i.e. if $\rm\:v = (v_0,v_1,\ldots)\in \mathbb N^{\mathbb N}$ is a sequence of naturals with finite support then the monoid map $\rm\:v\mapsto 2^{v_0} (3^{v_1} (5^{v_2} \cdots ))\:$ yields an isomorphism $\rm\ (\mathbb N^{\mathbb N},\: +)\:\cong (\mathbb P\:,\: \cdot)\:.\:$ That this map is onto means the primes are generators, i.e. existence of prime factorization; that it is $1$ to $1$ is the inference displayed above - that there are no nontrivial multiplicative relations between the generators, i.e. uniqueness of prime factorizations.

Your question has to do not with the above semantics of unique factorization but rather with the syntactic issues of how one chooses to represent terms of (free) monoids. There are of course various possibilities. Monoid terms may be represented as strings, multisets, or bags, depending on what is convenient for man or machine. But these low-level representational details have little to do with the high-level concepts. As I stressed in your prior questions, if one spends too much time dwelling on such low-level representaional matters then one risks missing the forest for the trees.

Associative normalization is indeed built-in to the representation - whether it be notation employed by humans or bags/multisets by machines. But that's not a flaw but, rather, a feature. There is no need to speak of different associations of products when working in monoids because associativity holds universally in monoids by hypothesis (axiom). This universal normalization is done once and for all so that one can focus on the essence of the matter. Associativity of multiplication is no more of a concern in monoid expressions than is associativity of addition in polynomial expressions. The same holds true even in real-world contexts. Remote control manuals don't say anything about the associativity of a string of button presses because there is no need to. It is assumed by the context that $\rm(A\ B)\ C = A\ (B\ C)$. Hence it makes no difference whether one places $\rm(A\ B)$ onto a macro button $\rm D$ then executes $\rm D C$, or if one places $\rm (B C)$ onto a macro button $\rm E$ and then executes $\rm A\ E$. Such hypotheses are built-in in by default in many contexts - whether rigorously or informally.

Compare the above to the reply that you'd receive by phoning customer support for your DVR and asking them the analogous question about associativity of button presses. Being a philosopher, perhaps you may find that exercise more interesting than this one. Their informal explanations may reveal more about such epistemological matters than any replies here.

  • 1
    A comment on the first paragraph: It's a bit precious to be insisting on a certain ordering of parentheses without defining the expected order of multiplication represented by exponentiation. If you want to avoid implicitly assuming associativity, you shouldn't substitute for that an implicit assumption of power associativity! – C Monsour Apr 21 at 9:45
  • I also wouldn't suggest phoning customer support with a question about discrete valuation rings. Try Stack Exchange instead. :) – C Monsour Apr 21 at 9:46

To provide a new answer to the new question (as opposed to all the merged in answers to a very old question): there is no inherent reason.

Presumably it is mostly an artifact of the fact that we can notationally leverage associativity by simply omitting parentheses, but we can't do the same for commutativity since text is a linear medium.

Really, it comes down to what exactly you take the Fundamental Theorem of Arithmetic as saying. Specifically, what a "product of powers of primes" means. In more formal presentations, we usually say something like: for each positive integer $n$, we have a (finite) set of primes $P$ and a family of positive integers $\{n_p\}_{p\in P}$ such that $n = \prod_{p\in P}p^{n_p}$ and that together $P$ and the family $\{n_p\}_{p\in P}$ are uniquely determined by $n$. Another common rendition is that for each positive integer $n$, there is a unique (finite) multiset (aka bag) of primes, $B_n$, such that $n=\prod B_n$ which is well-defined because multiplication is associative and commutative. Another rendition would be that for each positive integer $n$, there is a list (aka finite sequence) of primes, $L_n$, such that $n=\prod L_n$ which is well-defined because multiplication is associative. This list is then only unique up to reordering. A list modulo reordering is a finite multiset.

We could choose other representations for a "product of powers of primes". For example, we could say that for each positive integer $n$, we get a term $t_n$ in the term algebra $T_\Sigma(\mathbb P)$ where $\mathbb P$ is the set of primes and the signature $\Sigma$ consists of a constant symbol $1$ and a binary operation $*$. We have $n=\prod(t_n)$ where $\prod:T_\Sigma(\mathbb P)\to\mathbb N$ is defined by structural induction via $\prod(1)=1$, $\prod(p)=p$, and $\prod(t*t')=\prod(t)\prod(t')$. $t_n$ is then unique up to reassociating uses of $*$, reordering the arguments of $*$, and considering $1*t=t=t*1$. We could quotient $T_\Sigma(\mathbb P)$ by the congruence generated by relating $1*t\sim t\sim t*1$. This would make $T_\Sigma(\mathbb P)/{\sim}$ a free unital magma. $\prod$ remains well-defined and the $t_n\in T_\Sigma(\mathbb P)/{\sim}$ is now unique up to reassociating uses of $*$ and reordering the arguments of $*$. We could further quotient by the congruence generated by additionally relating $(t*t')*t\sim t*(t'*t'')$. This makes $T_\Sigma(\mathbb P)/{\sim}$ a free monoid, i.e. the set of lists of primes. $\prod$ remains well-defined and $t_n$ is unique up to reordering the arguments of $*$. Indeed, $t_n$ is essentially $L_n$ from the previous paragraph. We could then further quotient by the congruence generated by additionally relating $t*t'\sim t'*t$. In this case $T_\Sigma(\mathbb P)/{\sim}$ is essentially the set of finite multisets of primes. $\prod$ remains well-defined and $t_n$ is now simply unique. It should come as no surprise now that $t_n$ is essentially $B_n$ from the previous paragraph.

This term-oriented perspective makes it clear that there is no inherent reason to consider terms modulo associativity and identity but not commutativity. Thinking in terms of lists, though, i.e. up to associativity and identity but not commutativity, has some benefits. First, lists/finite sequences are things that most people are familiar with while multisets/bags are much less discussed. Lists are more canonical than the other choices I mentioned except for multisets. Lists viewed as terms modulo associativity and identity have normal forms, while multisets do not. Roughly speaking, this means two normal form terms of the free monoid term algebra are equal if and only if they look equal. Admittedly, that doesn't help much in this case since we are only considering lists up to reordering.

Ultimately, the way I'd recommend thinking of the Fundamental Theorem of Arithmetic is that it says that every positive integer is equal to the product of a multiset of primes for some unique multiset of primes. Saying a "list up to reordering" is just a way to say "multiset" without having to explicitly introduce the concept of a multiset.

  • 1
    The formulation I personally like is that, for every positive integer $x$, there exists a unique finitely supported sequence $\langle a\rangle$ of non-negative integers such that $x=\prod_i p_i^{a_i}$, where $p_i$ is the $i$-th prime. While it has the downside of featuring an infinite product, and thus needing a formal definition of what such a product means, it also has the advantage of giving an explicit group isomorphism between $(\mathbb N_+,\cdot)$ and $(\mathbb N_0^*,+)$ (which can be naturally extended to $(\mathbb Q_+,\cdot)$ and $(\mathbb Z^*,+)$ by adding inverses). – Ilmari Karonen Apr 22 at 16:51
  • @IlmariKaronen: nitpick: unique finitely supported infinite sequence..., since obviously you can truncate such sequences down to finite ones in many ways (unless you live in a world where finite sequences do not exist). – Marc van Leeuwen Apr 23 at 13:26
  • @Marc: I tend to calls those things "tuples". But I do acknowledge that terminology can vary here, and I haven't been perfectly and dogmatically consistent about it myself either. – Ilmari Karonen Apr 23 at 16:47

From Wikipedia:

Thus, when $\ast$ is associative, the evaluation order can therefore be left unspecified without causing ambiguity, by omitting the parentheses

Multiplication is associative, so there is no point in considering $2\cdot(3\cdot 5)$ and $(2\cdot 3)\cdot 5$ as "different ways of writing 30". They both correspond to the expression $2\cdot3\cdot 5$. Or, if you really insist, we can just add "up to order and parentheses" in the statement of FTA.

Under your interpretation, the number of ways of writing $n$ as a product of primes would be $C_{k-1}$ where $k$ is the number of prime factors of $n$, counted with multiplicity (see here). This is nowhere nearly as nice as saying it's unique; yet another reason to avoid this interpretation.

  • @Pete I'm not saying that which wff for "abc" you choose will matter when doing conventional number theory, or most branches of mathematics, or large parts of conventional mathematical logic. I say that "abc" is not a wff, and it's not a simple matter like how you can just transform ab into the wff (ab) by putting parentheses around it. Because of this, what 30 equals according to the product of its primes does not come as one and only one wff even up to order of the primes. As an experiment, try writing FTA in Polish, or reverse Polish notation, and see what happens. – Doug Spoonwood Aug 23 '11 at 2:18
  • 15
    @Doug: But FTA is not a uniqueness theorem for syntactic expressions: it is a uniqueness theorem about products of integers. It says that if you have prime numbers $p_1,\ldots,p_r$ and $q_1 \ldots q_s$ so that the (numbers!) $p_1 \cdots p_r = q_1 \cdots q_s$ are equal -- and if you claim not to understand what these products mean you are being too willfully obtuse -- then $r = s$ and there is a permutation $\sigma$ on $\{1,\ldots,r\}$ such that $q_i = p_{\sigma(i)}$ for all $i$. There's no "writing" going on here. – Pete L. Clark Aug 23 '11 at 3:41

In the context of FTA writing a positive integer $n>1$ uniquely as a product of primes means that if $$n=p_1\cdot p_2 \cdots p_n=q_1\cdot q_2\cdots q_m$$ where $p_i,q_j$ are primes, then $n=m$ and there is a permutation $\phi$ of the set $\{1,\ldots,n\}$ such that $q_i=p_{\phi(i)}$ for all $i\in\{1,\ldots,n\}$.

When stating this we understand that associativity of the multiplication of the natural numbers allows us to leave out parentheses in the products of the $p_i$'s and $q_j$'s. Note that writing $30$ as $(2\cdot 3)\cdot 5$ and $2\cdot(3\cdot 5)$ (both of which are equal to $2\cdot 3\cdot 5$) does not contradict FTA in any way.

The theorem's statement is to be interpreted by mathematicians and not by computers. But one can restate the theorem more precisely:

Let $n$ be a integer and $n>1$. There is a unique nonempty finite set $A$ consisting of prime numbers and a unique function $f:A\to \Bbb N$ such that $$n=\prod_{p\in A}p^{f(p)}$$

One needs to define and interpret product $\prod_{p\in A}p^{f(p)}$. The following theorem provides a definition:

Let $A$ be a finite set and $f:A\to \Bbb N$ be any function. There is a unique $m\in \Bbb N$ such that for every $a_1,\dots,a_n\in A$ with $A=\{a_1,\dots,a_n\}$, we have $$m=f(a_1)f(a_2)\dots f(a_n)$$ where the product is calculated by Polish notation (I omit the parantheses to keep it readable).

As is clear, a precise statement is hard to understand for humans. However, computers may be unable to interpret the usual rough (but friendly) statement.

Your point of view is more useful in promramming. It is not mathematical.


Btw, if you are familiar with programming you may know that in a class (for example in C++ or C#) the equality operator can be defined such that normally different class objects are the same. For example a string $(ab)c$ can be the same as $a(bc)$ as class objects.

Tl;Dr: the philosophy to view associativity as a more primitive notion than commutativity, is a consequence of viewing a finite set as a sequence, and of writing formulas on one line. If we were aliens that are used to view a finite set as a full binary tree and to write down formulas in various graph-like shapes, we would probably consider commutativity as being the more primitive notion and instead of

$\qquad$Prime factorization is unique up to a reordering of the factors.

we would say:

$\qquad$Prime factorization is unique up to a repairing of the factors. Bleep.


Uniqueness up to reordering the factors, really means: There is a sequence of prime numbers (possibly with repetition) whose product is $n$.

As Derek Elkins points out in his answer, the magic lies in the word product: It assumes we have defined what it means to take the product of a finite sequence of integers. We could define the product by multiplying the first and the second, then multiplying that result with the third, and so on: $$\prod_{i=1}^4p_i = ((p_1p_2)p_3)p_4$$ Note how we don't need associativity to define this. But associativity is an interesting property, since it implies that we get the same result by defining the above product as, for example, $$p_1(p_2(p_3p_4))$$ But in "the product of a sequence", the absence of any indication of where to put the brackets, suggests that we don't want to specify that, meaning that this phrase is well-adapted only to associative operations.

Likewise, "the product of a multiset" is a phrase that is well-adapted to associative and commutative operations.

Full binary trees are well adapted to commutative operations:

enter image description here (src)

("Full" means that every node has 0 or 2 childs.) It's a way to iterate an operation in a setting where we care about associativity but no commutativity: write a number at each leaf (a node without children). Multiply any two leaves with the same parent, write the result at their parent node, erase the two leaves and repeat the operation with the resulting tree.

Compare with $$2 \cdot 7 \cdot 3 \cdot 11$$ where we (may) care about commutativity but not about where to put the brackets. The algorithm is now: choose any two adjacent nodes, multiply them and consider them as one node.


To conclude, besides the fact that associative operations occur more naturally (composition of functions is associative), another reason why we use notations and terminology that are well-adapted to associative operations, is that we write line by line (sometimes column by column), instead of writing in the shape of trees and graphs.

It's all about uniformity of arrays. If $(xy)z$ is thought of as distinct from $x(yz)$, all is lost, and you win. If $(xy)z$ is synonymous with $x(yz)$ and to $(yz)x$, only a particular factorization is valid and logical.

  • 4
    It is amazing that your post contains no e's – robjohn Dec 16 '12 at 1:22
  • 3
    Alas, your alias contains a taboo symbol, totally disqualifying you from claiming this bounty. – Jason DeVito Dec 16 '12 at 2:38
  • Although your followup is a lipogram, its scholarly corpus is insubstantial, and not much good. – MJD Dec 16 '12 at 3:48

While being sloppy, mathematicians create an intuitive and simple language that allows deeper and deeper investigations in an extraordinary creative activity. Keeping all parenthesis and avoid all informal constructions would make mathematics more static.

Of course one can define a normal form which cooperates with the idea of the Fundamental Theorem of Arithmetic.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.