Binary Relation R, from set A to B : subset of AxB

Binary Relation R on set A : subset of AxA

• number of relations AxA: n^2 elements subset of AxA: 2^n^2 : number of relations

Reflexive Relations R is reflexive ↔ (a,a) ∈ R for all a ∈A *공집합에서의 관계는 reflexive

Symmetric Relations R is symmetric ↔ (a,b) ∈ R , (b,a) ∈ R for all a,b ∀x∀y[(x,y) ∈ R → (y,x) ∈R)]

Antisymmetric Relations R is antisymmetric ↔ (a,b) ∈ R and (b,a) ∈ R → a=b ∀x∀y [ (x,y) ∈ R ∧ (y,x) ∈ R → x=y ]

Transitive Relations ∀x∀y∀z [ (x,y) ∈ R ∧ (y,z) ∈ R → (x,z) ∈ R ]

ex)

• R={(a,b)|a≤b} transitive, antisymmetric, reflexive
• R={(a,b)|a=b} symmetric, reflexive

Composition 합성 R1: A to B, R2: B to C composition of R2 with R1: A to C (x,y): R1, (y,z): R2, (x,z): R2 * R1

Power R^1 = R R^n+1 = R^n ◦ R

• R is transitive ↔ R^n ⊆ R

zero-one matrix: if (i,j) ∈R Mij = 1 else 0

Directed Graph if (i,j) ∈R , (i,j) is edge

• Reflexivity all nodes have loop

• Symmetry (x,y) is edge ↔ (y,x)

• Antisymmetry if (x,y) is edge, (y,x) is not edge

• Transivity (x,y) and (y,z) are edges → (x,z) is edge

  • graph 보고 판단 가능해야 함.

• Power R^n의 (x,y): x에서 y의 path 존재시에만 존재

  

• Paths R on set A에서, length n의 a to b path ↔ (a,b) ∈ R^n

• connectivity relation R* : consists (a,b) s.t has path from a to b R* = UNION (n=1 n=∞) R^n
  • in terms of zero-one matrix: M_R* = M_R ∨ M_R^2 ∨… M_R^n
• transitive closure of R is R*
  • pf)
  • i) R* is transitive
    • R* contains R^1
    • if(a,b) in R*, (b,c) in R* then path(a,b), path(b,c) exist in R
    • obtain path a to c: a to b to c
    • therefore (a,c) in R*: transitive
  • ii) R* ⊆ S, S is transitive relation contains R
    • sps S is transitive relation: S^n ⊆ S
    • S* = S^k union, S^k ⊆ S, therefore S* ⊆ S
    • if R ⊆ S: R⊆S (any path in R is also path in S)
    • R* ⊆ S* ⊆ S any translative relation that contains R must contain R* hence R* is transitive closure of R ■

R={(a,b)|a ≡ b (mod m))}

• reflexivity: a≡a (mod m)(trivial)
• symmetry: suppose a≡b (mod m): a-b is div by m, therefore b-a is divisible so b≡a (mod m)
• Transivity suppose a≡b, b≡c (mod m) a-b = km, b-c = lm, a-c = (k+l)m: a ≡ c (mod m) Therefore, Equivalence relation.

Equivalence Class for equi relation R on a [a]_R = {s|(a,s)∈R} (동치인거 집합) if b ∈ [a]_R: b is representative(표상) of this equi class

• aRb == [a]=[b] == [a]∩[b] ≠ ∅
  • pf) i→ii
    • assume aRb, c in [a]: aRc
    • bRa → aRc
    • c in [b]: [a]⊆[b] and vice versa →[a]=[b]
  • pf) ii→iii [a]=[b]: [a]∩[b] ≠ ∅ (trivial)
  • pf) iii→i c in [a] and c in [b] exists → aRc, bRc cRb(symmetry): aRb