Pedido fraco - Weak ordering

Relações binárias transitivas

	Simétrico	Anti-simétrico	Conectado	Bem fundado	Tem junções	Tem encontros	Reflexivo	Irreflexive	Assimétrico
Também conhecido como:			Total, Semiconnex					Anti-reflexivo
Relação de equivalência	✓	✗	✗	✗	✗	✗	✓	✗	✗
Pré-encomenda (quase ordem)	✗	✗	✗	✗	✗	✗	✓	✗	✗
Pedido parcial	✗	✓	✗	✗	✗	✗	✓	✗	✗
Pré-encomenda total	✗	✗	✓	✗	✗	✗	✓	✗	✗
Ordem total	✗	✓	✓	✗	✗	✗	✓	✗	✗
Prewellordering	✗	✗	✓	✓	✗	✗	✓	✗	✗
Quase ordenado	✗	✗	✗	✓	✗	✗	✓	✗	✗
Bem ordenado	✗	✓	✓	✓	✗	✗	✓	✗	✗
Malha	✗	✓	✗	✗	✓	✓	✓	✗	✗
Unir-semilattice	✗	✓	✗	✗	✓	✗	✓	✗	✗
Meet-semilattice	✗	✓	✗	✗	✗	✓	✓	✗	✗


Ordem parcial estrita	✗	✗	✗	✗	✗	✗	✗	✓	✓
Ordem estrita fraca	✗	✗	✗	✗	✗	✗	✗	✓	✓
Pedido total estrito	✗	✗	✓	✗	✗	✗	✗	✓	✓
	Simétrico	Anti-simétrico	Conectado	Bem fundado	Tem junções	Tem encontros	Reflexivo	Irreflexive	Assimétrico
Definições: ${\ displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b \, {\ text {e}} \, S \ neq \ varnothing:}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$	${\ displaystyle \ scriptstyle {aRb \, {\ text {e}} \, bRa \ Rightarrow a = b}}$	${\ displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {ou}} \, bRa}}$	${\ displaystyle \ scriptstyle {\ min S \, {\ text {existe}}}}$	${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {existe}}}}$	${\ displaystyle \ scriptstyle {a \ wedge b \, {\ text {existe}}}}$	${\ displaystyle \ scriptstyle {aRa}}$	${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$

Todas as definições exigem tacitamente que a relação homogênea seja transitiva : Um " ✓ " indica que a propriedade da coluna é necessária na definição da linha. Por exemplo, a definição de uma relação de equivalência requer que ela seja simétrica. Listadas aqui estão propriedades adicionais que uma relação homogênea pode satisfazer.

{\ displaystyle R}

{\ displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b, c, {\ text {if}} aRb {\ text {e}} bRc {\ text {then}} aRc}.}

Uma ordem fraca no conjunto onde é classificada abaixo e e são de igual classificação, e é classificada acima e I) representação como uma ordem fraca estrita onde é mostrada como uma seta de para ; II) representações como uma pré-encomenda total mostrada por meio de setas; III) representação como uma partição ordenada, com os conjuntos da partição como elipses pontilhadas e a ordem total desses conjuntos mostrada com setas.

{\ displaystyle \ {a, b, c, d \}}

{\ displaystyle a}

{\ displaystyle b}

{\ displaystyle c, b}

{\ displaystyle c}

{\ displaystyle d}

{\ displaystyle b}

{\ displaystyle c}

{\ displaystyle \, <\,}

{\ displaystyle x <y}

{\ displaystyle x}

{\ displaystyle y}

{\ displaystyle \, \ leq,}

As 13 possíveis ordens fracas estritas em um conjunto de três elementos. As únicas ordens totais são mostradas em preto. Duas ordens são conectadas por uma aresta se diferirem por uma única dicotomia.

{\ displaystyle \ {a, b, c \}.}

Em matemática , especialmente na teoria da ordem , uma ordem fraca é uma formalização matemática da noção intuitiva de uma classificação de um conjunto , alguns de cujos membros podem estar ligados entre si. Ordens fracas são uma generalização de conjuntos totalmente ordenados (classificações sem empates) e, por sua vez, são generalizadas por conjuntos parcialmente ordenados e pré - ordens .

