Pré-ordem

Em matemática, mais especificamente em teoria da ordem, uma pré-ordem é uma relação binária reflexiva e transitiva. Toda ordem parcial ou relação de equivalência é também uma pré-ordem.

Definição formal

Seja A um conjunto e R uma relação binária sobre A (ou seja, R subconjunto de AxA). Então, R é uma pré-ordem sobre A se, e somente se, R é reflexiva e transitiva. Isto é:

$\forall a\in A\ (aRa)$ (propriedade reflexiva)

$\forall (a,b)\in A\times A(aRb\ \land bRc\ \ \Rightarrow aRc)$ (propriedade transitiva)

Muitas vezes é usada a notação de par-ordenado. Neste caso, escreveríamos: $(A,R)$ é uma pré-ordem.

Exemplos

• Todo espaço topológico finito gera uma pré-ordem nos seus pontos, na qual x ≤ y se, e somente se, x pertence a toda vizinhança de y.
• Sobre os arcos de um grafo orientado, a relação ser acessível por é uma pré-ordem. Se o digrafo é acíclico, essa relação vira uma ordem.
• Em um anel comutativo, a relação divide é uma pré-ordem.
• Seja $M$ um monóide. Definimos a relação $\leq$ em $M$ como

$x\leq y\iff {\big (}\exists z\in M{\big )}{\big (}xz=y{\big )}$.

Assim, $(M,\leq )$ é uma pré-ordem.

• A relação definida por $x\leq y\iff \exists f:x\rightarrow y$, injetora.
• Dada uma relação de pré-ordem $(X,\lesssim )$, então, $\forall \ Y\subset X\ (Y,\lesssim )$ também é uma pré-ordem.
• Uma categoria com no máximo um morfismo de algum objeto $x$ para algum outro onjeto $y$ é uma pré-ordem. Neste sentido, categorias "generalizam" pré-ordens aceitando mais do que uma relação entre objetos: cada morfismo é uma relação de pré-ordem diferente.
• Considere o conjunto ${}^{\mathbb {N} }{\mathbb {N} }$ de todas as funções do conjunto dos números naturais ${\mathbb {N} }$ em ${\mathbb {N} }$. Definimos a relação $\leqslant ^{*}$ para ${}^{\mathbb {N} }{\mathbb {N} }$ como

$f\leqslant ^{*}g\iff {\big (}\exists N\in {\mathbb {N} }{\big )}{\big (}\forall n\geqslant N{\big )}(f(n)\leqslant g(n){\big )}$

(considerando $\leqslant$ como a ordem natual de ${\mathbb {N} }$).

Então $({}^{\mathbb {N} }{\mathbb {N} },\leqslant ^{*})$ é uma pré-ordem.

Usos

• Toda pré-ordem pode gerar uma topologia, Topologia de Alexandrov e, de fato, toda pré-ordem admite uma bijeção com uma topologia de Alexandrov neste conjunto.
• Pré-ordens podem ser usadas para definir álgebras interiores.
• Pré-ordens induzem a semântica de Kripke para certos tipos de lógicas modais.

Esquema de temas relacionados

Teoria da ordem Bem ordenado Ordem total Parcialmente ordenado Pré-ordenado Relação reflexiva Relação transitiva Relação anti-simétrica Relação total Relação bem-fundada

Ver também

• Relação de ordem - pré-ordem que é também anti-simétrica.
• Relação de equivalência - pré-ordem que é também uma relação simétrica.
• Ordem total - pré-ordem que é também total e anti-simétrica.
• Lema de Newman