2005 4 1 1 2 2 6 3 8 4 11 5 14 6 18 7 20 8 22 9 24 10 26 11 27 http://matcmadison.edu/alehnen/weblogic/logset.htm 1
1 = = = (set) (element) a A a A a A a A a A {2, 5, (0, 1)}, [ 1, 1] = {x; 1 x 1}. (proposition) A = {x; P (x)} P (x) x x a A a A Remark. (i) {2, 0, 0, 5} = {0, 2, 5}. x {x; P (x) } = {y; P (y) } b a f(x) dx = b a f(y) dy (ii) ; : [a, b] = {x a x b}. (iii) {, } (iv) {a n } {a n ; n N} {( 1) n } {( 1) n+1 } {( 1) n ; n = 1, 2,... } = {( 1) n+1 ; n = 1, 2,... } = {1, 1} 2
(v) a, b (a, b) {x; a < x < b} ]a, b[= {x; a < x < b} (vi) f {y; y = f(x), x A} {f(x); x A} (vii) set, ensemble, Menge A, B A B A B A B (subset) A B A B A B A = B B B A B a b, b a a = b A B, B A A = B 1.1. {1, 2, (0, 1)} {2, 5, (0, 1)}, [0, 1] [ 1, 2]. 1., {1} {1, 2, 3}, {1} {1, 2, 3}, 1 {1, 2, 3}. (empty set) { } 0 A. 2. (universal set) 3
A U A U A U (complement) A c A U A c Remark. A, A A N = = {0, 1, 2,... }, Z = = {0, ±1, ±2,... }, Q = = { n ; m, n Z, m 0}, m R = = (, + ), C = = {x + iy; x, y R}. ir... 2 1 0 1 2 Z... R Remark. (i) 0 0 (ii) (natural number) (integer ) (rational number) (real number) (complex number) rational (ratio) irrational 3. integer integral, integrate 4
A, B (union) (intersection) A B = A B, A B = A B A B A B 1.2. A B A B (i) ( ) A B = B A, A B = B A. (ii) ( ) (A B) C = A (B C), (A B) C = A (B C). (iii) ( ) (A B) C = (A C) (B C), (A B) C = (A C) (B C). (iv) (DeMorgan s law) (A B) c = A c B c, (A B) c = A c B c. (v) (A c ) c = A. (Venn diagram ) (Boolean algebra) (Augustus De Morgan, 1806 1871), (Georg Boole, 1815 1864). A 1 A n A 1 A n 4. ((A B) C) D = A ((B C) D) 5. (A 1 A n ) B, (A 1 A n ) B. A \ B = {a A; a B} = A B c (difference set) A, B U A B A \ B 5
1.3. {1, 2,..., 5, 6} \ {1, 3, 7, 9} = {2, 4, 5, 6}, [1, 5] \ [0, 2] = (2, 5]. 6. A \ (A \ B) Remark. A B 2 (Georg Cantor, 1845 1918) (finite set) (infinite set) S S S N n(s) n number = 0 0 N 2.1. (i) A = {1, 2, 1, 2,... } A = 2. (ii) B = {(1, 0, 0), [0, 1], [0, 1], [0, 2]} B = 3. (iii) C = {c 1, c 2,..., c n } C n. C = n A, B, C A B = A + B A B, A B C = A + B + C A B B C A C + A B C A B C A 1,..., A n {1, 2,..., n} I A I A I = A i1 A ik, I = {i 1 < i 2 < < i k } 6
I = {1, 3, 4} A I = A 1 A 3 A 4 2.2 (Sieve Formula). A 1 A n = I ( 1) I 1 A I Proof. n = I {1, 2,..., n}, = J {1, 2,..., n, n + 1} A 1 A n A n+1 = A 1 A n + A n+1 (A 1 A n ) A n+1 = A 1 A n + A n+1 (A 1 A n+1 ) (A n A n+1 ) = ( 1) I 1 A I + A n+1 ( 1) I 1 A I A n+1 I I = ( 1) J 1 A J + n+1 J( 1) J 1 A J = ( 1) J 1 A J. J n+1 J 2.3. n n 1,..., n U k A k A k = {σ U; σ(k) = k} A c 1 A c n = (A 1 A n ) c U A 1 A n = n! + I ( 1) I A I A I I A I = (n I )! I = m I ( 1) I A I = I n ( ) n ( 1) m (n m)! = m m=1 ( n m n ( 1) m n! m! m=1 ( n! + n! + n! 2! n! ) n! + + ( 1)n 3! n! ) 7
n 1 1 1! + 1 2! 1 3! + + ( 1)n 1 n! = n k=0 1 k! ( 1)k n 1/e = 0.367879... 7. n = 4 ( ) ( ) ( ) ( ) 4 4 4 4 + + + = 2 4 1 = 15 1 2 3 4 15 8. n P 1,..., P n 2 n n = 2, 3 n 4 9. n 2 n = p e1 1... pe r r (p 1 < p 2 < < p r n 1, 2,..., n n φ(n) ) ) φ(n) = n (1 1p1... (1 1pr A j = {1, 2,..., n p j } r φ(n) = j=1 A j c = n r j=1 A j = n A i A i A j +... i i<j = n n + n n +... p i i p i<j i p j p i p j p k i<j<k ) ) = n (1 1p1... (1 1pr 3 A 1,..., A n A 1 A n A 1 A n n n A k, k=1 k=1 A k 8
A 1, A 2,... k=1 k=1 A k = {a; a A k } = {a; a A k k } A k = {a; a A k } = {a; k a A k } (existential quantifier), (universal quantifier) A k = {a; k, a A k }, k=1 A k = {a; k, a A k } k=1 X x P (x) x X, P (x) P(x) x X x X, P (x) x X P (x) 3.1. a, b ( x R, ax + b = 0) (a = 0 b = 0), ( x R, ax + b = 0) (a 0 a = b = 0) 10. a, b X x A x x A x X (a family of sets indexed by the set X) {A x } x X A x = {a; x X, a A x }, = {a; x X, a A x } x X x X A x A y = (x y) x X A x = x X {A x } x X (disjoint union) A x 9
3.2. x A x = [ 1, x] {A x } x>0 A x = [ 1, + ), x>0 A x = [ 1, 0] x>0 11. [1/n, n], (0, 1/n). n 1 n 1 12. 0 < r < 1 ( m n rm+n, m n + rm+n) 1 m n R 13. 7 k (0 k < 7) A k N = 6 k=0 A k P (x) x X x X P (x) DeMorgan DeMorgan ( 3.3. {A i } i I (i) ( ( i I A i ) B = i I(A i B), ( ) A i B = i I(A i B). i I (ii) (DeMorgan s law) ( ) c A x = A c x, x X x X ( ) c A x = A c x. x X x X Proof., x i I (A i B) i I x A i B x B x ( i A i ) B x A i i I x i a i ( i A i ) B 10
14. 3.4. m 1 n 1 [ n m, n + 1 m n 1 m 1 ] = [ ) 1 m, + = [1, + ), m 1 [ n m, n + 1 ] = =. m n 1 15. a 1 m 1 n 1 [ m 1 n, am + 1 ] n a 16. a, b ( x R, ax + b = 0) (a 0 a = b = 0) DeMorgan 17. x, y x Z, y Z, x + y = 2. x Z, y Z, x + y = 2. x Z, y Z, x + y = 2. x Z, y Z, x + y = 2. Remark. x, y P (x, y) x, y, P (x, y) ( ) x, y, P (x, y) 4 R (x, y) A, B A B = {(a, b); a A, b B} A B (product set) (direct product) (a, b) (ordered pair) 11
unordered pair) {a, b} A = B A A = A 2 A A A A = A 4 A B C = {(a, b, c); a A, b B, c C} R 2 R 3 (A B) C, A (B C), A B C ((a, b), c) (a, (b, c)) (a, b, c) Remark. (i) A B B A (x, y) (y, x) (ii) (Cartesian product) René Descartes (1596 1650) Cartesius (Pierre de Fermat, 1601 1665) 4.1. Z 2 R Z R 2 x 4.2. A, B A B A B = A B. [a, b] [c, d] (rectangle) [c, d] [a, b] (circle) C = {(x, y); x 2 + y 2 = 1} [0, 1] C [0, 1] (cylinder) [0, 1] C 12
C 2 = C C (torus) A {1, 2,..., n} A {1, 2,..., n} A n A A... A A {1} A {2} A {n} X Y A {A x } x X {A y } y Y A x = {y Y ; (x, y) A}, A y = {x X; (x, y) A}. 18. {(x, y, z) R 3 ; x 2 + y 2 z 2 = 1} z = c X X (power set) P(X) 2 X 4.3. X = {a, b, c} (a, b, c P(X) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }. 4.4. X 2 X = 2 X. 0 k n = X P k (X) = {A X; A = k} P(X) = n P k (X), P k (X) = k=0 ( ) n k 2 X = n k=0 ( ) n = 2 n k Remark. (John von Neumann, 1903 1957) 2 = { } 2 { } = {, { }} { } { } =, { }, {{ }},... 13
0, 1, 2,... 19. 2 R R = 2 X X X 4.5. X {A i } i I I J X X J X j = A j j J j J A j X = J 2 I X j x X x X J I J J = {j I; x A j } 20. I = {1, 2}, I = {1, 2, 3} 5 x y y x y = f(x) Short History: (Newton, Leibniz, (Euler, 1745), (Dirichlet, 1837), (Cantor, 1880 X, Y X x Y f(x) (mapping) f : X Y, x f(x) X f (domain) (initial set) Y f (range) (final set) f : X Y X Y f X = Y X (transformation) f : X Y f = f X = X, Y = Y x X, f(x) = f (x) f : X Y Y (function) X = N (sequence) f : X R, f : X C, 14
N R A n {1, 2,..., n} A ( ) x 5.1. R 2 y ( ) a b T = c d R 2 R 2 f ( x f : y) ( x T = y) ( ) ax + by cx + dy T (linear transformation) ( y y b ( 0 T d) 1) ( a c) ( 1 0) x x 21. f : R [0, + ), f(x) = x, g : R R, g(x) = x 2, h : R R, h(t) = t. X Y Y X 5.2. X, Y Y X = Y X. X = n Y n Y X 5.3. f : X Y (one-to-one) x x = f(x) f(x ) f(x) = f(x ) = x = x (injection) 5.4. T ad bc 0 15
5.5. X, Y X Y F { Y ( Y 1)... ( Y X + 1) if X Y, F = 0 otherwise. 22. 5.6. f : X Y (onto) Y x X f(x) (surjection) Remark. y Y, x X, y = f(x) 5.7. T ad bc 0 5.8. X, Y X Y G X Y n 1 ( ) n G = ( 1) k (n k) m. k k=0 ( n k ) X = m, Y = n = n C k Proof. X = {1,..., m}, Y = {1,..., n} A i = {f Y X ; x X, f(x) i} A i = (n 1) m 1 i 1 < < i k n A i1 A ik = (n k) m G = (A 1... A n ) c G = n m A 1 A n. A A n = n ( 1) k 1 A I = k=1 I =k n ( ) n ( 1) k 1 (n k) m k G k=1 16
23. S(m, n) n k=0 ( ) n S(m, k) = n m k S(m, n) 5.9. (bijection) 5.10. X, Y X Y X = Y X! = Y! 5.11. {1, 2,..., n} n (a permutation of degree n) ( ) 1 2... n f = f(1) f(2)... f(n) n S n S n = n! 5.12. 2 X {0, 1} X X A X χ A χ A (x) = { 1 if x A, 0 if x A A χ A χ A A (characteristic function) 24. A, B χ A B = χ A χ B, χ A c = 1 χ A, χ A B = χ A + χ B χ A B 5.13. (Y Z) X Y X Z X, Z X Y (Z X ) Y. 5.14. x y (lattice path) n (n, n) y x (2n)! n!(n + 1)! ( 1 lattice path m+n ) n y x (0, 0) (n, n) lattice path x +1 (1, 0) (n + 1, n) lattice path y = x path P (1, 0) (n + 1, n) lattice path y = x P P path p (i, i) (1, 0) (i, i) y = x (0, 1) (n + 1, n) 17
(0, n) (m, n) (0, 0) (m, 0) 1 lattice path p ( 2) P (1, 0) (n + 1, n) free lattice path ( 2n P n+1) ( ) ( ) 2n 2n = (2n)! n n + 1 n!(n + 1)! (n + 1, n) p p 2 25. X = {(x 1,..., x m ) N m ; x 1 + + x m = n} P m ({1, 2,..., m + n}) X 6 f : X Y A X, B Y f[a] = {f(a); a A}, f 1 [B] = {x X; f(x) B} A (image) B (inverse image) f[a] Y f 1 [B] X Remark. 18
(i) f[ ] =, f 1 [ ] = x X f[{x}] = {f(x)} (ii) f[a] f 1 [B] f(a), f 1 (B) A X A X f(a) f(a) Y f(a) Y f(a) X = {1, {1}} {1} X {1} X f : X R f(1) = 2, f({1}) = 3 {1} 3 {f(1)} = {2} ( ) 1 2 6.1. f L = {x+y = 0} C = {x 2 +y 2 = 1} 3 4 6.2. (polar coordinates transformation) x = r cos θ, y = r sin θ. r y θ x 6.3. f(x, y) f 1 [{a}] f 1 [[a, b]] f(x, y) = x 2 + y 2 [0, + ) f 1 [{a}] 6.4. [a, b] R 2 R 3 {(x, y) R 2 ; x 2 + y 2 = 1} [0, 2π] t (cos t, sin t) D R 2 R 3 26. 0 θ 2π, 0 φ π x = cos θ sin φ, y = sin θ sin φ, z = cos φ {(x, y, z) R 3 ; x 2 + y 2 + z 2 = 1} 6.5. (i) f[a B] = f[a] f[b]. (ii) f[a B] f[a] f[b]. (iii) f 1 [A B] = f 1 [A] f 1 [B]. (iv) f 1 [A B] = f 1 [A] f 1 [B]. 19
27. f : X Y A X, B Y A f 1 [f[a]], f[f 1 [B]] B 28. R 2 (x, y) (x + y, xy) 29. R 3 (x, y, z) ax + by + cz R ax + by + cz = d ( ) 1 1/2 30. Z 2 R 2 0 3/2 7 f g fg (f g)(x) = f(g(x)) 7.1. f(x) = sin x g(x) = x n f(g(x)) = sin(x n ), g(f(x)) = (sin x) n f g g f f : X Y g : Y Z (composite map) g f : X Z (g f)(x) = g(f(x)), x X 7.2. f : X Y, g : Y Z, h : Z W (h g) f = h (g f) f 1 f 2 f n x f 1 (f 2 (... f n (x)... )) 31. f g f f g g 32. 20
X X x x X X (identity mapping) 1 X id X 7.3. f : X Y f 1 X = f = 1 Y f 1 7.4. R 2 f : X Y x f(x) f(x) x Y X f (inverse mapping) f 1 f : X X 7.5. f : X Y (i) f (ii) g : Y X f g = 1 Y, g f = 1 X g g = f 1 33. f, g (f g) 1 = g 1 f 1 7.6. T f T T 1 f 1 T 1 34. a f(x) f 1 (a) f 1 [{a}] f : X Y A X A a f(a) Y f A (restriction) f A g f f g (extension) 35. f : X Y X Y {(x, f(x)); x X} f (graph) 36. f {(f(x), x); x X} 21
37. a, b C z f(z) = az + b C f f f a, b 8 f : X Y y Y X y = f 1 [{y}] {X y } y Y X y (y Y ) X = y Y X (partition) X {X i } i I X = i I X y X i X = i I X i, X i X j = if i j x X x X i i I q(x) = i q : X I X i = q 1 [{i}] X q : X I X {X i } i I x, y X q(x) = q(y) x y (i) x x (ii) x y y x. (iii) x y y z x z R(x, y) = (x y) X (equivalence relation) 8.1. (i) P, Q P Q X P Q P Q P Q / P Q (ii) n 2 Z x y x y n (iii) (similar) X x X C(x) = {x X; x x } x (equivalence class) 22
8.2. x, y X (i) x C(x). (ii) x y = C(x) = C(y). (iii) C(x) C(y) = C(x) = C(y). C(x) x C(x) C(x) X (i) X, (ii) X (iii) X x X x x = y x y (quotient set) x x (quotient map) X/ R (a system of representatives) (axiom of choice) 8.3. P Q P Q O O { OP } 8.4. n (residue class modulo n) n {0, 1,..., n 1} n = 7 38. 39. X Y X Y f : X Y x y = f(x) = f(y) 23
f : X Y f(x) = f(x) X Y x f(x) (well-defined) f : X Y 8.5. 8.6 ( ). X = {(m, n) Z 2 ; n 0} (m, n) (m, n ) mn = m n (m, n) m/n k/l + m/n = (kn + lm)/(ln), (k/l) (m/n) = (km)/(ln) 40. 41. A (x, y, z) (x, y, z ) 0 c R, (x, y, z) = c(x, y, z ) A/ S = {(x, y, z) R 3 ; x 2 + y 2 + z 2 = 1} 42 ( ). 1 n S n S n σ τ (σ(k), σ(k + 1),..., σ(n), σ(1), σ(2),..., σ(k 1)) = (τ(1), τ(2),..., τ(n)) 1 k n C(σ) S n / 9 (Galileo Galilei, 1564 1642) {2, 4, 6,... } {1, 2, 3,... } 9.1. A, B (i) A B (ii) B A A B B A Proof. (i) = (ii) (ii) = (i) Remark. A, B A B B A 24
9.2 (Cantor-Bernstein). (i) A B B A (ii) A B A, B (cardinal number) A B (equipotent) A = B A B Proof. f : A B, g : B A a A b B b = f(a) f f a A b B a A a = g(b) A n A n A B n, B A = A A 0 A 1..., B = B B 0 B 1... A 0 = A \ g(b), B 0 = B \ f(a) f(a k ) = B k+1, g(b k ) = A k+1, f(a ) = B, g(b ) = A. A 0 A 2... B 1 B 3..., A 1 A 3... B 0 B 2..., A B A B A A 0 A 1 A 2... B B 0 B 1 B 2...... Remark. 9.3. (i) A A. (ii) A B B A. (iii) A B B C A C. 25
Proof. (i) (ii) (iii) Remark. A = B (i) A = A, (ii) A = B = B = A, (iii) A = B, B = C = A = C, 9.4. [a, b] (a < b) [0, 1] R [0, 1] f : R [ 1, 1] f(x) = x/(1 + x ) 43. R (a, b) (a < b) R 44. A B, X Y A X B Y 45. A, B 2 A B (2 A ) B 46. A, B 2 A, 2 B 10 {a 1, a 2,..., a n } N {a 1, a 2,... } (countable set) ℵ 0 ( ) R ℵ ( ) Remark. (i) (ii) 10.1. Z Z = {0, 1, 1, 2, 2, 3, 3,... } 10.2. (i) (ii) {A i } i I I i I A i A i (iii) A 1,..., A n A 1 A 2 A n N 2, Z 2, Q 2 i I 26
Proof. (i) a 0, a 1, a 2,... (ii) I I = N A i } j 0 {a (i) j a (0) 0, a (0) 1, a(1) 0, a (0) 2, a(1) 1, a(2) 0, a (0) 3, a(1) 2, a(2) 1, a(3) 0,... i I A i (iii) A, B A B n 10.3. Q 10.4. (algebraic number) (transcendental number) 47. A 1 A 2... A n A n 10.5. A C A \ C A A \ C R R \ Q Proof. A \ C f : C A \ C B = f(c), A = A \ (B C) A = A B C B, C B C B C N B A A B = A \ C 48. (0, 1) [0, 1] n=1 11 11.1 (Cantor, 1874). R Proof. (0, 1) (0, 1) = {t 1, t 2,... } 0 < t j < 1 t j = t (1) j t (2) j..., t (k) j {0, 1, 2,..., 9} 27
t (1) 1, t(2) 2,... {c n } c n = { 1 if t (n) n = 0, 0 otherwise c = 0.c 1 c 2 = k=1 c k 10 k c = t n n n c c n t n c n t (n) t (n) n n (0, 1) Remark. Cantor (Cantor s diagonal argument) Gödel A A 2 A A 11.2 (Cantor, 188?). A 2 A A Proof. A 2 A f a A f(a) A A B B = {a A; a f(a)} B a A B f(a) a f(a) a B B = f(a) a f(a) a B B f(a) A 2 A N R 2 N n (n-adic expansion) 0 < a < 1 a = 0.a 1 a 2... (a j {0, 1,..., 9}) (decimal expansion) a = k=1 a k 10 k {a k } a a a k 10a = a 1 k=2 a k 10 k 1 a k = 9 (k 2) k=2 a k 10 k 1 < 9 10 k 1 = 1 k=2 28
a 1 = [10a] 10(10a a 1 ) = 10 2 a 10a 1 = a 2 + k=3 a k 10 k 2 a k = 9 (k 3) a 2 = [10 2 a 10a 1 ] a k = [10 k a 10 k 1 a 1 10a k 1 ] {a k } a k = 9 (k m) m m k=1 m 1 a k 10 k = k=1 a k 10 k + k=m m 1 9 10 k = k=1 a k 10 k + 1 10 m 1 a = 0.a 1 a 2... a m 2 a m 1, a m 1 = a m 1 + 1 a n 0 < a < 1 a = k=1 a k n k, a k {0, 1,..., n 1} {a k } a k = [n k a n k 1 a 1 na k 1 ] a n 0.a 1 a 2... a m 1 (n 1)(n 1) = 0.a 1 a 2... a m 2 a m 1, a m 1 = a m 1 + 1 C {0, 1,..., n 1} N {0, 1,..., n 1} N \ C R 11.3. n 2 {1, 2,..., n} N ℵ 49. R N 2 N 50. n 29
11.4. R π = 3.14159..., e = 2.71828..., n=1 1 10 n! Cantor Cantor R 2 R 1877 Dedekind 11.5. R n R Proof. n R {1, 2,..., n} N R 2 2 N 2 N {1, 2, 3, 4} N R Remark. R 2 R R R 2 Peano 51. R R 2 N R R 52. R R f f Q F R N R N = 2 N N = 2 N R F R 53. Cantor, Hilbert, von Neumann, Gödel. DeMorgan, Boole, Babbage, Turing, von Neumann. Agsaryim Ghuamie 30