Existem várias formas comuns de formalizar ordenações fracas, que são diferentes umas das outras, mas criptomórficas (interconvertíveis sem perda de informação): podem ser axiomatizadas como ordenações fracas estritas (conjuntos parcialmente ordenados em que a incomparabilidade é uma relação transitiva ), como total pré-ordens (relações binárias transitivas em que pelo menos uma das duas relações possíveis existe entre cada par de elementos), ou como partições ordenadas ( partições dos elementos em subconjuntos disjuntos, junto com uma ordem total nos subconjuntos). Em muitos casos, outra representação chamada arranjo preferencial com base em uma função de utilidade também é possível.

Pedidos fracos são contados pelos números de Bell ordenados . Eles são usados em ciência da computação como parte de algoritmos de refinamento de partição e na Biblioteca Padrão C ++ .

Exemplos

Nas corridas de cavalos , o uso de fotoacabamentos eliminou alguns, mas não todos, empates ou (como são chamados neste contexto) empates , então o resultado de uma corrida de cavalos pode ser modelado por uma ordem fraca. Em um exemplo da corrida de obstáculos da Maryland Hunt Cup em 2007, The Bruce foi o vencedor claro, mas dois cavalos Bug River e Lear Charm empataram em segundo lugar, com os cavalos restantes mais para trás; três cavalos não terminaram. Na ordem fraca que descreve este resultado, o Bruce seria o primeiro, Bug River e Lear Charm seriam classificados após o Bruce, mas antes de todos os outros cavalos que terminaram, e os três cavalos que não terminaram seriam colocados em último lugar na ordem, mas amarrados um com o outro.

Os pontos do plano euclidiano podem ser ordenados por sua distância da origem , dando outro exemplo de uma ordenação fraca com infinitamente muitos elementos, infinitamente muitos subconjuntos de elementos amarrados (os conjuntos de pontos que pertencem a um círculo comum centrado na origem) , e infinitamente muitos pontos dentro desses subconjuntos. Embora essa ordem tenha um menor elemento (a própria origem), ela não possui nenhum segundo menor elemento, nem nenhum elemento maior.

A pesquisa de opinião em eleições políticas fornece um exemplo de um tipo de ordenação que se assemelha a ordenações fracas, mas é melhor modelado matematicamente de outras maneiras. Nos resultados de uma votação, um candidato pode estar claramente à frente do outro ou os dois candidatos podem estar estatisticamente empatados, o que significa que os resultados não são iguais, mas que estão dentro da margem de erro um do outro. No entanto, se o candidato está estatisticamente empatado com e estatisticamente empatado com ele ainda pode ser possível ser claramente melhor do que estar empatado, neste caso, não é uma relação transitiva . Por causa dessa possibilidade, as classificações desse tipo são melhor modeladas como semiordens do que como ordens fracas. ${\ displaystyle x}$ ${\ displaystyle y,}$ ${\ displaystyle y}$ ${\ displaystyle z,}$ ${\ displaystyle x}$ ${\ displaystyle z,}$

Axiomatizações

Suponha que haja uma relação binária homogênea em um conjunto (ou seja, um subconjunto de ) e, como de costume, escreva e diga que é válido ou é verdadeiro se e somente se ${\ displaystyle \, <\,}$ ${\ displaystyle S}$ ${\ displaystyle \, <\,}$ ${\ displaystyle S \ times S}$ ${\ displaystyle x <y}$ ${\ displaystyle x <y}$ ${\ displaystyle (x, y) \ in \, <. \,}$

Pedidos estritos e fracos

Preliminares sobre incomparabilidade e transitividade da incomparabilidade

Dois elementos e de são incomparáveis com respeito a se nenhum deles for verdadeiro. A incomparabilidade em relação a é ela própria uma relação simétrica homogênea em que é reflexiva se e somente se é irreflexiva (o que significa que é sempre falsa), o que pode ser assumido de forma que transitividade seja a única propriedade que essa "relação de incomparabilidade" precisa para ser uma relação de equivalência . Definem também uma relação homogea induzida em declarando que ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle S}$ ${\ displaystyle \, <\,}$ ${\ displaystyle x <y {\ text {nor}} y <x}$ ${\ displaystyle \, <\,}$ ${\ displaystyle S}$ ${\ displaystyle \, <\,}$ ${\ displaystyle x <x}$ ${\ displaystyle \, \ leq \,}$ ${\ displaystyle S}$

{\ displaystyle x \ leq y {\ text {é verdadeiro}} \ quad {\ text {se e somente se}} \ quad y <x {\ text {é falso}}}

