Table of Content
Let \(A\) and \(B\) be sets. A binary relation from \(A\) to \(B\) is a subset of \(A \times B\).
Relation，是數個集合的成員之間的關係，類似 Function，但沒有不能一對多的限制。Reation 本身也是一集合 \(R\)；如果 \((a, b) \in R\)，寫做 \(a\ R\ b\)，讀做 \(a\) is related to \(b\) by \(R\)。
Fuction 事實上是 Relation 的特例。
A relation on a set \(A\) is a relation from \(A\) to \(A\)。
A relation \(R\) on a set \(A\) is called reflexive if \((a, a) \in R\), \(\forall a \in A\).
symmetric: \((a, b) \in R\) 和 \((b, a) \in R\) 同時成立，\(\forall a, b \in A\)
antisymmetric: 如果 \((a, b) \in R\) 和 \((b, a) \in R\)，則 \(a = b\)
asymmetric: \((a, b) \in R\) 和 \((b, a) \in R\) 不同時成立，也就是 \((a, a) \not\in R\)
\(R\) on a set \(A\) is transitive if \(\forall a\forall b \forall c(((a,b) \in R \land (b, c) \in R) \implies (a, c) \in R)\).
Let \(R\) be a relation from a set \(A\) to a set \(B\) and \(S\) a relation from \(B\) to a set \(C\). \((a, c) \in S \circ R\), for which \(\exists b \in B\) such that \((a, b) \in R\) and \((b, c) \in S\). (\(a \in A, c \in C\))
想想 function
\(R^1 = R\) and \(R^{n+1} = R^n \circ R\).
Definition
An equivalence relation \(R\) on a set \(S\) is one that satisfies reflexive, symmetric, and transitive, \(\forall x, y, z \in S\).
與底下的 poset 比較
定義集合上的 equivalence relation 是為了建構出 partition。
Example
對於任意非空集合 \(S\)，\((S, =)\) 是 equivalence relation。
Define a relation on \(\mathbb{R}^2\) as follows:
For any \(\vec{v} = (v_1, v_2), \vec{u} = (u_1, u_2) \in \mathbb{R}^2\),
\[\vec{v} \sim \vec{u} \text{ if } v_1-u_1 = v_2-u_2.\]
- Show that this is an equivalence relation.
- Find a complete set of representatives of equivalence classes.
Solution
1.
To show this is an equivalence relation, we have to verify whether it is relexive, symmetric, and transitive.
2.
We claim that \(S = \{(x, 0)\vert x\in \mathbb{R} \}\) is the desired set.
For any \(\vec{v} = (v_1, v_2) \in \mathbb{R}^2\), let \(x=v_1-v_2\). Then \(v_1-x = v_2 = v_2 - 0\). Therefore, \(\vec{v} \sim (x, 0)\). On the other hand, if \((x, 0)\sim (y, 0)\), then \(x-y = 0 - 0 = 0\), which means that \(x = y\) and \((x, 0) = (y, 0)\).
Thus, \(S\) is a complete set of represnetatives of the equivalence classes.
Remark
對於第二題，先驗證所有 \(\vec{v} \in \mathbb{R}^2\) 都和 \(S\) 的其中一個 element equivalent，然後再說明 represnetative 之間沒有重疊！
其實可以驗證 \(S\) 是 \(\mathbb{R}^2\) 的 subgroup 。
A relation \(R\) on a set \(S\) is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. And \((S, R)\) is called a partially ordered set, or poset. Members of \(S\) are called elements of the poset.
Example: \((\mathbb{Z}, \geq)\) is a poset
證明 \(\geq\) 在 \(\mathbb{Z}\) 上是 reflexive, antisymmetric, and transitive。
The elements \(a\) and \(b\) of a poset \((S, \preceq)\) are called comparable if either \(a \preceq b\) or \(b \preceq a\). Otherwise, \(a\) and \(b\) are called incomparable.
Example: In the poset \((\mathbb{Z}^{+}, \mid)\), \(5\) and \(7\) are incomparable.
Note : \(\preceq\) is used to denote the relation in any poset.
Note : \(a \prec b\) 讀做 “\(a\) precedes \(b\)” 或 “\(a\) is less than \(b\)”
若 \((S, \preceq)\) 是 poset 且 \(S\) 的任兩元素皆 comparable，則 \(S\) 稱為 totally ordered set 或 linearly ordered set，而 \(\preceq\) 稱為 a total order 或 a linear order。
\((S, \preceq)\) is a well-ordered set if it is a poset such that \(\preceq\) is a total ordering and every nonempty subset of \(S\) has a least element.
Example: \((\mathbb{Z}^{+}, \leq)\) is well-ordered, while \((\mathbb{Z}, \leq)\) is not.
Suppose that \(S\) is a well-ordered set. Then \(P(x)\) is true for all \(x \in S\), if
Inductive Step: For every \(y \in S\), if \(P(x)\) is true for all \(x \in S\) with \(x \prec y\), then \(P(y)\) is true.
廣義的數學歸納法
Proof
Suppose it is not the case that \(P(x)\) is true for all \(x \in S\) … (proof by contradiction).
A partition of a set \(S\) is a collection of nonempty subsets of \(S\) such that every element of \(S\) is in exactly one of the subsets. The subsets are the cells of the partition.
想想貝氏定理的分割圖（或任何分割圖）
\(\bar x\)：指包含 \(x\) 的 cell，稱作 the equivalence class containing \(x\)；而 \(x\) 叫做 a representative of the cell（代表元）。
設 \(\{S_1, S_2, \cdots\}\) 是 \(S\) 的一個 partition，則
\[S = \bigsqcup_i S_i。\]