Relation

Abstract

---

• Basically a Subset of Cartesian Product or Order n-tuples filtered by some conditions which define the relation among the elements from the given Set

Real-world Implication

Commonly used in Database, the columns are the different sets, the Cartesian Product of the columns are all the potential relation aka all the rows that can be stored inside the database. Each row is a actual Order n-tuples inside the relation

Binary Relation

• Let $x\in A,y\in B$, we say $xRy\leftrightarrow (x,y)\in R$

Inversion of Relation

• Basically reverse the order of elements of the Order n-tuples

$$R^{-1}=\{(y,x)\in B\times A:(x,y)\in R\}$$

Composition of Relation

---

• The composite of 2 Relation - R and S
• Given Set A, B, C, $R\subseteq A\times B$ and $S\subseteq B\times C$

$$\forall x\in A,\forall z\in C(xS\circ Rz\leftrightarrow (\exists y\in B(xRy\cap ySz)))$$

• For all $a$ in $A$ and all $z$ in $C$, the below 2 conditions must be fulfilled in order to have composition of relation $S\circ R$
  1. If there is a ‘path’ from $x$ to $z$, there must have a path from $x$ to $y$ AND $y$ to $z$ , the $S\circ R\to (\exists y\in B(xRy\cap ySz))$ part
  2. If there is a ‘path’ from $x$ to $y$ and $y$ to $z$, there must has a path from $x$ to $z$, the $S\circ R\leftarrow (\exists y\in B(xRy\cap ySz))$ part

Composition is Associative

• Let $A,B,C,D$ be Set
• The we have 3 Relation:
  • $R\subseteq A\times B$
  • $S\subseteq B\times C$
  • $T\subseteq C\times D$

$$T\circ (S\circ R)=(T\circ S)\circ R=T\circ S\circ R$$

Inverse of Composition

• Let $A,B,C$ be Set
• The we have 3 Relation:
  • $R\subseteq A\times B$
  • $S\subseteq B\times C$

$$(S\circ R{)}^{-1}=R^{-1}\circ S^{-1}$$

Relation Properties

---

• Not properties of the elements of the Set!

Reflexive

• Every element in the given Set must be related to itself

$$\forall x\in A(xRx)$$

Symmetric

• If an element is related to another element, the another element must be related to this element too

$$\forall x,y\in A(xRy\to yRx)$$

Transitive

• If an element is related to another element, and that element is related to a third element. Then this must be related to the third element

$$\forall x,y,z\in A(xRy\cap yRz\to xRz)$$

Equivalence Relation

• Let $A$ be a Set and $R$ be a Relation on $A$
• $R$ is equivalence relation iff $R$ is Reflexive, Symmetric and Transitive

Equivalence Class

• Basically same as the component of a Partition or elements of Equivalence Relation
• Can be represented with $[a{]}_{relation}$, it means the Equivalence Class contains element $a$
• $[a{]}_{relation}$ and $[b{]}_{relation}$ are the same iff $b$ is in the same equivalence class as $a$

Theorem

---

Lemma Rel.1

• Equivalence Relation
• Let ~ be an Equivalence Class on Set $A$ and $x,y\in A$
  1. $x$ is equivalent related to $y$
  2. The equivalent class $x$ is in is same as the equivalent class $y$ is in
  3. $[x]\cap [y]\ne \varnothing$

Theorem 8.3.4

• The Partition induced by Equivalence Relation
• If $R$ is equivalence relation on Set $A$, then the distinct Equivalence Class form a partition of $A$

Terminologies

---

Arrow Diagram

• Visualize Relation
• Usually used when there is more than one Set involve in the relation

Domain

• Basically the Set of elements of the left hand Set that is involved in the Relation

$$\{a\in A:aRbforsomeb\in B\}$$

Co-domain

• The whole Set at the right hand side

Range

• Basically the Set of elements of the right hand set that is involved in the Relation

$$\{b\in B:aRbforsomea\in A\}$$

N-ary Relation

• A Relation involving 2 Set is called binary relation, also known as 2-ary
• Ternary is 3-ary
• Quaternary is 4-ary

Congruence Modulo 3

• Congruence Modulo 3 means the Integer (整数) is divisible by 3

$$\forall x,y\in \mathbb{Z}(xRy\leftrightarrow 3|(x-y))$$

• A Relation that is Reflexive Symmetric & Transitive

Transitive Closure of Relation

• The Relation obtained by adding the least number of Ordered Pair to ensure Transitive
• Represented with $R^t$
• Following 3 properties:
  1. $R^t$ is transitive
  2. $R\subseteq R^t$
  3. $R^t\subseteq S$, where $S$ is any other transitive relation that contains $R$