代数结构与数理逻辑-学习笔记
代数结构与数理逻辑 学习笔记
第零部分 导论
卷积
记 $(a_0,a_1,a_2…) = (a_k)$.
两个序列 $(a_k)$ 和 $(b_k)$ 的卷积是序列 $(c_k)$ , $c_n=\sum^{n}{i=0}a_i b{n-i}$.
考虑序列 $\epsilon_0=(1,0,0,0,…)$. 任何序列 $(a_k)$ 与 $\epsilon_0$ 做卷积，结果仍为 $(a_k)$，和数的乘法中的 1 类似.
考虑序列 $\epsilon_1=(1,1,1,1,…), \epsilon_2=(1,-1,0,0,…)$，则 $\epsilon_1$ 与 $\epsilon_2$ 的卷积等于 $0$，$\epsilon_1=\epsilon_2^{-1}$, ( $\epsilon_1$ 与 $\epsilon_2$ 互为逆元 ).
线性空间
$\mathbb{R}^n={(a_1,a_2,…)|a_i\in\mathbb{R}}$
有加法 $(a_1,a_2,…,a_n)+(b_1,b_2,…,b_n)=(a_1+b_1,a_2+b_2,…,a_n+b_n)$
有数乘 $\lambda(a_1,…,a_n)=(\lambda a_1,…,\lambda a_n)$
$\vec{0}=(0,0,…0)$.
加法和数乘满足以下性质：
（1）结合律：$(\vec{a}+\vec{b})+\vec{c}=\vec{a}+(\vec{b}+\vec{c})$.
（2）$\vec{0}$ : $\vec{a}+\vec{0}=\vec{0}+\vec{a}=\vec{a}$.
（3）$\forall \vec{a} \in \mathbb{R}^n, \overrightarrow{a}+\overrightarrow{-a}=\vec{0}$.
（4）交换律：$\vec{a}+\vec{b}=\vec{b}+\vec{a}$.
前三条（1）（2）（3）：$(\mathbb{R},+)$ 做成群
加上（4）：$(\mathbb{R},+)$ 是交换群
（5）分配律：$(\lambda+\mu)\vec{a}=\lambda \vec{a}+\mu \vec{a}$.
（6）分配律：$\lambda(\vec{a}+\vec{b})=\lambda \vec{a} + \lambda\vec{b}$.
（7）$\lambda(\mu \vec{a})=(\lambda\mu)\vec{a}$.
（8）$1 \cdot \vec{a}=\vec{a}$.
（7）（8）：群作用
二元关系
$(a,b)$ 有序对
$X, Y, X \times Y={(a,b)|a\in X,b\in Y}$.
$X\times Y$ 的任何一个子集 $R\subseteq X\times Y$ 称为 $X$ 到 $Y$ 的一个二元关系.
二元关系 $R,T$
$Dom®={a|\exist b,s.t. (a,b)\in R}$.
$Ran®={b|\exist a, s.t.(a,b)\in R}$.
$R^{-1}={(b,a)|(a,b)\in R}$.
二元关系可以复合
$T\circ R={(a,c)|\exist b,s.t.(a,b)\in R,(b,c)\in T}$. 从右到左复合.
$(R^{-1})^{-1}=R, (T\circ R)^{-1}=R^{-1}\circ T^{-1}$.
设 $f$ 是二元关系，且 $\forall (a,b),(c,d)\in f$，只要 $a=c$，就有 $b=d$，则 $f$ 是一个映射（一个原像只能有一个像）.
等价关系
$\mathbb{Z}$ 按照奇偶性
$a \sim b \iff a$ 和 $b$ 的奇偶性相同
$M_{m,n}(\mathbb{R})={A|A是m行n列的实矩阵}$
$A\sim B\iff A和B有相同的秩\iff 存在m阶可逆阵P和n阶可逆阵Q，s.t.B=PAQ$
设 $X$ 是集合，$\sim$ 是 $X$ 上的一个二元关系，且下面三条性质成立
（1）自反性 $\forall x\in X, x \sim x$.
（2）对称性 $\forall x,y\in X$，若 $x \sim y$，则 $y\sim x$.
（3）传递性 $\forall x, y,z\in X$，若 $x\sim y,y\sim z$，则 $x\sim z$.
则称 $\sim$ 是 $X$ 上的一个等价关系.
$\forall x\in X, [x]={y|y\in X,x \sim y}$.
命题：
设 $\sim$ 是 $X$ 上的等价关系，则 $\forall x\in X$，有 $x\in [X]$，并且对 $a,b\in X$，下面三个论断等价：
（1）$[a]\cap [b]\ne \varnothing$.
（2）$a\sim b$.
（3）$[a]=[b]$.
证明：
$\forall x\in X, x\sim x, x\in [x]$.
$(1)\Rightarrow(2)$
取$x\in [a]\cap[b]$
$\because x\in[a] \therefore a\sim x$
$\because x\in[b] \therefore b\sim x$
由传递性，$a\sim x\sim b$
$(2)\Rightarrow(3)$
来证 $[a]\subseteq[b],[b]\subseteq[a]$.
只证明 $[a]\subseteq[b]$，$[b]\subseteq[a]$ 类似
$\forall x\in[a], a\sim x$
$\because a\sim b \therefore b \sim a$.
由传递性 $b\sim x$.
$\therefore x\in[b]$.
$(3)\Rightarrow(1)$
由 $a\ne \varnothing$ 显然.
数系的扩充
$\mathbb{N}\subset \mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}\subset …$
群
Def 11.1.1 设 $S$ 为非空集合，$\cdot$ 为 $S$ 上的二元运算，如果 $\cdot$ 满足结合律，即对 $\forall a,b\in S$ ，有 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ ，那么称 $(S,\cdot)$ 为半群，简称 $S$ 为半群.
Def 11.1.2 设 $(s,\cdot)$ 为半群，如果在 $S$ 中存在元素 $e$，使得对 $\forall a\in S$，有$a\cdot e=e\cdot a=a$，那么称 $(S,\cdot)$ 为幺半群，简称 $S$ 为幺半群. 称 $e$ 为 $S$ 的幺元，经常把 $e$ 记为 $1$.