Relação de pedido

Uma relação de ordem em um conjunto é uma relação binária nesse conjunto que permite que seus elementos sejam comparados entre si de maneira consistente. Um conjunto dotado de uma relação de ordem é um conjunto ordenado . Dizemos também que a relação define neste conjunto uma estrutura de ordem ou simplesmente uma ordem .

Definições e exemplos

Relação de pedido

Uma relação de ordem é uma relação binária reflexiva , antissimétrica e transitiva : seja E um conjunto; uma relação interna ≤ em E é uma relação de ordem se para todos os elementos x , y e z de E :

x ≤ x (reflexividade)
( x ≤ y e y ≤ x ) ⇒ x = y (antissimetria)
( x ≤ y e y ≤ z ) ⇒ x ≤ z (transitividade)

A própria forma desses axiomas permite afirmar que também são verificados pela relação binária recíproca ≥, definida por

y ≥ x se e somente se x ≤ y .

A qualquer relação de ordem está, portanto, associada uma relação de ordem oposta no mesmo conjunto; as fórmulas x ≤ y e y ≥ x podem ser lidas indiferentemente: " x é menor que y ", ou " x é menor que y ", ou " y é maior que x ", ou " y é maior que x " (ou às vezes, " x é no máximo igual ay " ou " y é pelo menos igual a x ").

Também associamos com qualquer relação de ordem ≤, uma relação conhecida como de ordem estrita notada então <(que não é uma relação de ordem no sentido definido anteriormente visto que a reflexividade não é satisfeita), que é a restrição da relação de ordem para os pares de elementos distintos:

x < y se e somente se x ≤ y e x ≠ y .

A fórmula x < y também é escrita y > x e diz: " x é estritamente menor que y ", ou " x é estritamente menor que y ", " y é estritamente maior que x " ou " y é estritamente maior que x ”.

Uma relação de ordem dentro do significado da definição acima é às vezes chamada de ordem ampla .

Algumas relações de ordem são relações totais , ou seja, dois elementos de E são sempre comparáveis : para todos os x , y de E :

x ≤ y ou y ≤ x .

Dizemos então que ≤ é uma relação de ordem total , e que o conjunto E é totalmente ordenado por essa relação. Uma relação de ordem em E é considerada parcial se não for total, e E é então parcialmente ordenada . Deve-se notar que, em inglês, ordem parcial denota qualquer ordem, que pode, portanto, ser total. Essa terminologia às vezes também é usada em francês.

Conjunto ordenado

Um conjunto ordenado é um conjunto fornecido com uma relação de pedido. Se um conjunto ordenado for finito, ele pode ser representado graficamente na forma de um diagrama de Hasse , semelhante à representação usual de um gráfico no papel, o que pode facilitar o seu trabalho. Se for infinito, podemos desenhar parte de seu diagrama de Hasse.

Exemplos e contra-exemplos

