---
tags: NTNU,CSIE,必修,Discrete Mathematics
title: Relation
description:
---

{%hackmd @NTNUCSIE112/S1VbPN1HU %}

# Relation
> When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connection is called a relation.
> [name=Angustus De Morgan][color=red]
## Function
> A function $f: S\to T$ is a "specific" mapping between elements of S and T, in such a way that every element of S corresponds to "an" element of T.

> $S =$ domain(定義域) of $f$
$T =$ codomain

- e.g.
- $f: \mathbb{R} \to \mathbb{R},\ x \mapsto x^2 (f(x) = x^2)$
- given $S = \{1,2,3\}$, $T = \{a,b,c,d\}$, define $f: S\to T,\ 1 \mapsto a,\ 2 \mapsto a,\ 3 \mapsto a$

- Functions
- 1-1 function, for $x,y \in S, x\neq y, f(x)\neq f(y)$
- onto function, $\forall y\in T,$there exist x \in S such that f(x) = y$

## Cardinality (size) of a set(集合的元素個數)

> The number of elements in a set S is called the size/cardinality of S, denoted by |s|.

- e.g. $S = \{1,2,3,4\} \rightarrow |S| = 4$
$Q:$ What is the cardinality of $\mathbb{R}$? (Ans. |$\mathbb{R}$| = $\infty$?)
$Q:$ what is the cardinality of $\mathbb{N}$? $\mathbb{Z}$? $\mathbb{Q}$? (Ans. $\infty$?)
> Cantor (186x -- double check --)
- Consider $\mathbb{N}$ and $\mathbb{Z}$, -- $\mathbb{N} \subseteq \mathbb{Z}, -1\in \mathbb{Z} - \mathbb{N} \rightarrow |\mathbb{N}|< |\mathbb{Z}|$?

$Q:$ Why $\mathbb{N} = \mathbb{Z}$?

**Definition:** Two sets $S$ and $T$ have the same cardinality if there is a one-to-one correspondence (bijection) between $S$ and $T$

### **Theorem:** $|\mathbb{N}| = |\mathbb{Z}|$.
- **proof:** We define a (bijection) $f: \mathbb{N} \rightarrow \mathbb{Z}$, where
$f(x) =
\begin{cases}
&\dfrac{x}{2}, &\text{if}\ x\ \text{is even.}\\
&\dfrac{-(x-1)}{2}, &\text{otherwise (if}\ x\ \text{is odd).}
\end{cases}$
- **claim:** $f$ is bijection (1-1 and onto)

### **Theorem:** $|\mathbb{N}| = |\mathbb{Q}^+|$.

(Recall: a rational number is quotient of two integers, which can be represented by $\frac{a}{b}$, a and b are integers, and b $\neq$ 0)

| | | | | | |
| --- | --- | --- | --- | --- | --- |
| 1/1 | 2/1 | 3/1 | 4/1 | 5/1 | 6/1 |
| 1/2 | 2/2 | 3/2 | 4/2 | 5/2 | 6/2 |
| 1/3 | 2/3 | 3/3 | 4/3 | 5/3 | 6/3 |
| 1/4 | 2/4 | 3/4 | 4/4 | 5/4 | 6/4 |
| 1/5 | 2/5 | 3/5 | 4/5 | 5/5 | 6/5 |
| 1/6 | 2/6 | 3/6 | 4/6 | 5/6 | 6/6 |

### **Theorem:** $|\mathbb{N}| \neq |\mathbb{R}|$ (cf. $|\mathbb{N}| = |\mathbb{Z}|$)
- **proof:** (diagonalization argument)(對角論證法) (proof by contradiction)
Suppose to the contrary that $|\mathbb{N}| = |\mathbb{R}|$ $\exists$ bijection $f: \mathbb{N} \to \mathbb{R}$
$i\mapsto r_i = r_{i0}.r_{i1}r_{i2}r_{i3}\cdots$, with $r_{i0}$ the integer part and $r_{ij}$ the j-th digit of the fraction part ($0 \leq r_{ij} \leq 9$, for j $\in \mathbb{N}$)
- e.g.
$1 \to r_1 = r_{10}.r_{11}r_{12}\cdots$
$2 \to r_2 = r_{20}.r_{21}r_{22}\cdots$
$\vdots$
$n \to r_n = r_{n0}.r_{n1}r_{n2}\cdots r_{nn} \cdots$
$\vdots$

