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}$.

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} ,\exists \;c\in (\mathbb {N} \cup \{0\}),tal\;que\;b\cdot c\leq a<b\cdot (c+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$