Seja
. Mostre que a relação de divisibilidade "
" em
é uma ordem parcial. Ou seja, dados
, defina
e mostre que (
) é um conjunto parcialmente ordenado. É verdade que (
) é totalmente ordenado?
Você é capaz de dizer quem são os elementos minimais de (
). Esse conjunto tem elementos maximais?
Passo 1
O enunciado dá o conjunto
e a relação binária definida por
isto é, existe
tal que
. As perguntas são:
- Mostrar que
é um conjunto parcialmente ordenado (ou seja, mostrar as três propriedades que definem uma ordem parcial). - Dizer se
é totalmente ordenado (comparabilidade para todo par). - Identificar os elementos minimais de
. - Dizer se existem elementos maximais e, em caso afirmativo, quais são.
As informações relevantes fornecidas pelo enunciado são apenas a definição de
e a definição da relação
(divisibilidade).
Passo 2
Primeiro vamos lembrar o que precisamos provar para que uma relação
em um conjunto
seja uma ordem parcial:
deve ser reflexiva, antissimétrica e transitiva. Vou provar cada uma dessas propriedades para a relação
em
. Em cada prova eu explico o que uso e por quê, passo a passo.
Passo 3
Definição que vamos usar: uma relação
é reflexiva em
se, para todo
, vale
.
Aplicação aqui: seja
. Podemos escrever
com
. Isso mostra que existe
(escolhemos
) tal que
. Pela definição de divisibilidade, isso significa
. Como
foi arbitrário, concluímos que a relação
é reflexiva em
.
Observação didática: reflexividade costuma ser a parte mais simples — verificar que todo elemento divide a si mesmo usando o fator
.
Passo 4
Definição que vamos usar: uma relação
é antissimétrica se, para quaisquer
,
e
implicam
.
Aplicação aqui: suponha
e que
e
. Então existem
tais que
Substituindo
da primeira equação na segunda obtemos
Agora usamos que estamos em
(números positivos): podemos cancelar o fator
dos dois lados (ou então, observar que a igualdade implica
porque dividindo por
chegamos a isso). Então
Como
, a única maneira de um produto natural ser
é ter
e
. Então
. Portanto
. Isso prova a antissimetria.
Observação didática: o passo de "cancelar
" é só a observação de que
e que se
então
. Em
isso força
.
Passo 5
Definição que vamos usar: uma relação
é transitiva se, para quaisquer
,
e
implicam
.
Aplicação aqui: suponha
com
e
. Então existem
tais que
Substituindo
na expressão de
obtemos
Como
, isso mostra que existe um natural (especificamente
) que multiplica
para dar
; portanto
. Assim a relação é transitiva.
Observação didática: a transitividade da divisibilidade é só a observação de que produtos se combinam: se
é múltiplo de
e
é múltiplo de
, então
é múltiplo de
.
Passo 6
Reunindo os passos anteriores:
em
é reflexiva, antissimétrica e transitiva. Portanto
é, de fato, uma ordem parcial.
Respire fundo — essa parte é sempre a primeira tarefa em questões parecidas: verificar as três propriedades.
Passo 7
Agora vamos ver se a ordem é total. Definição: uma ordem parcial é total se, para quaisquer
, ou
ou
(ou ambos) — em outras palavras, todo par de elementos é comparável.
Para mostrar que não é total basta encontrar um par
tais que nem
nem
. Um contraexemplo simples é
e
. Verificamos:
-
porque não existe com (o único candidato seria que não é natural). -
pela mesma razão (não existe com ).
Portanto
e
são incomparáveis; logo a ordem não é total.
Observação didática: em termos mais gerais, elementos coprimos e maiores que
frequentemente são incomparáveis sob divisibilidade (ex.:
e
,
e
, etc.). Isso mostra que há muitas incomparabilidades.
Passo 8
Definição que vamos usar: um elemento
de um poset
é minimal se não existe
com
e
. Em palavras: não há elemento estritamente menor que
.
Aplicação aqui: em
,
é minimal se não existe
tal que
.
-
Primeiro, examine
. Os divisores de em são apenas (porque não tem divisores naturais além de si mesmo). Então não existe com . Logo é minimal. -
Agora mostro que nenhum outro número é minimal. Seja
. Então e . Isso fornece um com . Portanto não é minimal.
Conclusão: o único elemento minimal em
é
. Além disso,
é mais forte que minimal: é o menor elemento (minimum ou least element), pois
para todo
.
Observação didática: muitas vezes em problemas com divisibilidade, o
aparece como mínimo porque divide tudo.
Passo 9
Definição que vamos usar: um elemento
de um poset é maximal se não existe
com
. Em outras palavras, não há elemento estritamente maior que
.
Aplicação aqui: em
,
é maximal se não existir
tal que
.
Mostro que não existem elementos maximais. Pegue qualquer
. Considere
. Temos
e
. Assim para todo
existe um
maior (no sentido da ordem
) que é múltiplo de
. Portanto nenhum
é maximal.
Observação didática: a existência de infinitos múltiplos de qualquer número impede a existência de máximos. (Uma versão alternativa: para qualquer
há um elemento
para algum primo
que é estritamente maior.)
Passo 10
- Antichain exemplo: o conjunto dos números primos é um antichain (exceto pelo
que não é primo): quaisquer dois primos distintos e não se dividem mutuamente, então são incomparáveis. Isso ilustra bem por que a ordem não é total. - Cadeias infinitas: por exemplo
é uma cadeia infinita (cada termo divide o próximo). - Síntese intuitiva: a relação de divisibilidade organiza os naturais pela propriedade “ser divisor de”; tem um menor elemento (
), muitos elementos incomparáveis (então não é total) e não tem elementos máximos.
Resposta
(
) é ordem parcial: Sim.
Totalmente ordenado?: Não (por exemplo e
são incomparáveis).
Elementos minimais: .
Elementos maximais: não existem.
Totalmente ordenado?: Não (por exemplo
Elementos minimais:
Elementos maximais: não existem.