Ordem lexicográfica

Em matemática, uma ordem lexicográfica, também conhecida como ordem do dicionário ou ordem alfabética, é uma estrutura de ordem natural do produto cartesiano de dois conjuntos ordenados.

Dados dois conjuntos parcialmente ordenados A e B, a ordem lexicográfica sobre o produto cartesiano A x B é definida como

(a,b) ≤ (a′,b′) se e somente se a < a′ (ou a = a) e b ≤ b′.

O resultado é uma ordem parcial. Se A e B são totalmente ordenados, então o resultado é uma ordem total também.

Mais genericamente, pode-se definir a ordem lexicográfica sobre o produto cartesiano de n conjuntos ordenados, no produto cartesiano de uma família infinita enumerável de conjuntos ordenados, e sobre a união de tais conjuntos.

Motivação e usos

O nome da ordem lexicográfica vem de sua generalização da ordem dada às palavras em um dicionário: uma sequência de letras (isto é, uma palavra)

a₁a₂ ... a_k

aparece em um dicionário antes de uma sequência

b₁b₂ ... b_k

se e somente se o primeiro a_i que é diferente de b_i vem antes de b_i no alfabeto. Isso pressupõe que ambos têm o mesmo comprimento; o que geralmente é feito é preencher a palavra mais curta de texto com símbolos para "em branco", e considerar que um branco é um novo elemento mínimo ('inferior').

Para os propósitos de dicionários, pode-se supor que todas as palavras têm o mesmo comprimento, adicionando espaços em branco no final, e considerando o espaço em branco como um caracter especial, que vem antes de qualquer outra letra do alfabeto. Isso também permite a ordenação de frases. Veja ordem alfabética.

Uma propriedade importante da ordem lexicográfica é que ela preserva relações bem-ordenadas, isto é, se A e B são um conjunto bem ordenado, então o conjunto de produtos A × B com a ordem lexicográfica é também bem-ordenado.

Uma exploração importante da ordenação lexicográfica é expressa no esquema de formatação de data da ISO 8601, que expressa uma data no formato YYYY-MM-DD. Este formato de data serve para a ordenação de strings que contenham data sejam ordenadas de forma direta, ficando em ordem cronológica, sem necessidade de um tratamento especial para datas. Note, no entanto, que para que isso funcione, deve haver sempre quatro dígitos para o ano, dois para o mês e dois para o dia, por isso, por exemplo, os dias de um único dígitos devem ser preenchidos com um zero resultando em ' 01 ',' 02 '... , ' 09 '.

Caso de vários produtos

Suponha que

\{A_{1},A_{2},\cdots ,A_{n}\}

é uma n-tupla de conjuntos, com os respectivos ordenamentos totais

\{<_{1},<_{2},\cdots ,<_{n}\}

O ordenamento do dicionário

\ \ <^{d}

de

A_{1}\times A_{2}\times \cdots \times A_{n}

é então

(a_{1},a_{2},\dots ,a_{n})<^{d}(b_{1},b_{2},\dots ,b_{n})\iff (\exists \ m>0)\ (\forall \ i<m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m})

Ou seja, se um dos termos

\ \ a_{m}<_{m}b_{m}

e todos os termos anteriores são iguais.

Informalmente,

\ \ a_{1}

representa a primeira letra,

\ \ a_{2}

a segunda e assim por diante, ao procurar uma palavra num dicionário, daí o nome.

Isto poderia ser declarado de forma mais elegante se definindo recursivamente a ordem de qualquer conjunto

\ \ C=A_{j}\times A_{j+1}\times \cdots \times A_{k}

representada por

\ \ <^{d}(C)

Isto irá satisfazer

a<^{d}(A_{i})a'\iff (a<_{i}a')

(a,b)<^{d}(A_{i}\times B)(a',b')\iff a<^{d}(A_{i})a'\lor (a=a'\ \land \ b<^{d}(B)b')

onde $B=A_{i+1}\times A_{i+2}\times \cdots \times A_{n}.$

Para colocar de forma mais simples, compare os primeiros termos. Se eles são iguais, compare os segundos termos - e assim por diante. A relação entre os primeiros termos correspondentes que não são iguais, determina a relação entre o conjunto inteiro de elementos.

Grupos e espaços vetoriais

Se os conjuntos de componentes são grupos ordenados então o resultado é um grupo não arquimediano, porque por exemplo n(0,1) < (1,0) for all n.

