Ordem total - Total order

Em matemática , uma ordem total ou linear é uma ordem parcial em que quaisquer dois elementos são comparáveis. Ou seja, uma ordem total é uma relação binária em algum conjunto , que satisfaz o seguinte para todos e em :

  1. ( reflexivo ).
  2. Se e então ( transitivo )
  3. Se e então ( anti-simétrico )
  4. ou ( fortemente conectado , anteriormente denominado total).

Os pedidos totais às vezes também são chamados de pedidos simples , connex ou completos .

Um conjunto equipado com um pedido total é um conjunto totalmente ordenado ; os termos conjunto ordenado simplesmente , conjunto ordenado linearmente e loset também são usados. O termo cadeia é algumas vezes definido como sinônimo de conjunto totalmente ordenado , mas geralmente se refere a algum tipo de subconjuntos totalmente ordenados de um determinado conjunto parcialmente ordenado.

Uma extensão de um determinado pedido parcial a um pedido total é chamada de extensão linear desse pedido parcial.

Pedidos totais estritos e não estritos

A ordem total rigoroso sobre um conjunto é uma ordem estrita parcial em em que quaisquer dois elementos são comparáveis. Ou seja, uma ordem total é uma relação binária em algum conjunto , que satisfaz o seguinte para todos e em :

  1. Não ( irreflexivo ).
  2. Se e então ( transitivo ).
  3. Se , então ou ( conectado ).

Para cada pedido total (não estrito), há uma relação associada , chamada de pedido total estrito associado, que pode ser definida de duas maneiras equivalentes:

  • se e ( redução reflexiva ).
  • se não (isto é , é o complemento do inverso de ).

Por outro lado, o fechamento reflexivo de um pedido total estrito é um pedido total (não estrito).

Exemplos

  • Qualquer subconjunto de um conjunto totalmente ordenado X é totalmente ordenado para a restrição da ordem em X .
  • O pedido exclusivo no conjunto vazio, , é um pedido total.
  • Qualquer conjunto de números cardinais ou números ordinais (mais fortemente, são boas ordens ).
  • Se X for qualquer conjunto e fuma função injetiva de X para um conjunto totalmente ordenado então f induz uma ordenação total em X definindo x 1x 2 se e somente se f ( x 1 ) ≤ f ( x 2 ) .
  • A ordem lexicográfica no produto cartesiano de uma família de conjuntos totalmente ordenados, indexados por um conjunto bem ordenado , é ela própria uma ordem total.
  • O conjunto de números reais ordenados pelas relações usuais "menor ou igual a" (≤) ou "maior ou igual a" (≥) é totalmente ordenado e, portanto, os subconjuntos de números naturais , inteiros e racionais . Cada um deles pode ser mostrado como o único (até um isomorfismo de ordem ) "exemplo inicial" de um conjunto totalmente ordenado com uma certa propriedade, (aqui, uma ordem total A é inicial para uma propriedade, se, sempre que B tiver o propriedade, há um isomorfismo de ordem de A para um subconjunto de B ):
    • Os números naturais formam um conjunto inicial não vazio totalmente ordenado sem limite superior .
    • Os inteiros formam um conjunto inicial não vazio totalmente ordenado, sem um limite superior nem inferior .
    • Os números racionais formam um conjunto inicial totalmente ordenado que é denso em números reais. Além disso, a redução reflexiva <é uma ordem densa nos números racionais.
    • Os números reais formam um conjunto inicial totalmente ordenado ilimitado que é conectado na topologia de ordem (definida abaixo).
  • Os campos ordenados são totalmente ordenados por definição. Eles incluem os números racionais e os números reais. Cada campo ordenado contém um subcampo ordenado que é isomórfico aos números racionais. Qualquer campo ordenado completo de Dedekind é isomórfico aos números reais.
  • As letras do alfabeto ordenadas pela ordem padrão do dicionário , por exemplo, A < B < C etc., é uma ordem total estrita.

Correntes

O termo cadeia é algumas vezes definido como sinônimo de um conjunto totalmente ordenado, mas geralmente é usado para se referir a um subconjunto de um conjunto parcialmente ordenado que é totalmente ordenado para a ordem induzida. Normalmente, o conjunto parcialmente ordenado é um conjunto de subconjuntos de um determinado conjunto que é ordenado por inclusão, e o termo é usado para declarar as propriedades do conjunto das cadeias. Este alto número de níveis aninhados de conjuntos explica a utilidade do termo.

