离散2

这里会放上我的一些作业

作业5

$$
\begin{align}
&(1)不是\
&A = {1, 2, 3}\
&R_1 = {<1,1>, <2,2>, <3,3>,<1,2>,<2,1>, <1,3>,<3,1>,<2,3>,<3,2>}\
&R_2 = {<1,1>, <2,2>, <1,2>,<2,1>}\
&则r(R_1 - R_2) = {<1,1>, <2,2>, <3,3>,<2,3>,<3,2>,<1,3>,<3,1>}\
&而有<1,3>,<3,2>\in r(R_1 - R_2) 但是<1,2> \notin r(R_1 - R_2),故r(R_1-R_2)不是传递的，因而不是等价关系\
&(2)不是\
& 上课已经讲过，R_1 , R_2是对称时，R_1 \circ R_2 不一定对称\
& 比如取A = {1, 2, 3}\
&R_1 = {<1,1>, <2,2>,<1,2>,<2,1>,}\
&R_2 = {<2,2>, <3,3>, <2,3>,<3,2>}\
&则R_1\circ R_2 = {<2,2>,<2,3>,<1,3>,<1,2>}显然不是等价关系\
&(3)是\
&R_1,R_2都是等价关系，那么都是自反，对称，传递的\
&就有R_1\cup R_2是自反的，对称的\
&同时如果R_1 \cup R_2 是自反的，对称的，那么t(R_1,R_2)仍然是自反、对称的，同时还是传递的\
&由等价关系的定义可知t(R_1, R_2)是等价关系
\end{align}
$$

$$
\begin{align}
&(a)\
&左到右:\
&S_1 \in A/R1,则\forall s_1 \in S_1\
&s_1 = [x]{R_1} = {y|y\in A \wedge x R_1y},x为A中元素\
&又R_1\subseteq R_2,及<x,y> \in R_1 有<x,y> \in R_2，即xR_2y\
&故s_1 \in S_2 = [x]{R_2} = {y|y \in A \wedge xR_2y}\
&即S_1 \subseteq S_2,由加细的定义有A/R_1 \le A/R_2\
&右到左:\
&A/R_1 \le A/R_2\
&有\forall S_1 \in A/R_1 , \exist S_2 \in A/R_2 , s.t. S_1 \subseteq S_2\
&\forall s_1 \in S_1\
&s_1 = [x]{R_1} = {y|y\in A \wedge x R_1y},x为A中元素\
&故\exist s_2 = [x]{R_2} = {y|y \in A \wedge xR_2y},s_1 \subseteq s_2 \
&即\forall xR_1y,有xR_2y,即R_1 \subseteq R_2\
&综上即可得证\
&(b)\
&左到右:\
&R_1 \subset R_2 必然有R_1 \subseteq R_2，则A/R_1 \le A/R_2\
&又R_1\ne R_2,即\exist <x_0,y> \in R_2,<x_0,y>\notin R_1\
&取s_2 = [x_0]{R_2} = {y|y \in A \wedge x_0R_2y},s_2 \in S_2，其中S_2 \in A/R_2\
&且由于<x_0,y>\notin R_1 ,s_2 \notin S_1,故S_1 \ne S_2,其中S_1 \in A/R_1\
&即A/R_1 \ne A/R_2\
&右到左:\
&A/R_1 \subset A/R_2,则同样易有R_1\subseteq R_2\
&A/R_1 \ne A/R_2\
&则存在S_2 \in A/R_2,找不到S_1 \in A/R_1,s.t. S_2 \subseteq S_1,\
&同样取s_2 = [x_0]{R_2} = {y|y \in A \wedge x_0R_2y},s_2\in S_2，且s_2 \notin S_1\
&即\exist <x_0,y_0>,s.t. x_0R_2y_0,x_0\overline{R_1}y_0\
&即R_1 \ne R_2\
&故R_1 \subset R_2\
&综上即可得证
\end{align}
$$

