( ) ( ) Iverson

Transcription

1 ( ) ( ) Iverson

2 ( ) ( ) a 1 B α n i = 1 e ( 2.718) π ( 3.14) 1 2 N 0 0 N Z, Q, R, C ϕ N ϕ 1.2 formula, logical formula x + y = 0 x 2 > y atomic formula logical connective,,,,,, A A A B A B A B A B A B A B A B A B x A x A x A x A

3 ( ) ( ) 3 (A) α (B) β Γ γ δ (E) ϵ, ε, (Z) ζ (H) η Θ θ, ϑ (I) ι (K) κ Λ λ (M) µ (N) ν Ξ ξ (O) (o) Π π, ϖ (P) ρ, ϱ Σ σ, ς (T) τ Υ υ Φ ϕ, φ (X) χ Ψ ψ Ω ω 1: A B A B A A A B A A A B A B A B 0 = 1 x > 3 x n x n x

4 ( ) ( ) 4 n N A, x R B n A x B n (n N A), x (x R B),,,,,,,,, x A y B C D E (( x A) (( y B) C)) (D E) x X y X s S x, y X, s S n m (n = m) x < y < z x < y y < z 1.1. a 0, a 1, a 2,... (a) a 0, a 1, a 2,... : a R ϵ R (ϵ > 0 n 0 N n N (n > n 0 a n a < ϵ)) (b) a 0, a 1, a 2,... Cauchy Cauchy : ϵ R (ϵ > 0 n 0 N n, m N (n > n 0 m > n 0 a n a m < ϵ)) (c) a 0, a 1, a 2,... : a R ϵ R (ϵ > 0 n N 0 < a n a < ϵ) (a) a (a R ( ϵ (ϵ R (ϵ > 0 ( n 0 (n 0 N ( n (n N (n > n 0 a n a < ϵ))))))))) (b) ϵ (ϵ R (ϵ > 0 ( n 0 (n 0 N ( n (n N ( m (m N ((n > n 0 m > n 0 ) a n a m < ϵ))))))))) (c) a (a R ( ϵ (ϵ R (ϵ > 0 ( n(n N ((0 < a n a ) ( a n a < ϵ)))))))) 1.2. (a) a 0, a 1, a 2,... (b) A (c) a A i.e. sup A = a (d) f a R (a) M R n 0 N n N (n n 0 a n < M) (b) M R x A x M

5 ( ) ( ) 5 (c) x A x a ( x A x c a c) (d) ϵ R (ϵ > 0 ( δ R (δ > 0 x R ( x a < δ fx fa < ϵ)))) 1.3. (a) a 1, a 2,..., a k R n (b) a 1, a 2,..., a k R n R n (c) R n R n f (a) c 1, c 2,..., c k R (c 1 a 1 + c 2 a c k a k = 0 c 1 = c 2 = = c k = 0) (b) c 1, c 2,..., c k R (c 1 a 1 + c 2 a c k a k = 0 c 1 = c 2 = = c k = 0) v R n c 1, c 2,..., c k R c 1 a 1 + c 2 a c k a k = v (c) x, y R n a, b R f(a x + b y) = af( x) + bf( y) 0 x x x A A x A x A A x x bound variable x N 0 x 0 0 x N 0 x x x Z 0 x x n i=1 i2 i a 0 x2 dx x i 1 n x 0 a free variable x N y x x y y y 1 n i=1 i2 n a 0 x2 dx a n(n + 1)(2n + 1)/6 a 3 /3 n a x x predicate condition closed formula proposition x A x A A scope Every man loves a woman M W x y L(x, y) x M y W L(x, y) y W x M L(x, y) 2 y W L(x, y) y M L(x, y) x y x M x M y W L(x, y) x y x M L(x, y) y W y W x M L(x, y)

6 ( ) ( ) 6 y x Z y Z x < y x y x + 1 x y Z x Z x < y yx Every integer is smaller than an integer 1.4. f f (a) f (b) f (c) f 1, f 2,..., f (d) f 1, f 2,..., f : (a) c R ϵ R (ϵ > 0 δ R (δ > 0 x R ( x c < δ fx fc < ϵ))) (b) ϵ R (ϵ > 0 δ R (δ > 0 c R x R ( x c < δ fx fc < ϵ))) x P Q Q x x P Q Q x x (P Q) 1.5. n (a) 2 n m n n (b) m n m n m n n m n m n prime(m) m n : (a) m N (2 m < n m n) prime(n) (b) m N (m n m n) A = B A B A B A = B B = A A = B A B sufficient condition B A necessary condition A B A B necessary sufficient condtion

7 ( ) ( ) 7 A, B x 1, x 2,..., x n A B x 1, x 2,..., x n (A B) A = B x 1, x 2,..., x n (A B) (A B) A B( A B B A) (A B) A B (A B) A B x X A x X A x X A x X A (1.1-a) a 0, a 1, a 2,... : a R ϵ R (ϵ > 0 n 0 N n N (n > n 0 a n a ϵ)) (1.1-b) a 0, a 1, a 2,... Cauchy : ϵ R (ϵ > 0 n 0 N n, m N (n > n 0 m > n 0 a n a m ϵ)) (1.1-c) a 0, a 1, a 2,... : a R ϵ R (ϵ > 0 n N a n = a a n a ϵ) (1.2-a) f(x) 1 : c R ϵ R + δ R + x R ( x c < δ f(x) f(c) ϵ) (1.2-b) f(x) : ϵ R + δ R + c R x R ( x c < δ f(x) f(c) ϵ) a 0, a 1, a 2,... (a) (b) (a) = (b) : (a) ϵ > 0 n 0 N n, m N (n > n 0 m > n 0 a n a m < ϵ) ϵ/2 > 0 (a) n N (n > n 0 a n a < ϵ/2) (A) n o n 0 n, m N (n > n 0 m > n 0 a n a m < ϵ) n > n 0 m > n 0 n, m a n a m < ϵ (A) a n a < ϵ/2 a m a < ϵ/2 a n a m a n a + a m a < ϵ/2 + ϵ/2 = ϵ (b) = (a) : Weierstrass

