Seja \mathbb{N}=\{1,2,3, \ldots\}. Mostre que a relação de divisibilidade " \mid " em \mathbb{N} é uma ordem parcial. Ou seja, dados a, b \in \mathbb{N}, defina
a \mid b \quad \text { se } \quad a \text { divide } b
e mostre que ( \mathbb{N}, \mid ) é um conjunto parcialmente ordenado. É verdade que ( \mathbb{N}, \mid ) é totalmente ordenado?
Você é capaz de dizer quem são os elementos minimais de ( \mathbb{N}, \mid ). Esse conjunto tem elementos maximais?

Passo 1

O enunciado dá o conjunto \mathbb{N}=\{1,2,3,\ldots\} e a relação binária definida por
a \mid b \quad\text{se e somente se}\quad a \text{ divide } b,
isto é, existe k\in\mathbb{N} tal que b = a k. As perguntas são:
  1. Mostrar que (\mathbb{N},\mid) é um conjunto parcialmente ordenado (ou seja, mostrar as três propriedades que definem uma ordem parcial).
  2. Dizer se (\mathbb{N},\mid) é totalmente ordenado (comparabilidade para todo par).
  3. Identificar os elementos minimais de (\mathbb{N},\mid).
  4. 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 \mathbb{N} e a definição da relação \mid (divisibilidade).

Passo 2

Primeiro vamos lembrar o que precisamos provar para que uma relação R em um conjunto X seja uma ordem parcial: R deve ser reflexiva, antissimétrica e transitiva. Vou provar cada uma dessas propriedades para a relação \mid em \mathbb{N}. Em cada prova eu explico o que uso e por quê, passo a passo.

Passo 3

Definição que vamos usar: uma relação R é reflexiva em X se, para todo x\in X, vale xRx.
Aplicação aqui: seja a\in\mathbb{N}. Podemos escrever a = a\cdot 1 com 1\in\mathbb{N}. Isso mostra que existe k\in\mathbb{N} (escolhemos k=1) tal que a = a k. Pela definição de divisibilidade, isso significa a \mid a. Como a foi arbitrário, concluímos que a relação \mid é reflexiva em \mathbb{N}.
Observação didática: reflexividade costuma ser a parte mais simples — verificar que todo elemento divide a si mesmo usando o fator 1.

Passo 4

Definição que vamos usar: uma relação R é antissimétrica se, para quaisquer x,y\in X, xRy e yRx implicam x=y.
Aplicação aqui: suponha a,b\in\mathbb{N} e que a\mid b e b\mid a. Então existem k,l\in\mathbb{N} tais que
b = a k \quad\text{e}\quad a = b l.
Substituindo b da primeira equação na segunda obtemos
a = (a k) l = a (k l).
Agora usamos que estamos em \mathbb{N} (números positivos): podemos cancelar o fator a dos dois lados (ou então, observar que a igualdade implica 1 = k l porque dividindo por a chegamos a isso). Então
1 = k l.
Como k,l\in\mathbb{N}, a única maneira de um produto natural ser 1 é ter k=1 e l=1. Então b = a k = a\cdot 1 = a. Portanto a=b. Isso prova a antissimetria.
Observação didática: o passo de "cancelar a" é só a observação de que a\neq 0 e que se a(kl)=a então kl=1. Em \mathbb{N} isso força k=l=1.

Passo 5

Definição que vamos usar: uma relação R é transitiva se, para quaisquer x,y,z\in X, xRy e yRz implicam xRz.
Aplicação aqui: suponha a,b,c\in\mathbb{N} com a\mid b e b\mid c. Então existem k,l\in\mathbb{N} tais que
b = a k \quad\text{e}\quad c = b l.
Substituindo b na expressão de c obtemos
c = (a k) l = a (k l).
Como k l\in\mathbb{N}, isso mostra que existe um natural (especificamente k l) que multiplica a para dar c; portanto a\mid c. Assim a relação é transitiva.
Observação didática: a transitividade da divisibilidade é só a observação de que produtos se combinam: se b é múltiplo de a e c é múltiplo de b, então c é múltiplo de a.

Passo 6

Reunindo os passos anteriores: \mid em \mathbb{N} é reflexiva, antissimétrica e transitiva. Portanto (\mathbb{N},\mid) é, 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 x,y\in X, ou xRy ou yRx (ou ambos) — em outras palavras, todo par de elementos é comparável.
Para mostrar que não é total basta encontrar um par a,b\in\mathbb{N} tais que nem a\mid b nem b\mid a. Um contraexemplo simples é a=2 e b=3. Verificamos:
  • 2\nmid 3 porque não existe k\in\mathbb{N} com 3 = 2k (o único candidato seria k=1{,}5 que não é natural).
  • 3\nmid 2 pela mesma razão (não existe k\in\mathbb{N} com 2 = 3k).
Portanto 2 e 3 são incomparáveis; logo a ordem não é total.
Observação didática: em termos mais gerais, elementos coprimos e maiores que 1 frequentemente são incomparáveis sob divisibilidade (ex.: 4 e 9, 6 e 35, etc.). Isso mostra que há muitas incomparabilidades.

Passo 8

Definição que vamos usar: um elemento m de um poset (X,\le) é minimal se não existe x\in X com x\neq m e x\le m. Em palavras: não há elemento estritamente menor que m.
Aplicação aqui: em (\mathbb{N},\mid), m é minimal se não existe x\neq m tal que x\mid m.
  • Primeiro, examine 1. Os divisores de 1 em \mathbb{N} são apenas 1 (porque 1 não tem divisores naturais além de si mesmo). Então não existe x\neq 1 com x\mid 1. Logo 1 é minimal.
  • Agora mostro que nenhum outro número é minimal. Seja n>1. Então 1\mid n e 1\neq n. Isso fornece um x\neq n com x\mid n. Portanto n não é minimal.
Conclusão: o único elemento minimal em (\mathbb{N},\mid) é 1. Além disso, 1 é mais forte que minimal: é o menor elemento (minimum ou least element), pois 1\mid n para todo n\in\mathbb{N}.
Observação didática: muitas vezes em problemas com divisibilidade, o 1 aparece como mínimo porque divide tudo.

Passo 9

Definição que vamos usar: um elemento M de um poset é maximal se não existe x\neq M com M\le x. Em outras palavras, não há elemento estritamente maior que M.
Aplicação aqui: em (\mathbb{N},\mid), M é maximal se não existir x\neq M tal que M\mid x.
Mostro que não existem elementos maximais. Pegue qualquer n\in\mathbb{N}. Considere x = 2n. Temos n\mid 2n e 2n\neq n. Assim para todo n existe um x maior (no sentido da ordem \mid) que é múltiplo de n. Portanto nenhum n é 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 n há um elemento n\cdot p para algum primo p que é estritamente maior.)

Passo 10

  • Antichain exemplo: o conjunto dos números primos é um antichain (exceto pelo 1 que não é primo): quaisquer dois primos distintos p e q 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 1\mid 2\mid 4\mid 8\mid 16\mid\cdots é 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 ( 1), muitos elementos incomparáveis (então não é total) e não tem elementos máximos.

Resposta

( \mathbb{N},\mid) é ordem parcial: Sim.
Totalmente ordenado?: Não (por exemplo \,2 e \,3 são incomparáveis).
Elementos minimais: \{1\}.
Elementos maximais: não existem.

Exercícios relacionados