Relations -Basic Notations the identity on S Ids {(x,x)|x∈S) the domain of p dom(p) f{x1y.(x,y)∈p} the range of p ran(p)de fyx(x,y)ep} composition of p and p pop e {(x,z）I3y.(x,y)∈pA(y,z)∈p} inverse of p p-1 {(y,x)I (x,y)Ep} 13/40
Relations – Basic Notations the identity on S IdS def = {(x, x) | x ∈ S} the domain of ρ dom(ρ) def = {x | ∃y.(x, y) ∈ ρ} the range of ρ ran(ρ) def = {y | ∃x.(x, y) ∈ ρ} composition of ρ and ρ 0 ρ 0 ◦ ρ def = {(x, z) | ∃y.(x, y) ∈ ρ ∧ (y, z) ∈ ρ 0} inverse of ρ ρ−1 def = {(y, x) | (x, y) ∈ ρ} 13 / 40
Relations-Properties and Examples (p3op2)op1=p3o(p2o P1) polds Cp2ldTop dom(Ids)=S=ran(Ids) IdTo lds =ldTns Ids-1=Ids (p-1)-1=p (p2op1)-1=p1-1op2-1 po0=0=0op 1dg=0=0-1 dom(p)=0←→p=0 14/40
Relations – Properties and Examples (ρ3 ◦ ρ2) ◦ ρ1 = ρ3 ◦ (ρ2 ◦ ρ1) ρ ◦ IdS ⊆ ρ ⊇ IdT ◦ ρ dom(IdS ) = S = ran(IdS ) IdT ◦ IdS = IdT∩S IdS −1 = IdS ρ −1 −1 = ρ (ρ2 ◦ ρ1) −1 = ρ1 −1 ◦ ρ2 −1 ρ ◦ ∅ = ∅ = ∅ ◦ ρ Id∅ = ∅ = ∅ −1 dom(ρ) = ∅ ⇐⇒ ρ = ∅ 14 / 40
Relations-Properties and Examples <二≤ <Uldw=≤ ≤n≥=ldw <n≥=0 <0≤=< ≤o≤=≤ ≥=≤-1 15/40
Relations – Properties and Examples < ⊆ ≤ < ∪ IdN = ≤ ≤ ∩ ≥ = IdN < ∩ ≥ = ∅ < ◦ ≤ = < ≤ ◦ ≤ = ≤ ≥ = ≤−1 15 / 40