8 ( ) ( ) 8 Cauchy 1 > 0 (b) n 0 N m N (m > n 0 a n0+1 a m < 1) a b < 1 a 1 < b < a + 1 M = max{a 1,..., a n0, a n }, L = min{a 1,..., a n0, a n0 +1 1} i N L a i M Cauchy Cauchy Weierstrass a ki (i = 1, 2,...) a ϵ > 0 n N (m > n 0 a km a < ϵ/2) n 0 (b) n, m N (n > n 1 m > n 1 a n a m < ϵ/2) n 1 k i i n 2 = max{n 0, n 1 } m > n 2 a m a a m a km + a km a < ϵ (c) (a) (c) (b) (a) (c): {a n a n = α, n = 1, 2,...} (c) (a): {a n a n = 1/n n, 1 + 1/n n, n = 1, 2,...} f f(x) = x x y A y x A, x y A y x A, x y A = y x A 1.9. fx = 2x f fx = x 2 f(x) = 2x f(x) ϵ δ δ = ϵ/2 x c < δ f(x) f(c) = 2x 2c = 2 x c < 2δ = ϵ

9 ( ) ( ) 9 f(x) = x 2 f(x) : x 2 c 2 = x c x + c = x c (x c) + 2c x c ( x c + 2 c ) ϵ δ = min{1, ϵ/(1 + 2 c )} x c < δ x 2 c 2 < δ(δ + 2 c ) δ(1 + 2 c ) ϵ : 1.4.(b) ϵ 1 δ > 0 x c < δ f(x) f(c) ϵ c x x = 1/δ + δ/4 c = 1/δ δ/4 x c = δ/2 < δ f(x) f(c) = x 2 c 2 = (x + c)(x c) = (2/δ)(δ/2) = 1 ϵ n, m +,, /, = (a) n m n m (b) n > m n m (c) prime n n 1 (d) Goldbach 4 2 (e) : (f) 0 (a) n m p N np = m (b) n > m p N n = m + p + 1 (c) p(n) n 1 m N (m n m = 1 m = n) (d) Goldbach n N l, m N (p(l) p(m) 2n + 4 = l + m) (e) n N m N (p(m) m > n) (f) 0 p N (p 0 m N n N (n m (n p))) 1.3 Iverson Kenneth Iverson [2] P [P ] P [P ] = 0 P