We claim that function $f$ is not onto; namely there exists a real number r* which is not listed by $f$

- **Define** $r* = 0.r^*_1r^*_2r^*_3c\cdots r^*_n \cdots$

$r^*_i =
\begin{cases}
1 &, \text{if } r_{ii} = 2\\
2 &, \text{otherwise}
\end{cases}$

> Given the bijection f, the number r* is well-defined, but not listed by f since for $n \in \mathbb{N}, r^* \neq f(n) = r_n (r^*_n \neq r_{nn})$, which is contradiction.

- Exercise: $F = \{f|f: \mathbb{N} \to \mathbb{N}\}$. Show that F is uncountable
- Exercise: Show that the set of all computer programs is countable. (A computer program is 01-string of finite length.)

--> There exists some function that is uncountable.

If there is a one-to-one correspendence between A and B, then $|A| = |B|$.
- **Definition:** We say that |A| <= |B| is an injection from A to B
- e.g. $|\mathbb{N}| \neq |\mathbb{R}|$, and there is a 1-1 function $f: \mathbb{N} \to \mathbb{R}, x \to x.$

**Question:**
1. Can you agree that |(0,1)| = |(0,1]|?
$(0,1) = \{x \in \mathbb{b} | 0 < x < 1\}, (0,1] = \{x \in \mathbb{b} | 0 < x \leq 1\}, || = \text{cardinality}$
**proof**
$f: A \to B, x \to x$
$g: B \to A, x \to \dfrac{x}{2}$
2. Can you agrue that |(0,1)| = |R|?
**proof**
訂一個function 把實數壓到（0,1）區間（可以利用三角函數）

### **Theorem[Schroder-Bernstein]:**
If A and B are sets $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

Definition: Let A and B be two sets. A relation from A to B is a subset of $A\times B$
- $A \times B$: the Cartesian of A and B, defined

### **Equivalence relation**

- Let $R$ is binary relation on a set of $A$ ($R$ is a relation from $A \to A$)
- **reflexive**: for a $\in$ A, (a,a) $\in$ $\mathbb{R}$.
- **symmetric**: for a,b $\in$ A, (a,b) $\in$ $\mathbb{R}$ $\implies$ (b,a) $\in$ $\mathbb{R}$.
- **antisymmetric**: for a,b $\in$ A, (a,b) $\in$ $\mathbb{R}$ $\implies$ (b,a) $\notin$ $\mathbb{R}$ or a = b
- **transitive**: for a,b,c $\in$ A, (a,b) $\in$ $\mathbb{R}$ $\cap$ (b,c) $\in$ $\mathbb{R}$ $\implies$ (a,c) $\in$ $\mathbb{R}$

A relation $R$ is an equivalence relation if $R$ is reflexitive, symmetric, and transitive.

- **Definition**: The set of all elements that are relates to an element a set of A is called the equivalence of a, denoted by [a]; namely [a] = {x $\in$ A \| (a,x) $\in \mathbb{R}$}
- e.g. congruence relation modulo 5
[0] = {0, 5, -5, 10, -10,$\cdots$}

**Proposition**: Let $R$ be an equivalence relation on a nonempty set A. For a,b $\in$ A, the following statements equivalent:

( a ) aRb, ( b ) [a] = [b], ( c ) [a] $\cap$ [b] $\neq \varnothing$

