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

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

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

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

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

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