Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In this very short paper, I would like understand why the author says

$f$ is injective by the fundamental theorem of arithmetic

In my opinion, the Fundamental Theorem of Arithmetic (FTA) is necessary to define $f$, but it isn't necessary to prove that $f$ is injective. For example, if FTA were not true but you were able to ensure the uniqueness of $k_i$ by any other way then $f$ would be injective because $(k_1,\ldots,k_N)=(m_1,\dots,m_N)\Rightarrow k_i=m_i$.

In other words, I think the uniqueness of $k_i$ (and therfore FTA) is necessary to define $f$, but not to prove that $f$ is injective.

What can you talk about this?


share|cite|improve this question
I think a better way to conclude this paper would have been "considering the injectivity of $f$, the fundamental theorem of arithmetic and the pigeonhole principle are now contradictory". – M Turgeon Jun 25 '13 at 23:07
@MTurgeon : I think it would have been better not to phrase the argument as a proof by contradiction at all. Instead of saying "Suppose only $N$ primes exist" and getting a contradiction, one could say "Consider any set of $N$ primes", and then show that there are some numbers bigger than $1$ that are not divisible by any of those. I think that is more straightforward. For one thing, it makes it clear that the proof is constructive. – Michael Hardy Jun 26 '13 at 4:20
up vote 1 down vote accepted

The fundamental theorem of arithmetic isn't necessary to define $f$, nor is it necessary to prove the injectivity of $f$.

The injectivity is immediate because

$$ g \colon \lbrace 0,\, \ldots,\, K\rbrace^N \to \mathbb{N}; \; g(e_1,\, \ldots,\, e_N) = \prod\limits_{i = 1}^N {p_i}^{e_i}$$

is a left inverse of $f$.

To define $f$, all you need is that each number has some representation as a product of primes. If the FTA didn't hold, such a representation would in general not be unique, but for a finite set of numbers and primes, a representation could be arbitrarily chosen even without thinking about the axiom of choice.

share|cite|improve this answer
@MichaelHardy Thanks. Too much Haskell coding. – Daniel Fischer Jun 25 '13 at 23:03
So, can we say that FTA is "useful" to define $f$, but "not necessary" to its injectivity? – Pedro Jun 25 '13 at 23:10
@Perguntador Yes, we could say that. With the FTA, the definition of $f$ is easy (and it's known that there is only one choice). For the injectivity, all we need is the well-definedness of multiplication. – Daniel Fischer Jun 25 '13 at 23:14

Existence of a prime factorization of each positive integer is necessary for existence of $f(x)$, and uniqueness of a prime factorization of each positive integer is necessary for $f(x)$ to be well defined.

Injectivity of $f$ does not depend on either existence or uniqueness of prime factorizations. It just says there can't be more than one value of $x$ that is equal to a specified product of other numbers.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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