세미오더

수학의 한 분야인 순서론에서 세미오더(semiorder)는 점수가 크게 다른 항목을 점수로 비교하고 주어진 오차범위 내의 점수는 비교할 수 없는 것으로 간주하는 수적 점수를 가진 항목을 주문하는 유형이다.준순서는 인간 선호의 모델로 던컨 루스(1956)가 수학 심리학에 도입해 적용했다.점수가 같은 항목은 동점이지만 오차범위는 없는 엄격한 취약 순서를 일반화한다.부분순서와 구간순서의 특수한 경우로, 추가 공리 또는 금지된 4항목 하위순서 2개에 의한 부분순서 가운데 특징지을 수 있다.

효용 이론

세미오더 도입의 원래 동기는 비교가능성이 타동적 관계라고 가정하지 않고 인간의 선호도를 모형화하는 것이었다.예를 들어, $x{\displaystyle }$ ${\displaystyle$ x$\},$ $y{\displaystyle }${\$displaystyle y}$ 및 $z{\displaystyle }${\$displaystyle z}$이(가) 동일한 재료의 세 수량을 나타내고$$ x ${\displaystyle x}$ 및 $z{\displaystyle }$ ${\displaysty$ z$}$이(가) 차이가 있을 때 $y{\displaystyle }$ ${\displaystysty$ y$}$은 두 $o$의 중간이다$$.$그{\displaystyle }$ 다음 x ${\displaystyle x}$과(와$$) $z{\displaystyle }$ ${\displaystyle z}$ 사이에 선호도가 존재하지만 다른 두 쌍 사이에는 존재하지 않아 transitability를 위반하는 것이 합리적이다.^[1]

$이{\displaystyle }$ 값을 수학적으로 모형화하려면$$u {\$displaystyle u}$을(를$)$ 비교할 객체를 실제 숫자에 매핑하는 유틸리티 함수가 되도록$$ 하여 객체에 수치 유틸리티 값이 부여된다고 가정하십시오$.$. 그런 다음에 숫자 문턱("1까지 정상화될 수 있)가 각 다른 사람들의 허용치 이내로 전력 회사 비할 데 없는, 이진 관계를<>를 정의하고, 사물에{\displaystyle<>}, x<>을 설정하여;y{\displaystyle x<, y} 때마다 너())≤ 너(y)− 1{\displaystyle u())\leq u(y)-1}선언된다. (X,<.)$(X,<)$는 세미오더를 형성한다.^[2]대신에, 만약 물체가 효용이 다를 때마다 비교가능하다고 선언된다면, 그 결과는 엄격한 약소 순서가 될 것이고, 그 결과 물체의 비교가능성은 (숫자의 동일성에 근거한) 전이될 것이다.^[1]

공리학

위와 같은 효용함수에서 정의한 세미오더는 다음과 같은 두 가지 특성을 가진 부분 순서의 집합이다.^[3]

• 때문에 u(w)≤ 너(y){\displaystyle u(w)\leq u(y)}w<>함축할 때마다 요소의 두 차갑쌍 w<>인스턴스서,^{\displaystyle w<^}및 y<>이 요소 사이에 z{\displaystyle y<, z}, 배려한 추가적인 비교, 비교할 만하다;z{\displaystyle w<, z}는 동안 u(지..지 )≥ 너(y){\di$splaystyle u(w)\geq u(y)}$는 < ${\displaystyle y<x}$를 의미할 것이다따라서 서로 비교할 수 없는 2점 선형 순서가 두 개씩이나 있는 것은 불가능하다.^[3]
• 3개 요소를 선형 순서 w<>를 형성하^<> 베{\displaystyle w<, x<, y}, 그때{z\displaystyle}적어도 그들 중 하나에 못지 않는 모든 네번째 요점은 z, 때문에 u(z)≤ 너()){\displaystyle u(z)\leq u())};y{\displaystyle z<, y}는 동안 u(z)≥ 너()){\displaystyle은<>를 암시합니다.u(z)\geq u())}$두{\displaystyle }$ 경우 모두 z {\$displaystyle$ z$$}^[3]이$($$)$ w {\$displaystyle$ $w$} 또는 y {\$displaystyle$ y}과(와) 비슷하다는 것을 나타내는 ${\displaystyle w$$}$을를$)$ 암시할 수 있다$.$ 따라서 네 번째 비교할 수 없는 점을 가진 3점 선형 순서를 갖는 것은 불가능하다.

