離散數學(7)

第七章 Relations: The Second Tine Around

A relation R on a set A is called reflexive(反身性) if for all x ε A (x,x) ε R

Relation R on set A is called symmetric(對稱性) if(x,y) εR → (y,x) ε R for
all x,y ε A

For a set A, a relation R on A is called transitive of, for all x,y,z ε A, (x,y),(y,z) ε R → (x,z) ε R.(So if x “is related to” y, and y “is related to” z, we want x “related to” z, withy playing the role of “intermediary”.

Given a relation R on a set A, R is called antisymmetric if for all a,b εA ,(aRb and bRa) → a=b

A relation R on a set A is called a partial order, or a partial ordering relation, if R is reflexive, antisymmetric, and transitive.

If A, B, and C are sets with R1cAxB and R2c BxC, then the composite relation R1◦R2 is a relation from A to C defined by  R1◦R2={(x,z)|x εA,
z ε C, and thereexists y ε B with (x,y) εR (y,z) εR2}