Unique Representation and The Fundamental Theorem of Arithmetic

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

-
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
You've asked a couple prior questions that explictly show nontrivial knowledge of matters regarding associativity of operations, e.g. this one. How can someone with such knowledge not already know the obvious answer to the above question? Is the above a serious question or, rather, is it yet another springboard for one of your critiques on the imprecision of informal mathematical conventions? –  Bill Dubuque Aug 22 '11 at 22:15
@Doug: You said it yourself. $2 * (3 * 5)$ and $(2 * 3)*5$ denote the same quantity. Therefore they are the same. End of story. –  JavaMan Aug 23 '11 at 1:01
I removed the "number-theory" tag and replaced it by "notation" since the question has nothing to do with number theory but, rather, with the notation used for associative operations, and general associativity. If it's tagged with any algebraic theory it should probably be group-theory, or elementary-group-theory. –  Bill Dubuque Aug 23 '11 at 1:34
@Doug: it would be best if you stopped using this site as a place where to evangelize. I am informed you do have a blog. Use it. –  Mariano Suárez-Alvarez Aug 24 '11 at 19:28

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

-
Matt E said to me on meta that "Dear Doug, I think most mathematicians regard xyz (multiplication of three numbers) as a ternary operation; at least I do." This answer makes sense. The binary operation can get used to define the k-ary operation, hence you'll see something like 2*3*5. But, the k-ary product does seem consonant with how many mathematicians think, especially when you consider the use of the capital Greek Sigma, and the capital Greek Pi symbols for k-ary sums, and n-ary products. –  Doug Spoonwood Nov 3 '11 at 4:52
As a consequence of making this all clear, one can reason that the k-ary products here don't have to get defined by the binary multiplication operation. They can get defined that way, of course, but strictly speaking other definitions could work. I mean so long as we have the k-ary product of primes equal to what using "repeated" binary multiplications would give us (that is *_3(2, 3, 5)=30 for example) we could have *_3(2, 4, 5)=500 instead of *_3(2, 4, 5)=40. –  Doug Spoonwood Nov 3 '11 at 23:27

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.

