Princípio da boa ordenação

O Princípio da boa ordenação ou princípio da boa ordem diz que todo subconjunto não-vazio formado por números naturais possui um menor elemento. Isso é o mesmo que dizer que todo subconjunto não vazio formado por números inteiros positivos possui um menor elemento. Este princípio é equivalente ao Princípio da indução.

Em teoria de conjuntos, esta noção é generalizada para a de um conjunto bem-ordenado, um conjunto totalmente ordenado tal que todo subconjunto não vazio possui um elemento mínimo.

Na Teoria axiomática dos Conjuntos de Zermelo-Fraenkel [sistema denotado como "ZF sem adição de axiomas extras"], a generalização deste princípio acima é equivalente para o Axioma da Escolha, criado em 1904 pelo matemático alemão Ernst Zermelo. Este é considerado um dos axiomas mais importantes da história da Matemática, apesar de suas consequências não-construtivas e controversas (vide o Paradoxo de Banach-Tarski, entre outros).

Exemplo e motivação

Seja $X\subset \mathbb {N}$ um subconjunto não-vazio do conjunto dos números naturais. Então $n_{0}\in X$ é o elemento mínimo de X quando $n_{0}\leq n,\forall n\in X$. Se $X\subseteq \mathbb {N}$ com $0\in X$, então 0 é o elemento mínimo de X. Isto é óbvio, visto que 0 é o menor elemento de $\mathbb {N} \,$.

Um elemento $k\in X$ é o elemento máximo de X quando $k\geq n,\forall n\in X$. Note que $\mathbb {N} \,$ não tem um elemento máximo, logo é de se esperar que existam subconjuntos de $\mathbb {N} \,$ sem um maior elemento.

Prova

Seja um conjunto X subconjunto dos números naturais, ou seja, $X\subset \mathbb {N}$. Por esse princípio, existe um determinado número "n" menor ou igual a todos os elementos do conjunto X, ou seja, $\exists n\leq x,\forall x\in X$. Há duas possibilidades para o conjunto X:

1. O número 1 pertence ao conjunto X, ou seja, $1\in X$. neste caso, 1 será o elemento mínimo do conjunto X.
   • Do contrário, existiria um número "n" pertencente ao conjunto X tal que $n<1$, ou seja, isso implicaria dizer que existe um número natural "q" tal que sua soma com "n" resultasse em 1: $n<1\longrightarrow \exists q\in \mathbb {N} ,n+q=1$ . Entretanto, a soma de dois números naturais é sempre o sucessor de algum número natural, e como 1 não é sucessor de nenhum número, essa tese contrária é um absurdo.
2. O número 1 não pertence ao conjunto X, ou seja, $1\notin X$.
   • Seja um conjunto $B$, subconjunto dos números naturais, tal que todos os seus elementos são menores que os elementos de $X$:

$B=\left\{b\in \mathbb {N} :b<x,\forall x\in X\right\}$ Obviamente, $1\in B$. Como $x\in X\implies x\notin B$ então $B\neq \mathbb {N}$ e deve existir $b_{i}\in B$ tal que $b_{i}+1\notin B$ pois do contrário o princípio da indução finita implicaria que $B=\mathbb {N}$, um absurdo. Além disso como $b_{i}\in B\implies x>b_{i},\forall x\in X$ e como $b_{i}+1\notin B\implies \exists x\in X,b_{i}+1\geq x$ então para algum $x\in X,b_{i}<x\leq b_{i}+1\iff x=b_{i}+1$, por fim se existisse $a\in X,a<b_{i}+1$como $b_{i}\in B\implies b_{i}<a<b_{i}+1$absurdo, logo existe o menor elemento de $X$, o número $b_{i}+1$.

Ver também

• Indução matemática
• Relação bem-ordenada