离散数学（信息与计算导论版）
Zsir：
group theory / number theory
no constraints
Yuan Zhang、Penghui Yao：
graph theory (8 weeks & 1 quiz each)
probably hw, check-in, exams (no guarantee from Zsir)
class 01, intro (Zsir)
Mostly abstract algebra
Definitions
Binary operation: \(f: G^2 \rightarrow G\)
Algebraic system: \((G,\cdot)\)
Closedness: \(\forall x,y \in G, x\cdot y\in G\)
Group: Algebraic system \((G, \cdot)\) where \(G\) is a set and \(\cdot\) is a binary function \(f: G^2 \rightarrow G\), and:
- \(\exists \text{ Identity }1 \in G \text{ s.t. } \forall a \in G, a\cdot 1 = 1\cdot a = a\)
- \(\forall a, b, c \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)\)
- \(\forall a \in G, \exists a^{-1} \in G \text{ s.t. } a^{-1} \cdot a = a \cdot a^{-1} = 1\)
Example 1: Klein 4-group
Klein bottle...
The group: \((\{1, a, b, c\}, \cdot)\)
| \(\cdot\) | \(1\) | \(a\) | \(b\) | \(c\) |
|---|---|---|---|---|
| \(1\) | \(1\) | \(a\) | \(b\) | \(c\) |
| \(a\) | \(a\) | \(1\) | \(c\) | \(b\) |
| \(b\) | \(b\) | \(c\) | \(1\) | \(a\) |
| \(c\) | \(c\) | \(b\) | \(a\) | \(1\) |
Example 2:
Geometrical operation on a regular triangle: \({}_{B}\mathop{\triangle}\limits^{A}{}_{C}\)
- identity operation: \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{B}\mathop{\triangle}\limits^{A}{}_{C}\)
- clockwise rotation by \(120^{\circ}\): \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{C}\mathop{\triangle}\limits^{B}{}_{A}\)
- counter-clockwise rotation by \(120^{\circ}\): \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{A}\mathop{\triangle}\limits^{C}{}_{B}\)
- reflection: \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{C}\mathop{\triangle}\limits^{A}{}_{B}\)
- reflection followed by clockwise rotation: \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{B}\mathop{\triangle}\limits^{C}{}_{A}\)
- reflection followed by counter-clockwise rotation: \({}_{B}\mathop{\triangle}\limits^{A}{}_{C} \rightarrow {}_{A}\mathop{\triangle}\limits^{B}{}_{C}\)
Composition is assosiative...
Example 3:
Let \(M\) be the set of \(n\times n\) real non-singular matrices, then \((M, \cdot)\) is a group.
Matrix multiplication is assosiative...
Uniqueness of identity and inverse
Uniqueness: \(1 \cdot 1' = ?\)
Cancellation law: \(a\cdot b = a\cdot c \Rightarrow b=c\), and \(b\cdot a = c\cdot a \Rightarrow b=c\)
We wonder if cancellation law holds, whether can we say we'll get a group.
Solution of group equation obviously exists in a group:
\(x \cdot a = b \Leftrightarrow x = b \cdot a^{-1}\)
\(a \cdot x = b \Leftrightarrow x = a^{-1} \cdot b\)
Introducing the magma: Closedness.
Introducing the semigroup: Closedness, Assosiativity.
Introducing the monoid: Closedness, Assosiativity, Identity.
If cancellation law holds in a semigroup, can we say we'll get a group?
Yes for finite semigroup.
\((\Z^+,+)\)
If solution of group equation always exist in a semigroup, can we say we'll get a group?
Yes.
class 02, graph theory (Yuan Zhang)
Very important, honestly