Binary Relations

Subjects: Set Theory
Links: Cartesian Product

A set $R$ is a binary relation if for any $z \in R$ , then there exists $x$ and $y$ such that $z = (x, y)$ . It is usually said that $x$ is in relation $R$ with $y$ iff $x R y$ , which is the same as $(x, y) \in R$ .

The domain of $R$ is the set of all $x$ such that there’s a $y$ that $x R y$ , $dom R = {x ∣ \exists y [x R y]}$

The range of $R$ is the set of all $y$ such that there’s an $x$ that $x R y$ , $ran R = {y ∣ \exists x [x R y]}$

The field of $R$ is just $dom R \cup ran R = field R$

If $field R \subseteq X$ , then $R$ is a relation in $X$ , or that is a relation between elements of $X$ . $R$ is a relation in $X$ iff $R \subseteq X \times X$ .

The image of $A$ under $R$ , is the set of all $y$ from the $ran R$ related to some element in $A$ , denoted as $R [A]$ ,

R [A] = {y \in ran R ∣ \exists x \in A [x R y]}

The inverse image of $B$ under $R$ is the set of all $x \in dom R$ , related to some element in $B$ , denoted as $R^{- 1} [B]$ ,

R^{- 1} [B] = {x \in dom R ∣ \exists y \in B [x R y]}

Let $R$ be a binary relation, the inverse of $R$ is the set

R^{- 1} = {(x, y) ∣ \exists x, y [y R x]}

The inverse image of $B$ under $R$ is equal to the image $B$ under $R^{- 1}$ .

Let $R$ and $S$ be binary relations. The composition of $R$ and $S$ is the relation

S \circ R = {(x, z) ∣ \exists y [x R y \land y S z]

Some properties about the image and inverse image of $R$ :
- $A_{1} \subseteq A_{2} ⟹ R [A_{1}] \subseteq R [A_{2}]$
- $R [A \cup B] = R [A] \cup R [B]$
- $R [A \cap B] \subseteq R [A] \cap R [B]$
- $R [A ∖ B] \supseteq R [A] ∖ R [B]$
- $A_{1} \subseteq A_{2} ⟹ R^{- 1} [A_{1}] \subseteq R^{- 1} [A_{2}]$
- $R^{- 1} [A \cup B] = R^{- 1} [A] \cup R^{- 1} [B]$
- $R^{- 1} [A \cap B] \subseteq R^{- 1} [A] \cap R^{- 1} [B]$
- $R^{- 1} [A ∖ B] \supseteq R^{- 1} [A] ∖ R^{- 1} [B]$
Some properties about binary relations on $A$ may have are, let $R$ be a binary relation on $A$ :
- $R$ is reflexive if for any $a \in A$ , then $a R a$ .
- $R$ is irreflexive if for any $a \in A$ , then $(a, a) \notin R$
- $R$ is symmetric if for any $a, b \in A$ , $a R b$ implies $b R a$ .
- $R$ is antisymmetric if for any $a, b \in A$ , $a R b$ and $b R a$ implies $a = b$ .
- $R$ is asymmetric if for any $a, b \in A$ , $a R b$ implies $(b, a) \notin R$ .
- $R$ is transitive if for any $a, b, c \in A$ , $a R b$ and $b R c$ implies $a R c$ .
- $R$ is connected if for any $a, b \in A$ , and $a \neq b$ , then $a R b$ or $b R a$ .
- $R$ is strongly connected if for any $a, b \in A$ , then $a R b$ or $b R a$ .

Cofinal and Coinitial Subsets