onde é importante, esta definição não é necessariamente a mesma que: se e somente se Dois elementos são incomparáveis com respeito a se e somente se são equivalentes com relação a (ou menos verbosamente, -equivalente ), o que por definição significa que ambos são verdadeiros. A relação "são incomparáveis com respeito a " é, portanto, idêntica a (isto é, igual a) a relação "são -equivalentes" (portanto, em particular, a primeira é transitiva se e somente se a última for). Quando é irreflexiva, em seguida, a propriedade conhecida como " transitividade de incomparabilidade " (definido abaixo) é exatamente a condição necessária e suficiente para garantir que a relação "são -equivalente", de fato, formar uma relação de equivalência em quando este for o caso, ele permite que qualquer dois elementos que satisfazem ser identificados como um único objeto (especificamente, eles são identificados juntos em sua classe de equivalência comum ).

{\ displaystyle x \ leq y}

{\ displaystyle x <y {\ text {ou}} x = y.}

{\ displaystyle x, y \ in S}

{\ displaystyle \, <\,}

{\ displaystyle x {\ text {e}} y}

{\ displaystyle \, \ leq \,}

${\ displaystyle \, \ leq}$

{\ displaystyle x \ leq y {\ text {e}} y \ leq x}

{\ displaystyle \, <}

{\ displaystyle \, \ leq}

{\ displaystyle \, <\,}

{\ displaystyle \, \ leq}

{\ displaystyle S.}

{\ displaystyle x, y \ in S}

{\ displaystyle x \ leq y {\ text {e}} y \ leq x}

Definição

Uma ordenação estritamente fraca em um conjunto é uma

ordem parcial estrita na qual a relação de incomparabilidade induzida por é uma relação transitiva . Explicitamente, uma ordem estrita fraca em é uma relação homogênea em que tem todas as quatro das seguintes propriedades:

{\ displaystyle S}

{\ displaystyle \, <\,}

{\ displaystyle S}

{\ displaystyle S}

{\ displaystyle \, <\,}

{\ displaystyle S}

{\ displaystyle \, <\,}

{\ displaystyle S}

Irreflexividade : Para todos, não é verdade que ${\ displaystyle x \ in S,}$ ${\ displaystyle x \ in S,}$ ${\ displaystyle x <x.}$ ${\ displaystyle x <x.}$
- Esta condição é válida se e somente se a relação induzida em for

reflexiva , onde é definida declarando que é verdadeira se e somente se for falsa .

{\ displaystyle \, \ leq \,}

{\ displaystyle S}

{\ displaystyle \, \ leq \,}

{\ displaystyle x \ leq y}

{\ displaystyle y <x}

Transitividade : para todosseentão

{\ displaystyle x, y, z \ in S,}

{\ displaystyle x <y {\ text {e}} y <z}

{\ displaystyle x <z.}

Assimetria : para todos,seé verdadeiro, entãoé falso.

{\ displaystyle x, y \ in S,}

{\ displaystyle x <y}

{\ displaystyle y <x}

Transitividade de incomparabilidade : Para todosseé incomparável com(o que significa que nemnemé verdadeiro) e seé incomparável comentãoé incomparável com

{\ displaystyle x, y, z \ in S,}

{\ displaystyle x}

{\ displaystyle y}

{\ displaystyle x <y}

{\ displaystyle y <x}

{\ displaystyle y}

{\ displaystyle z,}

{\ displaystyle x}

{\ displaystyle z.}

Dois elementos são incomparáveis com respeito a se e somente se eles são equivalentes com respeito à relação induzida (o que por definição significa que ambos são verdadeiros), onde, como antes, é declarado como verdadeiro se e somente se for falso. Assim, esta condição é válida se e apenas se a

relação simétrica em definido por " são equivalentes no que diz respeito a " é uma relação transitória, o que significa que quando são -equivalente e também são -equivalente então necessariamente são -equivalente. Isso também pode ser reafirmado como: quando e também , necessariamente

{\ displaystyle x {\ text {e}} y}

{\ displaystyle \, <\,}

{\ displaystyle \, \ leq \,}

{\ displaystyle x \ leq y {\ text {e}} y \ leq x}

{\ displaystyle x \ leq y}

{\ displaystyle y <x}

{\ displaystyle S}

{\ displaystyle x {\ text {e}} y}

