SchoolWork-LaTeX/离散数学/平时作业/第十三周作业.tex

\documentclass[全部作业]{subfiles}

\pagestyle{fancyplain}
\fancyhead{}
\fancyhead[C]{\mysignature}
\setcounter{chapter}{6}
\setcounter{section}{1}

\begin{document}
    \section{集合的基数}
    \label{cardinality}
    \begin{enumerate}
        \item 集合$\{ x\ |\ x\in \mathbb{Z},\text{且}x\text{不能被3整除} \}$是否是可数集？若是，则给出自然数集$\mathbb{N}$与它之间的一个一一对应。
        \begin{proof}[解]
        \begin{zhongwen}

            将给定的集合记为$A$，它是可数集。

            给出一一对应的函数如下：
            $$
            f\colon \mathbb{N} \to A, x \mapsto \begin{cases}
            \displaystyle (-1)^{\left\lfloor \frac{x}{2} \right\rfloor}\times 3 \left\lfloor \frac{x+2}{4} \right\rfloor + 1 , & x为偶数,x\geqslant 0 \vspace{1em} \\
            \displaystyle (-1)^{\left\lfloor \frac{x}{2} \right\rfloor}\times 3 \left\lfloor \frac{x+2}{4} \right\rfloor + 2 , & x为奇数,x\geqslant 0 \\
            \end{cases}
            $$
        \end{zhongwen}
        \end{proof}

        \item 设集合族$\{ A_n\ |\ n\in \mathbb{N} \}$和$\{ B_n\ |\ n\in \mathbb{N} \}$中的集合都是两两不相交的（$i\neq j$时$A_i\cap A_j=\varnothing $，$B_i\cap B_j=\varnothing $），且对任意$n\in \mathbb{N}$，$A_n\sim B_n$。请证明$\displaystyle \bigcup_{n\in \mathbb{N}} A_n \sim \bigcup_{n\in \mathbb{N}} B_n$。
        \begin{proof}
        \begin{zhongwen}
            
        对于$\forall n\in \mathbb{N}$，$A_n\sim B_n$，所以存在一一对应的$f_n: A_n \to B_n$。

        那么可以定义$f$如下：
        $$
        f\colon \bigcup_{n\in \mathbb{N}} A_n \to \bigcup_{n\in \mathbb{N}} B_n, x \mapsto \begin{cases}
        f_1(x) , & x\in A_1 \\
        f_2(x) , & x\in A_2 \\
        \cdots , & \cdots \\
        f_n(x) , & x\in A_n \\
        \end{cases}
        $$

        因为$\{ A_n\ |\ n\in \mathbb{N} \}$两两不相交，所以$f$是一个函数，下面证明$f$是一一对应的。

        对于任意的$\displaystyle y \in \bigcup_{n\in \mathbb{N}} B_n$，由于$\{ B_n\ |\ n\in \mathbb{N} \}$两两不相交，则必定存在唯一的$ i \in \mathbb{N}$使得$y \in B_i$，而$f_i:A_i \to B_i$是一一对应的，所以必定存在唯一的$\displaystyle x\in A_i \subseteq \bigcup_{n\in \mathbb{N}} A_n$使得$f(x)=y$，因此$f$是一一对应的。

        由于构造出了$\displaystyle \bigcup_{n\in \mathbb{N}} A_n$和$\displaystyle \bigcup_{n\in \mathbb{N}} B_i$之间的一一对应的函数，所以$\displaystyle \bigcup_{n\in \mathbb{N}} A_n \sim \bigcup_{n\in \mathbb{N}} B_n$。

        \end{zhongwen}
        \end{proof}

        \item 设$F$是$X$到$Y$的所有函数所组成的集合，$F=\{ f\ |\ f:X \to Y \}$，$\left\vert X \right\vert =n$。证明$F\sim Y^{n}$ \label{functioncardinality}。
        \begin{proof}
        \begin{zhongwen}

            对于$\forall f \in F$，$f$都唯一对应于一个$\left\vert X \right\vert $行$\left\vert Y \right\vert $列的关系矩阵，并且每行有且仅有一个1。
            那么每一行这个1的位置有$\left\vert Y \right\vert $种情况，一共有$\left\vert X \right\vert $行，所以一共有$\left\vert Y \right\vert ^{\left\vert X \right\vert }=\left\vert Y \right\vert ^{n}$种情况。
            所以$\left\vert F \right\vert =\left\vert Y \right\vert ^{n}$。

            $Y^{n}$表示集合的笛卡尔积，所以有$\left\vert Y \right\vert ^{n}=\left\vert Y^{n} \right\vert $。

            所以$\left\vert F \right\vert =\left\vert Y \right\vert ^{n}=\left\vert Y^{n} \right\vert $，所以$F\sim Y^{n}$。

        \end{zhongwen}
        \end{proof}

        \item *证明无限可数集的所有有限子集组成一个可数集。
        \begin{proof}
        \begin{zhongwen}
            
            设$A$为无限可数集，则$A$可以和$\mathbb{N}$一一对应，所以可以将$A$记为$\{ a_i\ |\ i\in \mathbb{N} \}$。

            对于$\forall M \in \mathbb{N}$，取$B_{M}=\{ a_i\ |\ i\in \mathbb{N},i\leqslant M \}$，则$A$的所有有限子集可以记作
            $$
            \bigcup_{M\in \mathbb{N}} P(B_{M})
            $$
            
            而对于$\forall M\in \mathbb{N}$，$a_{M+1} \not \in B_{M}$，$a_{M+1}\in B_{M+1}$，所以$\{ a_{M+1} \}\not \in P(B_{M})$，$\{ a_{M+1} \}\in P(B_{M+1})$，所以
            $$
            \bigcup_{1\leqslant m\leqslant M} P(B_{m}) \subsetneqq \bigcup_{1\leqslant m\leqslant M+1} P(B_{m})
            $$

            所以对于有限集合$\displaystyle \bigcup_{1\leqslant m\leqslant M} P(B_{m})$和$\displaystyle \bigcup_{1\leqslant m\leqslant M+1} P(B_{m})$，有
            $$
             \left\vert \bigcup_{1\leqslant m\leqslant M} P(B_{m}) \right\vert +1\leqslant \left\vert \bigcup_{1\leqslant m\leqslant M+1} P(B_{m}) \right\vert
            $$

            根据极限的定义可知
            $$
            \left\vert\bigcup_{M\in \mathbb{N}} P(B_{M})\right\vert=\left\vert\lim_{M \to \infty} \bigcup_{1\leqslant m\leqslant M} P(B_{m}) \right\vert \geqslant \lim_{M \to \infty}\left\vert \bigcup_{1\leqslant m\leqslant M} P(B_{m}) \right\vert =+\infty
            $$

            所以A的所有有限子集$\displaystyle \bigcup_{n\in \mathbb{N}} P(B_{M})$是无限集，并且能找到$\mathbb{N}$到$\displaystyle \bigcup_{n\in \mathbb{N}} P(B_{M})$的映射，所以$\displaystyle \left\vert \bigcup_{n\in \mathbb{N}} P(B_{M}) \right\vert \leqslant $可数集的基数，并且$\displaystyle \left\vert \bigcup_{n\in \mathbb{N}} P(B_{M}) \right\vert \geqslant $可数集的基数。

            所以A的所有有限子集$\displaystyle \bigcup_{n\in \mathbb{N}} P(B_{M})$是可数集。

            即 无限可数集的所有有限子集组成一个可数集。
        \end{zhongwen}
        \end{proof}
    \end{enumerate}

    \section{不可解问题}
    \begin{enumerate}
        \item *设集合$F=\{ f\ |\ \mathbb{N} \to M \}$，其中$M$为正偶数集。证明：$F$中存在这样的函数$f$，计算$f$的C程序不存在。
        
        \begin{proof}
        \begin{zhongwen}
            
            由于C程序的集合是可数的，因此只需证明$F$为不可数集合。

            根据 \ref{cardinality} 节的第 \ref{functioncardinality} 题可知，$
            \left\vert F \right\vert = \left\vert M \right\vert ^{\left\vert \mathbb{N} \right\vert }$，所以$F\sim \{ f\ |\ f:\mathbb{N} \to \mathbb{N} \}$，即$F$与问题集等势，所以$F$不可数。
        
        \end{zhongwen}
        \end{proof}
    \end{enumerate}
\end{document}