Relation Properties (Reflexive, Symmetric, Transitive)

Math for CS · Axiom Academy

Reflexive, symmetric, antisymmetric, transitive — and why they matter A relation R on a set A can have any combination of four fundamental properties. These properties determine the structure and behavior of the relation. Throughout this lesson, let R be a relation on set A . In a digraph: Every node has a self-loop. In a matrix: Every diagonal entry is 1. on — reflexive ( a a for all a ) = on any set — reflexive ( a = a ) In a digraph: Every edge goes both ways (or you can replace directed edges with undirected edges). In a matrix: The matrix is symmetric: M_ ij = M_ ji . = on any set — symmetric (if a = b then b = a ) — NOT symmetric ( 3 5 but 5 3 ) Warning: Antisymmetric is NOT the opposite of symmetric. A relation can be both, neither, or one without the other. on — antisymmetric (if a b and b a , then a = b ) on sets — antisymmetric (if A B and B A , then A = B ) Divides ( ) on ^+ — antisymmetric "is a sibling of" — NOT antisymmetric In a digraph: Between any two distinct nodes, there is at most one directed edge (no two-way arrows between different nodes). In a digraph: Whenever there is a path of length 2 from a to c through b , there must also be a direct edge from a to c . — transitive (if a b and b c , then a c ) "is an ancestor of" — transitive "is a parent of" — NOT transitive (your parent's parent is not your parent) Given A = \ 1,2,3\ and R = \ (1,1),(1,2),(2,1),(2,2),(3,3)\ :

This is the written version of the interactive lesson above. See the full Math for CS course.