Why worry about commutativity but not associativity in The Fundamental Theorem of Arithmetic?

Question

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? ​

---

It should be noted that some answers to this question were merged from another question, so they may not be completely consistent with this question exactly as it's stated.

Answer 1

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.

Answer 2

"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.

Answer 3

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.

Answer 4

Note This answer was merged from another question, so it may not be completely consistent with the question above.

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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:

^(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.

Answer 9

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.

Answer 10

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.