11.11 Relation

Set theory.

Natural numbers. \(0 = \emptyset\) \(1 = \{\emptyset\}\) \(2 = \{1, \emptyset\}\) ...

Peano Axioms

We obtain a set \(\mathbb{N}\) such that:

• There is a number \(1 \in \mathbb{N}\).
• For every \(x \in \mathbb{N}\), there is another one called the successor, which is denoted \(x + 1\).
• If \(x + 1 = y + 1\), then \(x = y\).
• \(\nexists x \in \mathbb{N}\) such that \(x + 1 = 1\).

PMI: If \(S \subseteq \mathbb{N}\) satisfies \(1 \in S\) and \(x \in S \Rightarrow x + 1 \in S\), then \(S = \mathbb{N}\).

(These are called Peano Axioms)

How to define \(m + n\)?

• \(m + 1\) is already defined.
• Assume we’ve defined \(m + n\).

We define \(m + (n + 1) = (m + n) + 1\).

\(\Rightarrow m + n\) is defined \(\forall \, n\) by PMI.

‍

How to define \(\leq\).

We should be able to prove associativity.

Recall: PCI:
Let \(S \subseteq \mathbb{N}\) such that:

1. \(1 \in S\)

2. \(k \in S \Rightarrow k + 1 \in S \, \forall k \in \mathbb{N}\).

Recall: WOP (Well-Ordering Principle). Every subset \(S \subseteq \mathbb{N}\) has a first element. \(\exists s \in S\) such that \(t \geq s \, \forall t \in S\).

RELATIONS

• Related to functions.
• Related to order.

Relation

Let \(A, B\) be two sets. A relation is a subset \(R \subset A \times B\).

So \(R\) consists of some ordered pairs \((a, b)\).

Notation

• \(a \, R \, b\) if \((a, b) \in R\) (meaning \(a\) is related to \(b\)).
• \(a \cancel R \, b\) if \((a, b) \notin R\) (meaning \(a\) is not related to \(b\)).

Example

• \(R \subset \mathbb{Z} \times \mathbb{Z}\), \(R = \{ (m, n) : m - n \text{ is an even number} \}\).
• \(R\subset\mathbb{Z}\times\mathbb{Q}\), \(R = \{ (n, \frac{1}{n}) : n \in \mathbb{Z} \setminus \{0\} \}\).

More explanation

Relations are generalizations of functions.

They can be represented as we represent functions.

Example

• ​

\(R=\{(a,1),(a,2),(b,2),(b,3),(c,3),(e,5)\}\subset A\times B\)

• We can use tables.​

​ * When \(A = B\), we can also use graphs.

\(R\subset A\times A\).

\(R = \{ (a, b), (b, b), (b, c), (c, b), (b, e), (g, e), (f, f) \}\)

​

Domain and Range

Def: \(R\subset A\times B\).

\(\operatorname{Dom}(R) = \{ a \in A : \exists b \in B \text{ such that } a R b \}\) (domain)

\(\operatorname{Range}(R)=\{b\in B:\exists a\in A\text{ such that }aRb\}\) (range)

Example

In Example 1,

\(\operatorname{Dom}(R) = \{ a, b, c, e \} \subseteq A\) \(\operatorname{Rg}(R) = \{ 1, 2, 3, 5 \} \subseteq B\)

Composition

Def: \(R\subset A\times B\), \(S\subset B\times C\).

\(S\circ R=\{(a,c)\in A\times C:\exists b\in B\text{ such that }aRb\text{ and }bSc\}\subset A\times C\).

\(\operatorname{Dom}(S\circ R)=\left\lbrace a_1,a_2\right\rbrace\), \(\operatorname{Rg}(S\circ R)=\left\lbrace c_1,c_2\right\rbrace\)​

Example

​

​

Identity relation

\(A\) is a set. \(I_{A}=\{(a,a):a\in A\}\subset A\times A\rightarrow\) identity relation.

Obs: \(a I_A b \iff a = b\).

Inverse of a relation

\(R\subset A\times B\)

\(R^{-1}=\{(b,a)\in B\times A:aRb\}\subset B\times A\)

So \(bR^{-1}a\;\iff\;aRb\).

Example

• In Example 1,

\(R^{-1} = \{ (1, a), (2, a), (2, b), (3, b), (3, c), (5, c) \}\) * Let \(R = \{ (x, x^2) : x \in \mathbb{R} \}\), where \(A = B = \mathbb{R}\).

​

The inverse relation \(R^{-1} = \{ (x^2, x) : x \in \mathbb{R} \}\).

​

(Theorem) Properties

Let \(R \subset A \times B\).

1. \(\text{Dom } R^{-1} = \text{Rg } R\).

   Proof

   \(R^{-1}\subset B\times A\)​

   \(\operatorname{Dom}(R^{-1})=\{b\in B:\exists a\in A\text{ such that }bR^{-1}a\}=\{b\in B:\exists a\in A\text{ such that }aRb\}=\operatorname{Rg}(R)\)​

2. \(\text{Rg } R^{-1} = \text{Dom } R\).

   Proof

   \(R^{-1}\subset B\times A\)

   \(\text{Rg }R^{-1}=\left\lbrace a\in A:\exists b\in B\text{ such that }bR^{-1}a\right\rbrace=\left\lbrace a\in A:\exists b\in B\text{ such that }aRb\right\rbrace=\text{Dom}R\)​

3. \(\left(R^{-1}\right)^{-1} = R\).

   Proof

   \(R^{-1}\subset B\times A\)

   \(\left(R^{-1}\right)^{-1}=\left(\left\lbrace\left(b,a\right)\in B\times A:bR^{-1}a\right\rbrace\right)^{-1}=\left\lbrace\left(a,b\right)\in A\times B:aR^{}b\right\rbrace=R\)​

