Relations

오늘도 이산수학 공부하고 정리하기~
중요한 것 위주로 정리하자.
 

Relation
릴레이션은 Set 나오는 부분에서도 나왔지만 중요해서 그런지 따로 챕터가 있다.
어제 공부한 걸 정리할겸 되돌아보면 Relation은 두가지로 정의(표현)된다.
첫째는 R⊆A×B로써 표현되며 집합임을 나타내며,
둘째는 aRb 형태로 표현되며 infix binary boolean operator를 나타낸다. True or False 값을 가진다.

Function 또한 앞에서 정의하였지만 Relation의 관점에서 다룬다.
함수는 (a,b)∈f일때 a에 대해 b가 하나만 존재하는 특수한 릴레이션이다.  
따라서 위에서 언급했던 릴레이션의 두가지 표현방식으로 볼 때,
a f b와 같이 표현하는것도 가능하다.
이 또한 T/F값을 가질 것이다.


Properties
릴레이션의 성질을 나타내는 용어들이 있다.
모든 member a에 대해서 aRa가 True이면 이 릴레이션 R은 reflexive하다고 말한다. 모든 member에 대해 aRa가 False이면 irreflexive한 릴레이션이다. 당연한 것이지만 reflexive하면서 irreflexive할 수는 없고, 하나의 성질만 만족한다.

aRb이면 bRa일 경우 symmetric한 릴레이션이라고 하며,
aRb이면 bRa가 아니면 asymmetric한 릴레이션,
aRb이면서 bRa인 것은 a=b일때만 가능한 것을 antisymmetric이라고 한다.
asymmetric이 antisymmetric보다 엄격한 기준을 적용하고 있다.

그리고 aRb이고 bRc일 때, aRc를 만족하면 transitive 성질을 가지는 릴레이션이라 한다.

위 정의들은 이후에 equivalence relation, poset의 정의에 필요한 성질이므로 확실히 숙지해야 할 듯 하다.


Equivalence Relation
릴레이션 R에 대해서, R이 reflexive, symmetric, transitive 성질을 가질 때 릴레이션 R을 Equivalence Relation 이라고 한다.

정의만 나오고 특별한 의미가 나오지 않아 무슨 의미인가 곰곰히 생각해봤다.
reflexive하니까 자기 자신과의 관계가 있는 것은 알겠고,,
symmetric하니까 aRb bRa이고 따라서 aRa.. 그래서 결과적으로 자기 자신과의 관계를 나타내기 때문에
Equivalence Relation이라고 하는 것인가.. 추측해 본다.

 
Partial Ordering
릴레이션 R⊆A×A 에 대해서, R이 (ir)reflexive, antisymmetric, transitive이면 릴레이션 R은 (ir)reflexive partial order라고 한다.
그리고, (A,R)을 partially ordered set, 또는 poset이라고 부른다.

그리고 (A,≤) poset의 모든 원소가 comparable할 경우 A를 totally ordered set 또는 linearly ordered set 이라고 부르며
 ≤를 total order 혹은 linear order라고 부른다.

이것도 특별한 설명없이 그냥 정의만 던져주었기에 좀 당황스러웠다.
처음에 partially order의 정의를 보았을때는 이유를 알 수 없었지만, total order의 정의를 보고 나니 어느정도 이해가 된다.
partial order의 정의만으로는 완벽하게 순서가 있다고 말할 수 없는 듯 하다. 왜냐하면 ∞같은 경우는 비교 자체가 불가능 하기 때문이다. 그래서 comparable의 개념을 도입하여 total order를 만듬으로써 그거보다 약간 부족한 초기의 정의를 partial order로 한 것이 아닐지.. (이것도 추측이다)