Um exemplo comum do uso de cadeia para se referir a subconjuntos totalmente ordenados é o lema de Zorn que afirma que, se cada cadeia em um conjunto parcialmente ordenado X tem um limite superior em X , então X contém pelo menos um elemento máximo. O lema de Zorn é comumente usado com X sendo um conjunto de subconjuntos; neste caso, o limite superior é obtido por provar que a união dos elementos de uma cadeia em X é em X . Essa é a maneira geralmente usada para provar que um espaço vetorial tem bases de Hamel e que um anel tem ideais máximos .

Em alguns contextos, as cadeias consideradas são de ordem isomórfica aos números naturais com sua ordem usual ou sua ordem oposta . Nesse caso, uma cadeia pode ser identificada com uma sequência monótona e é chamada de cadeia ascendente ou descendente , dependendo se a sequência é crescente ou decrescente.

Um conjunto parcialmente ordenado tem a condição de cadeia descendente se todas as cadeias descendentes eventualmente se estabilizarem. Por exemplo, um pedido é bem fundamentado se tiver a condição de cadeia descendente. Da mesma forma, a condição da cadeia ascendente significa que cada cadeia ascendente eventualmente se estabiliza. Por exemplo, um anel noetheriano é um anel cujos ideais satisfazem a condição da cadeia ascendente.

Em outros contextos, apenas cadeias que são conjuntos finitos são consideradas. Nesse caso, fala-se de cadeias finitas , muitas vezes encurtadas como cadeia . Nesse caso, o comprimento de uma cadeia é o número de desigualdades (ou inclusões de conjuntos) entre os elementos consecutivos da cadeia; ou seja, o número menos um dos elementos da cadeia. Assim, um conjunto de singleton é uma cadeia de comprimento zero e um par ordenado é uma cadeia de comprimento um. A dimensão de um espaço é freqüentemente definida ou caracterizada como o comprimento máximo de cadeias de subespaços. Por exemplo, a dimensão de um espaço vetorial é o comprimento máximo de cadeias de subespaços lineares , e a dimensão de Krull de um anel comutativo é o comprimento máximo de cadeias de ideais primos .

"Cadeia" também pode ser usada para alguns subconjuntos totalmente ordenados de estruturas que não são conjuntos parcialmente ordenados. Um exemplo é dado por cadeias regulares de polinômios. Outro exemplo é o uso de "corrente" como sinônimo de caminhada em um gráfico .

Outros conceitos

Teoria da Malha

Pode-se definir um conjunto totalmente ordenado como um tipo particular de rede , ou seja, aquele em que temos

para todos os a , b .

Em seguida, escrevemos ab se e somente se . Portanto, um conjunto totalmente ordenado é uma rede distributiva .

Pedidos totais finitos

Um argumento de contagem simples verificará se qualquer conjunto finito totalmente ordenado não vazio (e, portanto, qualquer subconjunto não vazio dele) tem um elemento mínimo. Assim, toda ordem total finita é de fato uma ordem boa . Tanto pela prova direta quanto pela observação de que toda ordem de poço é isomórfica de ordem a um ordinal pode mostrar que toda ordem total finita é isomórfica de ordem a um segmento inicial dos números naturais ordenados por <. Em outras palavras, uma ordem total em um conjunto com k elementos induz uma bijeção com os primeiros k números naturais. Portanto, é comum indexar ordens totais finitas ou ordens de poço com tipo de ordem ω por números naturais de uma maneira que respeite a ordem (começando com zero ou com um).

Teoria da categoria

Conjuntos totalmente ordenados formam uma subcategoria completa da categoria de conjuntos parcialmente ordenados , com os morfismos sendo mapas que respeitam as ordens, ou seja, mapas f tais que se ab então f ( a ) ≤ f ( b ).

Um mapa bijetivo entre dois conjuntos totalmente ordenados que respeite as duas ordens é um isomorfismo nesta categoria.

Topologia do pedido

Para qualquer conjunto totalmente ordenado X , podemos definir os intervalos abertos ( a , b ) = { x  : a < x e x < b }, (−∞, b ) = { x  : x < b }, ( a , ∞) = { x  : um < x } e (-∞, ∞) = X . Podemos usar esses intervalos abertos para definir uma topologia em qualquer conjunto ordenado, a topologia de ordem .

