集合论

第一课

overview, 离散数学研究的领域:

  1. 集合论, 图论
  2. 代数结构 - 研究各种代数的定律,交换律等等 组合数学-研究排列组合
  3. 数理逻辑-使用数理推理逻辑,

集合论包括: 集合、二元关系、函数、自然数、基数(势)

图论包括: 图、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配/覆盖/独立/匹配、带权图

逻辑演算: 命题逻辑演算,谓词逻辑演算

p q r 代表命题, 为真或者为假

  • ~ 否
  • v 或者
  • ^ 并且 合取式
  • -> 蕴含 implies
  • <-> 等价

以上存在优先级,从上至下。

  • 可满足
  • 矛盾式 永假
  • 重言式 永假

等值演算

A <=> B: A <-> B 是用真式

公式之间可以进行演算。

16 组等值演算律

  1. 幂等律 A <=> A v A , A <=> A ^ A
  2. 交换律 A v B <=> B v A, A ^ B <=> B ^ A
  3. 结合律 (A v B) v C <=> A v (B v C) / (A ^ B) ^ C <=> A ^ (B ^ C)
  4. 分配律
  5. 德摩根定律
  6. 吸收率
  7. 零律
  8. 同一律
  9. 排中律
  10. 矛盾律

值得记忆的是, 德摩根定律

~(A v B) <=> ~A ^ ~B

第二课

  1. 双重否定律
  2. 蕴含等值 A -> B <=> ~A v B
  3. 等价等值式
  4. 等价否定等值式 A <-> B <=> ~B <-> ~A
  5. 假言易位 A -> B <=> ~B -> ~A
  6. 归谬论 (A -> B) ^ (A -> ~B) <=> ~A (或者说,反证法经常用)

根据上面的等值式, 可以开始进行等值演算。

例子: p -> (q -> r)

重要的推理定律 9:00 若 A -> B 是永真式, 则 A => B

  1. 附加律
  2. 化简律
  3. 假言推理
  4. 拒取式
  5. 析取三段论
  6. 假言三段论
  7. 等价三段论
  8. 构造性两难

一阶谓词逻辑基本概念与命题符号化

全总个体域: 限定范围内所有的东西
量词: ForAll ThereExist
辖域:
指导变元:
自由变元:
约束出现:

有限个体域可以消去量词
量词可以进行否定 ~ForAqjjj1jjjjjjjjjjj:jkjkjkjlx A(x) <=> ThereExist ~A(x)
量词管辖域的收缩与扩张

第三课

等价 <=>
推理 =>
接着上一课仍然讲量词辖域的收缩与扩张

量词分配
ForAll(A(x) ^ B(x)) <=> ForAllA(x) ^ ForAll B(x)
ThereExist(A(x) v B(x)) <=> ThereE A(x) v ThereEB(x)

前束范式: 存在量词在最前面, 且作用到公式尾部。

重要的推理定律:

  1. ForA x A(x)v ForA B(x) => ForA (A(x) v B(x))
  2. ThereE x (A(x) ^ B(x)) => ThereE x A(x) ^ ThereE x B(x)
  3. ForA (A(x) -> B(x)) => ForA x A(x) -> ForA x B(x)
  4. ForA x (A(x) -> B(x) ) => ThereE x A(x) -> ThereE x B(x)

28:00 开始讲集合论

  1. 集合的概念
  2. 集合之间的关系
  3. 集合的运算
  4. 文氏图,容斥原理

谈到罗素悖论

集合的表示方法有哪些? 列举法/描述法/特征函数法/文氏图

谈到集合的概念, 集合用来定义数学基础。但是因为如果没有公理定义,则存在悖论。引出罗素悖论。所以谈到公理集合论,和朴素集合论。本课程是朴素集合论。

第四课

集合的运算方式

集合,子集,真子集,空集,幂集,n元集,指标集
交并补, 相对补集,对称差,绝对补,广义并,广义交

容斥原理, principle of inclusion/exclusion
主要是用于 counting, 可以说是用数论来计数,但是计算的是集合交集的运算方式。

