Relation

Definition: Properties of relations

A relation $R$ on a set $A$ is a rule which returns true or false depending on if $x R y$ for some $x, y \in A$ .

Property Definition On a digraph
Reflexive $\forall x \in A, x R x$ Every vertex has a self-loop
Irreflexive $\forall x \in A, x \neq R x$ No vertex has a self-loop
Symmetric $\forall x, y \in A, x R y ⟹ y R x$ All paths are bi-directional
Antisymmetric $\forall x, y \in A, x R y \land y R x ⟹ x = y$ All paths are single directions or self-loops
Transitive $\forall x, y, z \in A, x R y \land y R z ⟹ x R z$ Paths make a $Δ$ pointing to one vertex

Property	Definition	On a digraph
Reflexive	$\forall x \in A, x R x$	Every vertex has a self-loop
Irreflexive	$\forall x \in A, x \neq R x$	No vertex has a self-loop
Symmetric	$\forall x, y \in A, x R y ⟹ y R x$	All paths are bi-directional
Antisymmetric	$\forall x, y \in A, x R y \land y R x ⟹ x = y$	All paths are single directions or self-loops
Transitive	$\forall x, y, z \in A, x R y \land y R z ⟹ x R z$	Paths make a $Δ$ pointing to one vertex

Definition: Equivalence relation, equivalence class

A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive. The equivalence class of an element $a \in A$ is the set $[a] = {x \in A ∣ x R a}$ , the set of all elements related to $A$ by $R$ .

Bonnie's notes

Relation

Graph View

Backlinks