-
If my question has to do with the syntactic issues, that seems appropriate to me. I haven't seen any sufficiently precise definition of a theorem as a semantical statement, but I have as a syntactical statement. I don't see how this devolves into "low-level" representational details as you appear to imply though. A theorem by its very nature connects statements together, which at the very least, I would classify as coming at a higher level than considering those statements in isolation. An attempt at a theorem, attempts to connect statements together. –  Doug Spoonwood Aug 25 '11 at 0:55
@Doug Unique factorization is most naturally stated in the language of commutative monoids - see my recent comments to your answer. It's a property of a monoid. You're attempting to state it more syntactically in terms of some specific presentation of the monoid. That's unnecessary. It obfuscates the essence of the matter. It's akin to stating the associative law for a ring by first choosing a matrix representation then stating the law as some messy equation in terms of the coordinates of the matrices, vs. the much simpler $A(BC)=(AB)C$. –  Bill Dubuque Aug 25 '11 at 20:09
I'm not entirely clear how what you wrote above happens in the language of commutative monoids. Of course, you can't have both an exponential and a multiplication operation in a commutative monoid. So "2^(u0)" would have to come as an abbreviation for (2*(2*(...)), in other words, informally a product of 2s u0 times, which seems to happen outside the language of commutative monoids, as does ui=vi. –  Doug Spoonwood Oct 26 '11 at 22:19
Curiously, almost all answers were downvoted an hour ago. –  Bill Dubuque Jul 2 at 21:22

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.

-
In the integers under the binary operation of subtraction, there exist plenty of examples where a(bc) does not equal (ab)c. For example, 6 ( 4 8)=6(-4)=ten and (6 4) 8=2 8=-6. Given that you can join to that structure the appropriate product function P of variable arity, you can still write all terms here as a unique product P of primes... (6 4) 8=(2 3P2 2P)2 2 2P=2 8=-6. –  Doug Spoonwood Dec 16 '12 at 23:44
@DougSpoonwood I avow that associativity is not a trait of subtraction as a binary function. In point of fact, $2a=(a−1)+(a+1)=(a−2)+(a+2)$ and so on, forming $2a$ in many distinct ways. Thus additivity also won't factor simply. But by assumption in a UFD things fully and distictly factor by multiplication, not by addition or subtraction. All my post says that associativity of multiplication is an axiomatic principal of any UFD. –  Alexander Gruber Dec 17 '12 at 0:25
Consider the natural numbers under all possible binary operations and extended k-ary multiplication. This is NOT a UFD. You can still express every single number in every single meaningful expression in this structure uniquely as a k-ary product of only primes up to the permutation of the primes. So, how do UFDs, since they're commutative rings and the aforementioned structure is not a commutative ring, end up mattering here? –  Doug Spoonwood Dec 17 '12 at 1:54
Bravo.${}{}{}{}$ –  MJD Dec 17 '12 at 10:37

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.

-
@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
@Doug: You can apply it meaningfully because we're talking about numbers, not syntax. The syntax is just a means to the number. You're officially the first person I've ever met to get waist-deep in formal logic before you even understand what a number is. Not to mention Pete's already given you a way to inductively define the expressions with unique placement of parentheses - completely dispelling any issue you should have - and yet you simply look the other way and continue to argue and argue. This is the definition of obtuse. –  anon Aug 23 '11 at 5:10
@Doug: I give up. If what I said above it not enough to tell you what $p_1 \cdots p_r$ means then you are beyond my ability to help. –  Pete L. Clark Aug 23 '11 at 14:08
@Doug: Sorry, but mathematicians don't play by your rules. The expression $2\cdot3\cdot5$ outside of formal logic - which I keep telling you is where you are but you don't seem willing to listen to me - denotes the number that is a result of any number of multiplications, and it is well-defined because it is the same number regardless of how one proceeds. Imagine you're at a party and someone comes back with food saying "I went to the store," and you pretend not to understand what this means because they didn't specify which route they took. Naturally, you will not be taken seriously. –  anon Aug 23 '11 at 17:09
@Doug: How many times do I have to tell you we're not working in formal logic? How many times? Moreover, you're blatantly putting words in our mouths (we're talking specifically about standard multiplication in arithmetic, not multiplication plus your made-up operation); you are voicing concern over an imaginary position that exists only in your head. If you don't have the courtesy to listen to a word I say, I'm not going to say any further word to you. –  anon Aug 23 '11 at 21:03

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.

-
@Doug Spoonwood: your last comment shows either a lack of knowledge of associativity or (which seems more likely) a strange unwilligness to accept it. Since multiplication of integers is associative, it doesn't matter how you put the parentheses in. In other words, $a*b*c$ means both $(a*b)*c$ and $a*(b*c)$, which makes sense because these two elements are the same. None of this has anything to do with FTA... –  Pete L. Clark Aug 23 '11 at 1:26
@Doug: $a*b*c$ denotes a number. And only one possible number. There is no ambiguity - that is, unless you try to interpret it instead as nothing but a string of symbols to be constructed according to the conventions of formal logic. But the FTA isn't a theorem from formal logic, it's from arithmetic. I'm sorry, but sometimes the conventions from one area of math don't conform to the conventions of another. –  anon Aug 23 '11 at 2:56
@Doug: I already gave you a precise inductive definition of the syntactic expression $a_1 * \cdots * a_n$ for any positive integer $n$. Other definitions are possible...as always. If your point is merely that according to some standard rules of syntax $a*b*c$ is an abbreviation for a more complicated syntactically correct expression then....yes, you're right. But what does this have to do with FTA? (Answer: nothing.) –  Pete L. Clark Aug 23 '11 at 3:35
@Doug: Like I've said, you're not in Kansas / formal logic anymore. When an expression would be ambiguous because it's missing notation, but every possible consistent use of notation results in the same object, mathematicians simply don't bother with the notation. One can always translate the "ambiguous" notation into a more formal one by arbitrarily choosing how to insert accompanying notation - this should be a completely obvious fact that everyone immediately understands. You're going to have to accept the fact that mathematicians care more about substance than semantics. –  anon Aug 23 '11 at 5:24
Construing what I'm saying as giving you multiple contradictory definitions is a major misunderstanding on your part. I'm saying that you should use any one of several perfectly good definitions. And you should straighten out this basic stuff before you ask questions like "If uniqueness fails, what does the Fundamental Theorem of Arithmetic try to say?" Your apparent attitude -- that maybe large parts of mathematics are somehow invalid because no one before you has thought pedantically about syntactic issues -- is somewhat annoying to me, and I suspect to others as well. –  Pete L. Clark Aug 23 '11 at 18:32

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.

-

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.

-
It is amazing that your post contains no &#x65;'s –  robjohn Dec 16 '12 at 1:22
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
Phira's answer made it clear to me that ((xy)*z) and (x*(yz)) can get thought of as distinct AND we can still have the fundamental theorem of arithmetic (FTA), since it concerns a k-ary product up to a permutation of primes. FTA doesn't concern a binary product. –  Doug Spoonwood Dec 16 '12 at 23:49

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.

-

While being sloppy, mathematicians create a 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. (Nice record you got here, net 25-59 votes :)

-

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.

-
FTA is a statement about the multiplicative monoid $P$ of integers $>0$, not about some specific presentation of $P$. We can state FTA in the same manner that we state other laws of $P$, e.g. the cancellation law $ab = ac$ $\implies$ $b = c$. But first we need to define the $k$-ary derived multiplication operations $m_k(a_1,\cdots,a_k) = a_1\cdots a_k$. Now uniqueness of factorization may be stated as: if $p_i, q_i$ are primes and $m_j(p_1,\ldots,p_j) = m_k(q_1,\ldots,q_k)$ then $j = k$ and $(p_1,\ldots,p_k) = (q_1,\ldots,q_k)$ up to order, i.e. they are the same as bags or multisets. –  Bill Dubuque Aug 25 '11 at 19:42
Notice that the above makes no mention of any internal structure of the elements of $P$. It matters not if they're ordinals in ZFC or bitstrings in your laptop. Only the abstract monoid structure matters. This statement about uniqueness of factorizations in terms of some generators makes sense in any monoid. As I mentioned elsewhere, it says simply that the set of elements (e.g. generators) is free of any nontrivial multiplicative relations. Google "free monoid". –  Bill Dubuque Aug 25 '11 at 19:53
@Bill If the whole thing gets confined to the multiplicative monoid of integers, I think I agree to what you assert. But, consider this question... where can we apply prime factorization? Well, we can do this outside the multiplicative monoid of positive integers, including anywhere we have multiplication on the positive integers as meaningful. So, say we consider (n, M, P), with n as the positive integers, M as the minimum function, and P as multiplication. We have 23=6 under the notation used for the uniqueness part, which I actually have no problem with as I just take each numeral as... –  Doug Spoonwood Aug 26 '11 at 1:57
@Bill representing a number, and thus "23" indicates the product of "2" and "3" as the notation "ab" indicates for a multiplicative monoid. So, in (n, M, P), if we have a consistent notation, we should have 2M23 as meaningful, given 23 as representing a prime factorization. But, it's simply not, since (2M2)3=23=6, 2M(23)=2M6=2. The existence of a prime factorization of "6" into "23" clearly still applies here. But, to resolve the ambiguity of 2M23 and interpret things consistently, I don't see how we still will have uniqueness of prime factorization, even though we still have existence. –  Doug Spoonwood Aug 26 '11 at 2:05
Unique factorization as in $\mathbb N$ is about factorizations in commutative monoids, not other algebraic structures with multiple binary operations. Your odds of receiving replies will be much higher if you use standard mathematical language and notation. –  Bill Dubuque Aug 26 '11 at 2:29