{\ displaystyle \, \ leq \,}

{\ displaystyle x {\ text {e}} y}

{\ displaystyle \, \ leq}

{\ displaystyle y {\ text {e}} z}

{\ displaystyle \, \ leq}

{\ displaystyle x {\ text {e}} z}

{\ displaystyle \, \ leq}

{\ displaystyle x \ leq y {\ text {e}} y \ leq x}

{\ displaystyle y \ leq z {\ text {e}} z \ leq y}

{\ displaystyle x \ leq z {\ text {e}} z \ leq x.}

As propriedades (1), (2) e (3) são as propriedades definidoras de uma ordem parcial estrita, embora esta lista dessas três propriedades seja um tanto redundante em que a assimetria implica irreflexividade, e em que irreflexividade e transitividade juntas implicam assimetria. A relação de incomparabilidade é sempre simétrica e será reflexiva se e somente se for uma relação irreflexiva (o que é assumido pela definição acima). Conseqüentemente, uma ordem parcial estrita é uma ordem estrita fraca se e somente se sua relação de incomparabilidade induzida for uma

relação de equivalência . Nesse caso, suas classes de equivalência particionam e, além disso, o conjunto dessas classes de equivalência pode ser estritamente ordenado totalmente por uma relação binária , também denotada por que é definida para todos por:

{\ displaystyle \, <\,}

{\ displaystyle \, <\,}

{\ displaystyle S}

{\ displaystyle {\ mathcal {P}}}

{\ displaystyle \, <,}

{\ displaystyle A, B \ in {\ mathcal {P}}}

{\ displaystyle A <B {\ text {se e somente se}} a <b}

para alguns (ou equivalentemente, para todos) representantes

{\ displaystyle a \ em A {\ text {e}} b \ em B.}

Por outro lado, qualquer ordem total rigoroso sobre uma partição da dá origem a uma ordenação fraco rigoroso sobre definida por se e somente se existir conjuntos neste partição tal que ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle S}$ ${\ displaystyle \, <\,}$ ${\ displaystyle S}$ ${\ displaystyle a <b}$ ${\ displaystyle A, B \ in {\ mathcal {P}}}$ ${\ displaystyle a \ in A, b \ in B, {\ text {e}} A <B.}$

Nem toda ordem parcial obedece à lei transitiva da incomparabilidade. Por exemplo, considere a ordem parcial no conjunto definido pela relação Os pares são incomparável mas e estão relacionadas, portanto, incomparabilidade não formar uma relação de equivalência e este exemplo não é uma ordenação fraco estrito. ${\ displaystyle \ {a, b, c \}}$ ${\ displaystyle b <c.}$ ${\ displaystyle a, b {\ text {e}} a, c}$ ${\ displaystyle b}$ ${\ displaystyle c}$

A transitividade da incomparabilidade (juntamente com a transitividade) também pode ser expressa nas seguintes formas:

Se , em seguida, para todos , quer ou ambos. ${\ displaystyle x <y}$ ${\ displaystyle z,}$ ${\ displaystyle x <z {\ text {ou}} z <y}$

Ou:

Se é incomparável com então para todos satisfazendo ( ) ou ( ) ou ( é incomparável com e é incomparável com ). ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle z \ neq x}$ ${\ displaystyle z \ neq y,}$ ${\ displaystyle x <z {\ text {e}} y <z}$ ${\ displaystyle z <x {\ text {e}} z <y}$ ${\ displaystyle z}$ ${\ displaystyle x}$ ${\ displaystyle z}$ ${\ displaystyle y}$

Total de encomendas

As ordens fracas estritas estão intimamente relacionadas às pré -

encomendas totais ou ordens fracas (não estritas) , e os mesmos conceitos matemáticos que podem ser modelados com ordens fracas estritas podem ser modelados igualmente bem com as pré-encomendas totais. Uma pré-encomenda total ou pedido fraco é uma pré - encomenda em que quaisquer dois elementos são comparáveis. Uma encomenda total satisfaz as seguintes propriedades:

{\ displaystyle \, \ lesssim \,}