Theorem

The composition of relations is associative.

1. \(T \circ (S \circ R) = (T \circ S) \circ R\) for \(R \subseteq A \times B\), \(S \subseteq B \times C\), \(T \subseteq C \times D\).

   Proof

   \(T\circ(S\circ R)=T\circ\left\lbrace\left(a,c\right)\in A\times C:\exists b\in B,aRb,bSc\right\rbrace=\left\lbrace\left(a,d\right)\in A\times D:\exists b\in B,c\in C,aRb,bSc,cTd\right\rbrace\)​

   \(=\left\lbrace\left(a,d\right)\in A\times D:\exists c\in C,aRb,bSc,cTd\right\rbrace=\left\lbrace\left(a,d\right)\in A\times D:\exists c\in C,bSc,cTd\right\rbrace\circ R=\left(T\circ S\right)\circ R\)​

2. \(I_B \circ R = R\) for \(R \subseteq A \times B\).

3. \(R \circ I_A = R\) for \(R \subseteq A \times B\).

4. \((S \circ R)^{-1} = R^{-1} \circ S^{-1}\) for \(R \subseteq A \times B\), \(S \subseteq B \times C\).

Equivalence relation

Consider relations \(R \subseteq A \times A\). We say that \(R\) is:

• Reflexive if \(aRa \; \forall a \in A\).
• Symmetric if \(aRb \Leftrightarrow bRa\).
• Transitive if \(aRb \land bRc \Rightarrow aRc\).

A relation \(R \subseteq A \times A\) is called an equivalence relation if it is reflexive, symmetric, and transitive.

Example

1. \(=\) is an equivalence relation.

2. \(\leq\) on \(\mathbb{R}\):

   • Reflexive ✓: \(x \leq x\).
   • Symmetric ✗: \(1 \leq 2\) but \(2 \nleq 1\).
   • Transitive ✓: \(x \leq y\) and \(y \leq z \Rightarrow x \leq z\).

3. \(<\) on \(\mathbb{R}\):

   • Reflexive ✗: \(x < x\) is not true.
   • Symmetric ✗: \(1 < 2\) but \(2 \nless 1\).
   • Transitive ✓: \(x < y\) and \(y < z \Rightarrow x < z\).

4. \(\mid\) on \(\mathbb{Z}\):

   \(a \mid b\) if \(\exists c\) such that \(b = a \cdot c\).

   • Reflexive ✓: \(a \mid a\) because \(a = a \cdot 1\).
   • Symmetric ✗: \(1 \mid 2\) but \(2 \nmid 1\).
   • Transitive ✓: If \(a \mid b\) and \(b \mid c\), then \(\exists d_1, d_2\) such that \(b = a \cdot d_1\) and \(c = b \cdot d_2\). Then \(c = b \cdot d_2 = a \cdot (d_1 d_2)\), so \(a \mid c\).

   Recall:

   • \(a\mid b \wedge a\mid c\Rightarrow a\mid b\pm c\)​
   • \(a\mid b\Rightarrow a\mid kb,\forall k\)​

5. \(\equiv_m\) on \(\mathbb{Z}\):

   \(a \equiv_m b\) means \(m \mid (a - b)\). \(a\) is congruent to \(b\) modulo \(m\).

   Example: \(m = 7\).

   • \(2 \equiv_7 9\) since \(7 \mid (9 - 2)=7\).
   • \(0 \equiv_7 7\) since \(7 \mid (7 - 0)=7\).
   • \(3 \equiv_7 -4\) since \(7 \mid (3 - (-4)) = 7\).

   Another notation: \(a\equiv b(m)\)​

   \(\equiv_m\)

   • Reflexive ✓: \(m \mid (a - a) = 0 \Rightarrow a \equiv_m a\).
   • Symmetric ✓: If \(a \equiv_m b \Rightarrow m \mid (b - a)\). Since \(m \mid (a - b)\), it follows that \(b \equiv_m a\).
   • Transitive ✓: If \(a \equiv_m b\) and \(b \equiv_m c\), then \(m \mid (b - a)\) and \(m \mid (c - b)\). So \(m \mid [(b - a) + (c - b)] = (c - a)\), which implies \(a \equiv_m c\).

   Therefore, \(\equiv_m\) is an equivalence relation.

Remarks

1. \(a\equiv_{m}a+km\) for some integer \(k\).

2. If \(0 \leq r, r' \leq m - 1\) and \(r \equiv_m r'\), then \(r = r'\).

3. If \(a \equiv_m a'\) and \(b \equiv_m b'\), then:

   • \(a + b \equiv_m a' + b'\)
   • \(a \cdot b \equiv_m a' \cdot b'\)

   Proof for multiplication:
   \(a b - a' b' = a b - a' b + a' b - a' b' = (a - a') b + a' (b - b')\) Since \(a \equiv_m a'\), we have \(m \mid (a - a')\), and since \(b \equiv_m b'\), we have \(m \mid (b - b')\), so \(m \mid (a b - a' b')\).

4. \(a \equiv_m b \Rightarrow a^n \equiv_m b^n\) for all \(n \in \mathbb{N}\) (proved by induction).

Example

\(2024^{2024}\equiv_9\text{ small number}\), where \(m = 9\).

• \(10 \equiv_9 1\)
• \(10^2 \equiv_9 1^2\)
• \(20 \equiv_9 20\)
• \(2000 \equiv_9 20 \equiv_9 2\)
• \(24 \equiv_9 24\)

\(2024 \equiv_9 26 \equiv_9 -1\)

Therefore:

• \((2024)^{2024} \equiv_9 (-1)^{2024}\)
• Since \(2024\) is even, \((2024)^{2024} \equiv_9 1\).

‍

‍