Anéis Comutativos Ordenados e Princípios de Indução

Prévia do material em texto

Boa Ordenação, Indução Matemática, Indução Forte
Definição 1. Um anel D é um conjunto com duas operações (funções) + : D×D - D, · : D×D - D,
tais que
• (D,+) é um grupo (abeliano) (com elemento neutro 0);
• (D, ·) é um monóide (com elemento neutro 1);
• Val a propriedade distributiva
∀a, b, c ∈ D a(b+ c) = ab+ ac (a+ b)c = ac+ bc
O anel D é comutatívo se o produto · é comutatívo. O anel D é um dóminio se val a lei de anulação do
produto
∀a, b ∈ D ab = 0 =⇒ (a = 0 ∨ b = 0) .
Definição 2. Um anel comutatívo (D,+, ·, 0, 1) é ordenado se existe uma relação ≤ sobre D tal que
1. a ≤ a por cada a ∈ D;
2. Por cada a, b ∈ D, se a ≤ b, b ≤ a, então a = b;
3. Por cada a, b, c ∈ D, se a ≤ b, b ≤ c, então a ≤ c
e tal que ≤ seja compatível com as operações, ou seja
• por cada a, b, c ∈ D, se a ≤ b então a+ c ≤ b+ c;
• por cada a, b, c ∈ D, se 0 ≤ c e se a ≤ b, então ac ≤ bc.
Definição 3. Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado. Denotamos com [0, x] = {y ∈ D | 0 ≤
y ≤ x}. Consideramos o conjunto D≥0 = {x ∈ D | x ≥ 0} dos elementos não negativos em D.
• Dizemos que D≥0 satisfaz ao Princípio da Boa Ordenação (PBO) se ∀S ⊆ D≥0, S 6= ∅, então S tem
mínimo. (ou seja, se cada subconjunto não vazio de D≥0 tem mínimo).
• Dizemos que D≥0 satisfaz ao Princípio de Indução Matemática (PIM) se, ∀S ⊆ D≥0, tal que
– 0 ∈ S
– (∀x ∈ D≥0)(x ∈ S =⇒ x+ 1 ∈ S)
então S = D≥0.
• Dizemos que D≥0 satisfaz ao Princípio de Indução Forte (PIF) se, ∀S ⊆ D≥0, tal que
HPIF1 0 ∈ S,
HPIF2 (∀x ∈ D≥0)([0, x] ⊆ S =⇒ x+ 1 ∈ S),
então S = D≥0.
É claro que PIF =⇒ PIM , porquê a hipótese do PIF é mais fraca da hipótese do PIM.
Proposição 1. Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que D≥0 satisfaz o Principio da
Boa Ordenação. Então, por cada y ∈ D, não existe x ∈ D tal que y < x < y + 1.
1
Demonstração. Consideramos antes de tudo o caso y = 0. Supomos por absurdo que um tal x exista, ou
seja que exista x ∈ D tal que 0 < x < 1. Mas então o conjunto S = {x ∈ D≥0 0 < x < 1} é não vazio.
Pelo Princípio da Boa Ordenação, admite mínimo m = minS. Dado que m ∈ S, temos que 0 < m < 1.
Mas então 0 ≤ m, e então 0 = 0 ·m ≤ m2, mas por a Lei de Anulação do Produto, temos necessariamente
que m2 6= 0, porque se fosse 0 teriamos que m = 0, o que não é. Então 0 < m2. Do outro lado, de m < 1,
multiplicando por m temos1 m2 ≤ m < 1, e por transitividade, temos m2 < 1. Mas então 0 < m2 < 1, ou
seja, m2 ∈ S, mas m2 � m = minS. Absurdo.
Caso y geral. Se existesse x ∈ D tal que y < x < y+1, subtraindo y dos dois lados teriamos 0 < x−y < 1
e então existeria x− y ∈ D estritamente entre 0 e 1 que não pode existir por o caso precedente.
A mesma propriedade de não existencia de elementos entre y e y+1 pode ser deduzida só com o Princípio
de Indução Matemática.
Proposição 2. Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que D≥0 satisfaz o Principio de
Indução. Então, por cada y ∈ D, não existe x ∈ D tal que y < x < y + 1.
Demonstração. Demonstração. Consideramos antes de tudo o caso y = 0. Consideramos S = {x ∈ D≥0 | 0 <
x < 1} e consideramos S = D≥0 \ S. Queremos aplicar o Princípio de Indução Matemática a S. Reparamos
que
• 0 ∈ S.
Provamos agora que se x ∈ S, então x + 1 ∈ S. Mas se x ∈ S, então, ou x ≤ 0, ou x ≤ 1. Se x ≤ 0, o fato
que x ∈ D≥0, o que implica x = 0 e então x + 1 ≥ 1, ou seja x + 1 ∈ S. Se x ≥ 1, então x + 1 > x ≥ 1, e
x+1 ∈ S. Então provamos o passo indutívo para S. Mas o Principio de Indução então garante que S = D≥0
e então S = ∅, ou seja, não existem x ∈ D tais que 0 < x < 1.
Caso y geral. Se existesse x ∈ D tal que y < x < y+1, subtraindo y dos dois lados teriamos 0 < x−y < 1
e então existeria x− y ∈ D estritamente entre 0 e 1 que não pode existir por o caso precedente.
Corolário 1. Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que por cada y ∈ D, não existe
x ∈ D tal que y < x < y + 1. Então, por cada a, b ∈ D, se a > b, então a ≥ b+ 1.
Proposição 3 (PBO =⇒ PIM). Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que D≥0
satisfaz o Principio da Boa Ordenação. Então D≥0 satisfaz o Princípio de Indução Matemática.
Demonstração. Seja S ⊆ D≥0 tal que
• 0 ∈ S
• (∀x ∈ D≥0)(x ∈ S =⇒ x+ 1 ∈ S).
Consideramos S = D≥0 \S, o complementar de S em D≥0. Supomos que S 6= ∅. Dado que temos S ⊆ D≥0,
pelo Princípio da Boa Ordenação, temos que existe minS. Seja m = minS. É claro que m 6= 0, porquê
0 ∈ S. Então, pela corolário precedente, m ≥ 1. Mas então m− 1 ≥ 0. Mas m− 1 < m, então m− 1 6 inS.
Então m − 1 ∈ S. Mas então, por o passo indutívo, (m − 1) + 1 ∈ S. Ou seja, m ∈ S. Absurdo, porquê
m ∈ S, ou seja m 6∈ S.
Proposição 4 (PIM =⇒ PIF). Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que D≥0 satisfazo
Princípio de Indução Matemática. Então D≥0 satisfaz o Principio de Indução Forte.
Demonstração. Seja S ⊆ D≥0, tal que
HPIF1 0 ∈ S,
HPIF2 (∀x ∈ D≥0)([0, x] ⊆ S =⇒ x+ 1 ∈ S),
1Porquê: descreva todos os detalhes
2
Temos que mostrar que S = D≥0. Consideramos T = {x ∈ D≥0 [0, x] ⊆ S}. Então é claro que
0 ∈ T
porque [0, 0] = {0} ⊆ S, porque 0 ∈ S por hipótese HPIF1. Mostramos que val o passo indutívo para T ,
ou seja que se x ∈ T , então x + 1 ∈ T . Mas se x ∈ T , isto significa que [0, x] ⊆ S. Provamos agora que
[0, x+1] ⊆ S. Seja então z ∈ [0, x+1]. Ou 0 ≤ z ≤ x, no qual caso z ∈ [0, x] e então z ∈ S; ou x < z ≤ x+1,
o que implica por a não existencia de elementos estritamente entre x e x + 1 (que segue só do PIM), que
z = x+1 ∈ S, por HPIF2. Então [0, x+1] ⊆ S e então x+1 ∈ T . O que prova o passo Indutívo. Mas então
T = D≥0, ou seja D≥0 ⊆ T , o que significa que por cada x ≥ 0, temos [0, x] ⊆ S, que implica que x ∈ S. Ou
seja, se x ≥ 0, isto implica que x ∈ S. Mas então D≥0 ⊆ S, que é equivalente a D≥0 = S.
Proposição 5 (PIF =⇒ PBO). Seja (D,+, ·, 0, 1,≤) um domínio comutativo ordenado tal que D≥0 satisfaz
o Principio de Indução Forte. Então D≥0 satisfaz o Princípio da da Boa Ordenação.
Demonstração. Usamos que PIF implica PIM e então que PIF implica, por cada y ∈ D, a não existencia de
elementos x estritamente entre y e y + 1. Seja agora S ⊆ D≥0, tal que S 6= ∅. Para provar PBO, temos que
provar que S tem mínimo. Supomos que não tenha mínimo. Então 0 6∈ S, se não seria certamente mínimo,
dado que S ⊆ D≥0. Seja S = D≥0 \ S e aplicamos o PIF a S. Já temos
HPIF1 0 ∈ S .
Temos agora que provar HPIF2 para S. Supomos que [0, x] ⊆ S. Mas então ∀z ∈ S, z > x. Dado que não
ha elementos entre x e x+1, temos que ∀z ∈ S, z ≥ x+1. Então, se x+1 ∈ S, teriamos que x+1 = minS.
O que é absurdo, porquê assumimos que S não admite mínimo. Mas então x+1 ∈ S. Mas então val HPIF2
para S. Mas então podemos aplicar PIF a S e concluir que S = D≥0. Mas então S = ∅. Mas isto é absurdo,
porque foi assumido que S 6= ∅. Então S tem que ter mínimo.
3