符号注释

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【符号注释】本表覆盖原书符号表,按用途分组便于查找;同一符号在不同章节可有不同意义,以当处定义为准。N={0,1,2,…};集合真包含统一写⊊,避免⊂在不同文献中两种解释。图、关系、代数的上下标应保留,不能用相似字母随意替换。

【逻辑与偏序】∧:合取,在格中亦表示最大下界;∨:析取,在格中亦表示最小上界;¬:否定;→:蕴涵联结词;↔:等价联结词;⇒:元语言的推出;⇔:等值或当且仅当;∀:全称量词;∃:存在量词;∀−、∀+:全称消去、全称引入;∃−、∃+:存在消去、存在引入。规则必须符合第19章的新参数与防捕获条件。≼:偏序,≺:对应严格偏序。p*:对偶命题。

【数集】Z:整数;Z⁺:正整数;Z*:非零整数;Zₙ:模n剩余类集合,常以{0,…,n−1}作代表;Q、Q⁺、Q*:有理数、正有理数、非零有理数;R、R⁺、R*:实数、正实数、非零实数;C:复数;∅:空集;E:当前论域中的全集。星号表示非零数时与其他章节的对偶、字符串闭包不同。

【集合与基数】∈、∉:属于、不属于;⊆:包含于,允许相等;⊊:真包含;P(A):A的幂集;⋃𝒜、⋂𝒜:集族的广义并、广义交;(x,y)或⟨x,y⟩:有序对;A∪B、A∩B:并、交;A−B:从A除去B,即B对A的相对补;Ā或~A:相对已指定全集的绝对补;A×B:笛卡儿积;A⊕B:对称差。

|A|、card A:A的基数,有限时为元素数;ℵ₀:自然数集基数;原表用ℵ表示实数集基数,此处明确记,不能未经连续统假设就写ℵ₁。A≈B:等势;“B优势于A”表示A可单射到B,真优势另要求不等势;Bᴬ:从A到B的所有函数构成的集合,即“B上A”。:子集A′的特征函数。

【关系】:A上的恒等关系;:A×A上的全域关系;:关系矩阵;:关系图;dom R、ran R、fld R:定义域、值域、关系的域,fld R=dom R∪ran R;R⁻¹:逆关系;Rⁿ:n次关系复合;r(R)、s(R)、t(R):自反、对称、传递闭包;R↾A:定义域限制到A;R[A]:A在R下的像;[x]:等价类;[x]ₘ:模m等价类;x~y:x等价于y;A/R:等价关系R的商集。

F○G:右复合,先F后G,函数情形(F○G)(x)=G(F(x))。与不少文献的左复合约定相反,尤其置换与电话系统不能套错。第19.4节另用A◁R、R▷B表示定义域和值域限制。

【函数】f:A→B:从A到B的全函数;x↦y:f(x)=y;f(x):函数值;f(A′):子集A′的像;f⁻¹(B′):子集B′的原像,不要求f可逆;当f为双射时f⁻¹也可指逆函数,需看语境。a⁺:后继;|x|:绝对值;⌊x⌋、⌈x⌉:向下、向上取整;max(x,y)、min(x,y):较大、较小者。

【代数】e:单位元;θ:零元;x⁻¹:逆元;−x:加法负元;x′:格的补元;x⊕y、x⊗y:模n加与模n乘,模数应预先给定。Mᵀ:矩阵转置;det M:行列式;Mₙ(R):n阶实矩阵集合;⟨a⟩、⟨B⟩:由元素a、集合B生成的子群;H≤G、H<G:子群、真子群;[G:H]:子群指数。V₁≅V₂:代数系统同构;原表以V₁~V₂表示V₂是V₁的同态像,此处以V₁↠V₂强调满同态方向,不能把同态像误当双向同构。

【图的集合与运算】V(G)、E(G):顶点集、边集;G[V₁]:顶点集V₁导出子图;G[E₁]:边集E₁导出子图;G₁∪G₂、G₁∩G₂、G₁−G₂:并图、交图、差图;G∪(u,v)或G+(u,v):加边;G−v、G−V′:删除顶点及其关联边;G−e、G−E′:删除指定边;G\e:收缩边e;G₁⊕G₂:图的环和;Ḡ:补图;T̄:生成树T的余树,取同一母图中不在T内的边;G₁≅G₂:图同构。

【特殊图】Nₙ:n阶零图;Kₙ:n阶无向完全图;:两部分顶点数r、s的完全二部图;Wₙ:本书n阶轮图,总顶点数n,外围圈有n−1个点,不能套用以外围点数为下标的其他定义。

【度、距离与邻域】(v):无向图度数,自环计两次;(v)、(v)、(v):有向图出度、入度及二者和;Δ(G)、δ(G):最大、最小度;Δ(D)、δ(D):有向图最大、最小总度;Δ⁺(D)、δ⁺(D):最大、最小出度;Δ⁻(D)、δ⁻(D):最大、最小入度;d(u,v):u到v距离,有向图须沿方向,通常不对称;(v):v关联的边集;(v)、(v):开邻域;(v)、(v):原表的闭邻域,亦可记N[v];(v)、(v):先驱元集、后继元集。

【图的参数】ξ(G):圈秩;η(G):割集秩;κ(G):点连通度;λ(G):边连通度;χ(G)、χ′(G)、χ*(G):点色数、边色数、面色数;α₀(G):点覆盖数;α₁(G):边覆盖数;β₀(G):点独立数;β₁(G):匹配数或边独立数;γ(G):支配数。不同教材常交换α、β的习惯,本文坚持本书约定。边覆盖等参数须满足该节的图模型与存在条件。

【数论】φ(n):欧拉函数;gcd(x₁,…,xₙ)、lcm(x₁,…,xₙ):最大公因数、最小公倍数;b∣a、b∤a:b整除、不整除a;a≡b (mod m)、a≢b (mod m):模m同余、不同余;a⁻¹ (mod m):模逆,只有gcd(a,m)=1时存在;x mod n:除以正n的标准非负余数。模逆与普通实数倒数不同。

【计数】Pₙʳ=n!/(n−r)!:n元集r排列数;Cₙʳ或:r组合数,0≤r≤n;:多项式系数,nᵢ≥0且和为n;:无符号第一类斯特林数;:第二类斯特林数;(i₁i₂…iₖ):k阶轮换,乘积遵循右作用顺序。hₙ:原书卡塔兰数的下标约定,常见章节取hₙ=Cₙ₋₁;fₙ:原书斐波那契数,使用前核对初值,不能和F₀=0、F₁=1的另一套下标无说明混用。