Transitividade : para todos se então ${\ displaystyle x, y, {\ text {e}} z,}$ ${\ displaystyle x \ lesssim y {\ text {e}} y \ lesssim z}$ ${\ displaystyle x \ lesssim z.}$
Conexão forte : para todos ${\ displaystyle x {\ text {e}} y,}$ ${\ displaystyle x {\ text {e}} y,}$ ${\ displaystyle x \ lesssim y {\ text {ou}} y \ lesssim x.}$ ${\ displaystyle x \ lesssim y {\ text {ou}} y \ lesssim x.}$
- O que implica reflexividade : para todos ${\ displaystyle x,}$ ${\ displaystyle x \ lesssim x.}$

Uma encomenda total é uma pré-encomenda total anti-simétrica, ou seja, também uma encomenda parcial . As pré-encomendas totais às vezes também são chamadas de relações de preferência .

O complemento de uma ordem estrita fraca é uma pré-ordem total e vice-versa, mas parece mais natural relacionar ordens estritas fracas e pré-ordens totais de uma forma que preserva em vez de inverter a ordem dos elementos. Assim, tomamos o inverso do complemento: para uma ordenação fraca estrita definir uma pré-venda total de definindo sempre que não é o caso que Na outra direção, para definir uma ordem fraca estrita <de um total de pré-encomenda set sempre que não é o caso naquela ${\ displaystyle \, <,}$ ${\ displaystyle \, \ lesssim \,}$ ${\ displaystyle x \ lesssim y}$ ${\ displaystyle y <x.}$ ${\ displaystyle \, \ lesssim,}$ ${\ displaystyle x <y}$ ${\ displaystyle y \ lesssim x.}$

Em qualquer pré-venda há uma relação de equivalência correspondente onde dois elementos e são definidos como

equivalentes se No caso de um total de pré-venda a fim parcial correspondente sobre o conjunto de classes de equivalência é uma ordem total. Dois elementos são equivalentes em uma pré-encomenda total se e somente se eles forem incomparáveis na ordem estrita e fraca correspondente.

{\ displaystyle x}

{\ displaystyle y}

{\ displaystyle x \ lesssim y {\ text {e}} y \ lesssim x.}

Partições ordenadas

Uma partição de um conjunto é uma família de subconjuntos disjuntos não vazios que têm como união. Uma partição, juntamente com uma

ordem total sobre os conjuntos de partição, dá uma estrutura chamada por Richard P. Stanley uma partição ordenada e por Theodore Motzkin uma lista de conjuntos . Uma partição ordenada de um conjunto finito pode ser escrita como uma sequência finita dos conjuntos na partição: por exemplo, as três partições ordenadas do conjunto são

{\ displaystyle S}

{\ displaystyle S}

{\ displaystyle S}

{\ displaystyle \ {a, b \}}

{\ displaystyle \ {a \}, \ {b \},}

{\ displaystyle \ {b \}, \ {a \},}

e

{\ displaystyle \ {a, b \}.}

Em uma ordem estritamente fraca, as classes de equivalência de incomparabilidade dão uma partição de conjunto, na qual os conjuntos herdam uma ordem total de seus elementos, dando origem a uma partição ordenada. Na outra direção, qualquer partição ordenada dá origem a uma ordem estritamente fraca em que dois elementos são incomparáveis quando pertencem ao mesmo conjunto na partição e, de outra forma, herdam a ordem dos conjuntos que os contêm.

Representação por funções

Para conjuntos de cardinalidade suficientemente pequena , uma terceira axiomatização é possível, com base em funções de valor real. Se for qualquer conjunto, então uma função de valor real em induz uma ordem estritamente fraca em configurando ${\ displaystyle X}$ ${\ displaystyle f: X \ to \ mathbb {R}}$ ${\ displaystyle X}$ ${\ displaystyle X}$

{\ displaystyle a <b {\ text {se e somente se}} f (a) <f (b).}

A pré-encomenda total associada é dada por configuração e a equivalência associada por configuração

{\ displaystyle a {} \ lesssim {} b {\ text {se e somente se}} f (a) \ leq f (b)}

{\ displaystyle a {} \ sim {} b {\ text {se e somente se}} f (a) = f (b).}

As relações não mudam quando é substituída por (

função composta ), onde é uma função de valor real estritamente crescente definida em pelo menos o intervalo de Assim, por exemplo, uma função de utilidade define uma relação de preferência . Nesse contexto, ordens fracas também são conhecidas como arranjos preferenciais .

{\ displaystyle f}

{\ displaystyle g \ circ f}

{\ displaystyle g}

{\ displaystyle f.}

