OveriewPermalink

AS with 0 OperationPermalink

Set $\Rightarrow S$Permalink

Set is the very basic algebraic structure without any binary operation.

AS with 1 OperationPermalink

Magma (Groupid) $\Rightarrow (S,\circ )$Permalink

A magma (a.k.a. groupid) can be denoted by $(S,\circ )$, such that:

• $S$ is a set
• $\circ :S\times S\to S$ is a binary operation
  • 注意这其实表明了 $S$ is closed under $\circ$

Semigroup $\Rightarrow$ Associative Magma $(S,\circ )$Permalink

A semigroup is simply an associative magma, as:

• $\mathrm{\forall }a,b,c\in S,(a\circ b)\circ c=a\circ (b\circ c)$

Semigroup vs GroupPermalink

结构上：

• Semigroup 是 $(S,\circ )$
• Group 是 $(S,\circ ,\overline{e})$

性质上：

• Group 是 Invertible Monoid
• Monoid 是 Semigroup + Identity
• 所以 Group 一定是 Semigroup
• Semigroup 是 “没有 identity $\overline{e}$ (进而) 也没有 inverse” 的 Group

疑问：semigroup 连 monoid 都不如，为何挂着 group 的名字？根据 这个帖子:

In summary, the name “semigroup” comes from the fact that it is halfway between a “magma” (a set with a binary operation) and a “group” (a set with an associative binary operation, an identity element, and an inverse element for each element).

只是这个 “halfway” 离 group 离得有点远……

Band $\Rightarrow$ Idempotent Semigroup $(S,\circ )$Permalink

A band is simply an idempotent semigroup $(S,\circ )$, such that:

• $\mathrm{\forall }a\in S,a\circ a=a$

Semilattice $\Rightarrow$ Commutative Band $(S,\circ )$Permalink

本文是从 AS 角度定义，从 Poset 的角度定义请参考 Order-Theoretic Definition of Lattices.

A semilattice is simply a commutative band $(S,\circ )$, such that:

• $\mathrm{\forall }a,b\in S,a\circ b=b\circ a$

Bounded Semilattice $\Rightarrow$ Semilattice + Identity $\Rightarrow$Idempotent Abelian Monoid $(S,\circ ,\overline{e})$Permalink

A semilattice $(S,\circ )$ is bounded if $\mathrm{\exists }$ an identity element $\overline{e}\in S$ such that:

• $\mathrm{\forall }a\in S,a\circ \overline{e}=\overline{e}\circ a=a$

Monoid $\Rightarrow$ Semigroup + Identity $\Rightarrow$ $(S,\circ ,\overline{e})$Permalink

A monoid can be denoted by $(S,\circ ,e)$ such that:

• $(S,\circ )$ is a semigroup
• $\overline{e}\in S$ is the identity element w.r.t. $\circ$
  • i.e. $\mathrm{\forall }a\in S,a\circ \overline{e}=\overline{e}\circ a=a$

Also written as a tuple $(S,\circ )$ if we consider $\overline{e}$ associated with $\circ$ internally.

Abelian Monoid $=$ Commutative MonoidPermalink

虽然我们有 $a\circ e=e\circ a=a$ 但这并不意味着我们的 monoid 一定是 commutative 的 (i.e. $\mathrm{\forall }a,b$ 有 $a\circ b=b\circ a$)。如果是 commutative 的需要 explicitly 写出来。

同时 commutative monoid 也 a.k.a. abelian monoid.

Group $\Rightarrow$ Invertible Monoid $(S,\circ ,\overline{e})$Permalink

A group is a monoid with inverse.

假设 $(S,\circ ,\overline{e})$ 是 group，我们有：

• $(S,\circ ,\overline{e})$ 自然也是 monoid
• $\mathrm{\forall }a\in S$, there $\mathrm{\exists }b\in S$ such that $a\circ b=b\circ a=\overline{e}$
  • $b$ is the inverse of $a$, vice versa

Inverse / Negative / ReciprocalPermalink

你可以把 inverse 看成是一个 unary operation，也可以理解成 “group 中的任意 element 都有一个 inverse element”：

• 如果 $\circ$ 是 addition，$a$ 的 inverse element 一般写成 $-a$
  • 你也可以理解成是 “取 negative” 操作
• 如果 $\circ$ 是 multiplication，$a$ 的 inverse element 一般写成 $a^{-1}$
  • 你也可以理解成是 “取 reciprocal” 操作

Abelian Group $=$ Commutative GroupPermalink

好理解：普通的 monoid 构建出的是普通的 group，那么 abelian monoid 构建出的就是 abelian group。

AS with 2 OperationsPermalink