Se os conjuntos de componentes são espaços vetoriais ordenados sobre R (em particular simplesmente R), então o resultado é também um espaço vetorial ordenado.

Ordenamento de sequências de vários comprimentos

Dado um conjunto parcialmente ordenado A, as considerações acima permitem definir naturalmente uma ordem lexicográfica parcial $<^{\mathrm {d} }$ sobre o monoide livre A* formado pelo conjunto de todas as sequências finitas de elementos em A, com a concatenação de sequência como a operação do monoide, como se segue:

u<^{\mathrm {d} }v

se

$u$ é um prefixo de $v$ , ou
$u=wau'$ e $v=wbv'$ , onde $w$ é o maior prefixo comum de $u$ e $v$ , $a$ e $b$ são membros de A tais que $a<b$ , e $u'$ e $v'$ são membros de A*.

Se < é uma ordem total sobre A, então também é a ordem lexicográfica <^d em A*. Se A é um alfabeto finito e totalmente ordenado, A* é o conjunto de todos as palavras sobre A, e nós recuperamos o conceito de ordenação no dicionário usado em lexicografia que deu seu nome as ordenações lexicográficas. No entanto, em geral, isto não é um relação bem-ordenada, mesmo que seja no alfabeto A, por exemplo, se A= {a, b}, a linguagem {aⁿb | n ≥ 0} não tem último elemento: ... <^d aab <^d ab <^d b. Uma relação bem-ordenada para strings, baseada na ordem lexicográfica, é a ordem shortlex.

Da mesma forma, também podemos comparar uma string finita e uma infinita, ou duas strings infinitas.

Comparando-se strings de comprimentos diferentes também pode ser modelado como sendo comparações de strings de comprimento infinito preenchendo-se à direita com espaços em branco, se, como de costume, o espaço em branco é o último elemento do alfabeto (ou, se não é originalmente do alfabeto, acrescentando-o como o último elemento).

Generalização

Considere o conjunto de funções f de um conjunto bem ordenado X a um conjunto totalmente ordenado Y. Por duas funções f e g, a ordem é determinada pelos valores para o menor x tal que f(x) ≠ g(x).

Se Y também é bem-ordenado e X é finito, então a ordem resultante é bem-ordenada. Como já foi mostrado acima, se o X é infinito isso não é em geral o caso.

Se X é infinito e Y tem mais de um elemento, então o conjunto resultante Y^X não é um conjunto contável.

Correspondentemente, podemos também considerar um bem-ordenado X e aplicar a ordem lexicográfica, onde um maior x é uma posição mais significativa. Isso corresponde a exponenciação Y^X. Se o X e o Y são contáveis, então o conjunto resultante também é contável.

Monómios

Em álgebra é tradicional se ordenar termos em um polinômio, ordenando os monómios nos indeterminados. Isso é fundamental, para se ter um forma normal. Tais questões são tipicamente deixadas implícitas na discussão entre os seres humanos, mas tem naturalmente de ser tratadas com exatidão na álgebra computacional. Na prática, tem-se um alfabeto de indeterminantes X, Y, ... e as ordens de todos os monómios formados a partir deles, uma variante da ordem lexicográfica. Por exemplo, se se decidir ordenar o alfabeto por

X < Y < ...

e também olhar para os termos mais altos em primeiro lugar, o que significa ordenar

... < X³ < X² < X

e também

X < Y^k for all k.

Há uma certa flexibilidade na ordenação de monómios, e isso pode ser explorado na teoria das bases de Gröbner.

Frações decimais

As frações decimais do ponto decimal, a < b se aplica de forma equivalente para a ordem numérica e a ordem lexicográfica, desde que os números com decimais 9 recorrentes como 0,399999... não estejam incluídos no conjunto de strings que representam os números. Com essa restrição existe uma bijeção de preservação de ordem entre as strings e os números.

Ordem lexicográfica inversa

Em uma variação comum da ordem lexicográfica, se compara elementos através da leitura a partir da direita em vez da esquerda, ou seja, o componente mais à direita é o mais significativo, por exemplo, aplicados em um dicionário de rimas.

No caso de monómios, pode-se classificar os expoentes em ordem decrescente, com o expoente da primeira base variável como a chave principal de classificação, por exemplo:

x^{2}yz^{2}<xy^{3}z^{2}

.

Alternativamente, a ordenação pode ser feita pela soma dos expoentes, em ordem decrescente.

Ver também