AuB = A + A - A^B

第五课

集合恒等式,与等值演算类似。

11:00 提到对偶原理,用于讲解公式的对称性。

集合可以通过形式化的证明, 也就是讲集合转换成逻辑语句,然后进行等值演算。

28:00 讲解对称差的性质。也是对称差存在的一些定律。

43:00 特征函数与集合运算。

第六课

集族的一些性质,以及其证明

第七课 第二章

二元关系

有序对与笛卡尔集
有序三元祖, 有序 n 元组
笛卡尔集
笛卡尔集性质

36:00 开始讲解二元关系

A 上的二元关系。 举例来说, 三个元素存在多少种不同的二元关系。 512 种。 为啥? 3x3 ,然后从当中取出两个元素,也就是 2^9,512 种不同的取法。

第八课

一些特殊关系。

  • 空关系,
  • 恒等关系,
  • 全域关系,
  • 整除关系,
  • 小于等于,
  • 包含关系,
  • 真包含

二元关系有关的一些概念

  • 定义域(domain),值域(range),域(domain)
  • 逆(inverse),合成(compose)
  • 限制(restriction) 象(image)
  • 单根,单值

comments: 感觉这个部分,mit 的课程更加清晰一些。
injection, surjection, bijection, total, function

第九课

关系的表示/性质/闭包

关系的表示方法

集合,关系矩阵,关系图

关系矩阵在效率上存在一定的优势,关系图对理解层面,存在优势。

关系

自反,反自反,对称,反对称,传递

闭包

自反闭包,对称闭包,传递闭包

第十课

继续讲解关系当中,传递性

30:00 开始讲解闭包

一个对象刚开始不具备自反性,添加最小集合的元素,从而使对象具有自反性。
则,增加的这些元素的集合,称之为自反闭包。
以此类推。

第十一课

等价关系: 自反,对称,传递的二元关系。
具体实践有: 等价类,商集,划分,块,加细。
第二类, Stirling 数, Bell 数。

偏序关系:自反,反对称,传递的二元关系。

表达偏序关系使用哈斯图
特殊元素,链,反链。
线序,拟序,良序。

等价关系

R 是等价关系 <=> R 是自反的,对称的,传递的

提到 mod 关系。这个关系是等价关系。

A = {a,b,c} 上的全体等价关系有 5 种。

{a,b,c}/ {a},{b},{c},/ {a,b}, {c}/ {a,c},{b}/{b,c}, {a}

划分: partition

stirling 子集数 将 n 个不同的球放到 k 个相同的盒子,要求无空盒,不同放法的总数,称之为 striling 数。

30:00 左右开始讲划分

第十二课 偏序关系

3:00
partial order.
poset ,偏序集

12:00 哈斯图

  1. 用顶点表示 A 中元素。
  2. 当且仅当 y 覆盖(自然数当中,大于关系中,3 覆盖 2) x 时,y 在 x 上方,在 x 与 y 之间画无相边。
  3. 组织架构图可以理解为一种哈斯图

16:00 开始讲各种偏序关系的哈斯图的例子。

21:00 全序关系(线序关系) – 哈斯图是一条直线。

拟序关系: 反自反的,传递的 -> 反对称性

30:00 上确界, 下确界。

33:00 链, 反链 ,哈斯图当中的一个分支,就是一个链。

反链,就是链上元素互相都不可比较。

42:00 良序关系, well ordering principle…,良序集可以做数学归纳法
每一个集合都可以良序化。
良序原理 <=> 选择公理

第十三课 函数

偏函数: A 到 B 的偏函数 partial function – domF 属于 A ^ ranF 属于 B

全函数 total function: bijection + function

13:00 真偏函数
真偏函数,就是偏函数减去全函数

本节只讨论全函数。
单射: injection , F 是单根的。
满射: surjection, ran F = B
双射: bijection , 一一对应

函数的计数

33:00 image ,象与原象

