---
title: 離散 part9
---
{%hackmd @NTNUCSIE112/DM_card %}

# Relations and Boolean algebra
Ch.9 Relations

Reading assigned: 9.1 (except 9.1.5), 9.5, 9.6.1-9.6.3

- exercise
- 9.1: 1, 4, 8, 9, 48, 50, 51.
- 9.3: 4, 8, 23-28.
- 9.5: 2, 11, 15, 45, 61.
- 9.6: 1, 3, 6, 9-11, 21, 22, 24, 43
- video
- [0510](https://drive.google.com/file/d/1doM7IBCsEMerK1Mjb0Up2e9hotLnVhrx/view)

## Cartesian product
$A\times B$: the Cartesian product of A and B, defined as $\{(a,b)|a \in A, b \in B}\$
- $(a,b)$ is ordered pair
- e.g. $$A = \{1,2\}, B = \{a,b,c\}\\
A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}
$$
- Note: conventionally, we use parentheses to denote order an "ordered" pair/tuple; namely, $(a,b) \not = (b,a)$. For "unordered" pair/tuple, we use sets (cf. {a,b} = {b,a})
- In general $A\times B \not = B \times A$, unless $A = \emptyset$ or $B = \emptyset$
(Note. For any set $A$, $A \times \emptyset = \emptyset \times A = \emptyset$)
##

Definition. Let $A$ and $B$ be two sets. $A$ (binary) relation from $A$ to $B$ is a subset of $A\times B$.

- e.g. any function is a relation. Consider , , ,

, . Then can be represented by .

Notation: For , sometimes we use to denote .

Definition. A binary relation on a set is a relation from to .
A B A B

A × B

A
<!-- 上面那張圖的內容 待補齊 -->

## Equivalence relation
A relation $R$ is an equivalence relation if $R$ is reflexive, symmetric, and transitive.

### Definition
The set of all elements that are related to an element a of A is called the equivalence class

### Example
#### Proposition
Every sequence of $n+1$ distinct numbers contains either an increasing subsequence or decreasing subsequence of length at least $n+1$
#### e.g.
n = 2
| sequence | -100 | 88 | 79 | 5 | -7 |
| -------- | ---- | --- | --- | --- | --- |
| inc | 2 | 1 | 1 | 1 | 1 |
| dec | 1 | 4 | 3 | 2 | 1 |

#### Proof 1 pigeonhole
#### Proof 2 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 \leq j$ and $a_i\leq a_j$.
- $R$ is a partial order. (Verify that the 3 properties hold.)

- Any chain corresponds to an increasing subsequence. If the longest chain has 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.)
<!-- 以下是課本章節 -->

## 9.1 Relations and Their Properties

### 9.1.1 Introduction
### 9.1.2 Functions as Relations
### 9.1.3 Relations on a Set
### 9.1.4 Properties of Relations
Let $R$ be a binary relation a set $A$ ($R$ is a relation from $A$ to $A$). $R$ is
- reflexive: for $a \in A, (a,a) \in R$
- symmetric: for $a,b \in A, (a,b) \in R \implies (a,b) \in R$
- antisymmetric: for $a,b \in A, (a,b) \in R \implies (b,a) \notin R \text{ or } a = b$
- transitive
## 9.5 Equivalence Relations
### 9.5.1 Introduction
### 8.5.2 Equivalence Relation
## 9.6 Partial Orderings
### 9.6.1 Introduction
### 9.6.2 Lexicographic Order
### 9.6.3 Hasse Diagram