$$
\begin{align}
&看法不对,证明就不可能对了嘛。\
&若R是非空集合A的空关系，由于前件为0，R是对称和传递的，但是\forall x \in A, <x,x>\notin R\
&R不是自反的\
&故即可完成论证\
\end{align}
$$

$$
\begin{align}
&必要性:\
&(显然bushi)R是等价关系，且<a,b>\in R,<a,c> \in R\
&由于R是对称的，有<b,a>\in R\
&由于R是传递的，有<b,c>\in R\
&必要性即证\
&充分性:\
&若<a,b>\in R,<a,c>\in R,则<b,c>\in R\
&同时R是自反的\
&\forall <a,b>\in R, 且由自反性有<a,a> \in R \
&由条件可得，<b,a> \in R，故R是对称的\
&\forall <a,b> \in R , <b,c> \in R\
&证明了对称性，有<b,a>\in R,则结合条件可得\
&<a,c>\in R，故R是传递的\
&由等价关系的定义可知R是等价关系\
&充分性得证\
&综上即可得证\
\end{align}
$$

$$
\begin{align}
&必要性:\
&(也挺显然的)<x,y>\in R,<y,z>\in R\
&则由传递性，<x,z>\in R\
&再由对称性，<z,x>\in R\
&必要性即证\
&充分性:\
&R是自反的，且R是循环的\
&\forall <x,y> \in R, 由自反性<y,y>\in R\
&再有循环性，有<y,x>\in R，即R是对称的\
&\forall <x,y>\in R,<y,z>\in R\
&由循环性,<z,x>\in R,又已经证明R是对称的\
&则有<x,z>\in R，故R是传递的\
&必要性得证\
&综上即可得证
\end{align}
$$

作业六

$$
\begin{align}
&(1)能够\
&dom = {1,2,3,4}\
&ran = {<2,3>,<3,4>,<1,4>}\
&(2)能够\
&dom = {1,2,3}\
&ran = {<2,3>,<3,4>,<3,2>}\
&(3)不能够\
&(4)能够\
&dom = {1,2,3}\
&ran = {<2,3>}\
\end{align}
$$

$$
\begin{align}
& (1)\forall y \in f[A] - f[B]\
&\Rightarrow y \in f[A] \wedge y \notin f[B]\
&\exist x\in A \quad s.t. \quad y = f(x)\
&若x\in B,则与y\notin f[B]矛盾,故x\in A - B\
&即y \in f[A- B]\
&反例:\
&X= {1,2},Y = {0}\
&f = {<1,0>,<2,0>}\
&A = {1,2}, B = {1}\
&此时f[A] = {0},f[B] = {0},f[A] - f[B] = \varnothing\
&f[A-B] = {0}，等号不成立\
&(2)\forall x \in f^{-1}[C-D]\
&\exist y \in C- D , y = f(x)\
&\Rightarrow y\in C\wedge y\notin D\
&\Rightarrow x\in f^{-1}[C] \wedge x \notin f^{-1}[D]\
&\Rightarrow x \in f^{-1}[C]-f^{-1}[D]\
&因此有f^{-1}[C-D]\subseteq f^{-1}[C]-f^{-1}[D]\
&\forall x \in f^{-1}[C]-f^{-1}[D]\
&\exist y \in C ,y = f(x)\
&若y\in D,则x\in f^{-1}[D],矛盾，因此y\notin D\
&\Rightarrow y\in C-D\
&即x \in f^{-1}[C-D]\
&因此有f^{-1}[C]-f^{-a}[D] \subseteq f^{-a}[C-D]\
&故综上有f^{-1}[C-D] = f^{-1}[C]- f^{-1}[D]\
\end{align}
$$

$$
\begin{align}
&单射：(1),(2)\
&满射：(2),(3)\
&双射：(2)\
\end{align}
$$

作业七