Se for finito ou contável, toda ordem fraca em pode ser representada por uma função dessa forma. No entanto, existem ordens estritamente fracas que não têm função real correspondente. Por exemplo, não existe tal função para a

ordem lexicográfica em Assim, enquanto na maioria dos modelos de relação de preferência a relação define uma função de utilidade até as transformações que preservam a ordem, não existe tal função para preferências lexicográficas .

{\ displaystyle X}

{\ displaystyle X}

{\ displaystyle \ mathbb {R} ^ {n}.}

Mais geralmente, se for um conjunto, é um conjunto com uma ordem estritamente fraca e é uma função, então induz uma ordem estritamente fraca na configuração ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle \, <, \,}$ ${\ displaystyle f: X \ a Y}$ ${\ displaystyle f}$ ${\ displaystyle X}$

{\ displaystyle a <b {\ text {se e somente se}} f (a) <f (b).}

Como antes, a pré-encomenda total associada é dada por configuração e a equivalência associada por configuração. Não é assumido aqui que é uma função injetiva , então uma classe de dois elementos equivalentes em pode induzir uma classe maior de elementos equivalentes em Além disso, não é assumido para ser uma função sobrejetiva , de modo que uma classe de elementos equivalentes em pode induzir uma classe menor ou vazia em No entanto, a função induz uma função injetiva que mapeia a partição em. Assim, no caso de partições finitas, o número de classes em é menor ou igual ao número de classes em

{\ displaystyle a {} \ lesssim {} b {\ text {se e somente se}} f (a) {} \ lesssim {} f (b),}

{\ displaystyle a {} \ sim {} b {\ text {se e somente se}} f (a) {} \ sim {} f (b).}

{\ displaystyle f}

{\ displaystyle Y}

{\ displaystyle X.}

{\ displaystyle f}

{\ displaystyle Y}

{\ displaystyle X.}

{\ displaystyle f}

{\ displaystyle X}

{\ displaystyle Y.}

{\ displaystyle X}

{\ displaystyle Y.}

Tipos de pedidos relacionados

Semiordens generalizam

ordens estritamente fracas, mas não assumem transitividade de incomparabilidade. Uma ordem estrita fraca que é tricotômica é chamada de ordem total estrita . A pré-encomenda total que é o inverso de seu complemento é, neste caso, uma ordem total .

Para uma ordem fraca estrita outra relação reflexiva associado é o seu

fecho reflexivo , uma (não-estrito) ordem parcial As duas relações reflexivas associados diferem em relação ao diferente e para o qual nem nem : na pré-venda total correspondente a uma ordem fraca estrita obtemos e enquanto na ordem parcial dada pelo fechamento reflexivo não obtemos nem, nem. Para ordens totais estritas, essas duas relações reflexivas associadas são as mesmas: a ordem total correspondente (não estrita). O fechamento reflexivo de uma ordem estrita fraca é um tipo de ordem parcial série-paralela .

{\ displaystyle \, <\,}

{\ displaystyle \, \ leq.}

{\ displaystyle a}

{\ displaystyle b}

{\ displaystyle a <b}

{\ displaystyle b <a}

{\ displaystyle a \ lesssim b}

{\ displaystyle b \ lesssim a,}

{\ displaystyle a \ leq b}

{\ displaystyle b \ leq a.}

Todas as ordens fracas em um conjunto finito

Enumeração combinatória

O número de ordens fracas distintas (representadas como ordens fracas estritas ou como pré-ordens totais) em um conjunto de elementos é dado pela seguinte sequência (sequência

A000670 no OEIS ):

{\ displaystyle n}