特殊函数:

  • 常数函数 对于所有的 input, 输出均为常数
  • 恒等函数 对于所有的 input, 输出也为 x
  • 特征函数 对于所有的 input, 如果 x 属于 A, 则 output 为1, 否则为 0.
  • 单调函数 单调增, 单调减, input & output 是偏序集。
  • 自然映射/典型映射 一个元素对应到等价类,或者说等价关系。例如,所有男人都是渣男,看看谁谁谁都那么渣。

A = {a,b,c,d,}
A/R={{a,b},{c},{d}}
F:A -> A/R, F(x) = [x]
F(a) = {a,b},
F(b) = {a,b},
F(c) = {c},
F(d) = {d},

函数合成 fOg:A -> C; fOg(x) = f(g(x))

第十四课

反函数 f: A -> B f^-1: B -> A 是其反函数。

构造双射, 这个对应 mit 当中的 counting。这个很适合用来证明 countable and uncountable

19:00 单边逆,左逆, 右逆。

21:00 使用集合论定义自然数。

封闭性, A 在 F 函数下封闭,F(A) 属于 A , F: A -> A <=> F 是一元运算
例如: f: N -> N , f(x) = x+1

对于偶数不封闭, 对于 {2,3,4…} 封闭。

使用三元组定义自然数 <M,F,e> , F: M -> M ; Peano 系统

  1. e 属于 M( e for element)
  2. M 在 F 下封闭
  3. e 不属于 ranF
  4. F 是单射 injection
  5. A 属于 M ^ e 属于 A ^ A 在 F 下封闭 => A = M 极小性公理。

第五条: 如果 A 是 M 的子集, e 也属于 A, 并且 A 也在 F 下封闭, 那么 A 就是 M。
保证 M 是最小的, 或者说只有一个 M。

上面提出需求, 如何使用集合来实现上面的 peano 系统 ?

35:00 提到后继, A+ = A U {A} , 拥有 A 属于 A+, 并且 A 是 A+ 的子集

37:00 归纳集,空属于 A, 所有的 x, x 属于 A ,则 x+ 属于 A
A 是归纳集,A 含有空,且对后继封闭。

自然数是什么呢: 属于于每个归纳集的集合。 自然数集: 是包含于每个归纳集的集合.

问,所以自然数是有归纳集所拥有的性质吗?

所以,自然数的各种运算方式, 可以转换成集合的运算。

D = {v | v 是归纳集}
D 不是集合, 否则导致悖论! D 是类

自然数集 N = 广义交 D

N 是归纳集需要被证明

第十五课

5:00 证明 N 是归纳集

后继函数: 西格玛: N -> N, ForA n 属于 N,西格玛(n) = n+

自然数的定义是: <N, 西格玛, 0> 是 Peano 系统

28:00 传递集: 广义并属于其本身, 与之相对应的是归纳集。

42:00 开始用基本内容定义自然数的各种基本定律,或者说运算。

第十六课

基数

无穷集合如何比较大小?

A 与 B 等势。A 与 B 无穷集形成双射。

(0,1) 与 R 可以构造 bijection。

(0,1) 与 [0,1] 也可以构造双射。

hilbert 旅馆

6:40 讲如何让 0,1 开/闭区间建立一一映射。很有趣,值得一看。

x = 0, 对应 1/2
x = n, 对应 1/(n+2)
其他一一对应。

等势关系是一个等价关系。

12:00 N 与 R 不能等势
A 与 P(A) 不能等势。
28: 00 康托定理的证明
证明不可等势的一些方式方法。 uncountable 的一些方式方法。
对角化证明

公元前5世纪: 这句话是假的,悖论
公元13世纪: 我是说谎者。
1874: cantor 实数不可数。
1901: 罗素悖论 , 不以自身作为元素的集合的全体。
1931: 哥德尔不完全定理, 这句话没有证明。
哥德尔想表达的是,不是所有的东西都是有证明的。

1936: 图灵 停机问题是不可判定的。p np
任何东西都是一个字符串在计算机当中。所以计算机程序可以和自然数建立双射。
所以,实数比自然数多,所以存在一些 np 问题。
可能判定一个程序是否有 bug。也是使用对角线法证明。

