Natural number ( $N$ )

The natural numbers are the nonnegative integers

0, 1, 2, \dots

Table of contents
- Minimum excludant Natural number
  - Minimum excluded positive integer Minimum excludant
- Well-ordering principle for the natural numbers Natural number
  - Proof by minimal counterexample Well-ordering principle for the natural numbers

Minimum excludant ( $mex$ )

 0  0

The minimum excludant of a finite set of nonnegative integers is the smallest nonnegative integer absent from the set. For example,

mex {0, 1, 3} = 2

Minimum excluded positive integer

 0  0

For a set of positive integers, its minimum excluded positive integer is the least positive integer absent from the set. This is the positive-indexed version of the minimum excludant, which normally allows zero.

Well-ordering principle for the natural numbers ( $S \subseteq N, S \neq = \emptyset \Rightarrow min S exists$ )

 0  0

Every nonempty subset of the natural numbers has a least element in their usual order. Applying this principle to positive integer linear combinations proves Bézout's identity. This principle for the usual natural-number order is distinct from the general well-ordering theorem asserting that every set can be equipped with some well-order.

Proof by minimal counterexample

 0  0

Assume that a proposed statement fails for some natural number, and choose the least failing index using the well-ordering principle. Prove the necessary base cases and reduce the least failure to a smaller index that must satisfy the statement. If that smaller case implies the alleged failure also satisfies it, there is a contradiction. Reductions by a step larger than one require enough consecutive base cases to cover every possible residue class.