Quando mais de um pedido está sendo usado em um conjunto, fala-se sobre a topologia de pedido induzida por um pedido particular. Por exemplo, se N são os números naturais, <é menor que e> maior do que poderíamos nos referir à topologia de ordem em N induzida por <e a topologia de ordem em N induzida por> (neste caso, eles são idênticos, mas não em geral).

A topologia de ordem induzida por uma ordem total pode ser mostrada como hereditariamente normal .

Integridade

Um conjunto totalmente ordenado é considerado completo se todo subconjunto não vazio que possui um limite superior tiver um limite superior mínimo . Por exemplo, o conjunto de números reais R está completo, mas o conjunto de números racionais Q não. Em outras palavras, os vários conceitos de completude (não confundir com "total") não são transportados para restrições . Por exemplo, ao longo dos números reais uma propriedade da relação ≤ é que todos os não-vazia subconjunto S de R com um limite superior de R tem um extremo superior (também chamado supremum) em R . No entanto, para os números racionais, esse supremo não é necessariamente racional, de modo que a mesma propriedade não se aplica à restrição da relação ≤ aos números racionais.

Há uma série de resultados relacionando propriedades da topologia do pedido à integridade de X:

  • Se a topologia de pedido em X estiver conectada, X está completo.
  • X está conectado sob a topologia de ordem se e somente se estiver completo e não houver lacuna em X (uma lacuna é dois pontos a e b em X com a < b tal que nenhum c satisfaz a < c < b .)
  • X estará completo se e somente se cada conjunto limitado fechado na topologia do pedido for compacto.

Um conjunto totalmente ordenado (com sua topologia de ordem) que é uma rede completa é compacto . Os exemplos são os intervalos fechados de números reais, por exemplo, o intervalo de unidades [0,1] e o sistema de números reais estendido afinamente (linha de número real estendida). Existem homeomorfismos que preservam a ordem entre esses exemplos.

Somas de pedidos

Para quaisquer duas ordens totais disjuntas e , há uma ordem natural no conjunto , que é chamada de soma das duas ordens ou às vezes apenas :

Para , é válido se e somente se um dos seguintes for válido:
  1. e
  2. e
  3. e

Intuitivamente, isso significa que os elementos do segundo conjunto são adicionados em cima dos elementos do primeiro conjunto.

De forma mais geral, se for um conjunto de índices totalmente ordenado, e para cada um a estrutura é uma ordem linear, onde os conjuntos são disjuntos aos pares, então a ordem total natural em é definida por

Para , é válido se:
  1. Ou há algum com
  2. ou há alguns em com ,

Pedidos no produto cartesiano de conjuntos totalmente pedidos

Em ordem de força crescente, ou seja, conjuntos decrescentes de pares, três das ordens possíveis no produto cartesiano de dois conjuntos totalmente ordenados são:

  • Ordem lexicográfica : ( a , b ) ≤ ( c , d ) se e somente se a < c ou ( a = c e bd ). Este é um pedido total.
  • ( a , b ) ≤ ( c , d ) se e somente se ac e bd (a ordem do produto ). Este é um pedido parcial.
  • ( a , b ) ≤ ( c , d ) se e somente se ( a < c e b < d ) ou ( a = c e b = d ) (o fechamento reflexo do produto direto das ordens totais estritas correspondentes). Este também é um pedido parcial.

Todos os três podem ser definidos de forma semelhante para o produto cartesiano de mais de dois conjuntos.

Aplicado ao espaço vetorial R n , cada um deles o torna um espaço vetorial ordenado .

Veja também exemplos de conjuntos parcialmente ordenados .

Uma função real de n variáveis ​​reais definidas em um subconjunto de R n define uma ordem fraca estrita e uma pré - ordem total correspondente nesse subconjunto.

Estruturas relacionadas

Uma relação binária que é antissimétrica, transitiva e reflexiva (mas não necessariamente total) é uma ordem parcial .

Um grupo com um pedido total compatível é um grupo totalmente ordenado .

Existem apenas algumas estruturas não triviais que são (indefiníveis como) reduções de uma ordem total. Esquecer a orientação resulta em uma relação de intermediação . Esquecer a localização das extremidades resulta em uma ordem cíclica . O esquecimento de ambos os dados resulta em uma relação de separação .

Veja também

Notas

Referências

links externos