Lattice $\Rightarrow (S,\mathbf{\vee },\mathbf{\wedge })$Permalink

本文是从 AS 角度定义，从 Poset 的角度定义请参考 Order-Theoretic Definition of Lattices.

A lattice is a set with two binary operations, often called $\mathbf{\vee }$ (join) and $\mathbf{\wedge }$ (meet).

注意词义 overloading: 有的教材会把 $a\vee b$ 的 值 称为 “join of $a,b$”，相当于 join == greatest lower bound；同理，也会把 $a\wedge b$ 的 值 称为 “meet of $a,b$”，相当于 meet == least upper bound.

我们可以用 $(S,\mathbf{\vee },\mathbf{\wedge })$ 表示一个 lattice，它满足：

• $(S,\mathbf{\vee })$ is a semilattice
  • a.k.a. the join-semilattice
• $(S,\mathbf{\wedge })$ is a semilattice
  • a.k.a. the meet-semilattice
• absorption laws
  • $\mathrm{\forall }a,b\in S,a\vee (a\wedge b)=a$
  • $\mathrm{\forall }a,b\in S,a\wedge (a\vee b)=a$

Bounded Lattice $\Rightarrow$ Lattice + Identities $\Rightarrow (S,\mathbf{\vee },\mathbf{\wedge },\mathrm{\perp },\mathrm{\top })$Permalink

我们可以用 $(S,\mathbf{\vee },\mathbf{\wedge },\mathrm{\perp },\mathrm{\top })$ 表示一个 bounded lattice，它满足：

• $(S,\mathbf{\vee },\mathbf{\wedge })$ is a lattice
• $(S,\mathbf{\vee },\mathrm{\perp })$ is a bounded semilattice
  • $\mathrm{\perp }$ is a.k.a. least element, minimum, or bottom
  • $\mathrm{\perp }$ is also denoted by $\overline{0}$ or $\bigvee R$
• $(S,\mathbf{\wedge },\mathrm{\top })$ is a bounded semilattice
  • $\mathrm{\top }$ is a.k.a. greatest element, maximum, or top
  • $\mathrm{\top }$ is also denoted by $\overline{1}$ or $\bigwedge R$

