习题1.1 (1)(a)列出集合S={a,b,{c,d},47}的所有子集 (b)回答下列问题:c∈S?{c,a}∈S?0∈S?S∈S? (c)回答更多问题:{c,a}cS?{c,}cS?{b,47}cS?{c,d,47}cS?0sS? SCS? (2)写出下列集合的元素 (a){1,2,3,{4,5},{6,{7,8}} (b){x∈N:x2=3或x2=4} (c){x∈N:x2=3并且x2=4}。 (3)找出三个性质P(x)使得集合{x∈R:P(x)}为{1};找出三个性质Q(x)使得集合 {x∈z:Q(x)}=0。 (4)在有可能的情况下找出 (a)两个无穷集合A和B使得A∩B={1}并且AUB=Z。 (b)两个集合C和D使得CUD={t,h,,c,}并且C∩D={t,h,i,n} 注意:如果你认为不可能的话,请给出理由。 习题1.2 (1)验证下列关于整除关系的命题,其中所有字母都代表整数 (a)如果a|b,则对任何c都有a|be; (b)如果a|b并且b|c,则a|c; (c)如果a|b并且a|c,则对任何s和t都有a|(sb+tc); (d)如果a|b并且b|a,则a=±b; (e)如果a|b并且a,b>0,则a≤b; (f)如果m≠0则(a|b当且仅当ma|mb (2)假定a,b,c,n∈Z且n>0。证明同余关系的下列性质
习题 1.1. (1) (a) 列出集合 S = {a, b, {c, d}, 47} 的所有子集。 (b) 回答下列问题：c ∈ S？{c, d} ∈ S？∅ ∈ S？S ∈ S？ (c) 回答更多问题：{c, d} ⊂ S？{{c, d}} ⊂ S？{b, 47} ⊂ S？{c, d, 47} ⊂ S？∅ ⊆ S？ S ⊆ S？ (2) 写出下列集合的元素： (a) {1, 2, 3, {4, 5}, {6, {7, 8}}}。 (b) {x ∈ N : x 2 = 3 或 x 2 = 4}。 (c) {x ∈ N : x 2 = 3 并且 x 2 = 4}。 (3) 找出三个性质 P(x) 使得集合 {x ∈ R : P(x)} 为 {1}；找出三个性质 Q(x) 使得集合 {x ∈ Z : Q(x)} = ∅。 (4) 在有可能的情况下找出： (a) 两个无穷集合 A 和 B 使得 A ∩ B = {1} 并且 A ∪ B = Z。 (b) 两个集合 C 和 D 使得 C ∪ D = {t, h, i, c, k} 并且 C ∩ D = {t, h, i, n}。 注意：如果你认为不可能的话，请给出理由。 习题 1.2. (1) 验证下列关于整除关系的命题，其中所有字母都代表整数。 (a) 如果 a | b，则对任何 c 都有 a | bc； (b) 如果 a | b 并且 b | c，则 a | c； (c) 如果 a | b 并且 a | c，则对任何 s 和 t 都有 a | (sb + tc)； (d) 如果 a | b 并且 b | a，则 a = ±b； (e) 如果 a | b 并且 a, b > 0，则 a ≤ b； (f) 如果 m ̸= 0 则 (a | b 当且仅当 ma | mb)。 (2) 假定 a, b, c, n ∈ Z 且 n > 0。证明同余关系的下列性质： 1
(a)(自反性)a≡a(modn)。 (b)(对称性)如果a≡b(modn),则b≡a(modn) (c)(传递性)如果a≡b(modn)且b≡c(modn),则a≡c(modn) (3)判断下列命题是否对所有集合A,B,C和D成立,并给出理由 (a)A×(B∪C)=(A×B)U(A×C) (b)(A×B)∩(C×D)=(AnC)×(B∩D) (c)(A×B)U(C×D)=(AUC)×(BUD) 习题1.3 (1)对下列集合A和B找出所有从A到B的函数。 (a)A={x}andB={0,1} (b)A=f,y and B=(2]o (c)A={x,y}andB={0,1} (d)A={x,y}andB={0,1,2} 如果集合A和B分别含有n和m个元素,有多少个从A到B的函数? (2)令∫和g为从{1,2,3}到{2,3,4}的函数分别定义为∫(x)=-x+5和g(x)= x3+6x2-12x+11。证明f=g (3)令f:R→R和g:Z→Z为 g(n) 证明f为双射;g为单射但不是满射。 (4)考察函数∫:X→Y。判断下列命题的对错。 (a)f是满射当且仅当任何一个Y里的元素都是某个X里元素的像。 (b)f是满射当且仅当任何一个X里的元素都有某个Y里元素为它的像。 (c)f满射当且仅当对任何y∈Y都存在x∈X使得f(x)=y
(a) （自反性）a ≡ a (mod n)。 (b) （对称性）如果 a ≡ b (mod n)，则 b ≡ a (mod n)。 (c) （传递性）如果 a ≡ b (mod n) 且 b ≡ c (mod n)，则 a ≡ c (mod n)。 (3) 判断下列命题是否对所有集合 A, B, C 和 D 成立，并给出理由。 (a) A × (B ∪ C) = (A × B) ∪ (A × C)。 (b) (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D)。 (c) (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D)。 习题 1.3. (1) 对下列集合 A 和 B 找出所有从 A 到 B 的函数。 (a) A = {x} and B = {0, 1}。 (b) A = {x, y} and B = {2}。 (c) A = {x, y} and B = {0, 1}。 (d) A = {x, y} and B = {0, 1, 2}。 如果集合 A 和 B 分别含有 n 和 m 个元素，有多少个从 A 到 B 的函数? (2) 令 f 和 g 为从 {1, 2, 3} 到 {2, 3, 4} 的函数分别定义为 f(x) = −x + 5 和 g(x) = −x 3 + 6x 2 − 12x + 11。证明 f = g。 (3) 令 f : R → R 和 g : Z → Z 为 f(x) = 4x − 1, g(n) = 4n − 1。 证明 f 为双射；g 为单射但不是满射。 (4) 考察函数 f : X → Y 。判断下列命题的对错。 (a) f 是满射当且仅当任何一个 Y 里的元素都是某个 X 里元素的像。 (b) f 是满射当且仅当任何一个 X 里的元素都有某个 Y 里元素为它的像。 (c) f 满射当且仅当对任何 y ∈ Y 都存在 x ∈ X 使得 f(x) = y。 2
(d)f满射当且仅当对任何x∈X都存在y∈Y使得∫(x)=y (e)f满射当且仅当存在y∈Y使得对任意x∈X都有f(x)=y (f)∫满射当且仅当∫的值域等于Y。 (5)令∫和g为从R到R的函数。判断下列命题的对错并给出理由。 (a){x∈R|f(x)=0}∩{x∈R|g(x)=0}={x∈R|f2(x)+g2(x)=0}。 (b){x∈R|f(x)=0}={x∈R|f2(x)=0} (c)如果f和g都是双射,则∫+g也是双射。(这里函数f+g:R→R的定义是 (f+g)(x)=f(x)+g(x)) (6)(a)证明对任何函数f,g:R→R如果fog是单射,则g是单射 (b)找出函数f,g:R→R使得fog是单射,但∫不是单射。 (7)给定一个函数f:X→Y,定义两个新的幂集间的函数如下 F:P(X)→P(Y)和G:P(Y)→P(X) F(A)={f(a):a∈A}和G(B)={a∈X:f(a)∈B} 其中ACX并且BCY。判断下列命题是否正确并给出证明或反例 (a)如果f是单射,则F也是单射 (b)如果∫是满射,则G是满射。 (8)令a,d∈Z,q∈R并且n∈N (a)找出等差数列a,a+d,a+2d,……,a+nd的求和公式B(m)并用归纳法验证 (b)找出等比数列a,a,a2,…,an的求和公式C(n)并用归纳法验证 下面的练习都是集合论中基数练习的翻版。建议大家把它们“翻译”成基数的语言, 读出它们告诉我们的有关集合大小的信息。 9)找出N和Z之间的一个一一对应
(d) f 满射当且仅当对任何 x ∈ X 都存在 y ∈ Y 使得 f(x) = y。 (e) f 满射当且仅当存在 y ∈ Y 使得对任意 x ∈ X 都有 f(x) = y。 (f) f 满射当且仅当 f 的值域等于 Y 。 (5) 令 f 和 g 为从 R 到 R 的函数。判断下列命题的对错并给出理由。 (a) {x ∈ R | f(x) = 0} ∩ {x ∈ R | g(x) = 0} = {x ∈ R | f 2 (x) + g 2 (x) = 0}。 (b) {x ∈ R | f(x) = 0} = {x ∈ R | f 2 (x) = 0}。 (c) 如果 f 和 g 都是双射，则 f + g 也是双射。（这里函数 f + g : R → R 的定义是 (f + g)(x) = f(x) + g(x)。） (6) (a) 证明对任何函数 f, g : R → R 如果 f ◦ g 是单射，则 g 是单射。 (b) 找出函数 f, g : R → R 使得 f ◦ g 是单射，但 f 不是单射。 (7) 给定一个函数 f : X → Y ，定义两个新的幂集间的函数如下： F : P(X) → P(Y ) 和 G : P(Y ) → P(X) F(A) = {f(a) : a ∈ A} 和 G(B) = {a ∈ X : f(a) ∈ B} 其中 A ⊆ X 并且 B ⊆ Y 。判断下列命题是否正确并给出证明或反例。 (a) 如果 f 是单射，则 F 也是单射。 (b) 如果 f 是满射，则 G 是满射。 (8) 令 a, d ∈ Z，q ∈ R 并且 n ∈ N。 (a) 找出等差数列 a, a + d, a + 2d, · · · , a + nd 的求和公式 B(n) 并用归纳法验证。 (b) 找出等比数列 a, aq, aq2 , · · · , aqn 的求和公式 C(n) 并用归纳法验证。 下面的练习都是集合论中基数练习的翻版。建议大家把它们“翻译”成基数的语言， 读出它们告诉我们的有关集合大小的信息。 (9) 找出 N 和 Z 之间的一个一一对应。 3
(10)假定a,b,c,d为实数并且ab (c)令X为一非空集,A是X的非空子集的集合,R是A上的关系定义为URV 当且仅当U∩V≠0。 (d)R是R上的关系,使得aPb当且仅当ab≥0。 (e)f是R上的关系,使得aPb当且仅当|a-b≤2。 (2)令T={0,1,2,3,,12}。定义T上的一个关系~如下:对任意a,b∈T,a~b 只要下列条件之一成立 (a)a,b都是偶数 (b)a,b都是大于2的素数
(10) 假定 a, b, c, d 为实数并且 a b。 (c) 令 X 为一非空集，A 是 X 的非空子集的集合，R 是 A 上的关系定义为 URV 当且仅当 U ∩ V ̸= ∅。 (d) R 是 R 上的关系，使得 aRb 当且仅当 ab ≥ 0。 (e) R 是 R 上的关系，使得 aRb 当且仅当 | a − b |≤ 2。 (2) 令 T = {0, 1, 2, 3, . . . , 12}。定义 T 上的一个关系 ∼ 如下：对任意 a，b ∈ T，a ∼ b 只要下列条件之一成立： (a) a，b 都是偶数。 (b) a，b 都是大于 2 的素数。 4
(c)a,b∈{1,9}并且a=b 证明~是一个T上的等价关系并找出所有的等价类 (3)令Z=z-{0}为非零整数集,并且A=Z×z*。在A上定义如下关系 R={(a,b),(c,d)∈A×A 证明R是一个等价关系。找出等价类[(0,1)和[(2,4)] (4)令R为N×N上的如下关系 (a,b)R(C,d)当且仅当(丑k∈Z)a+b=c+d+3k 证明R是一个等价关系并且找出R的所有等价类。 (5)令A为一个非空集并且R是A上的一个二元关系。证明R是一个等价关系当且仅 当下述两条件成立 (a)对所有x∈AxRx成立 (b)对所有x,y,z∈A,如果xRy并且yRz,则zRx (6)令k为一个固定的正整数。定义Z上的关系E使得xEy当且仅当x≡y(modk) 我们已经知道E是Z上的一个等价关系。对任意整数,∈Z,找出一个从等价类 ]E到等价类[E的一个双射,并验证它的确是一个双射。 (7)对任意集合X,如果工cP(X),并且满足 ACB∈→A∈1且A,B∈T→AUB∈, 就称工是X上的一个理想。证明:如果工是理想,则其上的二元关系 R={(A,B)|(A△B)∈T} 是等价关系。 (8)考察整数间的关系E,定义为xEy当且仅当|x|=y|。验证E是一个等价关系并 找出商集z/E
(c) a，b ∈ {1, 9} 并且 a = b。 证明 ∼ 是一个 T 上的等价关系并找出所有的等价类。 (3) 令 Z ∗ = Z − {0} 为非零整数集，并且 A = Z × Z ∗。在 A 上定义如下关系 R： R = {((a, b),(c, d)) ∈ A × A | ad = bc}。 证明 R 是一个等价关系。找出等价类 [(0, 1)] 和 [(2, 4)]。 (4) 令 R 为 N × N 上的如下关系： (a, b)R(c, d) 当且仅当 (∃k ∈ Z)[a + b = c + d + 3k]。 证明 R 是一个等价关系并且找出 R 的所有等价类。 (5) 令 A 为一个非空集并且 R 是 A 上的一个二元关系。证明 R 是一个等价关系当且仅 当下述两条件成立： (a) 对所有 x ∈ A xRx 成立。 (b) 对所有 x, y, z ∈ A，如果 xRy 并且 yRz，则 zRx。 (6) 令 k 为一个固定的正整数。定义 Z 上的关系 E 使得 xEy 当且仅当 x ≡ y(mod k)。 我们已经知道 E 是 Z 上的一个等价关系。对任意整数 i, j ∈ Z，找出一个从等价类 [i]E 到等价类 [j]E 的一个双射，并验证它的确是一个双射。 (7) 对任意集合 X，如果 I ⊂ P(X)，并且满足： A ⊂ B ∈ I → A ∈ I 且 A, B ∈ I → A ∪ B ∈ I, 就称 I 是 X 上的一个理想。证明：如果 I 是理想，则其上的二元关系： R = {(A, B) | (A△B) ∈ I} 是等价关系。 (8) 考察整数间的关系 E，定义为 xEy 当且仅当 | x |=| y |。验证 E 是一个等价关系并 找出商集 Z/E。 5
习题1.5 (1)证明每一个有穷的偏序都可以延拓成一个线序。 习题1.6. (1)验证:如果p是素数,则{0,1,…,p-1}在模p的运算下满足域的所有公理 (2)证明每个非零的自然数都是某个自然数的后继 (3)证明抽屉原则(或称鸽舍原理):如果自然数n>m,则不存在从{0,1,…,n-1} 到{0,1,…,m-1}的单射。 (4)证明下列命题等价 (a)皮亚诺公理中的归纳原理。 (b)最小数原理:自然数的任意非空子集都有最小元 (c)强归纳原理:对任何一个自然数的性质P,如果从所有m<n,P(m)成立能 推出P(n)成立,则对所有自然数n,P(n)都成立 鸽舍原理, Pigeonhole Principle,叙述为:如果把n个鸽子放入少于n个鸽舍里,则至少有一个鸽舍里面有不止 只鸽子
习题 1.5. (1) 证明每一个有穷的偏序都可以延拓成一个线序。 习题 1.6. (1) 验证：如果 p 是素数，则 {0, 1, · · · , p − 1} 在模 p 的运算下满足域的所有公理。 (2) 证明每个非零的自然数都是某个自然数的后继。 (3) 证明抽屉原则 （或称鸽舍原理 1）：如果自然数 n > m，则不存在从 {0, 1, · · · , n − 1} 到 {0, 1, · · · , m − 1} 的单射。 (4) 证明下列命题等价： (a) 皮亚诺公理中的归纳原理。 (b) 最小数原理：自然数的任意非空子集都有最小元。 (c) 强归纳原理：对任何一个自然数的性质 P，如果从所有 m < n，P(m) 成立能 推出 P(n) 成立，则对所有自然数 n，P(n) 都成立。 1鸽舍原理，Pigeonhole Principle，叙述为：如果把 n 个鸽子放入少于 n 个鸽舍里，则至少有一个鸽舍里面有不止一 只鸽子。 6