4

In this very short paper by Dustin J. Mixon, 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?

Thanks.

Pedro
  • 18,817
  • 7
  • 65
  • 127
  • 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
  • 2
    @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 04:20

2 Answers2

1

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.

Michael Hardy
  • 1
Daniel Fischer
  • 206,697
  • @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
1

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.

Michael Hardy
  • 1