A relação "é menor (ou igual) a" é uma relação de ordem total no conjunto dos inteiros ( naturais ou relativos ), no conjunto dos racionais ou no conjunto dos reais .
Dado um conjunto ordenado ( E , ≤), a ordem lexicográfica no conjunto de n -uplos de elementos de E é a "ordem de dicionário", mais simples de definir por sua ordem estrita associada : ( x 1 , ..., X n ) < ( y 1 ,…, y n ) se x i = y i para todos os índices i até um certo k < n e x k +1 < y k +1 .
A relação de inclusão "é um subconjunto de" ou "está contido no" é uma relação de ordem sobre o conjunto E das partes de um conjunto X . Se X é finito, E é finito (mais precisamente se X contém n elementos, E contém 2 n ). A Figura 1 representa o diagrama de Hasse de ( E , ⊂) para n = 3.
Qualquer restrição sobre uma parte F de E de pedido no E é uma ordem de F . Em particular (de acordo com o ponto anterior): em qualquer conjunto F de partes de um conjunto X , a inclusão é uma relação de ordem - este "exemplo" é de fato genérico: toda ordem é isomórfica a uma ordem desta forma;
A relação de divisibilidade é uma relação de ordem parcial nos números naturais . A Figura 2 representa o diagrama de Hasse de sua restrição a inteiros de 0 a 9.
A ordem de inclusão (veja-se acima), em todas as partes de um produto cartesiano L × V é a finura relativa de relações binárias de U em V . Para V = U , esta relação torna possível, por exemplo (por restrição, ver acima) comparar entre eles:
- as relações de equivalência em U (ou, o que dá no mesmo: as partições de U );
- as relações de ordem de U .
Dada uma família ( E i ) i ∈ I de conjuntos ordenados, a ordem natural no conjunto de produtos ∏ i ∈ I E i é a ordem do produto , definida por:( x i ) i ∈ I ≤ ( y i ) i ∈ I se e somente se para qualquer índice i , x i ≤ y i .Por exemplo, no conjunto E I de funções de I em um conjunto ordenado E , a ordem produzida é dada por: f ≤ g se para todo i ∈ I , f ( i ) ≤ g ( i ). Para a ordem produzida em ℝ ℝ , uma função é menor do que outra se sua curva estiver sempre abaixo da outra.
Podemos generalizar a ordem lexicográfica (mencionada no início da lista) da seguinte forma: se I estiver bem ordenado , definimos uma ordem em ∏ i ∈ I E i por:( x i ) i ∈ I <( y i ) i ∈ I se e somente se houver índices i para os quais x i ≠ y i e se, para o menor deles, tivermos x i < y i .Se os pedidos em E i são totais, a ordem lexicográfica em ∏ i ∈ I E i também é total (mas não em geral a ordem do produto).
Uma relação de pré-ordem não é uma relação de ordem em geral porque carece da propriedade de antissimetria. Mas qualquer quociente de uma pré-ordem pela relação de equivalência associada é uma ordem.
Uma relação de ordem estrita em um conjunto não vazio não é uma relação de ordem porque não é reflexiva. Se <é uma ordem estrita em E , A "relação x < y ou x = y " é uma ordem de E .
Uma relação cíclica não é uma relação de ordem porque é uma relação ternária . Mas as relações binárias obtidas pela fixação de um de seus três argumentos são relações de ordem estrita.
Uma árvore enraizada é um grafo acíclico direcionado associado a uma relação de ordem parcial particular, importante na ciência da computação.

Conceitos relacionados

Aplicações monótonas

Se $( E , \leq)$ e $( F , ≼)$ são dois conjuntos ordenados, diz-se que um mapa $f$ de $E$ para $F$ está aumentando (ou às vezes aumentando no sentido amplo, ou isotônico) quando preserva a ordem, diminuindo (em sentido amplo), ou antítono quando inverte este, isto é:

f

está a aumentar, quando para todos os

x

y

E

x \leq y \Rightarrow f ( x ) ≼ f ( y )

;

f

está a diminuir quando para todos os

x

y

E

x \leq y \Rightarrow f ( x ) ≽ f ( y )

Diz-se de ser estritamente crescente quando se mantém a ordem estrita: para todos $x$ e $y$ de $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

e estritamente decrescente quando se inverte: para todos $x$ e $y$ de $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Observe que se um mapa crescente de $( E , \leq)$ em $( F , ≼)$ é injetivo, então ele é estritamente crescente, mas o inverso é falso em geral (no entanto, é verdadeiro se a ordem em $E$ for total).

Um monótona ou monótona aplicação no sentido lato (resp. Estritamente monótona) é um aumento ou diminuição aplicação (resp. Estritamente crescente ou decrescente estritamente).

