Unique Representation and The Fundamental Theorem of Arithmetic

Question

While reading this thread Is 1 a prime number?, I recalled that The Fundamental Theorem of Arithmetic (FTA) which says that every positive integer greater than 1 can get written uniquely as a product of only primes except for order of the factors. What does "uniqueness" here mean?

I ask, because the way I interpret uniqueness, if uniqueness exists, it means that there exists only one way (except for notation) of writing such a product of primes. E. G. for 6, we can only write (2#3) or (3#2), with "#" indicating multiplication. Those expressions only differ in the order of factors so the theorem applies there.

However, this doesn't always work. For example, say we consider 30 as the integer to get written as a product of primes. Then we can write 30 as ((2#3)#5) as well as writing (2#(3#5)) (note I don't see how 2#3#5 is clear as a unique product, but only that the two meaningful choices which would make it as a shorthand for a product equal each other). The order of factors ((2#3)#5) does not change when passing to (2#(3#5)), nor do we change the notation, so we have two different ways of "writing" 30, which perhaps becomes even more transparent to see if we require that all products get written in prefix or suffix notation (e.g. 30 can get written as ##235, or #2#35, so long as we understand the numerals appropriately). So, does uniqueness fail for FTA, or what exactly does uniqueness mean here? If uniqueness fails, what does the Fundamental Theorem of Arithmetic try to say? Does it mean something along the lines that for any positive integer c greater than 1 there exists a unique bag or multiset b such that no matter which way you take the product of two members of the bag to yield a result r, take the product of r and a member of the bag not used so far, and repeat this process until you have no members of the bag left, you will obtain the integer c?

Addendum: What happens to the Fundamental Theorem of Arithmetic if you require that all products get written via either a prefix notation scheme ("Polish" notation), or a suffix notation scheme ("Reverse Polish" notation)?

Answer 1

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

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 3

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 4

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

Define a "representation" of an integer i greater than 1, as a product r of integers such that r=i. Define a "prime representation" p of an integer greater than 1, as product of integers greater than 1 such that the only numerical symbols in the expression indicate prime numbers, the only operation symbols in the expression are product symbols, and p qualifies as a representation. Suppose we have one and only one symbol for each number, or at least that "14" indicating one number does not get confused with "1 4" which indicates two numbers. Consider all prime representations $p_1$, ... $p_n$ of any given integer i. The following, I think, then can get proven:

Every integer i greater than 1 has at least one prime representation, and if we omit all existing parentheses and operation symbols in prime representations $p_1$, ..., $p_n$ of i, then for all x, for all y, the string obtained from prime representation $p_x$ matches the string obtained from $p_y$ exactly, except for the order of the symbols of the string.

If correct, this at least seems to hold across all notational schemes, as for example, for 30 (ignoring order since P commutes and associates) with "P" as our product symbol, we have prime representations of PP235, P2P35 according to a prefix scheme, ((2P3)P5), (2P(3P5)) according to an infix scheme, and 235PP, 23P5P according to a suffix scheme. All six expressions upon dropping all existing parentheses and operation symbols become 235.

As a corollary, every integer i greater than 1 corresponds to a unique string s, except for order, of prime numbers such that all prime representations which use all of the symbols of s, and only symbols of s as numerical symbols, equal the integer i.

Answer 6

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 7

Following Phira, we can talk about all things of the NATURALS as a singular product K$_z$ of naturals

ab,...,zK$_z$

such that only "a" and 1 can factor into "a", only b and 1 can factor into b, ..., only z and 1 can factor into z, and such that function K$_z$ has z things, and ab,...,zK$_z$=a*b*...*z such that for * ,

1. (x*(y*z))=((x*y)*z) and
2. (x*y)=(y*x).

x factors into y iff (y/x)=n such that n is a natural.

Answer 8

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.