对于所有的输入,形成矩阵,因为输入是无穷的,所以也就是一个无穷的矩阵。 这个时候,沿着对角线取反,形成新的输入,这个输入与任何的输入都不同, 所以输入是不可数的, 也就是说,停机问题不可解决。
证明了通用机的存在性。

第十七课

基数的定义 card A = card B, <=> A 与 B 可以建立双射。
有穷集 A card A = n <=> A 与 n 可以建立双射。
N card N = 阿列夫
实数集R, card R= 阿利夫1 = 阿列夫 0, 1, 2 … 阿列夫0, 阿利夫 都称作基数。

B 比 A 优势 <=> A 比 B 劣势 <=> 存在 f:A -> B 单射。
绝对优势, 绝对劣势。

第十八课

基数运算的定义。
10: 00 基数运算的一些性质。

17:00 连续统假设 CH
19:00 ZF系统
20:00 ZFC 系统
选择公理的等价形式。
25:00 well ordering principle 良序

序数

38:00 3n+1 猜想。

图论

第十九课

无序积,对应的概念是笛卡尔集(卡氏积)
(a,b)

A & B = {{a,b} | x 属于 A ^ y 属于 B }
(a,b) = (b,a)

使用无序积, 可以定义无向图。

G = <V,E> (Graph)
V != null, 顶点集
E 是 V & V 的子集。

有向边,形成有向边。
V !=- null.
D =- <V,E>
E 是 V x V 的子集。

顶点集 V(), 边集E()

V(G) = V, E(G) = E

V(D) = V, E(D) = E

有几个顶点,就是几阶。
有限,就是有限图。
没有边的图, 是零图。Nn (null graph)

一阶零图(平凡图),二阶零图 … n 阶零图

空图代表 V = null, E = null

标定图:各个 V 都有标记。可用于计数。
对应的概念就是非标定图。

基图(低图)由有向图去掉方向得出。

相邻: 有边连接的两个顶点。有公共顶点的两条边。
有向图中,邻接与,邻接到。

关联,以及关联次数。无向图中,两个邻接的顶点,两个顶点的关联次数都是1.
环的关联次数是2.
有向图,出是+1, 入是 -1。

环,只与一个顶点关联的边。
孤立点: 不与任何点产生关联的顶点。

平行边,端点相同的两条无向边,是平行边。
起点与终点相同的两条有向边,是平行边。

邻域,Ng(V) ,就是与 V 相邻的所有的其他的顶点。
闭邻域。 Ng[V]. 与 V 相邻的所有顶点,包括 V 本身。

– 相邻表示同类元素之间的关系,关联表示不同元素之间的关系。

关联集: Ig(V) = {e e 与 V 关联}

前驱与后继。和链表类似。

顶点的度: 与顶点 v 关联的边的数量. d()

出度, 入度。

有向图的度,是入度与出度之和。

最大度,就是图里面 V 最大的度。
最大出度,最大入度。最小度。

27:00 图论的基本定理: 握手定理
G=<V,E> 是无向图。 V = {v1,v2,v3…,vn}, |E|=m
则 d(v1) + d(v2) + d(v3) + … + d(vn) = 2m.

对于有向图, 则 d(v1) + d(v2) + d(v3) + … + d(vn) = m.

可以推断出: 奇数度的顶点的个数,一定是偶数

简单图(simple graph): 既没有环也没有平行边的图。

度数列: 不同顶点的度的数列。

可图化的: 非负整数度数列,如果度数列能够被表示出图,则度数列可图化。

可简单图化:
推断的第一种方法: d1 + d2 + d3 + … + dn = 0(mod2)
n-1 >= d1 >= d2 >= … >= dn >= 0 可简单图化 <=>
d’ = (d2-1, d3-1 … , dd1+1-1, dd1+2, …, dn) 可简单图化。
重复递推到平凡情况,得出是否可简单图化。