10 ( ) ( ) 10 I n i, j- [i = j] n- x 1 x > 0 sgn x = 0 x = 0 1 x < 0 sgn x = [x > 0] [x < 0] [xy > 0] = [x > 0][y > 0] + [x < 0][y < 0], [xy < 0] = [x > 0][y < 0] + [x < 0][y > 0] sgn(xy) = (sgn x)(sgn y) Iverson n perfect number 2n = n]q q N[q [q n] q 0 n = q N[q n][q < n]q 6 28 m n, amicable number m + n = [q n]q = m]q q N q N[q x [x] x Gauss Iverson x π = 3, e = 3, 1 = 1 π e floor x x ceiling x x x 3 x N x = x x = x x = x x = x x = x x = x x R x x = [x Z] n x x x x x {x} x x R 0 {x} < x, y R x + y = x + y + [1 {x} + {y}] Iverson [1] 2

11 ( ) ( ) reduction to absurdity p n = p!+1 n p 1.5 pigeon-hole principle 2 1 n mn m (Ramsey : 6 ) a 5 (a) 3 (b) 3 (a) b, c, d b, c, d 3 2 a 3 (b) König 1.17 (König ). n 0 n 0 n 1 n 2, n 3,...

12 ( ) ( ) 12 Ramsey 1.18 (Ramsey : ). A A A S S S A a 0 A a 0 B 0 C 0 B 0 C 0 A A a 1 B 1 C 1 i N a i, B i, C i a i+1 B i C i a i+1 B i k > i a k B i a i+1 C i k > i a k C i a i B = {a i a i+1 B i }, C = {a i a i+1 C i } B C S S = B S S = C 1.6 N P [n α] P n α P n n N P P [n 0] k P [n k] P [n k + 1] mathematical induction 0 i P [n i] i k P [n k] P [n k + 1] n Z (n i P ) course of values induction k N (k < n P [n k]) P n N P (a) n N n(n + 1) = n(n + 1)(n + 2)/3 (b) n N (n 2 x R + (1 + x) n > 1 + nx) (c) n N θ R sin θ nθ (n + 1)θ (1 + cos θ + cos 2θ + + cos nθ) = cos sin 2 2 2

13 ( ) ( ) 13 (d) n N θ R sin θ nθ (n + 1)θ (sin θ + sin 2θ + + sin nθ) = sin sin : (c) (d) (a) A(n) n(n + 1) = n(n + 1)(n + 2)/3 n = 0 A(n) 0 A(n) n = k A(n) k(k + 1) + (k + 1)(k + 2) = k(k + 1)(k + 2)/3 + (k + 1)(k + 2) = (k + 1)(k + 2)(k + 3)/3 n = k + 1 A(n) n A(n) (b) A(n) x R + (1 + x) n > 1 + nx n = 2 A(n) (1 + x) 2 = 1 + 2x + x x A(n) n = k A(n) (1 + x) k+1 = (1 + x) k (1 + x) n = k + 1 A(n) > (1 + kx)(1 + x) x R + = 1 + (k + 1)x + kx 2 > 1 + (k + 1)x 2 A(n) (c) 2 A(n) B(n) θ R sin θ 2 (1 + cos θ + cos 2θ + + cos nθ) = 1 2 (sin θ (2n + 1)θ + sin ) 2 2 θ R sin θ 2 (sin θ + sin 2θ + + sin nθ) = 1 2 (cos θ (2n + 1)θ cos ) 2 2 n = 0 sin θ 2 1 = 1 2 (sin θ 2 + sin θ 2 ), sin θ 2 0 = 1 2 (cos θ 2 cos θ 2 ) A(n) B(n)

14 ( ) ( ) 14 n = k A(n) B(n) sin θ (1 + cos θ + + cos(k + 1)θ) 2 = 1 2 (sin θ (2k + 1)θ + sin ) + sin θ cos(k + 1)θ = 1 2 (sin θ 2 = 1 2 (sin θ 2 = 1 2 (cos θ 2 = 1 2 (cos θ 2 = 1 2 (cos θ 2 (2k + 1)θ + sin ) + 1 (2k + 1)θ ( sin + sin (2k + 3)θ + sin ) sin θ (sin θ + + sin(k + 1)θ) 2 2 (2k + 1)θ cos ) + sin θ sin(k + 1)θ 2 2 (2k + 1)θ cos ) + 1 (2k + 1)θ (cos cos (2k + 3)θ cos ) 2 n = k + 1 A(n) B(n) n A(n) B(n) (2k + 3)θ ) 2 (2k + 3)θ ) 2 n N A A N A N A A = n N n A n N k < n k N k A n A n A A n A n N n A n A n N A A n S S = {n N A} S n k < n k A[n k] A n [1] Graham, R. L., Knuth, D. E., and Patashnik, O.: Concrete Mathematics, Addison-Wesley, [2] Iverson, K. E.: A Programming Language, Wiley, APL 1976.

15 ( ) ( ) 15 2 ( ) X = {a 1, a 2,..., a n } ( )a 1 X, a 2 X,..., a n X x X x a 1, a 2,..., a n 1 P x {x P } P x ( ) x x A x z {x P } P [x z] (1) Russell R = {x x x} (1) {x U P } U {x U P } U x P z {x U P } z U P [x z] (2) 2.1 (Russell ). (1) x Q (1) z {x P } (P Q)[x z] (3) (3) R Q[x R] 1 (1) P (x) = x x,. (3) R R, R R R {x P (x)} P (R) R R. R R R {x P (x)} P (R) Q(R) R R Q(R) = R R R R R R (R R Q(R)) R R Q(R) R R Q(R). 1 U ( ) Q x U R U R

16 ( ) ( ) 16 (empty set) {} {x x x} 2.2. (a) {1, 2, 3} (b) {1, 1, 1, 1} (a) {x N 1 x 3} (b) {x C x 4 = 1} 2.3. (a) {x C x 6 = 1} (b) {x R (x + 1) 4 R} (c) {x Q y 3 = 2} (d) {x Z 0.1 < 2 x < 100} (a) {1, 1 + 3, 1 + 3, 1, 1 3, 1 3 } (b) (x + 1) 4 = x x 3 6x 2 4 1x + 1 x R 4x 3 4x = 0 x = 1, 0, 1 { 1, 0, 1} (c) {} (d) { 3, 2, 1, 0, 1, 2, 3, 4, 5, 6} a, b R a < b a, b [a..b] = {x R a x b} (a..b) = {x R a < x < b} (a..b] = {x R a < x b} [a..b) = {x R a x < b} [a..b], (a..b), (a..b], [a..b) a R (..a], (..a), [a.. ), (a.. ) (..a] = {x R x a} (..a) = {x R x < a} [a.. ) = {x R a x} (a.. ) = {x R a < x} {x P } x P {n 2 n Z} = {0, 1, 4, 9, 16, } {m n m, n N, mn = 6} = { 5, 1, 1, 5} 2.4. x {x P }

17 ( ) ( ) 17 (a) {1, 2, 4, 8, 16,...} (b) {..., 5/2, 3/2, 1/2, 1/2, 3/2, 5/2,...} (a) {2 x x N} (b) {x x Z} 2.5. {A M(2, 2; R) det A = 1, A = A 1 } = {( cos θ sin θ ) } sin θ θ R cos θ M(2, 2; R) 2 2 det A A A A A 1 A A M(2, 2; R) det A = 1, A = A 1 A 2 2 A = det A = ad bc = 1 A = ( a b ) ( c = A 1 1 d = d ad bc c ) b = a ( d a = d b = c ad bc = a 2 b 2 = 1 a, b R θ R a = cos θ b = sin θ ( ) cos θ sin θ θ R A = A M(2, 2; R) det A = (cos θ) 2 sin θ cos θ (sin θ) 2 = 1 A = A = A 1 c ) b a ( a c ) b d 2.2 X Y x X x Y X Y ( subset) 2 X Y Y X N Z Q R C {x U P } P U 2 {a, b} = {b, a, a}, {n Z n 0} = N, {n N n < 0} = 2 X X (complement) X C X C U( X) X C = {x U x X} U = R Q C ( ) (X C ) C = X U X C U \ X (difference) X \ Y {x X x Y } 2 Y X x Y Y x

18 ( ) ( ) 18 X Y X Y (intersection) X Y X Y X Y (union) X Y a X Y a X a Y, a X Y a X a Y A B A B (meet, intersect) A B = (disjoint) 2.6 (De Morgan ). U X, Y, Z U (a) (X Y ) C = X C Y C (b) (X Y ) C = X C Y C (c) X Z = X (Y Z) = (X Y ) Z (d) X Z = X Z C = Z X C (a) (b) De Morgan (a) x (X Y ) C (x X x Y ) x X x Y x X C Y C (b) 2.7 (). X Y (symmetric difference) X Y (a) X Y = (X Y ) \ (X Y ) (b) X Y = Y X (c) X = X (d) X X = (e) X (Y Z) = (X Y ) Z (f) (X Y ) Z = (X Z) (Y Z) X Y = (X \ Y ) (Y \ X) x ( ((X 1 X 2 ) X 3 ) X n ) x X 1, x X 2,..., x X n n n = 1 n = k + 1 x ( ((X 1 X 2 ) X 3 ) X k+1 ) x ( ((X 1 X 2 ) X 3 ) X k ) x X k+1 x ( ((X 1 X 2 ) X 3 ) X k ) x X k+1 x ( ((X 1 X 2 ) X 3 ) X k ) x X 1, x X 2,..., x X k x X 1, x X 2,..., x X k, x X k+1 x ( ((X 1 X 2 ) X 3 ) X k+1 ) x X 1, x X 2,..., x X k, x X k+1 (a) x X Y x Y x X x X Y (b)

19 ( ) ( ) 19 (c) x X x x X (d) x X x X 2 2 (e) (f) x y (pair) 3 x, y a, b = c, d a = c b = d (4) 2.8. x, y {{x}, {x, y}} (4) x, y = {{x}, {x, y}} a, b = c, d = a = c b = d. a = b a, b = {{a}} a, b = c, d {c} = {c, d} c = d {{a}} = {{c}} a = c a = c b = d a b a, b = c, d {{a}, {a, b}} = {{c}, {c, d}} a b {a, b} = {c} {a} = {c} {a, b} = {c, d} {a} = {c} a = c {a, b} = {a, d} a b a d b = d a = c b = d X Y (direct product) 4 X Y X x Y y x, y X Y = { x, y x X, y Y } 3 a 1, a 2, a 3 3 a 1, a 2, a 3 a 1, a 2, a 3 a 1, a 2, a 3 4 X 1, X 2,..., X n X 1 X 2 X n = { a 1, a 2,..., a n a 1 X 1, a 2 X 2,..., a n X n } n i=1 X i n i=1 X i x = (x 1,..., x n ) i x i x i (coordinate) X X X X X 2 n X X n X n n R n n 2.9. A, B, C, A, B (a) A (B C) = (A B) (A C) (b) A (B C) = (A B) (A C) 3 {x, y} (ordered pair) 4 (Cartesian product)

20 ( ) ( ) 20 (c) A (B \ C) = (A B) \ (A C) (d) (A B) (A B ) = (A A ) (B B ) (e) (A B) \ (A B ) = ((A \ A ) B) (A (B \ B )) (f) (A B) (A B ) = ((A A ) (B B )) \ (((A \ A ) (B \ B)) ((A \ A) (B \ B ))) 2.3 (family of sets) U = {X i i I} i I X i X i U i I X i U (intersection) X i U i I X i U (intersection) (union) U = i I X i = {x i I x X i }, U = i I X i = {x i I x X i } 2.10 (De Morgan ). {X i i I} U ( ) U \ X i = i I(U ( ) \ X i ), U \ X i = i I(U \ X i ) i I ( ) x U \ X i x U x X i x U ( i I x X i ) x U i I x X i i I i I i I (x U x X i ) i I (x U \ X i ) x i I(U \ X i ) i I {X i i I} {Y j j J} (a) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) (b) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) (c) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) (d) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) (e) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) (f) ( ( ) i I X i) j J Y j = i,j I J (X i Y j ) X 2 X X (power set) 2 X = {Y Y X} X Y (c), (e), (g)

