离散数学-自然数和基数

自然数和基数

后继集合:对于任意集合A,其后继集合\(A^+\)定义为:\(A^+=A\cup\{A\}\)

\(i)\emptyset^+=\{\emptyset\}\)

\(ii)\{\emptyset\}^+=\{\emptyset,\{\emptyset\}\}\)

\(iii)A\in A^+\)

\(iv)A\subseteq A^+\)

\(v)A^+\neq \emptyset\)

自然数系统

冯诺依曼方案

\[ \begin{aligned} &0=\emptyset\\ &1=0^+=\{\emptyset\}=\{0\}\\ &2=1^+=\{\emptyset,\{\emptyset\}\}=\{0,1\}\\ &...\\ &n+1=n^+=...=\{0,1,...,n\} \end{aligned} \]

自然数集合(归纳定义法)

\[ \begin{aligned} &i)0\in N,0=\emptyset\\ &ii)n\in N,n^+\in N\\ &iii)S\subseteq N满足\\ &\ 1)0\in S\\ &\ 2)如果n\in S,则n^+\in S\\ &\ 则S=N \end{aligned} \]

大小/小于

对每个自然数\(n\in N\),皆有\(n\in n^+\)及\(n\subseteq n^+\)

若\(m,n\in N\)使得\(m\in n\),则称m小于n,记为\(m<n\)

定理

\(proof:\forall n\in N:\bigcup n^+=n\) \[ \begin{aligned} &S=\{n|n\in N且\bigcup n^+=n\}\\ &1)0\in S:0\in N且\bigcup\{\emptyset\}=\emptyset=0\\ &2)若n\in S,则\bigcup n^+=n且n\in N\\ &\therefore n^+\in N,\bigcup((n^+)^+)=\bigcup(n^+\cup\{n^+\})\\ &=(\bigcup n^+)\cup(\bigcup\{n^+\})=n\cup n^+=n^+\\ &\therefore n^+\in S \end{aligned} \]

皮亚诺公理

\[ \begin{aligned} &1)0\in N\\ &2)n\in N,则有唯一的后继n^+\in N\\ &3)n\in N,则n^+\neq 0\\ &4)n,m\in N且n^+=m^+,则n=m\\ &5)若S\subseteq N满足i)0\in S,ii)如果n\in S,则n^+\in S\\ &则S=n \end{aligned} \]

第一数学归纳法

P(n)是自然数集合上的性质(或谓词),如果能证明

1)\(P(0)\)是真

2)对任何\(n\in N\),\(P(n)\Rightarrow P(n^+)\)

则对所有\(n\in N\),P(n)为真

即:

\(P(0)\wedge (\forall n)(P(n)\rightarrow P(n+1))\Rightarrow (\forall n)P(n)\) \[ \begin{aligned} &S=\{n|n\in N,P(n_0+n)为真\}\\ &0\in S:0\in N且P(n_0+0)为真\\ &若n\in S,则n\in N且P(n+n_0)为真\\ &因为:n_0+n^+=(n_0+n)^+\\ &因此:P(n^++n_0)为真,n^+\in S \end{aligned} \]

第二数学归纳法(强归纳定理)

\(\forall n\in N,令\overline{N_n}=N-N_n=\{n,n+1,n+2,...\}\)

\((\forall n)((\forall k)(k<n\rightarrow P(k))\rightarrow P(n))\Rightarrow (\forall x)P(x)\) \[ \begin{aligned} &Q(n):若k\in N且n_0\leq k\leq n,则P(k)为真\\ &Q(n)满足第一归纳法\\ &显然Q(n_0)即为真,所以Q(n_0)为真\\ &假设对任意n\in\overline{ N_{n_0} },Q(n)为真\\ &若k\in N且n_0\leq k\leq n,则P(k)为真\\ &因此,当k\in N且n_0< n^+时,P(k)也皆为真\\ &P(n^+)为真,表明Q(n^+)为真\\ &根据第一归纳法,对任意n\in \overline{ N_{n_0} },P(n)为真 \end{aligned} \]

二重归纳原理

设\(i_0,j_0\in N\),假定对任意自然数\(i\geq i_0\)及\(j\geq j_0\)皆有一个命题\(P(i,j)\)满足:

1. \(P(i_0,j_0)\)真
2. 对任意自然数\(k\geq i_0,l\geq j_0\),若\(P(k,l)真,则P(k+1,l)和P(k,l+1)\)皆真

则对任意自然数\(i\geq i_0,j\geq j_0,P(i,j)\)皆真

基数

等势

从A到B的双射,则称A和B相等/等势,记为\(A\sim B\)

无穷集合可以与它本身的真子集等势

鸽笼原理

任何有限集都不能与它的真子集对等

任何与自身真子集等势的集合均是无穷集合

集合的基数

\(设n\in N,A\sim n,则\sharp(A)=n\)

无限集的基数:\(\sharp(N)=\aleph_0\)

任意两个基数都可以比较大小

相等和大小顺序

1. 如果\(A\sim B\),就称A和B的基数相等,记作\(\sharp(A)=\sharp(B)\)
2. 如果存在从A到B的单射,就称A的基数小于等于B的基数,记作\(\sharp(A)\leq\sharp(B)\)

无穷集的等价条件

以下三个条件等价:

1. A为无穷集
2. A有可数无穷子集
3. A有与它对等的真子集

