7  Relações de ordem

7.1 A definição

Definição 7.1 Seja \(A\) um conjunto e \(R\) uma relação em \(A\). Dizemos que \(R\) é uma relação de ordem (ou ordem parcial) em \(A\) se

  1. \(R\) é reflexiva (\(aRa\) para todo \(a\in A\));
  2. \(R\) é antisimétrica (se \(aRb\) e \(bRa\) então \(a=b\) para todo \(a,b\in A\));
  3. \(R\) é transitiva (se \(aRb\) e \(bRc\) então \(aRc\) para todo \(a,b,c\in A\)).

7.2 Exemplos

Exemplo 7.1  

  1. Se \(A\) é um conjunto de números, então as relações \(\leq\) e \(\geq\) são relações de ordem, mas as relações \(<\) e \(>\) não são relações de ordem pela Definição 7.1 (pois elas não são reflexivas).

  2. Assuma que \(X\) é um conjunto e seja \[ A=\{Y\mid Y\subseteq X\}. \] As relações \(\subseteq\) e \(\supseteq\) são relações de ordem sobre \(A\).

  3. Seja \(A=\N\) e considere a relação \(\mid\) de divisibilidade. Em outras palávras, \(a\mid b\) se e somente se \(b=qa\) com algum \(q\in\N\). Então \(\mid\) é uma relação de ordem sobre \(A\). Note que a mesma relação não é relação de ordem sobre \(\Z\), pois \(2\mid -2\) e \(-2\mid 2\), mas \(-2\neq 2\). Ou seja, \(\mid\) não é antisimétrica em \(\Z\).

7.3 Ordem total ou linear

Definição 7.2 Seja \(R\) uma relação de ordem sobre o conjunto \(A\), Dizemos que \(R\) é uma ordem total ou ordem linear se \[ aRb\quad \mbox{ou}\quad bRa \] vale para todo \(a,b\in R\).

Exercício 7.1 Entre os exemplos no Exemplo 7.1, 1. é ordem total, mas 2. e 3. não são ordens totais.