21 ( ) ( ) 21 (a) 2 X 2 Y X Y (b) 2 X Y = 2 X 2 Y (c) 2 X Y 2 X 2 Y (d) 2 X Y = 2 X 2 Y X Y Y X (e) 2 X\Y 2 X \ 2 Y (f) 2 X\Y 2 X \ 2 Y (g) 2 X Y {A B A 2 X, B 2 Y } (c) X = {a}, Y = {b} 2 X 2 Y = {, {a}, {b}} 2 X Y = {, {a}, {b}, {a, b}} {A i i I} = (a) i I (2A i ) = 2 ( i I A i) (b) i I ) 2 ( (2Ai i I Ai) (a) x i I ) i x 2 (2Ai Ai i x A i x i I A i x 2 ( i I Ai) (b) x i I (2A i ) i x 2 A i i x A i = x i I A i x 2 ( i I A i) (b) 2.12 (c) 2 X X (family of subsets of X) U X A U A A U A X U U X = = X {a n } n N {b n } n N inf a n = a sup a n = a + inf b n = b sup b n = b + n N n N n N = (a) n N (a n..b n ) = (a..b + ) (b) n N [a n..b n ] [a..b + ] (c) n N (a n..b n ) (a +..b ) (d) n N [a n..b n ] = [a +..b ] A 0, A 1, A 2,..., (limit sup) lima n (limit inf) lima n 5 lima n = n N A k, k n lima n = n N A 0, A 1, A 2,... A n A n lim A n A 0, A 1, A 2,... lim A n (converge) n N k n A k (a) lima n lima n 5 lim sup A n lim inf A n

22 ( ) ( ) 22 (b) lim(a n ) C = (lima n ) C lim(a n ) C = (lima n ) C (c) (lima n ) (limb n ) lim(a n B n ) (lima n ) (limb n ) = lim(a n B n ) (d) (lima n ) (limb n ) = lim(a n B n ) (lima n ) (limb n ) lim(a n B n ) (e) A 1 A 2 = lim A n = n N A n (f) A 1 A 2 = lim A n = n N A n (g) (a) x lima n k N (k n 0 x A k ) n 0 N x lima n n N k n x A k k n k = max{n, n 0 } (b) (c) n A n A n B n B n A n B n lima n lim(a n B n ) limb n lim(a n B n ) lima n limb n lim(a n B n ) (d) A 1 A 2 k n A k = k N A k k n A k = A n (e) lima n = A k = A k = n N k N k N n N A n = lima n (f) A 2n = {a}, A 2n+1 = {}, n N lima n = {a} = lima n = {} (a..b) [a..b) (a..b] [a..b] (a) i=1 ( 1..1/i) (b) i=1 ( 1.. 1/i) (c) n=k (1/n /n) (d) lim(1/n /n) (e) n=k (( 1/n..1/n] (1/n /n)) (f) lim(( 1/n..1/n] (1/n /n))

23 ( ) ( ) 23 3 X Y X Y (function) (mapping) X Y f x X fx Y f (graph) {(x, fx) X Y x X} X Y fx f x (value) f x (image) 3.1 X Y Y X X f x X fx fx Y f Y f Y X x X fx Y x f fx f fx x fx = 3x + 4 f f λx R 3x + 4 λx X P X a X P [x a] (lambda notation) λx X P x x X P (λx X P )a a P [x a] x y R λx R yx + y 1 (0, y 1) y R y y x R λy R yx + y 1 x (λx R yx + y 1)0 = (yx + y 1)[x 0] = y 1 (λy R yx + y 1)0 = (yx + y 1)[y 0] = 1 X Y λx X x X Y (inclusion map) X = Y X (identity funtion) id X a Y λx X a a (constant map) X 2 f g x X x X fx = gx, f = g 3.2 f Y X, g Z Y f g (composition) g f λx X g(fx) (g f) Z X f Y X id Y f = f id X = f

24 ( ) ( ) f Y X, g Z Y, h W Z (h g) f = h (g f) x X ((h g) f)x = h((g f)x) = h(g(fx)) = (h g)(fx) = (h (g f))x (h g) f = h (g f) f Y X A X, B Y f (image) fa (inverse image) f 1 B fa = {fx Y x A}, f 1 B = {x X fx B} 3.2. fx = x(x 4) (a) f[0..3) (b) f 1 ( 3..0] (c) f 1 ( 5..a) ( a > 4 ) 3.3. f X Y A, A X B, B Y = (a) f(a A ) = fa fa, f 1 (B B ) = f 1 B f 1 B (b) f(a A ) fa fa, f 1 (B B ) = f 1 B f 1 B (c) f(a \ A ) fa \ fa, f 1 (B \ B ) = f 1 B \ f 1 B (d) f 1 (Y \ B) = X \ f 1 B (e) f(f 1 B) B, A f 1 (fa) f(x \ A) Y \ fa (a) b f(a A ) fa = b a A A a A A a A a A = b fa b fa b fa fa f(a A ) fa fa b fa fa b fa b fa fa = b a A A a A A b = fa f(a A ) f(a A ) fa fa f(a A ) = fa fa a f 1 (B B ) fa B B fa B fa B a f 1 B a f 1 B a f 1 B f 1 B. f 1 (B B ) = f 1 B f 1 B (b) b f(a A ) fa = b a A A a A A a A a A = b fa b fa b fa fa f(a A ) fa fa f 1 (B B ) = f 1 B f 1 B (a) (e) b f(f 1 B) fa = b a f 1 B fa = b B f(f 1 B) B a A fa faa f 1 (fa) A f 1 (fa) 3.4. f Y X g Z Y (a) A 2 X (g f)a = g(fa) (b) C 2 Z (g f) 1 C = f 1 (g 1 C)

25 ( ) ( ) f Y X x, x X (fx = fx x = x ) f (injection) y Y x X fx = y f (surjection) (bijection) f Y X f (a) f (b) X = h X Y h f = id X (c) A 2 X f 1 (fa) = A (d) Z g, g X Z (f g = f g g = g ) (e) A, A 2 X f(a A ) = fa fa (f) A, A 2 X f(a \ A ) = fa \ fa f (e) (c) 3.3 fa fa f(a A ) f 1 (fa) A b fa fa a A a A b = fa b = fa f a = a A A b f(a A ) a f 1 (fa) fa fa a A fa = fa f a = a A (b) a X y Y fx = y x hy = x hy = a h h h well-ined h f = id X (d) X = X Z = (Z ) X Z = {id } (Z = ) X (b) g = h f g = h f g = g f x x, fx = fx x, x X f({x} {x }) = = {fx} = f({x}) f({x }) x f 1 {fx} = f 1 (f{x}) {x} = f 1 (f{x}) h f = id X x = h(fx) = h(fx ) = x Z = {0} g(0) = x, g (0) = x f g = f g g g (b) (e) 3.7. f Y X f (a) f (b) B 2 Y f(f 1 B) = B (c) h X Y f h = id Y (d) Z g, g Z Y (g f = g f g = g ) f (b) 3.3 B f(f 1 B) b B f f(a) = b a A a f 1 B b = f(a) f(f 1 B) (c) y Y fx = y x hy = x f h = id X (d) (c) g = g f h = g f f = g f y Y f 1 {y} = {y} = f( ) = f(f 1 ({y})) f h = id Y y = f(hy) Z 2 gy g y z Y x y g(z) = g(z ) g, g g f = g f g g (b) (d)

26 ( ) ( ) f X Y f g f = id X f g = id Y g, g X Y g = g = f f X Y f g X Y Y f X Y X Y f f f f X Y f g f = id X f g = id Y g, g X Y g = g = f f X Y 2 X 2 Y f 2 Y 2 X f A 2 X f A = fa, B 2 Y f B = f 1 B (a) f f f (b) f f f A Z 2 X Y f X A Y A f Z Y Z X f f = λg X A f g, f = λg Z Y g f (a) f f f (b) f f f f, f Y X g, g Z Y (a) f g g f (b) f g g f (c) g f g (d) g f f (e) f g f = g f g = g (f) g g f = g f f = f (g) g f g f (h) g f g f (a) f, g x, x X g(fx) = g(fx ) g fx = fx f x = x g f (b) f, g z Z g gy = z y Y f fx = y x X z g(fx) = (g f)x = z x g f.

27 ( ) ( ) 27 A X x [x A] X {0, 1} X A (χ A λx X [x A] X A, B X (a) A B x X [x A] [x B] (b) x X [x A B] = [x A][x B] (c) x X [x A B] = [x A] + [x B] [x A][x B] (d) x X [x X \ A] = 1 [x A] (e) x X [x A \ B] = [x A] [x A][x B]

28 ( ) ( ) X Y 2 ((binary) relation) X Y X 1 X 2 X n n (n-ary relation) X n X n R x, y R xry f Y X { x, fx x X} X Y f (graph) X X = { x, x x X} X X (identity) R X Y xr 1 y yrx Y X R 1 R (inverse rellation) R 1 X Y R 2 Y Z x(r 1 R 2 )z y Y (xr 1 y yr 2 z) X Z R 1 R 2 R 1 R 2 (composition) X 2 R n R } R {{ R } R n R 0 = X n 4.1. R 1 X Y, R 2 Y Z, R 3 Z W (a) X R 1 = R 1 Y = R 1 (b) (R1 1 ) 1 = R 1 (c) (R 1 R 2 ) 1 = R2 1 R1 1 (d) (R 1 R 2 ) R 3 = R 1 (R 2 R 3 ) X (equivalent relation) X (a) : x X x x (i.e. X ) (b) : x, y X (x y y x) (i.e. = 1 ) (c) : x, y, z X (x y y z x z) (i.e. ( ) ) X x X [x] 6 [x] = {y X x y} 4.2. X x 1, x 2 X 4 (a) x 1 [x 2 ] (b) x 1 x 2 (c) [x 1 ] = [x 2 ] 6 [x] x/

29 ( ) ( ) 29 (d) [x 1 ] [x 2 ] X X (quotient set) X/ (X/ ) = {[x] x X} πx = [x] X X/ π (natural mapping) 4.3. f Y X, x y fx = fy f g (X/ ) X h Y X/ f = h g 4.4. R = < 4.5. S = R 2 \ {(0, 0)} λ x, y = λx, λy x, y x, y S ( x 2 + y 2 = 1 ) x, y 1 : () λ = 1 > 0 x, y = λ x, y () x, y = λ x, y, λ > 0 x, y = 1 λ x, y, 1 λ > 0 () x, y = λ x, y, λ > 0 x, y = λ x, y, λ > 0 x, y = λλ x, y, λλ > 0 1 x, y S x, y = λ x, y x 2 + y 2 = 1 1 = x 2 + y 2 = λ 2 (x 2 + y 2 1 ) λ > 0 λ = x2 + y 2 λ x, y = λ x, y x 2 + y 2 = n X 1, X 2,..., X n X 1 X 2 X n {1, 2,..., n} n i=1 X i x i {1, 2,..., n} xi X i {X i i I} (direct product) i I X i I i I X i x i I xi X i xi x i (coordinate) i xi x i i I X = i I X i X i λx X xi i (projection) π i π i x = xi 4.6. {A i i I}, {B i i I} = (a) ( i I A i) ( i I B i) = i I (A i B i )

30 ( ) ( ) 30 (b) ( i I A i) ( i I B i) i I (A i B i ) {X i i I} i I X i = = i I X i = i I X i = i I X i (axiom of choice) 7 i I x x X i = x ( i I X i ) I i I xi X i i I X i ZF 4.7. X Y X Y X Y X X Y : f X Y x 0 X Y X g y Y y f(x) y = f(x) x X 1 g(y) = x y f(x) g(y) = x 0 g g Y X x X g 1 {x} = X x X g 1 {x} = Y f f(x) g 1 {x} f f(x) = f(x ) g(f(x)) = g(f(x )) g(f(x)) {x}, g(f(x )) {x } x = g(f(x)) = g(f(x )) = x 4.8. (a) i I A i π i0 : i I A i A i0 (b) i I A i i I A i i I B i0 i I A i B i 4.9. i I f i : A i B i f : i I A i λ f f = λa i A i λ i I f i (a i ) i I B i f(a) i = f i (a i ) (a) f i I f i (b) f i I f i 7

31 ( ) ( ) X orderpartial order 8 X 2 (a) x X x x i.e. X (b) x, y X (x y y x x = y) i.e. ( 1 ) X (c) x, y, z X (x y y z x z) i.e. ) preorder X X x y x y y x A/ [x] [y] X (a) (b) (c) x x x x x y x y x y y x y x x y y x x y y z (x y y x) (y z z y) (x y y z) (z y y x) = x z z x x z X/ (a) (b) (c) x x [x] [x] [x] [y] [y] [x] x y y x x y [x] = [y] [x] [y] [y] [z] x y y z = x z [x] [z] X < x < y x y x y < (d) (e) x X x x x, y, z X x < y y < z x < z X < < x y x < y x = y : x < y x y x y x < x x x x (d) 8

32 ( ) ( ) 32 x < y y < z x, y, z X x < y y < z (x y x y) (y z y z) = (x y y z) x z x = z x y y z = x y y x = x = y x < y x z x < y y < z = x z x z x < z (e) (d),(e) X < x y x < y x = y (a) x = x = x < x x = x x x (b) x y y x (x < y x = y) (y < x y = x) (x < y y < x) (x < y y = x) (x = y y < x) (x = y y = x) = x = y ( 3 x > x ) (c) x y y z (x < y x = y) (y < z y = z) (x < y y < z) (x < y y = z) (x = y y < z) (x = y y = z) = x < z x = z x z ( 3 x < z ) X 1 < 1 > X X, X N Z Q R X 2 X X X X reverse order : x x y x = y x (a) x = x x x x (b) x x y y x x x = y (c) x x y y x z x = y y = z = x = z x x z X a x x x x (b) x y y x y x x y = x = y (c) x y y z y x z y = z x x z

33 ( ) ( ) R X 2 R i=0 Ri R (refrexive transitive closure) (R R 1 ) R (refrexive transitive simmetric closure) (a) (b) X, X, f x, y X (x y = f(x) f(y)) order-homomorphism 9 f x, y X (x y f(x) f(y)) f order-isomorphism X Y X = Y X, X X X x, y X x y x y extension X, S X x, y S x y x y) S S S X, X X X X X λx X x X, X, R ( 1..1) N Z Q R 2 X S X a S b S (b a) a S maximum, greatest b S(a b b = a) a S maximal S max S minimum, least minimal min S X order-preserving function monotone function, isotone function