\[ \begin{aligned} &1)\rightarrow 2)\\ &设A为无限集,取a_0\in A,对每个n\in N,若\{a_0,a_1,\dots,a_n\}\subseteq A,\\ &则必有a_{n+1}\in A且a_{n+1}\notin \{a_1,a_2,\dots,a_n\},因此,B=\{a_i|i\in N\}即为A的可列子集\\ &2)\rightarrow 3)\\ &A无穷,\therefore A\neq \emptyset\\ &任取a_1\in A\\ &再取a_2\in A-\{a_1\}\\ &\dots\\ &C=\{a_1,a_2\dots,a_n,\dots\}\\ &A=C\cup (A-C)\\ &A^`=(C-\{a_1\})\cup(A-C)\\ &设f:A\rightarrow A^`\\ &f(x)=\begin{cases}x,x\in A-C\\a_{i+1},x=a_i\end{cases} \end{aligned} \]

定理

• 任何无穷集合必含有可数无穷子集
• 实数集合R是不可数的
• 对每个集合A,皆有\(\sharp(A)<\sharp(\rho(A))\)
• \(\sharp(R\times R)=\aleph\)

例

取52个整数,必有两数之和或两数之差,被100整除

\[ \begin{aligned} &在51个抽屉:\{0\},\{1,99\},\{2,98\},\dots\{49,1\},\{50\}中选取52个整数\\ &必有两个整数r_a\mod 100,r_b\mod 100正好落在同一抽屉中\\ &a)r_a=r_b,则(r_a-r_b)|\ 100\\ &b)r_a\neq r_b,则(r_a+r_b)|\ 100 \end{aligned} \]

A=[0,1],B=(0,1),构造A到B的双射

\[ C=\{a_0,a_1,a_2,\dots a_i,\dots\}\\ (0,1)=C\cup\{(0,1)-C\}\\ C^`=(C-\{a_0,a_1\})\cup\{(0,1)-C\}\\ f:C\rightarrow C^`\cup\{0,1\}\\ f(x)=\begin{cases} a_0,x=0\\ a_1,x=1\\ a_{i+2},x=a_{i+1}\\ x,其他\\ \end{cases}\\ \]

\(\sharp(R)=\aleph\)

\[ \begin{aligned} &f:\mathscr P(N)\rightarrow [0,1]\\ &f(A)=\sum^\infty_{i=0}\frac{\chi_A(i)}{2^{i+1} },A\subseteq N\\ &f是满射,所以\sharp([0,1])\leq \aleph\\ &g:\mathscr P(n)\rightarrow [0,1]\\ &g(A)=\sum^\infty_{i=0}\frac{\chi_A(i)}{3^{i+1} },A\subseteq N\\ &若A,B\subseteq N且A\neq B,A\oplus B\neq \emptyset,i_0是A\oplus B的最小元素\\ &则\left|g(A)-g(B)\right|\geq \frac{1}{3^{i_0+1} }-\sum^{\infty}_{j=2}\frac{1}{3^{i_o+j} }>0\\ &\therefore g(A)\neq g(B)\\ &因此g是内射\\ &\aleph\leq \sharp([0,1])\\ &所以\sharp([0,1])=\aleph,但\sharp([0,1])=\sharp(R)\\ &\sharp(R)=\aleph \end{aligned} \]

设集合\(S=\{x|x\in(0,1)\}\)

\[ \begin{aligned} &假设S可数,把S的元素排列成无穷序列S_0,S_1,\dots,S_n,\dots\\ &已知S_i是0和1之间的实数,任何小于1的正数s可以表示为:\\ &s=0.y_1y_2y_3\dots\\ &这里y_i\in\{0,1,2,\dots,9\}\\ &S_0=0.a_{11}a_{12}a_{13}\cdots\\ &S_1=0.a_{21}a_{22}a_{23}\cdots\\ &构造一个实数r=0.b_1b_2b_3\cdots b_n\cdots\\ &若a_{jj}\neq 1,则取b_j=1;若a_{jj}=1,则取b_j=2\\ &r\notin S,导致矛盾,因此S是不可数的\\ &因为R和S是等势的,R也是不可数的\\ \end{aligned} \]

与集合R等势的集合的基数,用\(\aleph\)来表示,并称为连续统的势,#\(\rho(N)\)记为\(\aleph\)

#\((R\times R)=\aleph\)

\[ \begin{aligned} &证明:即证\text{ \sharp}([0,1)\times[0,1))= \text{ \sharp}([0,1))\\ &不妨设x=0.x_1x_2\dots\\ &y=y_1y_2\dots\\ &f(x,y)=0.x_1y_1x_2y_2\dots\\ &若存在f(x',y')=0.x_1'y_1'x_2'y_2'\dots=f(x,y),\\ &则x_1=x_1',y_1=y_1',\dots,故f为单射\\ &对于任意z=z_1z_2z_3\dots\in[0,1)\\ &存在x=z_1z_3\dots z_{2i+1}\dots,y=z_2z_4\dots z_{2i}\dots,\\ &使得f(x,y)=z\\ &因此f是满射\\ &所以\sharp([0,1)\times[0,1))=\sharp([0,1))\\ \end{aligned} \]

\(Q_+\sim N_+\)

正有理数到正整数

"小于"的定义

若#A=\(\alpha\),#B=\(\beta\),且A\(\prec\)B,则称\(\alpha\)小于\(\beta\),记为\(\alpha<\beta\)