(KR9.1,9.2,9.5,9.6)

Relations

A relation represents an association of objects of one set with objects of another set

• example

Binary Relations

Definition: a binary relation **$R$ from a set $A$ **to a set $B$ **is a subset $R \subseteq A \times B$

• relations are more general than functions
• a function is a relation where exactly one element of $B$ **is related to each element of $A$
• example

Binary Relation on a Set

Definition: a binary relation $R$ **on a set $A$ is a subset of $A \times A$ or a relation from $A$ to $A$

• example
• for every set $B$ with $n$ elements, there are $2^{n^2}$ subsets and/or relations

Reflexive Relations

Definition: $R$ is reflexive if and only if $(a,a) \in R$ for every element $a \in A$

• examples

Symmetric Relations

Definition: $R$ is symmetric if and only if $(b,a) \in R$ whenever $(a,b) \in R$ for all $a, b \in A$

• examples

Antisymmetric Relations