Does a proof using the well-ordering principle need a base case?
In the Wiki page,


  In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element.


Pay attention to the word non-empty.

Consider the negation of P(n). Before you assume the set that satisfying P(n) is false has a smallest element m, you already assume that the set is non-empty. You prove that there is another element that is less than m. This contradicts the assumption that the set is non-empty. Thus, the set is empty which means P(n) is true.