Extensão linear - Linear extension

Na teoria da ordem , um ramo da matemática , uma extensão linear de uma ordem parcial é uma ordem total (ou ordem linear) compatível com a ordem parcial. Como um exemplo clássico, a ordem lexicográfica de conjuntos totalmente ordenados é uma extensão linear de sua ordem de produto .

Definições

Dadas quaisquer ordens parciais e em um conjunto há uma extensão linear de exatamente quando (1) é uma ordem total e (2) para cada se então É essa segunda propriedade que leva os matemáticos a descrever como extensível${\ displaystyle \, \ leq \,}$${\ displaystyle \, \ leq ^ {*} \,}$${\ displaystyle X,}$ ${\ displaystyle \, \ leq ^ {*} \,}$${\ displaystyle \, \ leq \,}$${\ displaystyle \, \ leq ^ {*} \,}$${\ displaystyle x, y \ in X,}$${\ displaystyle x \ leq y,}$${\ displaystyle x \ leq ^ {*} y.}$${\ displaystyle \, \ leq ^ {*} \,}$ ${\ displaystyle \, \ leq.}$

Alternativamente, uma extensão linear pode ser vista como uma bijeção que preserva a ordem de um conjunto parcialmente ordenado para uma cadeia no mesmo conjunto básico. ${\ displaystyle P}$ ${\ displaystyle C}$

Princípio de extensão de pedido

A afirmação de que todo pedido parcial pode ser estendido a um pedido total é conhecido como princípio de extensão do pedido . Uma prova usando o axioma da escolha foi publicada pela primeira vez por Edward Marczewski em 1930. Marczewski escreve que o teorema já havia sido provado por Stefan Banach , Kazimierz Kuratowski e Alfred Tarski , novamente usando o axioma da escolha, mas que as provas não foram Publicados.

Na moderna teoria axiomática dos conjuntos, o próprio princípio da extensão da ordem é considerado um axioma, de status ontológico comparável ao axioma da escolha. O princípio de extensão de ordem está implícito no teorema do ideal primo booleano ou no teorema da compactação equivalente , mas a implicação reversa não é válida.

Aplicando o princípio da extensão de ordem a uma ordem parcial na qual cada dois elementos são incomparáveis ​​mostra que (sob este princípio) todo conjunto pode ser linearmente ordenado. Essa afirmação de que todo conjunto pode ser ordenado linearmente é conhecida como o princípio de ordenação , OP, e é um enfraquecimento do teorema de ordenação . No entanto, existem modelos de teoria dos conjuntos em que o princípio de ordenação é válido, enquanto o princípio de extensão de ordem não.

Resultados relacionados

O princípio de extensão de ordem é construtivamente demonstrável para conjuntos finitos usando algoritmos de ordenação topológica , onde a ordem parcial é representada por um gráfico acíclico direcionado com os elementos do conjunto como seus vértices . Vários algoritmos podem encontrar uma extensão no tempo linear . Apesar da facilidade de encontrar uma única extensão linear, o problema de contar todas as extensões lineares de uma ordem parcial finita é # P-completo ; no entanto, pode ser estimado por um esquema de aproximação aleatória em tempo polinomial completo . Entre todas as ordens parciais com um número fixo de elementos e um número fixo de pares comparáveis, as ordens parciais que têm o maior número de extensões lineares são semiordens .

A dimensão de ordem de uma ordem parcial é a cardinalidade mínima de um conjunto de extensões lineares cuja interseção é a ordem parcial fornecida; equivalentemente, é o número mínimo de extensões lineares necessárias para garantir que cada par crítico da ordem parcial seja revertido em pelo menos uma das extensões.

Os antimatróides podem ser vistos como generalizadores de ordens parciais; nesta visão, as estruturas correspondentes às extensões lineares de uma ordem parcial são as palavras básicas do antimatróide.

Esta área também inclui um dos problemas abertos mais famosos da teoria da ordem, a conjectura 1 / 3–2 / 3 , que afirma que em qualquer conjunto finito parcialmente ordenado que não seja totalmente ordenado , existe um par de elementos para os quais as extensões lineares de em que o número entre 1/3 e 2/3 do número total de extensões lineares de uma forma equivalente para indicar a conjectura é que, se se escolher uma extensão linear de modo uniforme de forma aleatória, existe um par que tem probabilidade de entre 1 / 3 e 2/3 de ser ordenado como No entanto, para certos conjuntos parcialmente ordenados infinitos, com uma probabilidade canônica definida em suas extensões lineares como um limite das probabilidades para ordens parciais finitas que cobrem a ordem parcial infinita, o 1 / 3-2 / 3 conjectura não se sustenta. ${\ displaystyle P}$${\ displaystyle (x, y)}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle x <y}$${\ displaystyle P.}$${\ displaystyle P}$${\ displaystyle (x, y)}$${\ displaystyle x <y.}$

Combinatória algébrica

Contar o número de extensões lineares de um poset finito é um problema comum em combinatória algébrica . Este número é dado pelo coeficiente líder do polinômio de ordem multiplicado por${\ displaystyle | P | !.}$

O tableau jovem pode ser considerado como uma extensão linear de um ideal de ordem finito no poset infinito e eles são contados pela fórmula do comprimento do gancho . ${\ displaystyle \ mathbb {N} \ times \ mathbb {N},}$

Referências