- reflexive : A집합에 속하는 모든 a에 대해 (a,a)가 어떤 Relation에 포함되면 그 Relation이 reflexive하다고 한다. 그래프에서 모든 Vertex가 자기 자신을 가리키는 Edge를 가지고 있는 걸 상상.
- symmetric : (a,b)가 어떤 Relation R에 포함되고 (b,a)도 포함되면 그 Relation은 symmetric하다고 한다. 그래프에서 두 Vetex가 서로를 향하는 Edge를 가지고 있는 것.
- antisymmetric : (a,b)와 (b,a)가 어떤 Relation R에 포함되면 a와 b는 같을 경우 이 관계를 antisymmetric이라고 한다. a,b가 서로 다른데 R이 (a,b), (b,a)를 포함하는 경우 antisymmetric이 아님. 그래프에서 두 Vertex를 서로 가리키는 Edge가 없는 것.
- transitive : (a,b) , (b,c)가 관계 R에 포함되고 (a,c)도 포함될때 이 관계를 transitive. 그래프에서 a에서 b가는 경로가 있고 ,b에서 c가는 경로가 있고, c에서 a가는 경로가 있을 때.
- equivalence relation : reflexive, symmetric, and transitive 한 관계.
- R이 equivalence relation일 때, aRb이면 a와 b가 equivalent하다고 한다.
- [a]R 은 a와 equivalent한 집합 A의 모든 요소들의 집합.
- partial ordering : reflexive, antisymmetric, and transitive한 관계.
- poset(S,R) : a set S 와 partial ordering R
- comparable : poset(A,≤*) 의 a,b에서 a≤*b 또는 b≤*a면 a,b는 comparable 하다고 한다. 예) poset(A,|) 에서 3|9은 comparable 이지만 5|7은 5|7도 7|5도 안되기 때문에 comparable이 아니다. (incomparable)
- total ordering : partial ordering에서 모든 요소의 쌍이 comparable일 경우
- well-ordered set : poset(S,≤*)이 total order고 공집합이 아닌 모든 S의 부분집합에서는 최소값을 갖는 set. 예를 들어 양의 정수의 집합은 ≤ 관계에 대해 well-ordered set이지만 S가 정수의 집합일 경우에는 total order이지만 최소값이 없기 때문에 well-ordered set이 아님.
- Hasse diagram : poset의 그래픽으로 표현한 것인데 loops 없애고, transitive로 유도되는 edges 없애고, vertex들의 위치를 맞춤으로써 방향 표시도 없앤 그래프.
- maximal element : poset에서 다른 요소들보다 작지 않은 요소. a<*b 인 b가 없을 때 a.
- minimal element : poset에서 다른 요소들보다 크지 않은 요소. b<*a인 b가 없을 때 a.
- greatest element : poset에서 모든 요소들보다 같거나 큰 요소 .
- least element : poset에서 모든 요소들보다 작거나 같은 요소
- upper bound of a set: poset(S,≤*)의 subset A 에서 S의 원소 u가 A의 모든 원소보다 크거나 같을 때 u는 upper bound
- lower bound of a set: poset(S,≤*)의 subset A 에서 S의 원소 u가 A의 모든 원소보다 작거나 같을 때 u는 lower bound
- least upper bound of a set: 가장 작은 upper bound
- greatest lower bound of a set: 가장 큰 lower bound
- lattice : 모든 두개의 원소가 a greatest lower bound와 a lowest upper bound를 가지는 an partially ordered set.
- compatible total ordering for a partial ordering : partial ordering을 포함하는 total ordering
- topological sort : partial ordering을 total ordering으로 만든 결과. ex) 선수강 트리
참고사이트
Well-ordered set
http://nicetoseeu.egloos.com/2613505
well-ordered induction
