Order Relation관련 용어 정리

1.(About symmetric)

-용어정의

-R이 symmetric란, for any a,b in X, R(a,b)이면 R(b,a)이다.

-R이 asymetric란, for any a,b in X, R(a,b)이면 not R(b,a)이다.

-R이 antisymmetric란, for any a,b in X, R(a,b) and R(b,a)이면 a=b이다.

(혹은 for any a,b in X, R(a,b)이고 a != b이면 not R(b,a)이다.)

symmetric의 부정은 asymmetric인게 아님.

asymmetric이면 irreflexive

irreflexive이고 antisymmetric의 필요충분은 asymmetric

(antisymmetric은 symmetric의 부정과도 비슷하지만, R(a,a)가 있을 수도 있을 때 이용)

2. (About reflexive)

-용어정의

-R이 irreflexive란, for any a in X, not R(a,a)이다.

-R이 reflexive란, for any a in X, R(a,a)이다.

irreflexive는 strict에서 사용(따라서 strict는 irreflexive나 asymmetric을 이용)

reflexive는 non-strict에서 사용(따라서 symmetric하지 않음이 필요하다면 antisymmetric사용)

irreflexive는 reflexive의 부정은 아님

3. (About totality)

-용어정의

-R이 total이란, for any a,b in X, R(a,b) or R(b,a)(둘다 성립해도 괜찮)

-R이 trichotomous란, for any a,b in X, 다음 3가지중 단 1개만 성립, R(a,b), a=b, R(b,a)

total이기 위해선 일단 reflexive여야 함(따라서 non-strict에서 totality가 필요할 때 total이용)

trichotomous는 irreflexive하면서 total한 느낌 살릴 때 이용(따라서 strict에서 totality가 필요할 때 trichotomous이용)

4. 

-용어정의

-R이 transitive란, R(a,b) and R(b,c)이면 R(a,c)이다.

transitive함이 ordering relation에서 기본적으로 필요

5. 

Order Relation에서는 고려해야할 것

(1) transitive반드시 필요, 

(2) reflexive, irreflexive 결정하면->symmetric(symmetric, antisymmetric, asymmetric)도 결정됨

(strict인 경우 irreflexive여야하고 그땐 (3) symmetric에서 결정안해도됨)

(non-strict인 경우 reflexive여야하고 그땐 (3) symmetric에서 antisymmetric여야함) 

(3) totality(total, trichotomous)결정

(strict인 경우 trichotomous결정)

(non-strict인 경우 total결정)

(이후 중복조건 제거, 예를 들면 total이면 reflexive됨)

*********이제부턴 다음이 유도가 쉬워짐**************

not total ordering relation

-non-strict partial ordering relation:transitive, reflexive, antisymmetric(모든 원소는 적어도 자기자신과는 relation되어야)

-strict partial ordering relation:transitive, irreflexive(모든 원소가 relation이지 않아도 됨)

total ordering relation

-non-strict total ordering relation:transitive, (reflexive), antisymmetric, total

-strict total ordering relation:transitive, irreflexive, trichotomous