34 ( ) ( ) 34 [a..b] (a..b] [a..b) (a..b) X a, b X closed interval [a..b] open interval (a..b) (a..b] [a..b) [a..b] = {x X a x b} (a..b) = {x X a < x < b} (a..b] = {x X a < x b} [a..b) = {x X a x < b} a b b a a b X chain X linear order total orderx antichain X < x, y X (x < y x = y x > y) X < a < b 2 a, b X [a, b] = {a, b} a < c < b c b a a b a b b a a a atom a a coatom 2 a, b a b dense X S s S (s b) b X b S upper bound S b S S least upper bound sup, join b S b 2 S b, a X (S a b a) S b, a X (S a b a) b S sup S lower bound greatest lower bound inf, meet b S S inf S S S b S, a X (a S a b)

35 ( ) ( ) 35 b S, a X (a S a b) X b X S X a S 2 (a) b S b a (b) x X (x < a b S x < b) X Y f Y X f x, y X (x < y fx < fy) X A B X max A max A = sup A max A max B max A max B sup A sup B sup A sup B min A min B inf A inf B X, Y X Y A Y sup A sup x A sup Y A inf (a) sup X A sup Y A sup X sup Y 2 (b) sup X A sup Y A (c) sup Y A sup X A N n m n m (a) N, (b) N, (c) N, S N sup S inf S (d) N, : (b) = 1 = 0 (c) sup S S inf S S (d) m n n m n 0 n n X 2 X U 2 x X sup U inf U X X X X O(X) O(X) O(X)