- **Proof**: (a $\implies$ b, b $\implies$ c, c $\implies$ a)
- (a $\implies$ b) We prove that [a] $\subseteq$ [b] and [b] $\subseteq$ [a]. For x $\in$ [a], by definition aRx. Since R is **symmetric**, aRb $\implies$ bRa. By **transitivity** of R, bRa and aRx imply bRx. Similarly, it can be derived that [b] $\subseteq$ [a].
- (b $\implies$ c) Since R is **reflexive**, aRa and bRb. Both [a] and [b] are nonempty, and thus [a] $\cap$ [b] $\neq \varnothing$.
- (c $\implies$ a) Since [a] $\cap$ [b] = $\varnothing$, there exists x $\in$ [a] $\cap$ [b], which means aRx and bRx. Since R is **symmetric**. bRx $\implies$ xRb. By the **transitivity** of R, aRx amd xRb imply aRb.

**Partition**: A partition of a set of S is a collection of disjoint nonempty subsets of S that have S as their union. Namely, {$A_i$ \| $i \in I$} (where $I$ is the index set) forms a partition of S
- $A_i \neq \varnothing$, $\forall i \in I$
- For $i \neq j$, $A_i \cap A_j = \varnothing$
- $\bigcup_{i \in I} A_i = S$
e.g. {{3, 1}, {4}, {5, 9}} is a partition of {1, 3, 4, 5, 9}. ($I$ = {1, 2, 3})

**Proposition**: Let R be an equivalence relation on A. The equivalence classes form a partition of A.

e.g. A = {1, 3, 4, 5, 9}, R: aRb if $a \equiv b \pmod{5}$
equivalence class: [1] = {1}, [3] = {3}, [4] = [9] = {4, 9}, [5] = {5}.

**Proposition**: Let {$A_i$ \| $i \in I$} be a partition of A. Then there is an equivalence relation R on A with equivalence classes $A_1, A_2, \cdots$

e.g. {{3, 1}, {4}, {5, 9}} $\to$ R = {(1, 3), (3, 1), (1, 1), (3, 3), (4, 4), (5, 5), (9, 9), (5, 9), (9, 5)}

**Proposition**: Let R be an equivalence relation on A. The equivalence classes form a partition of A.

- **Proof**: (Let A = {$a_1, a_2, \cdots , a_n$}, the equivalence classes $[a_1], [a_2], \cdots , [a_n]$)
- Since R is reflexive, for any a $\in$ A we have a $\in$ [a]. No equivalence class is empty, and thus $\bigcup_{a \in A} [a] = A$
- Since $[a] \cap [b] = \varnothing \iff [a] = [b]$. For two distinct equivalence classes [a] and [b], we have $[a] \cap [b] = \varnothing$

**Proposition**: Let {$A_i$ \| $i \in I$} be a partition of A. Then there is an equivalence relation R on A with equivalence classes $A_1, A_2, \cdots$

- **Proof**: We prove by defining the relation R, as aRb if $a \in A_i$ and $b \in A_i$ for some $i \in I$.
- R is reflexive: since $\bigcup_{i \in I} A_i = A$, every element is some $A_i$. Moreover aRa since $a \in A_i$ and $a \in A_i$.
- R is symmetric: "$a \in A_i$ and $b \in A_i$" implies "$b \in A_i$ and $a \in A_i$".
- R is transitive: Assume that $a, b \in A_i$ and $b, c \in A_j$. Since $i \neq j \implies A_i \cap A_j = \varnothing$, that $b \in A_i \cap A_j \implies A_i = A_j$, and thus aRc.

For $a \in A, a \in A_i \implies [a] = A_i$.
- ($A_i \subseteq [a]$) For $x \in A_i$, we have aRx, and thus $A_i \subseteq [a]$
- ($[a] \subseteq A_i$) By definition, $x \in [a]$ implies aRx, which means there exists j such that a, $x \in A_j$. By the definition of a partition, we know j = i. Thus $[a] \subseteq A_i$.

### **Partial order**

**Definition**: A relation R on a set A is a partial order if R is **reflexive, antisymmetric, and transitive**.

e.g.

