2
$\begingroup$

The standard proof of the fundamental theorem of arithmetic uses the well-ordering property of natural numbers. The contradiction argument claims that "By the Well-Ordering Principle, there is a smallest integer with this property" (meaning can be written as products of primes in more that one way).

My question is, why do we need to assume this? Why cannot we just build the contradiction claim as "Let's assume there is an integer which can be written as products of primes in more than one way" and continue to show the contradiction just following the exact same steps?

$\endgroup$
3
  • 2
    $\begingroup$ What would the contradiction be without the well-ordering property? $\endgroup$
    – Martin R
    Jul 10, 2019 at 15:01
  • 2
    $\begingroup$ You might find the answer on this yourself by trying to prove it on base of your assumption. $\endgroup$
    – drhab
    Jul 10, 2019 at 15:06
  • 1
    $\begingroup$ What is commonly described as the "well-ordering principle" for natural numbers is equivalent to the principle of induction for natural numbers. So you might well put your Question in better context if you look into this equivalence and phrase the problem in terms of what you would be assuming without the well-ordering property. For example, the ring of rational numbers $\mathbb Q$ shares some properties of arithmetic with the natural numbers, but there is no notion of "smallest integer" that we can appeal to. $\endgroup$
    – hardmath
    Jul 10, 2019 at 15:38

2 Answers 2

Reset to default
2
$\begingroup$

Without the well ordering property each number with multiple factorizations could be the product of some prime and another number with multiple factorizations.

$\endgroup$
2
$\begingroup$

A contradiction could be, that if there exist a least element, it produces a lower least element in a given set. In any set with a least element, this either has to stop eventually, or the solutions can no longer be labelled because some aren't even in the set, and none can be labelled the least, because we can't put them in bijection with ordinals. ex.

$$i^2=-1\\(-1)\cdot 1=-1\\(-i)^2=-1$$ Without a sense of ordering, we can't label any one of these the least factorization of -1 . Similarly, we can't call something the smallest counterexample, if it produces a smaller counterexample, where smallest is replacing first in order of a list of counterexamples ordered by place in underlying set.

The whole point of prime factorization is to an extent, to find a labeling of a number, written using the least factorizable numbers as bases, without an ordering, how do we tell which numbers those are ?

$\endgroup$

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