Semiring (Rig) $\Rightarrow (S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$Permalink

A semiring is a set with two binary operations, often called $\mathbf{+}$ (addition) and $\mathbf{\times }$ (multiplication).

我们可以用 $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$ 表示一个 semiring，它满足：

• $(S,\mathbf{+},\overline{0})$ is an abelian monoid
• $(S,\mathbf{\times },\overline{1})$ is a monoid
• $\mathbf{\times }$ is distributive w.r.t. $\mathbf{+}$, i.e. $a\mathbf{\times }(b\mathbf{+}c)=(a\mathbf{\times }b)\mathbf{+}(a\mathbf{\times }c)$
• $\mathbf{\times }$ has the absorption/annihilation law, i.e. $\overline{0}\mathbf{\times }a=a\mathbf{\times }\overline{0}=\overline{0}$
  • $\overline{0}$ is the absorbing element / annihilating element / annihilator w.r.t. $\mathbf{\times }$

我们这里用 $\overline{0}$ 和 $\overline{1}$ 来表示 identity elements，以区分具体的数 $0$ 和 $1$

Absorbing Element / Annihilating Element / Annihilator 这些名称都是等价的

Absorption / Annihilation Law: 定义还是性质？Permalink

我们在 ring 的部分可以通过其他三条定义直接推断出 absorption / annihilation law，所以对 ring 而言，这条 law 可以看做是 ring 的一个 property，而不用放到定义中去强调它。

但是对 semiring 而言，无法推断出 absorption / annihilation law，所以就只能把它写到定义中。

我个人的怀疑是先有的 ring，再有的 semiring，然后 semiring 的研究又常用到 absorption / annihilation law，于是就直接整合到 semiring 的定义中去了。

Ring $\Rightarrow$ Addition-Invertible Semiring $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$Permalink

我们可以用 $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$ 表示一个 ring，它满足：

• $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$ is a semiring
  • but $(S,\mathbf{+},\overline{0})$ is an abelian group, instead of an abelian monoid in a semiring

Trivial Ring (Zero Ring) $\Rightarrow$ Ring with Only 1 ElementPermalink

存在 trivial ring (a.k.a zero ring)，即只有一个元素的 ring，比如 $\epsilon$，它的 $\overline{0}=\overline{1}=\epsilon$.

Lemma: if $\overline{0}=\overline{1}$ $⟹$ then $S$ is a trival ring

Absorption / Annihilation Law 的证明Permalink

Given a ring $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$, $\mathrm{\forall }a\in S$, 有：

• 因为 $\overline{0}\mathbf{+}\overline{0}=\overline{0}$ (by monoid’s definition on identity)
• 所以 $\overline{0}\mathbf{\times }a=(\overline{0}\mathbf{+}\overline{0})\mathbf{\times }a=(\overline{0}\mathbf{\times }a)\mathbf{+}(\overline{0}\mathbf{\times }a)$
• 等式两边同时 $\mathbf{+}$ 加上 $(\overline{0}\mathbf{\times }a)$ 的 inverse，可得 $\overline{0}=\overline{0}\mathbf{\times }a$

我们称 $\overline{0}$ 为 left annihilator (w.r.t. $\mathbf{\times }$)。

同理 $\overline{0}$ 也是 right annihilator (因为同样可以推出 $\mathrm{\forall }a\in S$, 有 $\overline{0}=a\mathbf{\times }\overline{0}$).

Field $\Rightarrow$ Non-Trivial, Commutative, Almost Multiplication-Invertible Ring $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$Permalink

A field is a commutative ring where $\overline{0}\ne \overline{1}$ and $\mathrm{\forall }a\in S\setminus \{\overline{0}\}$ there is an inverse for $a$ w.r.t. $\mathbf{\times }$.

我们揉碎了说。假设用 $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$ 表示一个 field，它满足：

• $(S,\mathbf{+},\mathbf{\times },\overline{0},\overline{1})$ 自然也是一个 commutative ring
• $(S,\mathbf{+},\overline{0})$ is an abelian group
  • a.k.a. the additive group within the field
• $(S,\mathbf{\times },\overline{1})$ is an abelian monoid
• $(S\setminus \{\overline{0}\},\mathbf{\times },\overline{1})$ is an abelian group
  • a.k.a. the multiplicative group within the field
• $\mathbf{\times }$ is distributive w.r.t. $\mathbf{+}$, i.e. $a\mathbf{\times }(b\mathbf{+}c)=(a\mathbf{\times }b)\mathbf{+}(a\mathbf{\times }c)$
• $\overline{0}\ne \overline{1}$
  • this requirement is by convention to exclude trivial ring

Vector-related ASPermalink

Vector Space $\Rightarrow (V,\mathbf{+},\overrightarrow{0},\mathbf{\cdot },\overline{1}{)}_K$Permalink

我们在 Digest of Essence of Linear Algebra 的末尾提了一嘴，但没有说严格的数学定义，这里补充一下。

A vector space over a scalar field $K$, say $(K,\oplus ,\otimes ,\overline{0},\overline{1})$, is a non-empty set of vectors $V$ with with two binary operations:

1. vector addition $\mathbf{+}:V\times V\to V$, and
2. scalar multiplication $\mathbf{\cdot }:K\times V\to V$,

which satisfy the two closure axioms $C1,C2$ as well as the eight vector space axioms $A1-A8$:

• $C1$ (Closure under vector addition) Given $\mathit{v},\mathit{w}\in V$, $\mathit{v}\mathbf{+}\mathit{w}\in V$
• $C2$ (Closure under scalar multiplication) Given $\mathit{v}\in V$ and $\alpha \in K$, $\alpha \mathit{v}\in V$

For arbitrary vectors $\mathit{u},\mathit{v},\mathit{w}\in V$, and arbitrary scalars $\alpha ,\beta \in K$:

• $A1$ (Commutativity of addition) $\mathit{v}\mathbf{+}\mathit{w}=\mathit{w}\mathbf{+}\mathit{v}$
• $A2$ (Associativity of addition) $(\mathit{u}\mathbf{+}\mathit{v})\mathbf{+}\mathit{w}=\mathit{u}\mathbf{+}(\mathit{v}\mathbf{+}\mathit{w})$
• $A3$ (Existence of a zero vector) $\mathrm{\exists }\overrightarrow{0}\in V$ such that $\overrightarrow{0}\mathbf{+}\mathit{v}=\mathit{v}\mathbf{+}\overrightarrow{0}=\mathit{v}$
• $A4$ (Existence of additive inverses) $\mathrm{\forall }\mathit{v}\in V$, $\mathrm{\exists }\mathbf{-}\mathit{v}\in V$ such that $\mathit{v}\mathbf{+}(\mathbf{-}\mathit{v})=(\mathbf{-}\mathit{v})\mathbf{+}\mathit{v}=\overrightarrow{0}$
• $A5$ (Distributivity of scalar multiplication over vector addition) $\alpha (\mathit{v}\mathbf{+}\mathit{w})=\alpha \mathit{v}\mathbf{+}\alpha \mathit{w}$
• $A6$ (Distributivity of scalar addition over scalar multiplication) $(\alpha \oplus \beta )\mathit{v}=\alpha \mathit{v}\mathbf{+}\beta \mathit{v}$
• $A7$ (Associativity of scalar multiplication) $(\alpha \otimes \beta )\mathit{v}=\alpha (\beta \mathit{v})$
• $A8$ (Scalar multiplication with $\overline{1}$ is the identity) $\overline{1}\mathit{v}=\mathit{v}$

注意：

• 最常见的 $K$ 即是 $\mathbb{R}$，但也可以是任何抽象的 field，只要满足 axioms 即可
• 仅讨论 set $V$ 和 set $K$ 的话：
  • 如果 $V\ne K$:
    • 那么 scalar multiplication $\mathbf{\cdot }:K\times V\to V$ 这个 operator 就不满足最基础的 Monoid 的要求，所以 $(V,\mathbf{\cdot },\overline{1})$ 就啥也不是
    • 但是 $(V,\mathbf{+},\overrightarrow{0})$ 构成 Abelian Group
  • 如果 $V=K$:
    • 你可以：
      • 假设 $\overline{1}=\overrightarrow{1}$
      • 假设 vector addition $\mathbf{+}$ 等价于 $\oplus$
      • 假设 scalar multiplication $\mathbf{\cdot }$ 等价于 $\otimes$
    • 但即使这样，也很难论证 $(V\setminus \{\overrightarrow{0}\},\mathbf{\cdot },\overrightarrow{1})$ 一定能构成 Abelian Group
      • 所以很难说 vector space 一定能构成 field
    • 但如果你反过来看，任意的 field $K$ 都能构成一个 vector space $(K,\oplus ,\overline{0},\otimes ,\overline{1}{)}_K$
      • 我们总结成：Any field is a vector space over itself.

Algebra $\Rightarrow$ Vector Space + Bilinear Vector Multiplication $\Rightarrow (V,\mathbf{+},\mathbf{\times },\overrightarrow{0},\mathbf{\cdot },\overline{1}{)}_K$Permalink

我们可以用 $(V,\mathbf{+},\mathbf{\times },\overrightarrow{0},\mathbf{\cdot },\overline{1}{)}_K$ 表示一个 Algebra，它满足：

• $(V,\mathbf{+},\overrightarrow{0},\mathbf{\cdot },\overline{1}{)}_K$ is a vector space over a field $(K,\oplus ,\otimes ,\overline{0},\overline{1})$
• vector multiplication $\mathbf{\times }:V\times V\to V$ is a bilinear mapping, i.e. it satisfies:
  1. Left distributivity w.r.t. vector addition: $\mathit{w}\mathbf{\times }(\mathit{u}\mathbf{+}\mathit{v})=\mathit{w}\mathbf{\times }\mathit{u}\mathbf{+}\mathit{w}\mathbf{\times }\mathit{v}$
  2. Right distributivity w.r.t. vector addition: $(\mathit{u}\mathbf{+}\mathit{v})\mathbf{\times }\mathit{w}=\mathit{u}\mathbf{\times }\mathit{w}\mathbf{+}\mathit{v}\mathbf{\times }\mathit{w}$
  3. Compatibility with scalars: $(\alpha \mathit{u})\mathbf{\times }(\beta \mathit{v})=(\alpha \beta )(\mathit{u}\mathbf{\times }\mathit{v})$

一般我们称：

• $V$ is an algebra over field $K$
  • or $V$ is a $K$-algebra
• $K$ is the base field of $V$

仅讨论 set $V$ 和 set $K$ 的话：

• 如果 $V\ne K$:
  • 类似 vector space 的讨论，$(V,\mathbf{\cdot },\overline{1})$ 还是啥也不是
  • 类似 vector space 的讨论，$(V,\mathbf{+},\overrightarrow{0})$ 还是能构成 Abelian Group
  • 但是 $(V,\mathbf{+},\mathbf{\times },\overrightarrow{0})$ 就很尴尬，因为没有 $\overrightarrow{1}$，所以它够不上 Semiring
    • 于是有的教材会强行要求 $\mathbf{\times }$ 的定义要带上 $\overrightarrow{1}$，使得 $(V,\mathbf{+},\mathbf{\times },\overrightarrow{0},\overrightarrow{1})$ 构成 Ring
      • 带有 $\overrightarrow{1}$ 的 Algebra 也称 Unitary Algebra
• 如果 $V=K$:
  • 类似地，任意的 field $K$ 都能构成一个 Algebra $(K,\oplus ,\otimes ,\overline{0},\otimes ,\overline{1}{)}_K$
    • 我们总结成：Any field is an algebra over itself.