$$
\begin{align}
&由上课讲的定理显然可得：\
&(定理如下，课上证明了，课下就不证了了吧)\
&f:X ⟶ Y 和 g: Y ⟶ Z，则\
&(1) 若 f 和 g 都是满射，则 g\circ ƒ 也是满射\
&(2) 若 f 和 g 都是单射，则 g\circ ƒ 也是单射\
&(3) 若 f 和 g 都是双射，则 g\circ ƒ 也是双射\
&用数学归纳法显然可证\
&n = 1时，结论成立 \
&若n时结论成立，则n+1时\
&f^{n+1} = f^n \circ f\
&f^n和f都是满射，单射或双射，则f^{n+1}时满射，单射或双射\
&由数学归纳法即可得证
\end{align}
$$

$$
\begin{align}
&(1)g\circ f为满射，g为单射\
&则ran(g\circ f) = Z\
&且由课上结论,g为满射，故g为1-1映射\
&dom(g) = Y,g^{-1}[Z] = Y \
&又g[ran(f)] = Z\
&即ran(f) = Y\
&故f为满射\
&综上即可得证\
&(2)g\circ f为单射,f为满射\
&且由课上结论，f为单射，故f为1-1映射\
&\forall y_1 ,y_2\in Y,且y_1 \ne y_2\
&由于f为1-1映射,故存在唯一x_1,x_2,s.t.y_1 = f(x_1),y_2 = f(x_2)\
&若x_1 = x_2 ,则显然y_1 = y_2，故有x_1 \ne x_2\
&则g\circ f(x_1) = g(y_1) = z_1,g\circ f(x_2) = g(y_2) = z_2\
&由g\circ f为单射,故z_1\ne z_2\
&故可得g也为单射\
&综上即可得证
\end{align}
$$

$$
\begin{align}
&dom(f\circ f) = {x | x\in \R \wedge x \ne 0}\
&ran(f\circ f) = {x | x\in \R \wedge x \ne 0}\
&dom(h\circ g) = {x | x\in \R}\
&ran(h\circ g) = {x | x\in \R_+ | x = 0}\
&dom(g\circ h) = {x|x \in \R_+ | x = 0}\
&ran(g\circ h) = {x|x \in \R_+ | x = 0}\

\end{align}
$$

作业7

$$
\begin{align}
&左推右\
&显然!!f可逆等价于f有唯一的左逆和右逆\
&右推左\
&若f有唯一的左逆(右逆证明类似)\
&那么可以推出f是单射\
&需要证明f是可逆的，那么只需要证明f是右可逆的\
&这里采用反证法，假设f不是右可逆的，那么等价于f不是满射\
&设A中至少有的两个元素为a_1, a_2,由于f是单射\
&设f(a_1) = b_1, f(a_2) = b_2,且有b_1 \ne b_2，同时由于不是满射\
&B中至少存在一个元素，设为b_3,A中没有元素映射到b_3\
&接下来我们构造g_1,g_2,使得g_1 \circ f = I_A,g_2\circ f_2 = I_A，且g_1 \ne g_2\
&g_1(x) = \begin{cases}
a_i, & if, x = b_i,i=1,2\
a_1, & if, x = b_3\
f^{-1}(x), & if, x \in ran(f) \wedge x \notin{b_1, b_2}
\end{cases}\
&g_2(x) = \begin{cases}
a_i, & if, x = b_i,i=1,2\
a_2, & if, x = b_3\
f^{-1}(x), & if, x \in ran(f) \wedge x \notin{b_1, b_2}
\end{cases}\
&那么就有g_1 \circ f = I_A,g_2\circ f_2 = I_A，且g_1 \ne g_2成立，与f有唯一的左逆矛盾\
&故有上面的反证法可以得到f是右可逆的，那么f是可逆，即可得证\
&综上即可得证
\end{align}
$$

$$
\begin{align}
(1)&f是左可逆，右可逆，可逆的\
&显然f是单射，满射，因此是可逆的。同时求出f的逆即为f的左逆和右逆\
&构造g(x) = \begin{cases}
4,& if, x= 0\
x-1,& if, x = 1,2,3,4\
x,& if, x > 5
\end{cases}\
&可以验证f\circ g = I_N, g\circ f = I_N\
&即为所求\
(2)&f是右可逆，不是左可逆，不是可逆\
&由于f(1) = f(3) = 3,因此f不是单射，f不是左可逆\
&f是满射，\forall x \in N,\exist f(2x) = x,2x \in N;
&下面构造f的右逆g\
&g(x) = 2x, x \in N;即为右逆之一
\end{align}
$$