- $R_1 = \{(x, y) \in \mathbb{Z} \times \mathbb{Z} | x \ge y\}$ ($R_1$ is equivalence relation? partial order?)
- $R_2 = \{(x, y) \in \mathbb{N} \times \mathbb{N} : x | y \}$
- $R_3 = \{(x, y) \in 2^{\mathbb{N}} \times 2^{\mathbb{N}} : X \subseteq Y\}$

**Representation of relations**

e.g. R = {(1, 3), (3, 1), (1, 1), (3, 3), (4, 4), (5, 5), (9, 9), (5, 9), (9, 5)}.

- using matrices: 
- using directed graph (diagraph): a diagraph consists of a set V of vertices and a set E of ordered pairs of elements of V, call edges.

digraph G{
    rankdir=LR
    1 -> 3;
    3 -> 1;
    1 -> 1;
    3 -> 3;
    
    9 -> 5;
    5 -> 9;
    5 -> 5;
    9 -> 9;
    
    4 -> 4;
}

- **Hasses's diagram**: Many edges in the digraph for a finite poset do not haveto be shown because they must be present. The procedure for simplifyingthe digraph of a poset is as follows:
- Draw the digraph for the poset $(S, R)$
- Remove all the loops.
- Remove edges $(x,y)$ for which there is an element $z \in S$ such that xRz and zRx.
- Arrange each edge so that its initial vertex is below its terminal vertex.
- Remove all the arrow s on the edges.

- e.g. $A = {a, b, c}$, R the "subset" relation on $2^A$. The Hasses's diagram of (A, R) is

graph G{
    "a, b, c" -- "a, b";
    "a, b, c" -- "b, c";
    "a, b, c" -- "a, c";
    "a, b" -- a;
    "a, b" -- b;
    "b, c" -- b;
    "b, c" -- c;
    "a, c" -- a;
    "a, c" -- c;
    a -- Ø;
    b -- Ø;
    c -- Ø;
} 

**Definition**: For a partial order R on A, (A, R) is called a Partially Orderedset, or poset for abbreviation.

**Definition**: A relation R on a set A is a total order (or, linear order) if R isa partial order and every two elements of A are related.

**Definition**: Let (A, R) be a poset. A chain is a subset of A in which everytwo elements are related. An antichain is a subset of A in which no twoelements are related.

- Theorem. [Dilworth 1950] Let (A, R) be a (finite) poset, and let $w$ be theminimum number of chains that for a partition of A. The maximum size ofan antichain is $w$

**Proposition**: Every sequence of $n^2+1$ distinct numbers contains either an increasing subsequence or a decreasing subsequence of length at least $n+1$.

- **Proof-1**: (by the pigeonhole principle), Let the sequence be $a_1,a_2,\cdots,a_{n^2+1}$
- Suppose to the contrary that the longest increasing(decreasing) subsequence has length at most n. We associate each number $a_i$ with a pair of integers $(x_i, y_i)$, where
- $x_i$: the length of the longest increasing subsequence starting at $a_i$.
- $y_i$: the length of the longest decreasing subsequence starting at $a_i$.
- By the assumption, we have $1 \le x_i, y_i \le n$, so there are at most $n^2$ different pairs of $(x_i, y_i)$. Since there are $n^2+1$ numbers, by the pigeonhole principle, there exist $i$ and $j$ $(i \neq j)$ such that $(x_i, y_i) = (x_j, y_j)$

- **Proof-2** (by Dilworth's theorem) Let the sequence be $a_1, a_2, \cdots, a_{n^2+1}$. We define a relation R on A = {$a_1, a_2, \cdots, a_{n^2+1}$}, where $a_iRa_j$ if $i \le j$ and $a_i \le a_j$.
- R is partial order (Verify that the 3 properties hold)
- Any chain corresponds to an increasing subsequence. If the longest chain has the length less than $n+1$, the any partition of (A, R) into chains contains at least $n+1$ chains.
- By Dilworth's theorem, there is an antichain of size at least $n+1$. (Any antichain corresponds to a decreasing subsequence.)