Análise real/PBO

Teorema (Princípio da boa ordenação)

Todo subconjunto não-vazio $A\subset \mathbb{N}$ possui um elemento mínimo, ou seja, se $A\subset \mathbb{N},A\ne \varnothing ,logo\mathrm{\exists }n\in A,talquen<m,\mathrm{\forall }m\in A-\{n\}$.

Prova

• Devemos mostrar o complementar de $A$ em relação ao $\mathbb{N}$ assim $B\subset \mathbb{N}-A$
  • Tomemos um subconjunto $\mathbb{N}$ : $B$ formado pelos elementos que não estão em $A$, ou seja, $B=\{x\in \mathbb{N}/x\in ̸A\}$.
• a quem pertence o elemento $1$
  • Se $1\in A$ o teorema está demonstrado, pois $1$ é o menor elemento do $\mathbb{N}$.
  • Se $1\in ̸A,$ logo $1\in B$
• O conjunto $I_n$
  • Agora tomemos um subconjunto de $B$, chamado $I_n=\{1,2,...n\}$ onde n é o maior natural tal que aconteça isso, assim $1\in ̸A,2\in ̸A,...,n\in ̸A$
• mostrar que $n+1\in A$
  • Pela construção do conjunto $I_n$, temos que $n\in I_n$. Se $n+1\in B$, teríamos $n+1\in I_n$ e logo $I_{n+1}$. Como não faz sentido, logo $n+1\in ̸B$, portanto $n+1\in A$
• Devemos mostrar que $n+1$ é o menor elemento de $A$
  • Como todos os antecessores de $n+1$ são os elementos de $I_n$, temos que $n+1$ é o menor elemento de $A$, pois os elementos menores que $n+1$ estão em $B$

Teorema (Boa Ordem = Indução)

Vale o Princípio da Boa Ordem se, e somente se, vale o Princípio da Indução.

Demonstração

• Suponha válido o Princípio da Boa Ordem. Seja $A\subset \mathbb{N}$ satisfazendo as propriedades do princípio da indução.
  • Suponhamos, por absurdo, que $A\ne \mathbb{N}$. Isto significa que existe algum elemento de $\mathbb{N}$ que não pertence a A e, portanto, o conjunto $B={\complement }_{\mathbb{N}}A\subset \mathbb{N}$ é não vazio.
  • Pelo Princípio da Boa Ordem, B possui um elemento mínimo $m\in B$. Com certeza m > 1, pois como $1\in A\Rightarrow 1\in ̸A^C=B$. Assim, $m-1$ é um natural menor que m.
  • Pela minimalidade de m, temos que $m-1\in ̸B$ e portanto $m-1\in A$. Pelo 2ª propriedade do princípio da indução, concluímos que $m=(m-1)+1\in A$, o que é um absurdo.
• Suponha válido o Princípio da Indução. Seja $B\subset \mathbb{N}$ não vazio.
  • Suponhamos por absurdo que B não possua elemento mínimo. Em particular, $1\in ̸B$ (senão 1 seria elemento mínimo de B). Seja $A=\{n\in N/n<m,\mathrm{\forall }m\in B\}$.
  • Observamos inicialmente que $A\cap B=\varnothing$. De fato, se $A\cap B\ne \varnothing$, então existiria $n\in A\cap B$, ou seja, n < n.
    • Tendo $n\in A$ temos também n < m qualquer que seja $m\in B$, em particular, tomando $m=n\in B$ obtemos n < n o que é absurdo. Concluímos que $A\cap B=\varnothing$.
  • Mostraremos a seguir que $A=\mathbb{N}$. Vejamos agora que isto é suficiente para concluir a demonstração. Neste caso temos $\varnothing =A\cap B=\mathbb{N}\cap B=B$ contradizendo a hipótese $B\ne \varnothing$.
  • Mostremos, por indução, que $A=\mathbb{N}$. Já sabemos que $1\in ̸B$ e portanto $1<m$ qualquer que seja $m\in B$, ou seja, $1\in A$. Tomemos $n\in A$. Por definição de A temos $n<m$ qualquer que seja $m\in B$, logo $n+1\le m$ para todo $m\in B$. Se $n+1\in B$ então $n+1$ é um elemento mínimo de B. Como, por hipótese, B não possui elemento mínimo, segue que $n+1\in ̸B$ e portanto $n+1<m$ para qualquer $m\in B$. Concluímos que $n+1\in A$. Pelo Princípio da Indução $A=\mathbb{N}$.

Nota: 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 1

Mostre que, dados $a,b\in \mathbb{N},\mathrm{\exists }c\in (\mathbb{N}\cup \{0\}),talqueb\cdot c\le a<b\cdot (c+1)$.

• Dados $a,b\in \mathbb{N}$, pela lei da tricotomia, temos três possibilidades $a<b,a=boub<a$.
  • Caso $a<b$, tome $c=0$, assim $b\cdot 0\le a<b\cdot (0+1)\Rightarrow 0\le a<b$
  • Caso $a=b$, tome $c=1$, assim $b\cdot 1\le a<b\cdot (1+1)\Rightarrow b\le a<2b$
  • Caso $b<a$. Tome $A=\{n\in \mathbb{N};b\cdot n>a\}\subset \mathbb{N}$. A não é vazio, pois $b\cdot (a+1)>a$.
    • Pelo Princípio da Boa Ordem (P.B.O.), $\mathbb{N}\supset A\ne \varnothing \Rightarrow \mathrm{\exists }m\in A;m=min(A)\Rightarrow b\cdot (m-1)<a<b\cdot m$.

Exemplo 2

Se $n\in \mathbb{N},\mathrm{\exists }p\in \mathbb{N},talquen<p<n+1.$

• Considere $A=\{n\in \mathbb{N}:p<n\}\ne \varnothing ,A\subset \mathbb{N}$. Pelo PBO, $\mathrm{\exists }m\in \mathbb{N},talquem=min(A)\Rightarrow m=s(p)\Rightarrow p+1=m\Rightarrow p=m-1$