第二种方法:
d1 + d2 + d3 … + dn = 0(mod2)
并且对 r = 1,2,…,n-1 有
d1+d2+d3+…+dr <= r(r-1) + min{r,dr+2} + … + min{r, dn}.

介绍埃尔特希。

第二十课

图同构: 两个图能够完全重合。形式上讲,顶点可以双射。
~ =

当G1 的两个顶点存在边,那么对应的顶点也有存在边。
如何判定图同构?
NAUTY 算法。
提到零知识证明。

有向图同构。

17:00 图族

完全图, 有向完全图, 竞赛图
柏拉图图,彼得森图,库拉图斯基图
r 部图,二部图(偶图), 完全 r 部图
路径,圈,轮,超立方体

简单图中,边达到最大,则称之为完全图。
有向完全图,边数是无向的两倍。
无向完全图,给每个边添加上方向,形成竞赛图, 可以用来表达竞赛结果。

柏拉图图: 五种正多面体。

  • 正四面体
  • 正六面体
  • 正八面体
  • 正十二面体
  • 正二十面体

彼得森图: 中间一个五角星,外面套一个五边形。

库拉图斯基图(判定图是否能够被画成平面图):

  • 完全 2 部图 K3,3。
  • 完全图。

r 部图:
顶点集合可以分为 r 个部分, 每个部分的顶点不能相连。

2 部图:
偶图。

完全 r 部图

路径, paths, P1, 下标指代边数。
圈 , cycles , 就是有环路。
轮,wheel 在圈当中多一些轴心。有几个轴就是 W 几
超立方体。两个正方形,形成立方体,两个立方体,内外又可以嵌套。

子图。 G’ 是 G 的子图,就是
V’ 是 V 的子集, E’ 是 E 的子集。
真子图, 生成子图(顶点集和原图一样)。
导出子图,取出一部分的顶点,然后把这些顶点相关的边留下来。

补图: 完全图,拿掉简单图, 就形成了部图。

自补图: 图与其部图同构,则为自补图。

画图,可以先求度数列,然后根据度数列再画图。

图的运算:

  • 删除,收缩,加新边,不交。
  • 并图,交图,差图,环和。
  • 联图,积图。

删除,删除边直接删除,删除顶点需要同时删除其相关的边。
搜索,删除一个边后,两个相连的顶点合并。
加新边
两个图没有公共顶点,图不相交。

联图(join)不交无向图。
就是将两个图连起来。

积图(product)

第二十一课

图的连通性。

通路 walk, 起点,终点,通路长度。
顶点与边的交替序列, 是 walk。
回路。 closed walk, start v = end v.

simple walk: no repeat path.

element walk 初级通路 .没有重复顶点的通路。

element 初级回路。 没有重复顶点的回路。

可以用顶点序列表示通路(walk)。

G 是含圈的图。周长,最长圈的长度,就是图的周长。无圈的,周长要么为零,要么为无穷大。

最短圈的长度是围长。

在 n 阶图G中,若从不同顶点 vi 到 vj 有通路,则最多 n-1 条边。

极大路径法。
在无向简单图中,路径的两个端点不与路径本身以外的顶点相邻,这样的路径称之为极大路径。

扩大路径法。任何一条路径,只要不是,则至少有一个端点可以更大。

扩大路径法证明,如果每个顶点的度>=2. 则存在长度 >= 最小度数 + 1 的圈。

  • 联通 无向图, u v 之间有通路, 联通关系是等价关系。
  • 联通分支, 联通图的等价类。
  • 联通分支数, 等价类的个数。
  • 联通图, p(G) = 1. 就是联通图。
  • 短程线(测底线), u, v 之间最短距离。
  • 距离(短程线的长度), 两个点之间的通路长度。
  • 顶点之间的最大距离, 直径。两个点之间的最大距离。

距离函数:
满足两个点距离非负, 两个点对称, d(u,v) + d(v,w) >= d(u,w). 任何函数满足以上性质,那么就是一个距离函数。

G 是一个二部图 <=> G 中无奇圈。
证明: 使用染色法

