Understanding the sieve of eratosthenes

Question

Wikipedia, explains the basic algorithm of eratosthenes and several pages such as this, explain the refinements made on the sieve. But the thing I'm having a hard time to find is:
Why does the next number after the smallest prime being crossed out with its multiple have to be a prime? Is there a proof for this?
For example:

in the set s = {2,3,4,5,6,7,8,9}, after crossing out all the multiples of 2 (including 2 itself), why does 3 have, to be a prime?

Answer 1

By induction:

Assume you have found all primes smaller than $n$. All the multiples of these primes have been struck out.

If $n$ is composite, it has a nontrivial prime factor smaller than itself and it is struck out. So it $n$ remains, it must be a prime.

Then you have found all primes smaller than $n+1$.

Answer 2

I find an easy way to think of the why, is

all the numbers that are being crossed off are multiples of the smaller numbers

if it hasn't been crossed off then it isn't a multiple of any smaller number

therefore it is a prime.

Answer 3

By contradiction: If it is not a prime, it is divisible by some smaller factor. So it should be already crossed.