Binary Relations

Binary Relations: Denote a relation over a set $A$ be $R$ , if the relation is binary relation, then $\forall a, b \in A$

if $a$ relates $b$ under relation $R$ , denote as $a R b$
else $a \neq R b$

Some Property of Binary Relations $R$ over a set $A$ may have:

irreflexive: $\forall a \in A, a \neq R a$
reflexive: $\forall a \in A, a R a$
asymmetric: $\forall a, b \in A, a R b ⟹ b \neq R a$
symmetric: $\forall a, b \in A, a R b ⟹ b R a$
antisymmetric: $\forall a, b \in A (a R b \land b R a ⟹ a = b)$
transitive: $\forall a, b, c \in A, a R b \land b R c ⟹ a R c$
connected: $\forall a, b \in A, a \neq = b ⟹ a R b \lor b R a$
cyclic: $\forall a, b, c \in A, a R b \land b R c ⟹ c R a$
irreflexive $\land$ transitive $⟹$ asymmetric

Strict (partial) Order: a binary relation $R$ over a set $A$ is irreflexive, asymmetric(not necessary) and transitive

e.g.: Dependencies, Little-o, $\subset$ , etc.

Strict Total Order: a binary relation $R$ over a set $A$ is strict order and connected

e.g.: Dictionary Order, etc.

Hasse Diagram: $\forall R, R$ is strict order over a set $A$ , $\forall a, b \in A$ , Hasse diagram has a edge $a \to b ⟺ a R b \land ∄ c, a R c \land c R b$

Notice: it (binary relation) is very different with the binary operation of group theory.

Partial Order: a binary relation $R$ over a set $A$ is reflexive, antisymmetric and transitive

Total Order: a binary relation $R$ over a set $A$ is partial order and connected.

Equivalence Relation: a binary relation $R$ over a set $A$ is reflexive, symmetric and transitive

e.g. $=$ , modular $(\equiv_{n}) : a = b (m o d n), a, b, n \in N$
cyclic and reflexive $R ⟹$ $R$ is equivalence relation

Equivalence Class: Let $R$ be Equivalence Relation on a set $A$ , $\forall a \in A$ , the Equivalence Class of $a$ respect to $R$ , denoted $[a]_{R}$ has property $[a]_{R} = {b \in A : a R b}$

$\forall a, b \in A, [a]_{R} = [b]_{R} ⟺ a R b$ (lemma)

Partition: let $A$ be any set, and $X$ be a collection of subsets of $A$ . $\forall a \in A, \exists S \in X, a \in S ⟹ X$ is a partition of $A$

Let $R$ be an equivalence relation on a set $A$ . The set of Equivalence Classes is a partition of $A$ .
Or we can say $\forall a \in A, \exists [a]_{R}, a \in [a]_{R}, [a]_{R}$ is unique

Yorafa's Blog

Explorer

Binary Relations

Binary Relations

Graph View