선형연장

수학의 한 분야인 순서 이론에서 부분 순서의 선형 확장은 부분 순서와 호환되는 총 순서(또는 선형 순서)이다.전형적인 예로, 완전 주문 세트의 사전 순서는 그들의 제품 주문의 선형 확장이다.

정의들

Given any partial orders ${\displaystyle \,\leq \,}$ and ${\displaystyle \,\leq ^{*}\,}$ on a set ${\displaystyle X,}$ ${\displaystyle \,\leq ^{*}\,}$ is a linear extension of ${\displaystyle \,\leq \,}$ exactly when (1) ${\displaystyle \,\leq ^{*}\,}$ is a total order and (2) for every ${\displaystyle x,y\in X,}$ if ${\displaystyle x\leq y,}$ then ${\displaystyle x\leq ^{*}y.}$ It is that second property that leads mathematicians to describe ${\displaystyle \,\leq ^{*}\,}$ as extending ${\displaystyle \,\leq .}$

또는, 선형 확장은 부분적으로 주문한 P ${\displaystyle P}$에서 동일한 접지 세트의 체인 C ${\displaystyle C}($으)로의 주문 보존 편향으로 볼 수 있다.

순서연장원리

모든 부분 순서는 전체 순서에 따라 연장할 수 있다는 말은 순서 연장 원리로 알려져 있다.선택이라는 공리를 사용한 증거는 1930년 에드워드 마크제프스키에 의해 처음 발표되었다.마르체브스키는 그 정리가 스테판 바나흐, 카지미에츠 쿠라토프스키, 알프레드 타르스키에 의해 다시 선택이라는 공리를 사용하여 이전에 증명되었지만, 그 증거는 발표되지 않았다고 쓰고 있다.^[1]

현대 자명 세트 이론에서 순서 확장 원리는 그 자체가 선택이라는 공리와 유사한 존재론적 지위를 갖는 공리로 받아들여진다.순서 연장 원리는 부울 프라임 이상 정리나 등가 콤팩트 정리에 의해 함축되어 있으나 역 함축성은 함축되지 않는다.^[2][3]

두 요소마다 비교할 수 없는 부분적인 순서에 순서 확장 원리를 적용하면 (이 원칙에 따라) 모든 세트가 선형적으로 순서가 가능하다는 것을 알 수 있다.모든 세트를 선형적으로 정렬할 수 있다는 이 주장은 순서 원리 OP로 알려져 있으며, 잘 정돈된 정리를 약화시키는 것이다.그러나 순서 연장 원리는 유지하지만 순서 연장 원리는 유지하지 않는 집합 이론의 모델이 있다.^[4]

관련결과

순서 확장 원리는 위상학적 정렬 알고리즘을 사용하여 유한 집합에 대해 건설적으로 증명할 수 있으며, 여기서 부분 순서는 집합의 요소를 정점으로 한 방향의 AC 순환 그래프로 표현된다.여러 알고리즘이 선형 시간에서 확장을 찾을 수 있다.^[5]단일 선형 확장을 쉽게 찾을 수 있음에도 불구하고 유한 부분 순서의 모든 선형 확장을 계산하는 문제는 #P-완전하다. 단, 완전 다항식 시간 무작위 근사법으로 추정할 수 있다.^[6][7]원소의 수가 정해져 있고 비교할 수 있는 쌍의 수가 정해져 있는 모든 부분순서 중에서 선형 확장의 수가 가장 많은 부분순서는 반순서다.^[8]

부분 순서의 순서 치수는 주어진 부분 순서가 교차하는 선형 확장 집합의 최소 카디널리티다. 동등하게, 부분 순서의 각 임계 쌍이 적어도 하나 이상의 확장에서 반전되도록 하는 데 필요한 최소 선형 확장의 수입니다.

항이마트로이드는 부분 순서를 일반화하는 것으로 볼 수 있다. 이러한 관점에서 부분 순서의 선형 확장에 해당하는 구조는 항이마트로이드의 기본 단어들이다.^[9]

또한 이 영역은 순서가론의 가장 유명한 개방적 문제 중 하나인 1/3–2/3 추측을 포함하며, 완전히 순서가 정해지지 않은 유한 부분 순서의 P ${\displaystyle P}$에는 P ${\displaystyle P}$ 요소의 쌍(x, y ) ${\displaystyle (x,y)$이 존재하며, P의 선형 확장이 있다.에서{P\displaystyle})<>y 1/3와 2/3P의 선형 확장의 총 수를 사이에{\displaystyle x<, y}번호입니다.{P.\displaystyle}만약 한 P의 선형 확장{P\displaystyle}균일하게 임의로에서를 택한다면, 한쌍입니다는(), y)는 추측한 등가 방법[10][11]. {\displayst$(x,y)}$은(는) x< . ${\displaystyle x<y$)로 주문될 확률의 1/3과 2/3 사이입니다$.$$}}$ 그러나, 어떤 무한 부분 순서 집합의 경우, 그 선형 확장에 대해 무한 부분 순서를 포괄하는 유한 부분 순서에 대한 확률의 한계로 정의되는 표준적 확률을 가지고 있는 경우, 1/3–2/3 추측은 유지되지 않는다.^[12]

대수적 결합론

유한양세트의 선형 확장 수를 세는 것은 대수적 결합학에서 흔히 있는 문제다.이 숫자는 다항식 순서의 선행 계수에 P!. . ${\displaystyle$ P !를 곱하여 주어진다$.$$}$

젊은 tableau는 무한 포셋N × N, {\$displaystyle \mathb${N} \$timees$ \mathb ${N} ,}$에서 유한한 순서 이상에 대한 선형 확장으로 간주할 수 있으며, 후크 길이 공식에 의해 계산된다.

참조