Definition

Relation (between two sets)

Let $A$ and $B$ be sets, a binary relation from $A$ to $B$ is a subset of $A \times B$ . Given an ordered pair $(x, y)$ in $A \times B$ , $x$ is related to $y$ by $R$ , or $x$ is $R$ -related to $y$ .

Relation on a Set

A relation on set $A$ is a relation from $A$ to $A$ It is a subset of $A \times A$ ( $A^{2}$ ) Note: the arrow diagram of such a relation can be modified so that it becomes a directed graph

Notation

$x$ is related to $y$ by $R$ $x R y$ means $(x, y) \in R$ $x \neq R y$ means $(x, y) \neq \in R$

Domain, Co-domain, Range

Let $A$ and $B$ be sets and $R$ be a relation from $A$ to $B$

Domain

$Do m (R)$ is the set ${a \in A : a R b for some b \in B}$

Elements in $B$ that are “part of” $R$

Co-domain

$coDo m (R)$ is the set $B$

Range

$R an g e (R)$ is the set ${b \in B : a R b for some a \in A}$

Elements in A that are “part of” $R$

Inverse Relation

If $R$ is a relation from $A$ to $B$ , then a relation $R^{- 1}$ from $B$ to $A$ can be defined by interchanging the elements of all the ordered pairs of $R$ Either $R^{- 1} = {(y, x) \in B \times A : (x, y) \in R}$ Or $\forall x \in A, \forall y \in B ((y, x) \in R^{- 1} \Leftrightarrow (x, y) \in R)$

Composition of Relations

Relations can be composed: Set Relation Composition

N-ary Relations

A $n$ -ary relation involves $n$ sets. Given $n$ sets $A_{1}, A_{2}, \dots, A_{n}$ , an $n$ -are relation $R$ on $A_{1} \times A_{2} \times \dots \times A_{n}$ is a subset of $A_{1} \times A_{2} \times \dots \times A_{n}$ 2-ary, 3-ary and 4-ary relations are called binary, ternary and quatenary relations respectively

Diagrams

Set Relation Diagrams

Reflexivity, Symmetry and Transivity

Properties of Set Relations

Examples

1: Relation

Let $A = {0, 1, 2}$ and $B = {1, 2, 3}$ Suppose we define the relation R such that $x R y$ iff $x < y$ Then, $0 R 1, 0 R 2, 0 R 3, 1 R 2, 1 R 3, 2 R 3$ but $1 \neq R 1, 2 \neq R 1, 2 \neq R 2$

2: Defining Relations

Let $A = {1, 2}$ and $B = {1, 2, 3}$ Relation $R$ is defined from $A$ to $B$ as: $\forall (x, y) \in A \times B ((x, y) \in R \Leftrightarrow \frac{x - y}{2} \in Z)$ State explicitly which ordered pairs are in $A \times B$ and which are in $R$ $A \times B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}$ $R = {(1, 1), (1, 3), (2, 2)}$

3: Domain, Co-domain, Range

Let $A = {1, 2, 3}$ and $B = {2, 4, 9}$ , and define a relation $R$ from $A$ to $B$ as follows: $\forall (x, y) \in A \times B, (x, y) \in R \Leftrightarrow x^{2} = y$ $Do m (R) = {2, 3}$ $coDo m (R) = {2, 4, 9}$ $R an g e (R) = {4, 9}$

🪴 Notes Hehe

Explorer

Set Relations