二部图在资源分配是一个基本模型。
有一些对象,如何分配一些资源。

无向图是联通的, 则 G 的边数 m > n-1

图的联通度。

  1. 如何定量的比较连通性?

中央控制机构的连通性最差。

提到点连通度: 为了破坏连通性,至少需要删除多少个顶点?
边连通度: 至少要删除多少条边?

破坏连通性是什么?
– 联通分支数增加。

点割集, 最小的破坏连通性的集合。
一个点构成的点割集,就是割点。
边割集。

第二十二课

扇形割集。
割边,桥
扇形割集。

点连通度。最小的点割集的数量。
边连通度。同理。

k 连通图。至少要删除 k 个顶点,才能破坏连通性。
k 边连通图。

彼得森图是: 1/2/3-连通图。
但是不是 4 连通图。

1/2/3 边连通图。
边不交路径(edge-disjoint)路径。

K边连通的充分必要条件。
3阶以上的无向图 G 是 k 连通图,当且仅当 G 中 任意 2 低昂定剑佑 k 条以上独立路径。

block 块:极大无割点连通子图。

块的充分必要条件。

可达, reachable: 有向图某两个当中存在通路。
双向可达, 有向图某两个存在双向的通路。

单向连通。

竞赛图一定有初级通路(路径)过每个顶点,恰好一次。可用来排序。

强连通(双向连通),任何一对顶点双向可达。

单向连通,有向图 D 中有通路至少经过每个顶点一次。

强连通分支。单向连通分支,弱连通分支。

第二十三课

欧拉图与哈密顿图

欧拉图: 走过所有边一次,并且恰好一次。

欧拉被称之为有史以来最多产的科学家。

1736 年, 7桥问题,图论与拓扑学诞生。

每一个顶点的度都是偶数度,7 桥问题就被解决了。

经过图中所有的边的简单通路,就被称之为欧拉通路。
有欧拉通路的图,就是半欧拉图
经过图中搜有边的简单回路,就是欧拉回路。
有欧拉回路的图,就是欧拉图。

若欧拉回路总共 k 次经过顶点 v, 则 d(v)= 2k.

无向欧拉图的充要条件:
G是无向连通图,G 是欧拉图 <=> G 中所有的顶点都是偶数度。 <=> G 是若干个边不交的圈的并。

无向半欧拉图的充要条件:

G 中桥好有 2 个奇数度顶点。

有向欧拉图的充要条件:
有向半欧拉图的充要条件:

25:00 Fleury 算法(避桥法)可以得到欧拉回路。

欧拉回路的应用之一: 轮盘设计

41:00 哈密顿图: 走过顶点,并且恰好一次。

哈密顿通路: 经过图中所有顶点的初级通路。
有哈密顿通路的图,就是半哈密顿图
哈密顿回路: 经过所有顶点的回路。
有哈密顿回路的图。

目前没有简单判断是否为哈密顿图的算法。

目前没有充分必要条件。

必要条件:
p(G-V1) <= |v1|

半哈密顿图的必要条件
p(G-V1) <= |v1| + 1

有向哈密顿图充要条件。
有向半哈密顿充要条件。

二十四课 树

代数结构

第三十五课

现代数学的特点

结构与分析
学科的交叉: 运筹学与管理学,离散数学与计算机科学
确定性与非确定性的交叉: 离散概率

CS: computer Science IS: Information System CE: Computer Engineering SE: Software Engineering

研究离散个体以及其结构。

数理逻辑主要研究推理,以及逻辑, 形式化证明。
集合论,主要是表示方法。

组合数学, 是离散结构的存在性。如何计数?如何枚举?如何优化?

28:00 离散数学的知识架构图。

数理逻辑: 人工智能,程序正确性证明及验证。
集合论: 关系数据库模型
图论: 数据结构,数据库模型,网络模型。
代数结构: 软件规约,形式化语义,编译系统,编码理论,密码学,数据仓库
组合数学: 算法设计与分析,编码理论,容错。

30:00 汉诺塔问题。指数爆炸。涉及到组合数学问题。

