0

I am having trouble understanding this proof that every integer from 2 onwards can expressed as a product of primes:

Assume the negation of the statement is true (proof by contradiction):

Negation of the statement: There exists an integer greater or equal to 2 that cannot be expressed as a product of primes.

Let S be the set of integers from 2 onwards which cannot be expressed as a product of primes.

By the well ordering property, this set has a least element s, say.

The proof then goes on to show that s is a product of numbers less than s which are prime. So s is a product of primes and I accept this.

The proof then states "So we have a contradiction and s is not in S therefore S is empty."

So the proof shows that s is not an element of S.

How does this prove that S is empty? Do we not have to show that the next least elements (i.e. s+1, s+2 etc) are not in S?

Thank you

Perfect Pans
  • 1
  • 1
    Your negation of the original statement is wrong and should read "there exists an integer greater or equal to 2 that cannot be expressed as a product of primes". – Alex Provost Nov 29 '17 at 13:02
  • I corrected the negation of the original statement and I understand that we don't need the well ordering property here. I was trying to understand how the well ordering property is used though. – Perfect Pans Nov 29 '17 at 13:43
  • It's used to obtain a contradiction, and that's all we need to conclude. – Alex Provost Nov 29 '17 at 13:58

2 Answers2

1

The negation of what we want to prove should read "there exists an integer greater or equal to 2 that cannot be expressed as a product of primes". This is equivalent to the statement that your set $S$ is non-empty. Therefore, upon arriving at a contradiction, this statement has to be false, i.e., $S$ has to be empty.

Alex Provost
  • 20,991
0

We have shown the least value of the set does not belong to the set without actually looking at what the value is. So in short a set cannot exist, as no matter what set we create it will have a least value and as we have shown that cannot exist so the set has to be a null set.

In other words consider $S$ now you have said the least value does not belong to the set. Remove that value and create a new set $S_{new}=S-s$ and you can take the new set into consideration and continue removing elements till there are none left

avz2611
  • 3,658