Ordem total
Em matemática , chamamos de relação de ordem total em um conjunto E qualquer relação de ordem ≤ para a qual dois elementos de E são sempre comparáveis, ou seja,
.
Dizemos então que E é totalmente ordenado por ≤.
Definição
Uma relação binária ≤ em um conjunto E é uma ordem total se (para todos os elementos x , y e z de E ):
- se x ≤ y e y ≤ z , então x ≤ z ( transitividade );
- se x ≤ y e y ≤ x , então x = y ( antissimetria );
- x ≤ x ( reflexividade );
- x ≤ y ou y ≤ x ( totalidade ).
As três primeiras propriedades são aquelas que fazem ≤ uma relação de ordem. O quarto torna esse pedido um pedido total.
Exemplos
- O conjunto de letras de um alfabeto é completamente ordenado por ordem alfabética .
- Qualquer campo euclidiano , como o campo ℝ de números reais , é dotado de uma ordem total natural: x ≤ y se e somente se y - x for um quadrado .
- Seja f : X → Y uma injeção , ≤ uma ordem em Y e ≼ a ordem induzida em X definindo: x 1 ≼ x 2 se e somente se f ( x 1 ) ≤ f ( x 2 ). Se ≤ for total, então ≼ também. Em particular: restringir uma porção X de Y de uma ordem total em Y é uma ordem total em X . Por exemplo, qualquer parte de ℝ é totalmente ordenada pela relação de ordem usual.
- Se uma ordem ≤ em E é total, então a ordem oposta ≥ em E é total (o inverso resulta).
- A ordem lexicográfica no produto cartesiano de um conjunto bem ordenado de conjuntos totalmente ordenados é ela própria uma ordem total; por exemplo, qualquer conjunto de palavras é completamente ordenado alfabeticamente e qualquer boa ordem é a ordem total.
- Uma cadeia de um conjunto parcialmente ordenado ( E , ≤) é uma parte de E sobre a qual a ordem ≤ é total. Essa noção desempenha um papel importante na teoria dos conjuntos , pelo lema de Zorn .
- Podemos definir um conjunto totalmente ordenado como uma rede em que { a ∨ b , a ∧ b } = { a, b } para todo a , b ; podemos então definir a ≤ b se e somente se a = a ∧ b ; provamos que uma ordem total também é uma rede distributiva.
- De acordo com o teorema da extensão de Szpilrajn , qualquer ordem parcial ≤ em um conjunto E é extensível em uma ordem total em E , chamada de extensão linear de ≤.
Contra-exemplos
- No conjunto dos inteiros naturais, a relação de ordem “é um divisor de” não é uma ordem total, pois podemos encontrar pares de inteiros positivos, nenhum dos quais é um divisor do outro.
- Do mesmo modo, no conjunto de peças de um conjunto que contém pelo menos dois elementos de um e b (distinta), a inclusão é apenas uma ordem parcial: não temos nem { um } ⊂ { b }, nem { b } ⊂ { um } .
O caso acabado
- Em um conjunto finito completamente ordenado, qualquer parte não vazia possui um elemento menor . Em outras palavras: em um conjunto finito, qualquer ordem total é uma boa ordem .
- Qualquer conjunto finito totalmente ordenado é isomorfa a ordem para um segmento inicial de N .
Na teoria da categoria
Conjuntos totalmente ordenados formam uma subcategoria da categoria de ordens , cujos morfismos são aplicações crescentes .
Qualquer bijeção crescente de uma ordem total para qualquer ordem é um isomorfismo de ordem .
Pedido estrito total
A bijeção canônica entre as ordens estritas e as ordens no mesmo conjunto E associa uma relação de ordem estrita <(anti-reflexiva e transitiva, portanto anti-simétrica) a uma relação de ordem ≤ (reflexiva, transitiva e anti-simétrica), por:
x < y ⇔ ( x ≤ y e x ≠ y )ou :
x ≤ y ⇔ ( x < y ou x = y ).Um pedido ≤ é total se e somente se o pedido estrito associado <satisfaz:
∀ x , y ∈ E ( x < y ou x = y ou y < x ).Chamamos de ordem estrita total qualquer ordem estrita de verificação dessa propriedade, chamada de “tricotomia”.