数据仓库的视图格: OLAP 联机分析处理。如何组织视图,才能够让查询足够快?
每一个聚类就是一个划分,多个维度,再进行笛卡尔积。再形成一个格结构。
引出格的结构。

进程的资源共享模型。命题的迁移,与图有关。

第三十六课

代数系统的基本概念 – 8 学时

  • 二元运算的性质
  • 代数系统的构成
  • 子代数与积代数
  • 代数系统的同态与同构
  • 代数系统上的同余关系与商代数

半群,独异点与群 – 12 学时

  • 半群与独异点的定义与性质
  • 群的定义与分类
  • 群的基本性质
  • 子群
  • 循环群
  • 变换群
  • 置换群
  • 群的分解(陪集分解与 Lagrange 定理,共轭类分解与分类方程)
  • 正规子群
  • 商群及性质
  • 群的同态与同构
  • 群的直积

环与域

  • 环的定义及基本性质
  • 特殊的环
  • 子环
  • 理想
  • 商环及环同态 格与布尔代数
  • 格的定义与性质
  • 子格
  • 格同态与格的直积
  • 特殊的格
  • 布尔代数

代数结构的组成

  1. 载体
  2. 运算
  3. 公理

在以上的基础上,如何构成新的东西。 由已知的代数系统构成新的代数系统。

  1. 子集: 子代数
  2. 不同的代数系统进行笛卡尔积: 积代数
  3. 等价关系: 商代数

通过映射,可以映射到另外一个代数系统。
那么代数系统就是同构的。
通过同态,同构,可以把一些些系统理解为同样的系统。
比如说线性代数系统和自然数可以理解为同构的

对代数系统的典型应用系统研究:

  1. 半群与群,包含一个运算 只有一个二元运算
  2. 环域, 包含两个运算
  3. 格与布尔代数

进一步可以推广至 西格玛代数: 理解下来感觉就是不封闭的。

二元运算以及性质

f:AxA -> A 称之为为 A的二元运算。
0元, 就是选择一个元素。
1元, 针对一个元素的操作, 比如说取反。
2元, 乘法,加法等。

算律

和一个运算相关的

  • 交换律
  • 幂等律
  • 结合律
  • 消去律

和两个及多个元素有关

  • 分配律
  • 吸收率

特异元素

  • 单位元
  • 零元
  • 可逆元素

第三十七课

二元运算的性质体现为两类

  1. 算律
  2. 特异元素

幂等律: a o a = a

特异元素

特异元素名称:

  • 单位元 幺元,e ( eoa = a0e = a, 比如说自然数当中的 + 和 0 )
  • 零元 0 ( aoa = a00 = 0 , 比如说 0 和 x )
  • 幂等元 (aoa = a ,乘法有两个幂等元, 0,1)
  • 可逆元和逆元 (存在单位元的系统, xoy = yoa = e )

打个比方: 加法当中, 单位元是0,没有零元,幂等元也是0,逆元就是正数与负数。
乘法当中,单位元是 1, 零元是 0, 幂等元是 1,0. 逆元就是自然数及其倒数。

特异元素有时候也可以作为算律

  • 同一律(存在单位元)
  • 零律(存在零元)

单位元与零元在整个系统当中具有唯一性。
若存在逆元,针对元素其唯一。

第三十八课

形式化的记法: V = < A, 欧米茄, K >
A: 载体, 比如说集合。
欧米茄: 运算集,非空
K: 代数常数集

V = < A, 欧米茄 >

从高元到低元进行列举
V = < A, o1, o2, o3, … on >

例子

  • < Z, +, * >
  • < Zn, mod+,mod * > …

同类型的: 构成成分相同。
同种的: 构成成分与公理都相同。

22:00 子代数
B 是某代数系统的非空子集。 若 B 对于 A 中所有的运算封闭, 则 B 是 A 的子代数。

子代数与原系统是同种的系统。
子代数一定存在。

29:00 积代数
两个代数系统, 做笛卡尔积。

运算相当于对与对的运算。