A bijeção recíproca de uma bijeção crescente $f : ( E , \leq) \to ( F , ≼)$ não é necessariamente crescente (tome por exemplo a identidade de mapeamento , de $E$ = ℝ dotada da ordem de igualdade em $F$ = ℝ fornecida com o usual pedido). É, no entanto, se ≤ for total (se $f -1 ( y 1 ) \geq f -1 ( y 2 )$ então, pelo crescimento de $f$ , $y 1 ≽ y 2.$ Portanto, por contraposição : se $y 1 ≺ y 2$ e se ≤ for total, então $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

Um isomorfismo entre dois conjuntos ordenados $( E , \leq)$ e $( F , ≼)$ é uma bijeção $f$ de $E$ em $F$ que está aumentando e cujo inverso está aumentando, o que equivale a dizer que $f$ é bijetivo e satisfaz para todos os $x$ e $y$ de $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

Uma incorporação de conjuntos ordenados de $( E , \leq)$ em $( F , ≼)$ é um mapa $f$ a partir de $E$ a $F$ satisfatório para todos os $x$ e $y$ de $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

(tal aplicação é necessariamente injetiva ). Isomorfismos de ordem são, portanto, embeddings sobrejetivos .

Na categoria de conjuntos ordenados, os morfismos são por definição os mapas crescentes, e os isomorfismos são, portanto, aqueles introduzidos acima.

Maior elemento e elemento máximo

Em um conjunto ordenado E , não existe necessariamente um elemento maior . Se E for finito, conterá (pelo menos) um elemento máximo . Se E é um conjunto indutivo infinito, o lema de Zorn ainda garante a existência de um elemento máximo.

Relação de ordem estrita

Vimos que para uma relação de ordem ≤ em um conjunto E , naturalmente associamos uma relação <em E , que é então uma relação de ordem estrita , ou seja, anti-reflexiva ( x < x n 'é verdadeiro para qualquer elemento x de E ) e transitivo.

No entanto, qualquer relação de ordem estrita é antissimétrica e mesmo assimétrica (o que equivale a: antissimétrica e antirrefletiva), ou seja, para todo x e y :

x < y ⇒ não ( y < x) .

Consequentemente, reciprocamente, com qualquer relação de ordem estrita <em E , pode-se associar uma relação de ordem ≤ em E colocando:

x ≤ y se e somente se x < y ou x = y .

É fácil verificar que, colocando essas duas construções ponta a ponta, de uma ordem ou de uma ordem estrita, encontramos a relação inicial. A escolha de uma ou outra das axiomatizações, portanto, não é importante em si mesma.

Para uma ordem estrita, a totalidade é expressa da seguinte forma:

∀ x , y ∈ E ( x < y ou x = y ou y < x ).

e dizemos então que é uma relação de ordem estrita total . Não há confusão possível com a noção de relação total , porque as relações de ordem estrita são anti-reflexivas, enquanto as relações totais são reflexivas.

Para uma ordem total estrita, as três possibilidades - x < y , x = y e y < x - são exclusivas, e às vezes falamos, seguindo Cantor , da propriedade da tricotomia .

Relação acíclica

O fechamento reflexivo transitivo de uma relação R é uma relação de ordem - ou ainda: o fechamento transitivo de R é antissimétrico - se e somente se R for acíclico .

O fechamento transitivo de R é uma ordem estrita se e somente se R for estritamente acíclico, ou seja, se seu gráfico for acíclico .

Negação (ou complemento) de uma relação de pedido

A negação de uma relação binária definida em um conjunto é a relação do gráfico complementar daquela de in . Nós notamos isso . Em outras palavras, dois elementos estão relacionados por se e somente se não estiverem . $R$ $NO$ $R$ $A \ vezes A$ $\ não \! R$ $\ não \! R$ $R$

Dizer que uma ordem é total é dizer que sua negação está estritamente na ordem inversa. Isso quer dizer que existe uma equivalência para uma ordem entre: $\ leqslant$

$\ leqslant$ é total;
$x \ não \ leqslant y \ iff y <x$ .

Por outro lado, desde que haja dois elementos distintos não comparáveis por uma ordem, sua negação não pode ser uma ordem (estrita ou ampla), porque não é antissimétrica. A negação de uma ordem não total, portanto, nunca é uma ordem.

Por exemplo, a negação da inclusão ⊄ no conjunto das partes de um conjunto de pelo menos dois elementos não é uma ordem, porque, se a ≠ b , sempre temos { a } ≠ { b } com porém { a } ⊄ { b } e { b } ⊄ { a }.

Pedido duplo

A ordem dual (ou ordem oposta ) de um conjunto ordenado P = ( E , ≤) é o conjunto ordenado P op = ( E , ≤ op ), onde ≤ op é a relação de ordem oposta de ≤, c ', ou seja, a relação ≥ (às vezes usamos * em vez de op ).

O bidual ( P op ) op de P for igual a P .

Pedido antecipado

Uma pré - encomenda é uma relação binária reflexiva e transitiva .

Qualquer pré-ordem ℛ em um conjunto $E$ induz uma relação de ordem no conjunto $E$ quocientada pela relação de equivalência ~ definida por “ $x ~ y se e somente se ( x ℛ y e y ℛ x )$ ”.

Para obter mais detalhes e exemplos, consulte o artigo detalhado.

Propriedades complementares

Compatibilidade

A compatibilidade de uma relação de ordem com uma estrutura algébrica só pode ser definida caso a caso.

Uma ordem ≤ em um meio-grupo ( G , +) é considerada compatível se, para todos os x , y e z em G tais que x ≤ y , temos x + z ≤ y + z e z + x ≤ z + y .
Quando ( G , +) é um grupo , dizemos que ( G , +, ≤) é um grupo ordenado e que um elemento é positivo se for maior que o elemento neutro .
Qualquer grupo arquimediano totalmente ordenado é abeliano e está imerso em ( ℝ , +, ≤).
Um anel ou um campo ( A , +, ×) é dito ordenado se ele tem uma ordem ≤ tal que ( A , +, ≤) é um grupo ordenado e o produto de dois elementos positivos é positivo.
Qualquer corpo arquimediano totalmente ordenado é imerso em (ℝ, +, ×, ≤).
Em um campo totalmente ordenado, –1 nunca é um quadrado ou mesmo uma soma de quadrados.
Um espaço vetorial ordenado (de) é um espaço vetorial real ( E , +, ∙) dotado de uma ordem ≤ tal que ( E , +, ≤) é um grupo ordenado e que qualquer produto vetorial de um real positivo por um vetor positivo é positivo.

Conjunto bem ordenado

Um conjunto ordenado é considerado bem ordenado se cada subconjunto não vazio este conjunto tiver um elemento menor .

Treliça

Um conjunto é chamado de rede se for ordenado e se qualquer par de elementos tiver um limite superior e um limite inferior .

Formulários

Topologia do pedido

Um conjunto ordenado pode ser fornecido com várias topologias resultantes do pedido : a topologia do pedido, a topologia do pedido à direita e a topologia do pedido à esquerda.

Links com complexos simpliciais

Uma classe importante de complexos simpliciais vem de conjuntos ordenados finitos. Definimos o complexo de ordem D (P) de um conjunto ordenado finito P como sendo o conjunto de cadeias de P. O complexo de ordem é trivialmente um complexo simplicial.

O estudo do conjunto ordenado em si fornece informações sobre seu complexo de ordem e, portanto, é interessante estudar um complexo simplicial como o complexo de ordem de um conjunto ordenado.

Notas e referências

N. Bourbaki , Elementos da matemática : teoria dos conjuntos [ detalhe das edições ], p. III.4 .
Bourbaki , p. III.5.
(in) AG Kurosh , Lectures in General Algebra , Pergamon Press ,1965( leia online ) , p. 11.
Bourbaki , p. III.22-23.
Nathalie Caspard, Bruno Leclerc e Bernard Monjardet, Finite conjuntos ordenados: conceitos, resultados e usos , Springer,2007( leia online ) , p. 73.
Bourbaki , p. III.7 e III.14.
Gustave Choquet , Course of Analysis , 1966, p. 23 .
(em) Steven Roman, Lattices and Ordered Sets , Springer ,2008, 305 p. ( ISBN 978-0-387-78900-2 , leitura online ) , p. 13.
Roman , 2008 , p. 284.
Por exemplo J. Riguet , “ Relações binárias, fechamentos, correspondências de Galois ”, Bull. Soc. Matemática. Fr. , vol. 76,1948, p. 114-155 ( ler online ).
(en) George Bergman (en) , Um convite para álgebra geral e construções universais , Cham, Springer ,2015, 2 nd ed. ( 1 st ed. 1988), 572 p. ( ISBN 978-3-319-11478-1 , leitura online ) , p. 113.
Bourbaki , p. III.4 e III.77.
Jean-Pierre Ramis , André Warusfel et al. , Matemática Tudo-em-Um para a Licença: Nível L1 , Dunod ,2013, 2 nd ed. ( leia online ) , p. 37.

Veja também

Bibliografia

(pt) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ detalhe das edições ] ( apresentação online )
(pt) Efe A. Ok, Teoria da Ordem e suas Aplicações ( leia online )

Relação de pedido

Definições e exemplos