Princípio da boa ordenação

Predefinição:Mais notas 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\le n,\mathrm{\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\ge n,\mathrm{\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, $\mathrm{\exists }n\le x,\mathrm{\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⟶\mathrm{\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=\{b\in \mathbb{N}:b<x,\mathrm{\forall }x\in X\}$ Obviamente, $1\in B$. Como $x\in X⟹x\notin B$ então $B\ne \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⟹x>b_i,\mathrm{\forall }x\in X$ e como $b_i+1\notin B⟹\mathrm{\exists }x\in X,b_i+1\ge x$ então para algum $x\in X,b_i<x\le b_i+1⟺x=b_i+1$, por fim se existisse $a\in X,a<b_i+1$como $b_i\in B⟹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