반대로 위에서 설명한 두 가지 금지된 4점 순서를 피하는 모든 유한 부분 순서는 효용 값을 주어 세미오더로 만들 수 있다.^[4] 따라서 효용 측면에서 정의의 결과라기보다는 이러한 금지된 순서, 즉 공리의 등가 시스템이 준순서의 조합적 정의로 받아들여질 수 있다.^[5]만약 세미오더가 이러한 공리에 순응하면서 요소 쌍들 간의 순서 관계로만 주어진다면, $시간{\displaystyle }$O (${\displaystyle {n\mathrm{}}^{}}$ 2$){\displaystyle$ O $(n^{2})$의 순서를 나타내는 유틸리티 함수를 구성할 수 있다$.$ 여기서 $n{\displaystyle }$ ${\displaystyn}$은(는) 세미오더의 요소 수이고 O ${\d$.$isplaystyle O}$은(는) 큰 O 표기법의 한 예다.^[6]

무한대의 요소 집합에 대한 순서는 효용 함수에 의해 정의될 수 있는 순서와 금지된 4점 순서에 의해 정의될 수 있는 순서가 서로 다르다.예를 들어, 세미오더,<) ${\displaystyle (X,<)}($금지된 주문에 의해 정의됨)가 완전히 주문할 수 없는 부분 집합을 포함하는 경우, 유틸리티 함수로 나타낼 수 있을 만큼 충분히 충분한 간격의 실제 숫자가 존재하지 않는다.피시번(1973)은 숫자로 정의할 수 있는 세미오더의 정확한 특성화를 제공한다.

다른 종류의 질서와의 관계

부분주문

하나는 semiorder(X,<.)에서) 때마다 양쪽 x<>:;y나 x)공리가 부분적인 명령에 복종하는 것이 필요하다 중에서 y., 재귀성()≤))자동으로 이 정의로부터 다음과 같이 ≤를 선언한 부분 순서(X,≤)을 규정할 수 있,antisymmetry(if)이 어두워져서, y≤ ≤) 다음 = y)첫번째 semiorder은 공리에서, 타동성(만약 x다음 ≤ yd y ≤ z 그 다음 x z z)는 두 번째 세미오더 공리에서 따온다.반대로, 이러한 방식으로 정의된 부분 순서로부터, x ≤ y와 x ≠ y가 있을 때마다 x < y를 선언함으로써 세미오더를 회복할 수 있다.위에 열거된 제반 공리 중 첫 번째 공리는 부분 순서를 정의하는 공리에서 자동으로 따르며, 다른 공리는 그렇지 않다.두 번째와 세 번째 세 번째 세 번째 공리는 두 개의 분리된 사슬을 형성하는 네 가지 항목의 부분 주문을 금지한다. 두 번째 공리는 두 개의 사슬을 각각 두 개씩 금지하고, 세 번째 공리는 한 개의 관련 없는 사슬을 가진 세 개 항목의 사슬을 금지한다.

약주문

엄격하고 약한 모든 주문 < 역시 준주문이다.더욱 특히 <에 대한 초월성과 <함께>에 대한 비교불가능성의 초월성은 위의 공리 2를 내포하고 있는 반면, 비교불가능성의 전이성만 해도 공리 3을 내포하고 있다.맨 위 이미지에서 보이는 세미오더는 가장 오른쪽 꼭지점이 가장 가까운 왼쪽 이웃 두 곳과 비교할 수 없을 만큼 엄밀하게 약한 순서가 아니다.