36 ( ) ( ) Peano N 0 N S N N 3 10 (P1) n, m N (Sn = Sm n = m) (P2) n N Sn 0 (P3) P [n 0] k N (P [n k] P [n Sk]) n N P (P2) 0 S S 1 {0} = (P1) S (P3) P n P [n α] P n α A = {n N P } k A P [n k] (P3) A 2 N ((0 A k A Sk A) A = N) Sx x succesor x + 1 (P1) (P3) (P3) n N P P [n 0] k P [n k] P [n k + 1] 2 2 P [n 0] k N (P [n k] P [n Sk] 1.6 f f0 k fk f(k + 1) n fn 5.1 ( ). x + 0 = x, x + Sy = S(x + y)

37 ( ) ( ) ( ). 5.3 (). x0 = 0, x(sy) = x + xy N (a) (b) (c) (d) 1 = S0 (e) : x, y, z N (x + z = y + z x = y) (f) x, y N (x + y = 0 x = y = 0) 5.4 () x y N z Nx + z = y 1.6 (course of values induction) (P3 ) n N ( k N (k < n P [n k]) P ) = n N P (P3) (P3 ) 5.6. P n (P3) (P3 ) (: n Q k N (k < n P [n k]) n N Q ) 5.7. (a) x, y, z N(x < y = x + z < y + z) (b) x, y, z N(x < y z 0 = xz < yz) (c) : x, y, z N (xz = yz z 0 x = y) n k fk fn 5.8. n i ( ) ( 0 n + 1 = [i = 0], i i ) ( ) n n i ( ) n = + i 1 ( ) n i

38 ( ) ( ) 38 ( ) n (a) i [0..n] = 0 i i n ( ) ( ) n n (b) n N = = 1 n ( 0 ) n + m (n + m)! (c) n, m N = m m!n! m ( ) ( ) n + i n + m + 1 (d) n, m N = n n + 1 i=0 ( ( ) ) n n! (c) A(n) i N 0 i n = i i!(n i)! ( ) 0 n = 0 A(n) = 1 0! = 1 A(n) 0 0!0! n = k A(n) 0 < i < k + 1 ( ) ( ) k + 1 k = + i i 1 ( ) k + 1 (k + 1)! = 1 = 0 0!(k + 1)!, ( ) k = i n = k + 1 A(n) A(n) (d) ( ) k + 1 k + 1 = 1 = (k + 1)! (k + 1)!0! k! (i 1)!(k i + 1)! + k! (k + 1)! = i!(k i)! i!(k i + 1)! 2 P x, y,..., z x, y,..., z P x, y,..., z f(x, y,..., z) n Q x, y,..., z (f(x, y,..., z) = n P ) x, y,..., z P n N Q x, y,..., z (f(x, y,..., z) = 0 P ) k x, y,..., z (f(x, y,..., z) = k P ) x, y,..., z (f(x, y,..., z) = k + 1 P ) k x, y,..., z (f(x, y,..., z) < k P ) x, y,..., z (f(x, y,..., z) = k P ) 2 2 P m, n m, n N P n N P [m 0]

39 ( ) ( ) 39 P [m 0][n 0] k P [m 0][n k] P [m 0][n k + 1] j n N P [m j] n N P [m j + 1] P [m j + 1][n 0] k P [m j + 1][n k] P [m j + 1][n k + 1] Ackermmann 2 A(m, n) n N A(0, n) = n + 1 m N A(m + 1, 0) = A(m, 1) m, n N A(m + 1, n + 1) = A(m, A(m + 1, n)) 2 2 A(m+1, 0) A(m + 1, n + 1) k A(m, k) A(m + 1, n + 1) A(m + 1, n) 5.9. Ackermann A(m, n) (a) A(1, n) = n + 2 (= 2 + (n + 3) 3) (b) A(2, n) = 2n + 3 (= 2(n + 3) 3) (c) A(3, n) = 8 2 n 3 (= 2 n+3 3) A(4, n) A(5, n) n L n (A), (B) L 2 = 4 L 3 = 7 (A) (B) (a) L n (b) L n n (a) L n L 0 = 1 L n = L n 1 + n (n = 1, 2,...) n n 1

40 ( ) ( ) 40 n n 1 n (b) L n = n + (n 1) = n(n + 1)/ n m m n m 1 m 1 m + 1 L(m, n) (2 ) n 3 P n P n P 0 = 1 P n = P n 1 + L n 1 (n = 1, 2,...) L n n n n 1 L n 1 n 1 L n 1 P n n P n = n i=1 {n(n 1)/2 + 1} + 1 = n(n2 + 5)/6 + 1 m L(m, n) L(1, n) = n + 1, L(m + 1, 0) = 1, L(m + 1, n + 1) = L(m + 1, n) + L(m, n) 5.12 (Catalan ). n n A B Catalan C n n = 3 5 C 3 = 5 B Catalan A C 0 = 1 C n+1 = n C i C n i C n = 1 ( ) 2n n + 1 n i=0 5.3 N 2 Z N 2 / p 1, m 1 p 2, m 2 p 1 + m 2 = p 2 + m 1

41 ( ) ( ) N 2 [ p, 0 ] +p [ 0, m ] m +p p p N N Z [ p 1, m 1 ] + [ p 2, m 2 ] = [ p 1 + p 2, m 1 + m 2 ] [ p 1, m 1 ][ p 2, m 2 ] = [ p 1 p 2 + m 1 m 2, p 1 m 2 + m 1 p 2 ] [ p 1, m 1 ] [ p 2, m 2 ] Z (a) well-ined (b) (c) p 1 + m 2 m 1 + p 2 (d) (e) 0 = [ 0, 0 ] +p = [ p, 0 ] p = [ 0, p ] (f) +1 = [ 1, 0 ] (g) x, y Z( x)y = x( y) = (xy) (h) x Zx0 = 0x = Z (a) well-ined (b) p, m N (0 [ p, m ] m p) x Z (0 x x 0) (c) x, y, z Z (x < y x + z = y + z) x, y Z (x > 0 y > 0 xy > 0) Z x, y, z Z (xz = yz z 0 x = y) 5.4 Z (N \ {0}) Q Z (N \ {0})/ n 1, d 1 n 2, d 2 n 1 d 2 = n 2 d 1 [ n, d ] n/d / nd 1 n/1 n n Z Z Z n 1 /d 1 + n 2 /d 2 = (n 1 d 2 + d 1 n 2 )/d 1 d 2 n 1 /d 1 n 2 /d 2 = n 1 n 2 /d 1 d 2 n 1 /d 1 n 2 /d 2 n 1 d 2 d 1 n 2

42 ( ) ( ) Z (N \ {0}) Q (a) well-ined Z (b) (c) (d) (e) 0 = 0/1 n/d ( n)/d (f) 1 = 1/1 (g) 0 = 0/1 Q Q (a) well-ined Z (b) Q (c) x, y, z Q (x < y x + z < y + z) x, y Q (x > 0 y > 0 xy > 0) 5.20 ( ). x, y Q (x < y z Q x < z < y) 5.5 x Q N Cauchy sequence n N i 0 N i, j N (i > i 0 j > i 0 x(i) x(j) < 1/n) Cs(Q) Cs(Q)/ R x y n N i 0 N i N (i > i 0 x(i) y(i) < 1/n) q Q [λi N q] R q Q Q R Q R [x] + [y] = [λi N x(i) + y(i)] [x] [y] = [λi N x(i)y(i)] [x] [y] n N i 0 N i N (i > i 0 x(i) y(i) < 1/n) x R x 0 x x x Cs(Q)

43 ( ) ( ) R x Cs(Q) n N i N x(i) < n (a) well-ined Q (b) (c) (d) (e) 0 = [λi N 0] [x] [x] = [λi N x(i)] (f) 1 = [λi N 1] (g) 0 = [λi N 0] R x R s Cs(Q) x = [s] s x R x = [x] R (a) well-ined Q (b) R (c) x > y n 0 N i 0 N i N (i i 0 x(i) y(i) 1/n 0 ) (d) x, y, z R (x < y x + z < y + z) x, y R (x > 0 y > 0 xy > 0) (a) x y x x y y x y n N x y i 0 N i i 0 x(i) y(i) < 1/(3n) x x y y i 1, i 2 N i i 1 x(i) x (i) < 1/(3n) i i 2 y(i) y (i) < 1/(3n) j = max{i 0, i 1, i 2 } i > j x (i) y (i) = x (i) x(i) + x(i) y(i) + y(i) y (i) < 1/(3n) + 1/(3n) + 1/(3n) = 1/n x y q, r Q R q = [λi N q] r = [λi N r] Q r q n, i N r(i) q(i) = q r 0 < 1/n R r q (b) x x x(i) x(i) = 0 < 1/n x y y x n N i 0, i 1 N i i 0 x(i) y(i) < 1/n i i 1 y(i) x(i) < 1/n j = max{i 0, i 1 } i > j x(i) y(i) < 1/n x y x y y z n N i 0, i 1 N i i 0 x(i) y(i) < 1/(2n) i i 1 y(i) z(i) < 1/(2n) j = max{i 0, i 1 } i > j x(i) z(i) = (x(i) y(i)) + (y(i) z(i)) < 1/(2n) + 1/(2n) = 1/n x z x y y x n 0, n 1 N i N j > i x(j) y(j) 1/n 0 i N k > i y(k) x(k) 1/n 1 n = max{n 0, n 1 } x, y

44 ( ) ( ) 44 i 0, i 1 N j, k > i 0 x(j) x(k) < 1/n j, k > i 1 y(j) y(k) < 1/n j, k > max{i 0, i 1 } x(j) y(j) 1/n 0 y(k) x(k) 1/n 1 1/n 0 + 1/n 1 (x(j) y(j)) + (y(k) x(k)) x(j) x(k) + y(j) y(k) < 1/n + 1/n n = max{n 0, n 1 } (c) ((b) x > y x y n 0 N i N j N (j i x(j) y(j) 1/n 0 ) x y n 0 i 1, i 2 N j, k i 1 x(j) x(k) < 1/(3n 0 ) j, k i 2 y(j) y(k) < 1/(3n 0 ) j max{i 1, i 2 } x(j) y(j) 1/n 0 j k j x(k) y(k) = x(k) x(j) + x(j) y(j) + y(j) x(k) 1/(3n 0 ) + 1/n 0 1/(3n 0 ) = 1/(3n 0 ) (d) i N y(i) x(i) = (y(i) + z(i)) (x(i) + z(i)) x > 0 y > 0 (c) n 0, n 1, i 0, i 1 N j i 0 x(j) 1/n 0 j i 1 y(j) 1/n 1 n = n 0 n 1 i = max{i 0, i 1 } j N j i x(j)y(j) 1/(n 0 n 1 ) = 1/n (c) xy > x R x = [λi N x(i) ] : x(j) x(k) x(j) x(k) x Cs(Q) λi N x(i) Cs(Q) 0 x x = x n N 0 x i 0 N j i 0 0 x(j) < 1/(2n) j i 0 x(j) x(j) x(j) + x(j) < 1/n λi N x(i) x = x 0 > x x = x 5.24 (c) n 0, i 0 N j i 0 0 x(j) 1/n 0 > 0 j i 0 n N x(j) + x(j) = x(j) + x(j) = 0 < 1/n λi N x(i) x = x x R q Q x < q x q i 0 N j N (j i 0 x(j) < q) : 5.24 (c) x < q n 0, i 0 N j i 0 q x(j) 1/n 0 j i 0 x(j) q 1/n 0 < q i 0 N j i 0 x(j) < q m N j i 0 x(i) q < 0 < 1/m x q 5.27 (). x, y R (x < y q Q x < q < y)

45 ( ) ( ) 45 : x, y R x < y 5.24(c) n 0, i 0 N j i 0 y(j) x(j) > 1/n 0 x, y i 1, i 2 N j, k i 1 x(j) x(k) < 1/(4n 0 ) j, k i 2 y(j) y(k) < 1/(4n 0 ) i 3 = max{i 0, i 1, i 2 } q = y(i 3 )/2 + x(i 3 )/2 Q j i 3 j q x(j) = q x(i 3 ) + x(i 3 ) x(j) = y(i 3 )/2 x(i 3 )/2 + x(i 3 ) x(j) > 1/(2n 0 ) 1/(4n 0 ) = 1/(4n 0 ) 5.24(c) x < q j i 3 j y(j) q > 1/(4n 0 ) q < y 5.28 (). x R (x > 0 y R n N y < nx) : x > 0 n 0, i 0 N i i 0 x(i) 1/n 0 y R n 1 N y(i) < n 1 n = n 0 n i i 0 nx(i) y(i) n/n 0 y(i) = n 1 + 1/n 0 y(i) 1/n 0 nx > y x R (x > 0 n N 1/n < x) x R N n N i 0 N i, j N (i i 0 j i 0 x(i) x(j) < 1/n) a n N i 0 N i N (i i 0 x(i) a < 1/n) limit a converge lim i x(i) = a x(i) a (i ) s Cs(Q) s(i) (i N) x i x i = [λj N s(i)] λi N x i x = [s] lim i x i = x : n N i 0 N j i 0 x j x < 1/n 5.25 x x j x j x = [λk N s(j) s(k) ] j i 0 j N i 1 N k i 1 s(j) s(k) < 1/(2n) 5.26 x j x 1/(2n) < 1/n s Cs(Q) j, k i 2 s(j) s(k) < 1/(2n) i 2 N i 0 = i 1 = i () (). R