Proposición: principio de la buena ordenación

El principio de la buena ordenación que si (\mathbb{N}_0, \leq) es un conjunto bien ordenado (es decir, cualquier subconjunto de \mathbb{N}_0 no vacío) tiene mínimo

Demostración: principio de la buena ordenación

Se va a probar por reducción al absurdo

Supongamos que existe un subconjunto A\subset\mathbb{N}_0, A\not=\emptyset, que no tiene mínimo

Entonces definimos el conjunto S=\{n\in\mathbb{N}_0|n\leq a, \forall a\in A\}

Debemos darnos cuenta de que si n\in A\cap S, tendríamos que n=\text{mín}(S) y hemos supuesto que S no tiene mínimo, por tanto A\cap S=\emptyset

Ahora vamos a probarlo para todo el conjunto usando el axioma de inducción:

Comprobamos que 0\in S
0+a=a entonces 0\leq a, \forall a\in A

\text{Si }n\in S, como A\cap S=\emptyset entonces n < a, \forall a\in A, (por la definición de orden en \mathbb{N}_0) en cada caso existirá un número natural n_a \geq 1 tal que n+n_a=a, con lo cual se cumple siempre que s(n)=n+1\leq n+n_a=a, y por tanto s(n)\in S

Cumpliéndose estas condiciones, el axioma de completitud nos asegura que S=\mathbb{N}_0

Que es un absurdo, ya que A\cap S=\emptyset entonces A=\emptyset, que es claramente una contradicción de la suposición original A\not=\emptyset