인터벌 오더

유틸리티 함수 $u{\displaystyle }$ ${\displaystyle u}$에서 정의된 세미오더는 [${\displaystyle u}$( ${\displaystyle x}$)${\displaystyle }$,${\displaystyle u}$ ${\displaystyle (}$x ${\displaystyle )}$+ ${\displaystyle 1}$ ${\displaystyle ]}$ $[\displaystyle [$u$(x),u$ ($x)+1]$에 의해 정의된 간격 순서로 동등하게 정의될 수 있으므로$$, 모든 세미오더는 구간 순서의 예시라고 할 수 있다$.$^[7]관계는 단위 길이 간격의 간격 순서$({\displaystyle }$ as ${\displaystyle i_{}}$ ${\displaystyle \mathrm{\ell }}$ ${\displaystyle i_{}}$+ 1${\displaystyle }$)로 얻을 수 있는 경우에만 세미오더(\$ell _{i}\ell _{i}+1$)이다$.$

퀘이스트란시브 관계

아마르티아 K에 의하면. Sen,^[8] 준주문자는 Dean T. Jamison과 Lawrence J. Lau가^[9] 검사한 결과, Quasitrantic 관계의 특별한 경우인 것으로 밝혀졌다.사실 모든 반향은 quasitrantic이고, ^[10]quasitransivity는 비교가 안 되는 모든 쌍의 아이템을 추가하는 데 불변이다.^[11]맨 위 이미지에서 모든 비수직 빨간색 선을 제거하면 여전히 Quasitrantic이지만 공리 2와 3을 모두 위반하는 관계에 대한 Hasse 다이어그램이 생성되며, 이 관계는 더 이상 선호 순서로 유용하지 않을 수 있다.

콤비네이터 열거

라벨이$$ 부착되지 않은 $n{\displaystyle }$ ${\displaystylen}$개 품목에 대한 구별되는 세미 오더 수는 카탈루냐^[12] 번호로 지정됨

$n{\displaystyle }$ ${\displaystylen}$ 레이블이$$ 지정된 항목의 세미오더 수는 순서에^[13] 따라 지정됨

기타 결과

어떤 유한한 세미오더는 최대 3개의 순서 차원을 가지고 있다.^[14]

원소의 수가 정해져 있고 비교할 수 있는 쌍의 수가 정해져 있는 모든 부분순서 중에서 선형 확장의 수가 가장 많은 부분순서는 반순서다.^[15]

Semiorders은1/3–2/3 추측에 따르기:이 아닌 전체 주문 어떤 유한 semiorder에는 요소의 한쌍){\displaystyle)}이 존재한다면으로 알려져 있y{이\displaystyle}가 x{\displaystyle)}것보다 일찍 베{이\displaystyle}사이에 1/3와 3분의 2의 선형 확대의 전 semiorder.[3]

$n{\displaystyle }$ ${\displaystyle n}$ -element$$ 세트의 세미오더 세트는 등급이 양호하며, 같은 세트의 세미오더 두 $개$가 k$${\$displaysty k}$ 오더$$ 관계를 추가하거나 제거하여 서로 다른 경우, 첫 번째 세미오더에서 두 번째 세미오더까지의 $k{\displaystyle }$ ${\displaysty k}$ 단계의$$ 경로를 찾을 수 있다.경로의 각 단계는 단일 순서 관계를 추가하거나 제거하며 경로의 각 중간 상태는 그 자체로 세미오더(semiorder)이다.^[16]

세미오더의 비교가능성 그래프를 무관심 그래프라고 하는데 구간 그래프의 특별한 경우다.^[17]

메모들

참조

추가 읽기

• Pirlot, M.; Vincke, Ph. (1997), Semiorders: Properties, representations, applications, Theory and Decision Library. Series B: Mathematical and Statistical Methods, vol. 36, Dordrecht: Kluwer Academic Publishers Group, ISBN 0-7923-4617-3, MR 1472236.