# 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\neq \varnothing ,\;logo\;\exists \;n\in A,\;tal\;que\;n<m,\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\not \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\not \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\not \in A,2\not \in A,...,n\not \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\not \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\neq \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\not \in A^{C}=B$. Assim, $m-1$ é um natural menor que m.
** Pela minimalidade de m, temos que $m-1\not \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\not \in B$ (senão 1 seria elemento mínimo de B). Seja $A=\{n\in N/n<m,\forall \;m\in B\}$.
** Observamos inicialmente que $A\cap B=\varnothing$. De fato, se $A\cap B\neq \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\neq \varnothing$.
** Mostremos, por indução, que $A=\mathbb {N}$. Já sabemos que $1\not \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\leq 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\not \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}$.

## Exemplo 1

* Dados $a,b\in \mathbb {N}$, pela lei da tricotomia, temos três possibilidades $a<b,a=b\;ou\;b<a$.
** Caso $a<b$, tome $c=0$, assim $b\cdot 0\leq a<b\cdot (0+1)\Rightarrow 0\leq a<b$
** Caso $a=b$, tome $c=1$, assim $b\cdot 1\leq a<b\cdot (1+1)\Rightarrow b\leq 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\neq \varnothing \Rightarrow \exists \;m\in A;m=min(A)\Rightarrow b\cdot (m-1)<a<b\cdot m$.

## Exemplo 2

Se $n\in \mathbb {N} ,\not \exists \;p\in \mathbb {N} ,tal\;que\;n<p<n+1.$
* Considere $A=\{n\in \mathbb {N} :p<n\}\neq \varnothing ,A\subset \mathbb {N}$. Pelo PBO, $\exists m\in \mathbb {N} ,tal\;que\;m=min(A)\Rightarrow m=s(p)\Rightarrow p+1=m\Rightarrow p=m-1$