$$
\begin{align}
&\chi_{A-B\cap C}\
&= \chi_A - \chi_A \chi_{B\cap C}\
&= \chi_A - \chi_A\chi_B*\chi_C\
&\chi_{(A-B)\cup (A-C)}\
&=\chi_{A-B} + \chi_{A-C}-\chi_{A-B}\chi_{A-C}\
&=\chi_A-\chi_A\chi_B+\chi_A-\chi_A*\chi_C - (\chi_A-\chi_A*\chi_B)(\chi_A-\chi_A\chi_C)\
&=\chi_A-\chi_A*\chi_B+\chi_A-\chi_A*\chi_C-(\chi_A-\chi_A*\chi_A*\chi_C-\chi_A*\chi_B*\chi_A+\chi_A*\chi_B*\chi_A*\chi_C)\
&=\chi_A-\chi_A*\chi_B+\chi_A-\chi_A*\chi_C-(\chi_A-\chi_A*\chi_C-\chi_A*\chi_B+\chi_A*\chi_B*\chi_C)\
&=\chi_A - \chi_A*\chi_B*\chi_C\
&于是显然有\chi_{A-B\cap C} = \chi_{(A-B)\cup (A-C)}\
&于是可以证明A-B\cap C = (A-B)\cup(A-C)\
\end{align}
$$

$$
\begin{align}
&\chi_{A\oplus B}\
&=\chi_{A} - \chi_{A\cap B} + \chi_{B}-\chi_{A\cap B}\
&=\chi_{A} + \chi_{B} - 2*\chi_{A}\chi_{B}\
&=0\
&那么有\chi_{A}(1-\chi_{B}) = \chi_B*(1-\chi_{A})\
&\iff \chi_{A}\chi_{\sim B} = \chi_{B}\chi_{\sim A}\
&\iff \chi_{A\cap \sim B} = \chi_{B\cap \sim A}\
&\iff A\cap \sim B = B \cap \sim A\
&即为所求
\end{align}
$$

作业8

$$
\begin{align}
&利用第一数学归纳法进行证明\
&(1)由于为自然数序列，所以显然有0\le a_0\
&(2)\forall n\ge 0,若n \le a_n,下面证明n^+\le a_{n^+}\
&由于为单调递增序列，因此显然有a_n <a_{n^+}\
&同时为正整数序列，由于正整数是不稠密的\
&有a_n + 1 \le a_{n^+}\
&n^+ = n + 1 \le a_n + 1\le a_{n^+}\
&综上即可得证
\end{align}
$$

$$
\begin{align}
&对于本题我们先证明如下结论:\
&\forall i \in n, 有i \subseteq n\
&使用第一数学归纳法进行证明\
&(1)n = 0时显然成立。\
&(2)\forall n \ge 0,若结论成立，即\forall i \in n, 有i\subseteq n\
&那么对于n^+,有n^+ = {n,{n}}\
&\forall i \in n^+, 有i = n 或者i \in n(由三歧性可得)\
&若i = n,显然有i\subseteq n^+\
&若i\in n,由归纳假设，i\in n\
&又n\in n^=,则又i\in n^+\
&故该结论得证\
&对于本题,\forall a \in n,\forall x \in a\
&由于可推出a \in n, 于是显然有x \in n\
&故综上即可得证\forall n \in N 是传递的
\end{align}
$$

$$
\begin{align}
&本题应该是想用二重归纳法做，但是太麻烦了，我就直接用构造法哈(goutou)\
&设n = k(m+1) + t,(t < m+1)\
&由于n > m 且(m+1)\nmid n\
&可得k \ge 1, t \ne 0\
&那么甲第一次取t个球，然后每次乙取x个球\
&甲取(m+1-x)个球，一轮取球数维m+1，故经过k轮\
&恰好甲取完最后的球，获胜
\end{align}
$$