Número de relações binárias de n elementos de diferentes tipos
Elementos	Algum	Transitivo	Reflexivo	Pedido antecipado	Pedido parcial	Pré-encomenda total	Ordem total	Relação de equivalência
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65.536	3.994	4.096	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ² - n}			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$	n !	${\ textstyle \ sum _ {k = 0} ^ {n}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Esses números também são chamados de números de Fubini ou

números ordenados de Bell .

Por exemplo, para um conjunto de três itens rotulados, há uma ordem fraca em que todos os três itens estão empatados. Existem três maneiras de particionar os itens em um conjunto de singleton e um grupo de dois itens vinculados, e cada uma dessas partições fornece duas ordens fracas (uma em que o singleton é menor do que o grupo de dois e outra em que esta ordem é invertida), dando seis ordens fracas desse tipo. E há uma única maneira de particionar o conjunto em três singletons, que podem ser totalmente ordenados de seis maneiras diferentes. Assim, ao todo, existem 13 pedidos fracos diferentes em três itens.

Estrutura de Adjacência

O permutoedro em quatro elementos, um poliedro convexo tridimensional . Possui 24 vértices, 36 arestas e 14 faces bidimensionais, que, em conjunto com todo o poliedro tridimensional, correspondem às 75 ordens fracas em quatro elementos.

Ao contrário das ordens parciais, a família de ordens fracas em um determinado conjunto finito não é, em geral, conectada por movimentos que adicionam ou removem uma única relação de ordem para ou de uma dada ordem. Por exemplo, para três elementos, a ordem na qual todos os três elementos são amarrados difere em pelo menos dois pares de qualquer outra ordem fraca no mesmo conjunto, seja na ordem estrita fraca ou nas axiomatizações totais pré-ordem. No entanto, um tipo diferente de movimento é possível, no qual as ordens fracas em um conjunto são mais altamente conectadas. Defina uma dicotomia como uma ordenação fraca com duas classes de equivalência e defina uma dicotomia como compatível com uma dada ordenação fraca se todos os dois elementos relacionados na ordenação estiverem relacionados da mesma maneira ou amarrados na dicotomia. Alternativamente, uma dicotomia pode ser definida como um corte de Dedekind para uma ordenação fraca. Então, uma ordenação fraca pode ser caracterizada por seu conjunto de dicotomias compatíveis. Para um conjunto finito de itens rotulados, cada par de ordenações fracas pode ser conectado entre si por uma sequência de movimentos que adicionam ou removem uma dicotomia por vez para ou a partir desse conjunto de dicotomias. Além disso, o gráfico não direcionado que tem as ordens fracas como seus vértices, e esses se movem como suas arestas, forma um cubo parcial .

Geometricamente, as ordenações totais de um determinado conjunto finito podem ser representadas como os vértices de um permutoedro e as dicotomias nesse mesmo conjunto como as facetas do permutoedro. Nesta representação geométrica, as ordens fracas no conjunto correspondem às faces de todas as diferentes dimensões do permutoedro (incluindo o próprio permutoedro, mas não o conjunto vazio, como uma face). A codimensão de uma face fornece o número de classes de equivalência na ordem fraca correspondente. Nesta representação geométrica, o cubo parcial de movimentos em ordens fracas é o gráfico que descreve a relação de cobertura da rede da face do permutoedro.

Por exemplo, para o permutoedro em três elementos é apenas um hexágono regular. A estrutura de face do hexágono (novamente, incluindo o próprio hexágono como uma face, mas não incluindo o conjunto vazio) tem treze elementos: um hexágono, seis arestas e seis vértices, correspondendo a uma ordenação fraca completamente amarrada, seis ordenações fracas com um empate e seis pedidos no total. O gráfico de movimentos nessas 13 ordens fracas é mostrado na figura. ${\ displaystyle n = 3,}$

Formulários

Como mencionado acima, os pedidos fracos têm aplicações na teoria da utilidade. Em programação linear e outros tipos de problemas de otimização combinatória , a priorização de soluções ou de bases é freqüentemente dada por uma ordem fraca, determinada por uma função objetivo de valor real ; o fenômeno dos empates nessas ordenações é chamado de "degeneração", e vários tipos de regra de desempate têm sido usados para refinar essa ordenação fraca em uma ordenação total, a fim de evitar problemas causados pela degeneração.

As ordens fracas também têm sido usadas na ciência da computação , em algoritmos baseados em refinamento de partição para pesquisa lexicográfica em amplitude e ordenação topológica lexicográfica . Nestes algoritmos, uma ordem fraca nos vértices de um gráfico (representada como uma família de conjuntos que particionam os vértices, junto com uma lista duplamente ligada fornecendo uma ordem total nos conjuntos) é gradualmente refinada ao longo do algoritmo, eventualmente produzindo uma ordenação total que é a saída do algoritmo.

Na Biblioteca Padrão para a linguagem de programação C ++ , os tipos de dados conjunto e multiset classificam sua entrada por uma função de comparação que é especificada no momento da instanciação do modelo e que se supõe implementar uma ordenação estritamente fraca.

Veja também

Comparabilidade
Pré - encomenda - relação binária reflexiva e transitiva

Languages

In other projects