Transcription

1 數學導論 學數學

2

3 前言 學 學 數學 學 數學. 學數學 論. 學,. (Logic), (Set) 數 (Function)., 學 論. 論 學 數學.,,.,.,., 論,.,. v

4

5 Chapter 1 Basic Logic 學 數學 學 言., logic. 學 學,, 學., 學 數學. 數學 論 statement. 2 > 0 statement, 3 < 2 statement x > 0 statement ( x ) Connectives 數 statements statement, statements connectives. connectives statement And. and connective. connective. P Q statement, P Q P and Q statement. P Q? and, P Q P Q, P Q, P Q. 2 > 0 and 2 < 7, 2 > 0 2 > 7. truth table connectives statements. T (true), F (false). true table. P Q P Q T T T T F F F T F F F F Truth table P,Q, P,Q,. P T, Q F P Q F. 1

6 2 1. Basic Logic P,Q P Q Q P. P Q Q P. logically equivalent. Truth table statements connectives, (P Q) R truth table P Q R P Q (P Q) R T T T T T T F T F F F T T F F F F T F F T T F T F T F F F F F T F F F F F F F F Question 1.1. P (Q R) truth table? (P Q) R P (Q R). (P Q) R P Q R ; P (Q R) Q R P. truth table (P Q) R P (Q R) logically equivalent Or. P Q statement, P Q P or Q statement. or. :,., ; , 105. 數學, or, P Q P Q ( P Q ). 言, P Q, P Q., 4 < 5 or 4 < 3 statement, 4 < 5. 4 > 5 or 4 > 6 statement,. 4 < 5 or 4 > 3 statement, and,,. P Q truth table. P Q P Q T T T T F T F T T F F F Question 1.2. P Q Q P logically equivalent? (P Q) R P (Q R) logically equivalent? and, or connectives,. P,Q,R statements (P Q) R, (P Q) R,... statements.

7 1.1. Connectives 3? (P Q) R (P Q) R. R, (P Q) R, R P,Q, (P Q) R., (P Q) R P (Q R) logically equivalent. P (Q R) P Q R. R, Q Q R, P P (Q R). R, (P Q) R, (P Q) R P (Q R) logically equivalent. truth table logically equivalent. P Q R P Q (P Q) R T T T T T T F T F T F T T F T F F T F T T T F T T T F F F F F T F F F F F F F F P Q R Q R P (Q R) T T T T T T F T T T F T T T F F F T T F T T F T T T F F F F F T F T F F F F F F, (P R) (Q R) truth table, (P Q) R (P R) (Q R) logically equivalent. P Q R P R Q R (P R) (Q R) T T T T T T T F T T T T F T T T T T F F T T T T T T F T T T T F F T F F F T F F T F F F F F F F Question 1.3. truth table (P Q) R (P R) (Q R) logically equivalent. truth table logically equivalent. logic logical equivalences. connectives truth table. 論 logical equivalences, logical equivalences. or 數學. 數學 x y x > y or x = y, 4 3 statement or. 4 5, If - Then. 數學 connective 學 connective,. P Q statement, P Q if P then Q statement, P Q. P Q 數學., 數學 P Q P,Q ( P,Q ). P,Q statement, x 數.

8 4 1. Basic Logic connective P,Q ( ). 數學 if x > 3 then x 2 > 9 statement ( x > 3 x 2 > 9 statement, if-then, statement). x > 3 x 2 > 9. if 3 > 2 then 2 is even statement ( 3 > 2 2 數 ). P Q 前, 數學 論 論. 數學, if P then Q P, Q. ( : statement,,.), if P then Q P, Q. P, Q. 數學 論 if P then Q P, Q, P. if P then Q P,Q statements connective, if P then Q statement, P,Q P Q. P Q Q P 數學. 學 P Q Q P., P Q P Q, P Q. if x > 3 then x 2 > 9, x 3 x 2 > 9. Q P. 言, P Q Q P. if P then Q, P Q Q P equivalent. Question 1.4. P Q. Q, 言 P? P Q. 前 數學, P,Q statements, P Q, P Q, P Q. P Q, P Q, P Q. P, P Q? P Q 論 P, Q, P, Q 前 P Q, P Q. 2 > > 9, 前 if x > 3 then x 2 > 9 statement., 4 > 3, ( 4) 2 > 9, 前 if x > 3 then x 2 > 9 statement. 言, P Q truth table. P Q P Q T T T T F F F T T F F T Question 1.5. truth table Q P P Q logically equivalent? (P Q) R P (Q R) logically equivalent? 學 P Q, if and only if connective.

9 1.1. Connectives 5 P Q. if P then Q, Q if P P implies Q P is sufficient for Q ( P Q ) Q is necessary for P ( Q P ) P only if Q ( Q P ) Q whenever P ( P Q ) If and Only If. P Q Q P and, (P Q) (Q P), P if and only if Q, P Q. 數學 P Q. 數學 P Q P Q Q P. P Q, Q P. P,Q. 言, P Q Q P Q P ( P Q ). P Q P Q ( P Q). P Q. 前 數學, P Q P Q Q P.. P,Q. P Q P Q. P Q truth table. P Q P Q T T T T F F F T F F F T Question 1.6. P Q Q P truth table P Q truth table. Question 1.7. P Q Q P logically equivalent? (P Q) R P (Q R) logically equivalent? P Q, 數學,. P Q P, Q, P Q., (P Q) (Q P) P Q, P,Q, P Q, P Q Q P. P,Q, P Q. P Q, Q P, P Q P Q. P Q, 導 P Q, Q P P Q truth table ( equivalent), 前 數學 P Q Q P, P Q, P Q. P Q. P if and only if Q,

10 6 1. Basic Logic P iff Q P is equivalent to Q P is necessary and sufficient for Q 1.2. Logical Equivalence and Tautology 前 logical equivalence. logical equivalence 導 logical equivalences. Truth table logical equivalence.. P,Q statements, P Q Q P statements ( ), P Q Q P logically equivalent. P,Q 數, statement, P Q P,Q, P Q statement., ( ) P,Q, connectives statement form, P Q Q P statement forms logically equivalent. statement forms logically equivalent, (P Q) (Q P). logical equivalence : logically equivalent statement forms 數 statement form, logical equivalence. (P Q) (Q P), P P Q ((P Q) Q) (Q (P Q))., logically equivalent statement forms truth table, 數 statement forms truth table., 數 ( ) logically equivalent statement forms, statement forms logically equivalent. (P Q) (Q P) (R S) (S R), (P Q) (Q P) P R S, P S R ((R S) Q) (Q (S R))., statement forms A,B logically equivalent B statement form C logically equivalent, A C logically equivalent. ((P Q) R) ((Q P) R), ((Q P) R) (R (Q P)), ((P Q) R) (R (Q P)). truth table. truth table statement forms logically equivalent. logically equivalent. 前

11 1.2. Logical Equivalence and Tautology 7 學 logical equivalences,, (P Q) (Q P), (P Q) (Q P) (1.1), ((P Q) R) (P (Q R)), ((P Q) R) (P (Q R)) (1.2),, ((P Q) R) ((P R) (Q R)), ((P Q) R) ((P R) (Q R)) (1.3) 導 logical equivalences. Example (P Q) (P Q) statement form. ((P Q) R) ((P R) (Q R)), R P Q, (1.3) (P Q) (P Q) ((P (P Q)) (Q (P Q))). (1.4) (P (P Q)) ((P P) Q) (Q (P Q)) (Q (Q P)) ((Q Q) P) ((P (P Q)) (Q (P Q)) (((P P) Q) ((Q Q) P)). (1.5) (P P) P (P P) P, (((P P) Q) ((Q Q) P)) ((P Q) (Q P)) (P Q). (1.6) (1.4), (1.5), (1.6), ((P Q) (P Q)) (P Q). statement form truth table, statement form tautology.. P P truth table P P P T T, F T P P tautology. Question 1.8. P P tautology? P (P P) tautology? Tautology,. logically equivalent. statement forms A,B logically equivalent, A,B, A B. A B tautology., A B tautology, A,B, truth table. A B.. Proposition A,B statement forms. A B logically equivalent A B tautology.

12 8 1. Basic Logic 前, A B A B tautology ( A B A B tautology), A B tautology A B. Proposition A B A B tautology. Question 1.9. A,B statement forms. A B A B tautology? A B tautology A B? Question A,B,C statement forms. A B B C tautology, A C tautology? tautology contradiction ( ). statement form. contradiction, not. Question A,B statement forms. (1) A tautology, (A B) B A B tautology. (2) A contradiction, (A B) B A B contradiction Not and Contradiction not not equivalences. 前,.,,. Not, statement P, P, not P, P. P, P., P, P. P truth table., P P T F. F T P ( P). (1.7) Not P, connectives statement not,. (P Q), ( P) ( Q), truth table P Q P Q (P Q) T T T F T F F T F T F T F F F T P Q P Q ( P) ( Q) T T F F F T F F T F F T T F F F F T T T, P Q P Q, (P Q) ( P) ( Q)., truth table, (P Q) ( P) ( Q). (1.8)

13 1.3. Not and Contradiction 9 數學. 0 x 1, x 1 and x 0., x > 1 or x < 0. 數 x P x 1 statement, Q x 0, P, Q x > 1, x < 0. 0 x 1 P Q x > 1 or x < 0 ( P) ( Q). (P Q) ( P) ( Q) logically equivalent, ( P) ( Q) ( x > 1 and x < 0 ). statement form logically equivalent not. (1.8) P, Q P Q, (( P) ( Q)) ( ( P)) ( ( Q)). ( P) P, (( P) ( Q)) (P Q). not, (P Q) ( P) ( Q). (1.9) x 0, x < 0. P, Q x > 0, x = 0, x 0 P Q. P x 0, Q x 0. ( P) ( Q) x 0 and x 0, x < 0 x 0. (1.7), (1.8), (1.9) 導 not statement forms logical equivalence. (1.8), (1.9) DeMorgan s laws., statement form (P Q) logically equivalent? P Q, truth table, P P Q P Q, P. (P Q) P Q logically equivalent,. Question x 0 x 1 數 x, x 0 x < 1 數 x.? P Q P,,., A, B statement form A tautology, (A B) A B logically equivalent., A, A B B. Question x 2 0 x > 0 數 x, x 2 0 x 0 數 x.? (P Q) logically equivalent, P Q. P Q P Q. Q, P. Q, P. Q P statement form. truth table

14 10 1. Basic Logic P Q P Q P T T F T T F F F F T T T F F T T (P Q) (Q P). (1.10) (Q P) (( P) Q) ( Q) Q, (P Q) (( P) ( Q)), (1.10) (( P) ( Q)) (( Q) ( P)), (P Q) (( Q) ( P)). (1.11) P Q, Q P,. (1.10), (P Q) (Q P). DeMorgan s laws (Q P) (( Q) ( P)) (P Q) (P ( Q)). (1.12) (1.10), (1.11), (1.12) P Q 論 logical equivalences. (1.10), statement form logical equivalence,,. P Q,, ( (1.3)) (P Q) (Q ( P)) (P ( Q)). (1.13) (P Q) (P Q) (( P) ( Q)). (1.14) DeMorgan s laws, (1.7),, ( (1.1),(1.2), (1.3)), 導 statement form not logical equivalence. (1.13) not (P Q) (( Q) P) (( P) Q)., (1.14) Q Q, (P Q) (P Q). A statement form, A A, A A truth table, A A contradiction., B statement form A B contradiction, A B, B A. Proposition Proposition A,B statement forms. A B logically equivalent A B contradiction.

15 1.4. Quantifiers Quantifiers statement connective not, statement form. statement,,. 數學 statement quantifier ( ),. quantifiers,. 數學 quantifiers : for all, for every ( ),. there exists, there is (, ),. there is a unique ( ),!.!, 論,., 論 quantifiers. 數 數, 數 數. quantifiers,. 數. x x, for all x in R there exists an x in R, 數. : x, x 2 0. 數 x x 2 0. statement, 數 x,. statement x, P(x). P(x) x ( P(x) x 2 0). x P(x). statement x,. x, x 2 > 0 (x = 0 )., x, P(x), x P(x). statement, x P(x).,,, ( there exists ). x, x 2 > 0, x, x 2 > 0 ( x = 1, )., x, P(x), x, P(x) ( x ).. x P(x), x P(x).. x, P(x),? 前 x, P(x) x P(x),, x P(x). x, P(x). 前 x, x 2 > 0, x, x 2 0. 學 x, P(x) x, P(x). x, P(x) x, P(x). x, P(x), x, P(x). x, P(x) x, P(x). x, x 2 > 0, x, x 2 0,

16 12 1. Basic Logic x, x 2 0.,. 言 logical equivalence ( x,p(x)) ( x, P(x)). (1.15) x, P(x), x P(x). x P(x), x, P(x)., 學 x, P(x) x, P(x)., x P(x) x P(x). x, P(x) x, P(x). 言 logical equivalence ( x,p(x)) ( x, P(x)). (1.16) Question (1.15) logical equivalence 導 (1.16). Quantifier 數, 數, 數 數. 數, x, y,p(x,y) statement, P(x,y) x,y., 數 f (x) x = a l ( lim x a f (x) = l) ε > 0, δ > 0,0 < x a < δ f (x) l < ε 數. statement. (1) x, y, P(x, y) (2) x, y, P(x, y) (3) x, y, P(x, y) (4) x, y, P(x, y). (1) : x y P(x,y). x, y, y, x. x, y,x + y = 0 statement. x, y x + y = 0. y x, y = x. x = 1 y = 1, x = 2 y = 2. x,y,. (2) : x y P(x,y). x, y, x, y. x, y,x + y = y statement. x y x + y = y. x, x = 0. (1) x, y,x + y = 0 statement, x y y, x,x + y = 0 statement. y x x + y = 0.,, x, y,p(x,y) y, x,p(x,y) x y,. Question x, y,x + y = y statement, y, x,x + y = y,? x, y,x + y = y y, x,x + y = y,? Question f (x,y),g(x,y) 數. x, y, f (x,y) = 0 y, x,g(x,y) = 0. f (x,y) = 0 g(x,y) = 0, x = 101? (3) (4). (3) x, y P(x,y)., (x,y) P(x,y),

17 1.4. Quantifiers 13 x y statement. (4) x y P(x,y)., (x,y) P(x,y). x y statement. x = 3, y = 7 P(3,7), y = 7, x = 3 P(x,y). 言 (3), (4) 數 quantifier, x,y. (3) x,y, P(x,y), (4) x,y, P(x,y). 數 statement quantifier. (1), x, y,p(x,y)., y,p(x,y) H(x). statement x,h(x). (1.15), x, H(x). (1.16) H(x) ( y, P(x,y)), ( x, y, P(x, y)) ( x, y, P(x, y)). ( x, y, P(x, y)) ( x, y, P(x, y)) ( x, y, P(x, y)) ( x, y, P(x, y)) ( x, y, P(x, y)) ( x, y, P(x, y)). 前, 數 f (x) lim x a f (x) = l ε > 0, δ > 0, (0 < x a < δ f (x) l < ε). (1.12) (0 < x a < δ f (x) l < ε) ((0 < x a < δ) ( f (x) l ε)). lim x a f (x) = l ε > 0, δ > 0,(0 < x a < δ) ( f (x) l ε).,., x. x 3 x 2 9, statement x,x 3 x 2 9., statement 數 x. 數 x, x 3, x 2 9. x < 3, x 3 前, x 3 x 2 9. x,x 3 x 2 9 ( P P Q, 學 ). x, x x. 言, x P(x) Q(x) statement, x,p(x) Q(x), x P(x) Q(x). x P(x) Q(x), x., x, x,p(x) Q(x), x,p(x) Q(x)., x,p(x) Q(x) x P(x) Q(x), P(x) x P(x) Q(x). x P(x), x,p(x) Q(x), x P(x) Q(x). 3 數 x, x 2 = 10

18 14 1. Basic Logic x,(x > 3) (x 2 = 10) ( x = 10), x,(x > 3) (x 2 = 10) ( x = 2 ). Question f (x,y) 數. 數 a > 0 f (a,y) = 0 statement, 數學? statement.

19 Chapter 2 Methods of Proof 學, 學..,, IF-Then 數學 P Q statement. statement, direct method, contrapositive method contradiction method Direct Method. direct method, P Q. (, P, Q ). P Q, P,.. Example p,a,b 數. if p a and p b, then p a + b. Proof. p a, p b, 數 m,n a = pm,b = pn. a + b = pm + pn = p(m + n). m + n 數, p a + b.,. P Q, P R R Q, P Q. P R, P R, R Q R Q, P Q, P Q.. Example a 數 a 1. x,y 數 a x = a y, x = y. Proof. 數 y, a y 0, a x = a y, a y a x y = 1. 數 z, a z = 1, z = 0, x y = 0, x = y. 15

20 16 2. Methods of Proof, (a x = a y ) (a x y = 1), (a x y = 1) (x = y) (a x = a y ) (x = y)., a 數 a 1, a z = 1, z = 0. direct method, contradiction method. direct method, P, Q. proof in cases.. Example x 數. if x 2 3x + 2 < 0, then 1 < x < 2. Proof. x 2 3x + 2 = (x 1)(x 2) < 0, 2, (1) (x 1) < 0 and (x 2) > 0; (2) (x 1) > 0 and (x 2) < 0. (1) x < 1 x > 2. 數 x x < 1 x > 2, (1), (2), x > 1 x < 2. 1 < x < 2.,, 學 (1), (2) x 2 3x+2 < 0?. : x x 2 3x+2 < 0, x (1) (2). (1) (2), x x 2 3x+2 < 0, x (2). x (2) x 2 3x + 2 < 0, (1), if 1 < x < 2, then x 2 3x + 2 < 0, if x 2 3x + 2 < 0, then 1 < x < 2.. Question 2.1. x 數. (1) If x 2 3x + 2 < 0, then 0 < x < 3. If x 2 3x + 2 < 0, then 1.3 < x < 1.7. statements? (2) If 0 < x < 3, then x 2 3x + 2 < 0. If 1.3 < x < 1.7, then x 2 3x + 2 < 0. statements? Contrapositive Method. ( Q) ( P) P Q statement contrapositive statement., P Q ( Q) ( P) logically equivalent ( (1.11)). P Q ( Q) ( P)., ( Q) ( P) P Q. P Q, P, Q contrapositive method. ( Q) ( P).., 導, statement, contrapositive statement. contrapositive method.. Example x,y 數. if x y, then x 3 y 3.

21 2.1. IF-Then 17, f (x) = x 3,.. contrapositive method, (x 3 y 3 ) ( x 3 = y 3 ), (x y) ( x = y). Proof. contrapositive method, x 3 = y 3, 0 = x 3 y 3 = (x y)(x 2 + xy + y 2 ). x 2 + xy + y 2 = (x y) y2. x 2 + xy + y 2 > 0, x = 0 and y = 0 ( x = y). (x y)(x 2 + xy + y 2 ) = 0 x y = 0, x = y. if x y, then x 3 y 3. statement x, x, contrapositive method.. Example x 數. if x 2 is even ( 數 ), then x is even. Proof. contrapositive method, x 數, x 2 數. x 數, x x = 2n + 1, n 數. x 2 = (2n + 1) 2 = 4n 2 + 4n + 1 = 2(2n 2 + 2n) + 1 數. Question 2.2. x,y 數. contrapositive method if x + y is even, then x and y are both even or odd ( 數 ). proof in cases, contrapositive method. Example contrapositive method., (1 < x < 2) ( x 2 or x 1) (x 2 3x + 2 < 0) ( x 2 3x + 2 0).. Example x,y,a 數. if xy = a, then x a or y a. Proof. contrapositive method, ((x a) (y a)) ( x > a and y > a) (xy = a) ( xy a). x,y,a, x > a and y > a xy > ( a) 2 = a, xy a. Question 2.3. x,y,a 數. if xy = a, then x a or y a?, Example 2.1.6,? Contradiction Method. (1.10) P Q Q P logically equivalent., Q P P Q. Q P, 前 proof in cases,. (P Q), ( Q) P logically equivalent ( (1.12)). ( Q) P, P Q. contradiction method ( ). Contradiction method, ( Q) P, 導 statement. ( Q) P, P Q. P Q, 導,

22 18 2. Methods of Proof direct method P, contrapositive method Q., direct method contrapositive method 導 ( P 導 Q Q 導 P), 導. P Q, P Q, P Q contradiction method.. Example r 數, if r 2 = 2, then r is irrational ( 數 ). 數 數, direct method. contrapositive method r 數, r 2 2. 前 導, contradiction method. Proof., r 數 r 2 = r,. r 數, r r = (m/n), m,n 數. m,n 數, 2,, m,n 數. r 2 = 2, m 2 = 2n 2, Example m 數. m m = 2m, m 數. 4m 2 = 2n 2, n 2 = 2m 2. Example n 數. m,n 數. if r 2 = 2, then r is irrational. Example 2.1.7, r = (m/n) 2,. contradiction method. Example 2.1.2,, a 1 數, z 數 a z = 1, z = 0. contradiction method statement. Example a 1 數. z 數 a z = 1, z = 0., z 0 a z = 1.? statement a = 1 前 ( ), a 1. Proof. contradiction method, z 0 a z = 1. z 0, 1/z, (a z ) 1/z = a a z = 1, a = (a z ) 1/z = 1 1/z = 1. a 1, a z = 1, z = If and Only If. P Q P Q Q P., 導 P Q, P Q.,,, P Q., 導. P Q P Q Q P.

23 2.2. Existence and Uniqueness 19 a 數 a 2 數 a 數,. a = 2n, n 數, a 2 = (2n) 2 = 4n 2 數. 導,. a 2 數, a 2 4n 2? 導 ( Example ). (P Q) (( Q) ( P)) (Q P) (( P) ( Q)) P Q ( P) ( Q) logically equivalent. 學 P Q, ( P) ( Q).,. a,b 數, ab is even a is even or b is even ab is odd a and b are odd.,,. 學 ( Q) ( P) P Q.,,. statement, 前.,.,? 數學 statement: The following are equivalent. (1) P; (2) Q; (3) R. ( P,Q,R, ). P Q, Q R and R P.,. P Q, Q R and R P. Q P, Q R R P, R Q, R P P Q. P R, P Q Q R.,, R Q, Q P and P R., P R, P Q and Q R. P R, P Q Q R, R P, R Q Q P.,, 導, statement. 前 statement 導 statement, Existence and Uniqueness Existence, uniqueness. 數學., existence uniqueness..,., 論 existence uniqueness.

24 20 2. Methods of Proof Existence. existence. constructive method. nonconstructive method 論 導,. 數 x 6x 2 x 1 = 0. 6x 2 x 1 (2x 1)(3x + 1) x = 1/2 ( x = 1/3) 數 6x 2 x 1 = 0. construct method. 數 f (x) = 6x 2 x 1, f (0) = 1 < 0 f (1) = 4 > 0. 數 數 數, f (x) = 0 0 < x < 1,., x 6x 2 x 1 = 0, nonconstructive method.. Example there exists irrational numbers a,b such that a b is rational. Proof. Constructive Method: a = 2 b = log 2 9. a 數. b 數. m,n 數 log 2 3 = n/m. 2 m = 3 n, 3 數 數,. b = log 2 9 數. a b = log 2 9 = 2 log 2 3 = 3, 數 a,b a b 數. Nonconstructive Method: a = 2 b = 2. a,b 數. c = (a ) b. c 數, a = 2,b = 2. c 數, a = c,b = 2, a b = ( 2) 2 2 = 2 2 = 2. 數 a,b a b 數. nonconstructive method 2 2 數. a = b = 2 a = 2,b 2 = 2,, nonconstructive method. 2 2 數, a = 2,b 2 2 = 2 constructive method. 2 數 ( ).,, nonconstructive method. Question 2.4., construct method there exists irrational numbers a,b such that a b is rational. constructive method,,., 學 導,. 學,. 導,, 導., 導,,,, (

25 2.2. Existence and Uniqueness 21 P Q ).,,.. Example 數 x 3 2x = x 2?, 3 2x = x 2 4x + 4, x 2 2x + 1 = 0. x = 1., x = 1. x = 1, 數. x = 1, 1 = 1. 數 x 3 2x = x 2. nonconstructive method,. 前 數 數 x 6x 2 x 1 = 0.,., pigeonhole principle ( ). Dirichlet s drawer principle, pigeonhole principle. Theorem (Pigeonhole Principle). n 數. n n.,. Proof., constructive method., statement, n n, n.. pigeonhole principle.,,. 6 數, 數 5 數. 6 數 6, 數 0 0, 數 1 1,. 數 6 數 5,,. 數 5 數.. 16 數, 4 數 5 數. 數 5 數 0,1,2,3,4 3, 數 15, 16 數. Theorem 2.2.3,. Theorem k,n 數. n kn., k. Question 2.5. Theorem 2.2.4, 數 數 ( ). 數 數. 數 數.,.

26 22 2. Methods of Proof Uniqueness. 前..,,. Example x x = 1,.,.. 前,.,. R 2. Example R 2 O R 2 V V + O = V, O. (1) : O = (x,y), V = (a,b) R 2. O V + O = V, (a,b) + (x,y) = (a + x,b + y) = (a,b). x = 0,y = 0. O, (0,0). a + x = a,b + y = b, (2) : O, Q R 2 O Q V R 2, V + O = V (2.1) V + Q = V (2.2) Q = V (2.1) Q + O = Q. O = V (2.2) O + Q = O. Q + O = O + Q, Q = O. O Q,. Question 2.6. V R 2 : R 2 W V + W = O, W. Example 2.2.5, O, O = (0,0)., O = (0,0),...,. 數學,.. Example 數 r, r 3 = 3, 數 r. Proof. Example 2.1.4, x,y 數 x y, x 3 y 3. r R, r 3 = 3 s r 數 s 3 = 3, Example = s 3 r 3 = 3. 數 s s 3 = 3. Example x y, x,y,.., Example 數 r r 3 = 3,., 數 ( 數 f (x) = x 3 ). 3 1/3 r 3 = 3 數 r.

27 2.3. Mathematical Induction Mathematical Induction 數學. 數學 數 axiom ( ), 論. 數學. 數學,,,. 數學 論 axiom ( ). 數學 前, well-ordering principle., 前. well-ordering principle.,. well-ordering, 數,. principle ( )!, 數 1,..,,., 數學. Theorem (Mathematical Induction). statement (1) P(1) (2) k N P(k), P(k + 1) 數 n, P(n). Proof. 數 n P(n),. (1), (2) 數 n, P(n). 數 n, P(n), 數 n, P(n). P(n) 數 n., well-ordering principle, 數 m P(m). (1) P(1), m 1. m 1 數. m 1 數 m 1 < m, m P(m) 數 P(m 1). (2), P(m 1), P((m 1) + 1) = P(m). P(m). 數 n, P(n), 數 n, P(n). 數學, (1) P(1), (2) k = 1, P(1) P(2). k = 2, P(2) P(3).. P(1). (2) P(k) P(k + 1). P(k), P(k), P(k) P(k + 1). P(k) P(k + 1), 數學. f (x) = x 2 + x x = 1 f (1) = 43 數. x = 2, f (2) = 47 數. f (3) = 53, f (4) = 61,

28 24 2. Methods of Proof f (5) = 71 數. x 數 n f (n) 數. x = 39 數., f (k) 數 f (k + 1) 數, 數學., x = 40, f (40) = = 40(40 + 1) , 數. 數學. Example a,b 數, 數學 : 數 n a n b n a b 數. Proof. a n b n (a b)(a n 1 + a n 2 b + + b n 1 ), a n b n a b 數. 數學. n = 1 a b. a b 數,. a k b k a b 數, a k+1 b k+1 a b 數. a k+1 b k+1 a k b k. a k+1 b k+1 a k b k, a k+1 b k+1 = aa k bb k = aa k ab k + ab k bb k = a(a k b k ) + (a b)b k. a k b k a b 數, a k b k (a b)m, m 數. a k+1 b k+1 = a(a b)m + (a b)b k = (a b)(am + b k ). a k+1 b k+1 a b 數. 數學, 數 n, a n b n a b 數, 數學,. P Q, 前 2.1. P(k) P(k + 1), P(1),P(2), P(2),P(3),. P(k) P(k + 1)., P(k) P(k + 1),.. Example 數學 n 數. 論, 論. : 數,. : k 數, k + 1 數. k + 1 數, 數 a, k 數. k 數 b. 數, 數 a. k 數, a = b. 數學, n 數.. 數 k 1 數. k = 1,, 數 a 數, a = b. 論 k 2, P(k) P(k + 1), k = 1 P(k) P(k + 1). 數學 數 k, P(k), P(k + 1). 論.

29 2.3. Mathematical Induction 25 n = 1, n 5, 2 n > n 2. 數學 1,., Theorem 論, 數學. Corollary (Extended Mathematical Induction). m 數. statement (1) P(m) (2) k m 數 P(k), P(k + 1) m 數 n P(n). Proof. Q(n) = P(m + n 1). P(m), Q(1) = P(m). k N Q(k), m + k 1 m 數, P(m + k 1) = Q(k), (2) P(m+k) = Q(k +1)., k N Q(k), Q(k +1). Theorem n N, Q(n) = P(m + n 1). n m 數, P(n). extended mathematical induction Corollary, Theorem m = 1 Corollary Theorem 2.3.1, Theorem Corollary equivalent. Example 數 n, n 5, 2 n > n 2. Proof. extended mathematical induction m = 5 P(n) 2 n > n 2. n = 5, 2 5 = 32 > 25 = 5 2, P(5). k 5 數 2 k > k 2. 2 k+1 = 2 2 k, 2 k > k 2 2 k+1 > 2k 2. (k + 1) 2 = k 2 + 2k + 1 2k 2 > k 2 + 2k + 1, 2 k+1 > (k + 1) 2, P(k + 1). 2k 2 > k 2 + 2k + 1 k 2 2k > 1, k 2 2k = k(k 2), k 5 k 2 2k > 1. k 5 數 P(k), P(k + 1), extended mathematical induction (Corollary 2.3.4) 5 數 n P(n), 2 n > n 2. 數學 P(k) P(k + 1). 數, 前. P(1) P(2), P(2) P(3), P(1), P(2) 前, P(1). P(3) P(4), P(1),P(2), 數學. Corollary (Strong Mathematical Induction). m 數. statement (1) P(m) (2) k m 數 P(m),P(m + 1),...,P(k 1),P(k), P(k + 1)

30 26 2. Methods of Proof m 數 n P(n). Proof. m 數 n, Q(n) = P(m) P(m+1) P(n 1) P(n). P(m), Q(m) = P(m). k m 數 Q(k), P(m),...,P(k 1),P(k), (2) P(k + 1). P(m),P(m + 1),...,P(k 1),P(k), Q(k + 1) = P(m) P(m + 1) P(k) P(k + 1)., k m 數 Q(k), Q(k + 1). Corollary m 數 n Q(n). Q(n) P(m),P(m + 1),...,P(n 1),P(n), P(n), n m 數, P(n). Corollary Corollary P(k) P(k + 1) P(m),P(m + 1),...,P(k 1),P(k) P(k + 1), Corollary Corollary strong mathematical induction extended mathematical induction. Question 2.7. Corollary Corollary 前 extended mathematical induction mathematical induction, 數學.. strong mathematical induction. Example 數 數. 學. n 1 數, n 數, n 數. n 數, n n 1 數, 數.., ( 數 ). 數學,., k 數, k + 1 數, strong mathematical induction. Proof. n = 2, 2 數,. k 2 i = 2,3,...,k, i 數. k + 1. k + 1 數, k + 1 數. k + 1 = ab, 1 < a,b k. 前 a,b 數, k + 1 = ab 數. strong mathematical induction 1 數 數. 數學, P(k) ( P(m),P(m + 1),...,P(k) ) P(k + 1). 導 k. Example 2.3.3, k 數 k + 1 數 k 2. k = 1,

31 2.3. Mathematical Induction 27 ( Example )., k, k,,., 數學,,. Example Fibonacci sequence {F 0,F 1,F 2,...}, F 0 = 0,F 1 = 1 i 2, F i F i = F i 1 + F i 2. F n < 2 n 2, for n 4., F k+1 F k F k 1, F k F k+1. strong mathematical induction. F 2 = F 1 +F 0 = 1, F 3 = F 2 +F 1 = 1+1 = 2, n = 4, F 4 = F 3 + F 2 = = 3, F 4 = 3 < = 4. k 4 4 i k, F i < 2 i 2. F k+1 = F k + F k 1. F k < 2 k 2 F k 1 < 2 (k 1) 2 = 2 k 3 F k+1 < 2 (k+1) 2 = 2 k 1. k = 4, i = k 1 4 i k, F k 1 < 2 k 3 ( F k 1 = F 3 = 2 = ). k = 4, F k+1 = F 5 = F 4 + F 3 = 5 < = 8,. Proof. F 4 = 3 < 2 4 2,F 5 = 5 < k 5 i = 4,5,...,k F i < 2 i 2. 4 k 1 k 4 k k, F k < 2 k 2,F k 1 < 2 (k 1) 1 = 2 k 3, F k+1 = F k + F k 1 < 2 k k 3 = 2 k 3 (2 + 1) < 4 2 k 3 = 2 k 1 = 2 (k+1) 2. 數學 F n < 2 n 2, for n 4., 20 數 4 5 數. n > 20, 數 l,m n = 4l + 5m. 學 1 = 5 4, k = 4l + 5m, k + 1 = 4l + 5m + (5 4) = 4(l 1) + 5(m + 1)., 數 4 數 5 數, 4 5 數., k = 4l + 5m, k + 4 = 4(l + 1) + 5m, 21,22,23, 數, 數學. Example n 數 n > 20, l,m 數 n = 4l + 5m. 前, n 0 數, n,22 + 4n,23 + 4n,24 + 4n 4l + 5m, l.m 數. 20 數. 21 = ,. k k = 4l + 5m, l.m 數. 21+4(k+1) = (21+4k)+4 = 4l +5m+4 = 4(l +1)+5m,. n 0 數, n 4l + 5m, l.m 數. 22 = , 23 = = , 數學. 數學, strong mathematical induction. Proof. 21 = , 22 = , 23 = = n = 21,22,23,24. k i k 數 i,

32 28 2. Methods of Proof 數 l,m i = 4l + 5m. k + 1, k + 1 = (k 3) + 4, i = k 3 21 i k, 數 l,m k 3 = 4l + 5m, k + 1 = 4l + 5m + 4 = 4(l + 1) + 5m. 數學, n 20 數, l,m 數 n = 4l + 5m. Question 2.8. 數 4 數 5 數. 數學 數學. 數, 數 數學. 數, 數 數學. 數, row 數 column 數 數學.

33 Chapter 3 Set 論 數學 論. 論. 論, Basic Definition,. 數學,.,. ( set),, ( element). set, A,B,S, set. 數學. : N 數, Z 數, Q 數, 數 R. x S, x S, x belongs to S ( x S). x S, x S. 數學, set element element. S, x, x S.,,. S = {1,2,3} 3, 1,2 3. S, 1 S, 4 S., set-builder notation. {x : P(x)}, : x x, : P(x) x P(x). {x : P(x)} P(x) x. 前,,. Definition A,B. B element A element, B A subset ( ), B is contained in ( ) A, B A. B A A B, A,B equal, A = B. B A B A, B A proper subset, B A. 29

34 30 3. Set subset proper set,,. B A, B x, A, 數學 x B x A. A = B x B x A.,,,. : Example A = {1,2,2}, B = {1,2,3}, C = {3,3,1,2}, D = {n N : 1 n 3}, E = {2,4}. A 1,2, 1 B 2 B, A B. 3 B 3 A, B A, A B. B = C. x B, x N 1 x 3, x D. B D., x D x N 1 x 3, x = 1,2,3 B, D B, B = D. 1 B 1 E, B E subset., 4 E 4 B, E B subset. A,B sets, B A subset, B A. B A A B, B A. Question 3.1. P(x), Q(x) statement form. P = {x : P(x)} Q = {x : Q(x)} : (1) P Q P(x) Q(x). (2) P = Q P(x) Q(x).,., subset, universal set ( ). 論 數, R universal set. x R. universal set, a,b 數, universal set Q 論 ax + b = 0. 論 ax 2 + b = 0, universal set R 數 C.,, universal set. universal set, 論 set universal set subset. empty set ( )., /0. /0?, x /0. operations, /0. universal set empty set,. Proposition X universal set A set. A X /0 A.

35 3.1. Basic Definition 31 Proof. X universal set, A X subset, A X., /0 A x /0 x A. x /0, P P Q x /0 x A /0 A. Question 3.2. Question X universal set. universal set? empty set? 數學,, 論 subset. Proposition A,B,C sets,. (1) A A. (2) A B B C, A C. Proof. (1) x A, x A, A A. (2) x A, A B x B. B C x C. 言, x A x C, A C. Question 3.3. Proposition A = B B = C, A = C. Question 3.4. A,B,C sets,? (1) A B B C, A C. (2) A B B C, A C. (3) A B B C, A C. (4) A B B C, A C., A = B A B B A., 數, 學.. Example A = {(x,y) R 2 : x 2 x = y = 2} B = {(2,2),( 1,2)}. A = B. Proof. (x,y) A, x 2 x = 2 y = 2, x = 2 x = 1 y = 2. (x,y) A, (x,y) = (2,2) (x,y) = ( 1,2). x B, A B. (x,y) B, (x,y) = (2,2) (x,y) = ( 1,2) x 2 x = y = 2, (x,y) A. B A, A = B Question 3.5. A = {x R : x = x 2}, B = {1}, C = {4}, D = {1,4}. A,B,C,D. Venn diagrams., universal set, ( ) set. X set A.

36 32 3. Set X A. Venn diagrams A,B. X X A Ḅ. A B A B X A,B, A,B, A B. Venn diagrams,. Proposition (2) A B B C, A C. X A. B C Venn diagrams,. Question 3.6. A,B,C sets. A B. B C, Venn diagrams. A C? B C, Venn diagrams, A C?, A,C Venn diagrams, B,C. ( ) ( ).,. A B B C A C, A B B C A C. A = {1}, B = { {1} } { {{1} } }, C =. A B B C, A C.

37 3.2. Set Operations Set Operations set operation,. operations, intersection, union set difference, set operations Intersection and Union. intersection union. Definition A,B sets. A B = {x : x A and x B} the intersection of A and B (A B ). A B = {x : x A or x B} the union of A and B (A B ). A B A,B, A B A,B.. Example A = {1,2,3}, B = {2,4,6}. 2 A B, A B = {2}. 1,3 B A, A B 1,3 A B. 4,6 A B. 2 A B A B, 2 A B. 數 A B, A B = {1,2,3,4,6}.. A B = {2} A = {1,2,3} B = {2,4,6} A B = {1,2,3,4,6}., x A B, x A x B, x A x B, (A B) A and (A B) B. (3.1) A B, A,B disjoint., A,B disjoint. x A, x A B, x A B. A (A B) and B (A B) (3.2) Question 3.7. (A A) = A (A A) = A.,. Proposition A,B,C,D sets A B C D. (A C) (B D) and (A C) (B D). Proof. A B, x A x B. C D, x C x D. x A C, x A x C. x B x D. (A C) (B D)., x A C, x A x C. x A x B, x C x D. x A C x B D. (A C) (B D).

38 34 3. Set, A B A D, C = A Proposition (A A) (B D). (A A) = A, A (B D)., A B C B, (A C) (B B). (B B) = B, (A C) B.. Proposition 導, corollary ( ). Corollary A,B,C,D,E sets. (1) A B A C, A (B C). (2) D A E A, (D E) A. Question 3.8. Corollary 3.2.4, 導 Proposition Proposition A,B sets. equivalent. (1) A B. (2) (A B) = A. (3) (A B) = B. Proof. (1) (2) (1) (3). (1) (2): A B, (A B) = A. (3.1) (A B) A, A (A B). A A A B, Corollary A (A B). (1) (2)., (3.1) (A B) B. A = (A B) A B, (2) (1). (1) (3): A B, (A B) = B. (3.2) B (A B), (A B) B. A B B B, Corollary 3.2.4, (A B) B. (1) (3)., (3.2) A (A B). (A B) = B A B, (3) (1). Definition and, or. : (1) A B = B A. (2) A B = B A. (3) (A B) C = A (B C). (4) (A B) C = A (B C). (3),, A B C. (4),, A B C.

39 3.2. Set Operations 35,, ((P Q) R) ((P R) (Q R)), ((P Q) R) ((P R) (Q R)),. Proposition A,B,C sets, ((A B) C) = (A C) (B C), ((A B) C) = (A C) (B C). Proof. (A B) A C C Proposition ((A B) C) (A C). ((A B) C) (B C). Corollary ((A B) C) (A C) (B C). x (A C) (B C) x A C x B C. proof in cases, x C x C. x C, x (A B) C. x C, x A C x B C, x A x B, x A B. x (A B) C., x (A C) (B C) x (A B) C, ((A C) (B C)) (A B) C. ((A B) C) = (A C) (B C). ((A B) C) = (A C) (B C), A (A B) C C Proposition (A C) ((A B) C), (B C) ((A B) C). Corollary (A C) (B C) ((A B) C)., x (A B) C, x A B x C. x A B, x A x B. x A, x C, x A C. x (A C) (B C)., x B, x B C. x (A C) (B C), ((A B) C) (A C) (B C). ((A B) C) = (A C) (B C) Question 3.9. Proposition (1) (2) Proposition Proposition (2) (3) Set Difference. set difference. Definition A,B sets, A \ B = {x : x A and x B}, the set difference of B in A (B A ). X universal set, A c = X \ A = {x : x A} the complement of A (A ). A c {x : x X and x A}, X universal set, X, x X x A.,. Q, Q c = /0, R, Q c 數., A\B = A B c, A\B B\A. (A \ B) (B \ A) = /0. A A c = /0 B B c = /0, (A \ B) (B \ A) = (A B c ) (B A c ) = (A A c ) (B B c ) = /0. Example X = {1,2,3,4,5,6},A = {1,2,3},B = {2,4,6}. 1,3 A 1 B 3 B, 1,3 A \ B. 2 A 2 B, 2 A \ B. A \ B = {1,3}.

40 36 3. Set B \ A = {4,6}. (A \ B) (B \ A) = {1,3} {4,6} = /0. 1,3,5 X 1,3,5 B, 1,3,5 B c. 2,4,6 B 2,4,6 B c, B c = {1,3,5}. A B c A B c = {1,2,3} {1,3,5} = {1,3} = A \ B. set difference. A,B,C sets A B, x B, x A. x A, A B x B, x B. A B x C \ B, x C x B, x C x A, x C \ A. (C \ B) (C \ A)., A C,. Proposition A,B,C sets. A B (C \ B) (C \ A). A C, A B (C \ B) (C \ A). Proof. 前 A B C \ B C \ A ( A C ). A C (C \ B) (C \ A), A B, x A x B. C \ B,C \ A not, contradiction method. x A, x B,. A C x A x C, x B, x C \ B. 前 (C \ B) (C \ A), x C \ A, x C x A. x A. x A x B, A B. Question A C A B (C \ B) (C \ A)? A C,? C = X, A C = X, Proposition 3.2.9, A B (X \ B) (X \ A).. Corollary A,B sets. A B B c A c. Definition set difference not, 導 set difference,. Proposition A,B,C sets,. (1) (C \ (C \ A)) = (C A)., (A c ) c = A. (2) C \ (A B) = (C \ A) (C \ B)., (A B) c = (A c B c ). (3) C \ (A B) = (C \ A) (C \ B)., (A B) c = (A c B c ). Proof. 前 equivalence 導,. (1): x C \ (C \ A) x C x C \ A. x A, x C \ A ( x C), x C \ A, x A. x (C \ (C \ A)), x C X A ( x C A). (C \ (C \ A)) (C A)., x C A, x C, x (C \ A), x C \ (C \ A). x (C \ A) x C x A,

41 3.2. Set Operations 37 x C A, x (C \ A). (C A) (C \ (C \ A)), (C \ (C \ A)) = (C A). C = X, X \ A = A c, X \ (X \ A) = X \ A c = (A c ) c. X A = A, (A c ) c = A. (2): (A B) A, Proposition (C\A) (C\(A B)). (A B) B (C \ B) (C \ (A B)). Corollary (2) (C \ A) (C \ B) C \ (A B)., x C \ (A B), x C x A B. x A, x C \ A, x (C \ A) (C \ B). x A, x B, x B x A x B, x A B. x C \ B, x (C \ A) (C \ B). C \ (A B) (C \ A) (C \ B). C = X, X \ A = A c, X \ B = B c X \ (A B) = (A B) c (A B) c = (A c B c ). (3): (2) (A c B c ) c = ((A c ) c (B c ) c ), (1), (A c B c ) c = (A B). complement (1) (A c B c ) = (A B) c. C \ (A B) = C (A B) c = C (A c B c ) and (C \ A) (C \ B) = (C A c ) (C B c ), C (A c B c ) = (C A c ) (C B c ), C \ (A B) = (C \ A) (C \ B). Question Proposition (2) C \ A = C \ (C A). Proposition (C A) (C B) (C \ B) (C \ A). operations,, connectives,. operations 導., operations 導,.,, 導, 導., 學 導.. Example A,B,C B c A, ((C \ A) B) = B. :. B ((C \ A) B), ((C \ A) B) B. x ((C \ A) B), x B. x ((C \ A) B) x C \ A x B. x B,, 論 x C \ A, x C x A. x B,, x B. x B, x B c, B c A x A. x A, x B. ((C \ A) B) B. : 前. B, Proposition (C \ A) B, ((C \ A) B) = B.

42 38 3. Set (C \ A) B? B c A. C \ A = C A c, Corollary B c A A c (B c ) c, Proposition (1) A c B. (C \ A) = (C A c ) (C B) B Indexed Family 前,, operation., 論.,,. 前,.,,. 論, 數, 5 A,B,C,D,E, A B C D E.,.,.. 數, 前.,, 100, A 1,A 2,...,A 100 (, A i ). summation, A i, A i. A i = [i 1,i] ( i 1 i 數 ), 100 i=1 A i = /0, i=1 100 i=1 i=1 A i = [0,100].? 前, 數 i N, A i, A i. 學 數, A i, A i., i i=1 數,, A 5, A 6, A 7, A A i, A i. i m n A i, i=5 i=5 n n A i, A i. i m A i, i=m i=m n n A i, A i., 學 A i, A i A i, A i n i=m i=m i=m i=m i=m i=m.,.., 數 數 數. 數, 數. 數, ( r,r) r > 0,,?, index set. index set. 前 A i = [i 1,i], i 數 N, N index set. [ r,r], 數 R + index set, i=1

43 3.3. Indexed Family 39 A r = [ r,r]. A r,r R +, indexed family., index set. index set, indexed family. I index set, A i, {A i,i I} indexed family., indexed family.,, indexed family. A,B, index set I = {1,2} indexed family, A 1 = A, A 2 = B. index family. A,B, ; A,B.. Definition I index set, {A i, i I}, I index set indexed family. indexed family intersection A i = {x : x A i, i I}. i I indexed family union A i = {x : x A i, i I}. i I,. Example index set I 1 數. i I, A i = {m/i : m Z}. A i = Z, i I A i = Q. i I, n Z, n = ni/i. ni Z, n A i, i I. Z A i., x A i, i I x A i. x A 2 x A 3, i I i I x = m/2 x = m /3, m,m Z. 3m = 2m, 3m 數. m 數 2n, n Z. x = m/2 = n Z. A i Z, A i = Z. i I i I x Q, 數, x m/n, m Z, n N. n = 1, x = m Z. x x = 2m/2, x A 2. n 2, n I, x A n. Q i I A i., x i I A i, n I, x A n. x = m/n, m Z. x Q, A i Q, A i = Q. i I i I Question A i Example m Z, p,q 數 p mq, p m, p,q 數, A p A q = Z. m N, A i = Z. i=m

44 40 3. Set Question A i Example 3.3.2, m N, n 數 m < n A i = Q? i=m A i = Q. i=m, indexed family. Proposition Proposition {A i, i I}, {B i, i I} I index set indexed family. i I A i B i, i I A i i I B i and A i B i. i I i I Proof. x i I A i, i I, x A i, A i B i, x B i. i I, x B i. A i B i. i I i I i I x A i, i I x A i, A i B i, x B i. x B i, i I i I A i B i. i I i I, i I, A i = A, A i = A A i = A. i I i I Proposition Corollary Corollary A,B set {A i, i I}, {B i, i I} I index set indexed family. (1) i I A A i, A i I A i. (2) i I B i B, i I B i B. A i 數 N index set indexed family A 1 A 2 A i ( n A i+1 A i, i N). n N, A n A i, i n, Corollary 3.3.4, A n A i. i=1 n n, A i A n, A i = A n., i N, A i, i=1 n i=1.. i=1 A i., Example 數 N index set indexed family {A i, i I}, i N A i+1 A i A i, A i = /0. i=1

45 3.3. Indexed Family 41 i N A i (0,1/i). A i A i /0 A i+1 A i. A i = /0. x A i, x > 0. n N n > 1/x. i=1 i=1 x > 1/n, x (0,1/n) = A n. x A i, i=1 A i = /0.,,,., Proposition Proposition B set, {A i, i I} I index set indexed family. ( A i ) B = (A i B) and ( A i ) B = i B). i I i I i I i I(A i=1 Proof. k I ( i I A i ) (A k B) B (A k B), Corollary (2) (( i I A i ) B) (A k B). k I, Corollary (1) (( A i ) B) i B). i I i I(A, x i I(A i B), i I, x A i x B. x B x B 論. x B, x ( i I A i ) B. x B, x A i i I, x A i, x ( A i ) B. (A i B) (( A i ) B), i I i I i I i I ( A i ) B = i B). i I i I(A, k I (A k B) ( i I A i ) (A k B) B, Corollary (1) (A k B) ( i I A i ) B. k I, Corollary (2) i B) ( i I(A A i ) B. i I, x ( A i ) B, x A i x B. i I, x A i x B. i I i I i I x A i B. x (A i B), (( A i ) B) i B), i I i I i I(A ( A i ) B = i B). i I i I(A Question A i,b i, i I I index set indexed family. ( A i ) ( B i ) = (A i B i ) and ( A i ) ( B i ) = i B i )? i I i I i I i I i I i I(A

46 42 3. Set DeMorgan s laws (Proposition (2)(3)). Proposition C sets {A i, i I} I index set indexed family,. (1) C \ ( A i ) = (C \ A i )., ( A i ) c = A c i. i I i I i I i I (2) C \ ( A i ) = (C \ A i )., ( A i ) c = A c i. i I i I i I i I Proof. (1): k I, A i A k, Proposition (C \A k ) (C \ A i ). i I i I Corollary (2) (C \ A i ) (C \ A i )., x C \ A i, x C i I i I i I x A i, x A i. i I x A i, x C x C \ A i. i I x (C \ A i ), (C \ A i ) \ A i ). i I i I i I(C C = X, X \ A i = A c i X \ ( A i ) = ( A i ) c i I i I ( A i ) c = A c i. i I i I (2): (1) ( A c i ) c = i I i I(A c i ) c, Proposition (1), ( A c i ) c = A i. complement Proposition (1) ( A i ) c = A c i. i I i I i I i I C \ ( A i ) = C ( A i ) c = C ( A c i ) and i I i I i I C ( A c i ) = A i I i I(C c i ), \ A i ) = i I(C (C A c i ), i I C \ ( A i ) = \ A i ). i I i I(C Question C sets {A i, i I} I index set indexed family. ( A i ) \C (A i \C) (A i \C),? ( A i ) \C? i I i I i I i I 3.4. Power Set and Cartesian Product 前 (, ), ( ),.

47 3.4. Power Set and Cartesian Product Power Set. power set. Definition A set. A power set A subsets, P(A). P(A) = {S : S A}. set A, /0 A A A, /0 P(A) A P(A)., /0, /0 P(A). /0 P(A) /0 P(A). a A, {a} A, {a} P(A). set power set,.. Example /0, P(/0) = {/0}. A = {1,2,3}, 前 /0, A, {1}, {2}, {3} P(A). {1,2}, {1,3}, {2,3} A, P(A) = { /0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }. A, finite set. #(A) A 數. Example #(A) = 3, #(P(A)) = 2 3 = 8. finite set, 數, power set 數. Proposition A finite set #(A) = n. #(P(A)) = 2 n. Proof. #(P(A)) = 2 n. 論, 數學. A 數 #(A) 數學. #(A) = 0, A, A = /0. Example 3.4.2, #(A) = 1 = 2 0. #(A) = 1, A, a, A = {a}. P(A) = {/0,{a}}, #(A) = 2 = a 1. n = 0,1. 數 k. #(A) = k + 1, A = {a 1,...,a k,a k+1 }. A = A \ {a k+1 }. #(A ) = k, P(A ) = 2 k, A 2 k. A A, A subset A subset. P(A) 2 k. A subset A, a k+1 subset. S subset, A k+1 S. S = S \ {a k+1 }, S A., S A, S = S {a k+1 }, S A subset, A subset. 言, A subset, A subset, A subset {a k+1 }. A subset 數 2 k + 2 k = 2 k+1, #(P(A)) = 2 k+1. 數學, #(A) = n, #(P(A)) = 2 n. 論 power set set., power set. power set, A set, S P(A) S A., power set., power set. Proposition A,B sets. A B P(A) P(B).

48 44 3. Set Proof. ( ): A B. S P(A), S A. A B S B, S P(B). P(A) P(B). ( ): P(A) P(B). A P(A), P(A) P(B), A P(B). power set, A B. Question A,B sets. A B P(A) P(B)? Power set,. Proposition A,B sets. P(A B) = P(A) P(B). Proof. (A B) A (A B) B Proposition P(A B) P(A) P(A B) P(B). Corollary P(A B) P(A) P(B)., S P(A) P(B) S P(A) S P(B), S A S B. Corollary S (A B), S P(A B). P(A) P(B) P(A B), P(A B) = P(A) P(B). Question {A i, i I} I index set indexed family. P( A i ) i I P(A i )? i I Power set. P(A) P(B) P(A B) ( A (A B) B (A B) Proposition P(A) P(A B) P(B) P(A B)), P(A B) P(A) P(B). S P(A B) S (A B), S A S B. A = {1}, B = {2}, S = {1,2} A B, S A S B. P(A) = {/0,{1}},P(B) = {/0,{2}}, P(A) P(B) = {/0,{1},{2}}. P(A B) = {/0,{1},{2},{1,2}}. P(A B) P(A) P(B), P(A) P(B) P(A B). P(A) P(B) = P(A B), A B A B. A B B A, P(A) P(B) P(B) P(A). (A B) = B (A B) = A, P(A) P(B) = P(A B)., A B B A (, A B B A ), a A \ B b B \ A. S = {a,b}, S A B S A S B, S P(A B) S P(A) S P(B), S (P(A) P(B)). P(A B) P(A) P(B).. Proposition A,B sets. (P(A) P(B)) P(A B). (P(A) P(B)) = P(A B) A B B A., Power set. A,B sets, /0 P(A), /0 P(B). /0 P(A) \ P(B). /0 P(A \ B),

49 3.4. Power Set and Cartesian Product 45 (P(A) \ P(B)) P(A \ B). S /0, S P(A \ B), S (A \ B). (A\B) A, S A ( S P(A)). S B ( S P(B)). S, x S, S B, x B. S (A \ B), x A \ B, x B,. S P(A) S P(B) S P(A) \ P(B). P(A \ B), P(A) \ P(B), (P(A \ B) \ {/0}) (P(A) \ P(B)).. S P(A) \ P(B) S A S B. S (A \ B). A \ B /0 A B /0, a A \ B b A B S = {a,b}. {a,b} A {a,b} B ( S P(A) \ P(B)), {a,b} (A \ B) ( S P(A\B)\{/0}). (P(A)\P(B)) (P(A\B)\{/0})., A\B = /0 A B = /0, (P(A) \ P(B)) (P(A \ B) \ {/0}), 前 Lemma. Lemma A,B sets. (1) A \ B = /0 (P(A) \ P(B)) = /0. (2) A B = /0 (P(A) \ P(B)) = (P(A) \ {/0}). Proof. (1): A \ B = /0, A B. A B, a A a B, a A \ B. Proposition 3.4.4, P(A) P(B). (P(A) \ P(B)) = /0. (2): /0 P(B), {/0} P(B). Proposition (P(A) \ P(B)) (P(A) \ {/0})., S P(A) \ {/0} S P(A) S {/0}, S A S /0. A B = /0, S P(B). S P(B) S B, S A Corollary 3.2.4(1) S (A B) = /0, S /0. A B = /0, S P(A) \ {/0} S P(A) \ P(B), (P(A) \ {/0}) (P(A) \ P(B)). A B = /0 (P(A) \ P(B)) = (P(A) \ {/0}). Question A,B sets. A \ B = /0 (P(A) \ P(B)) = /0? A B = /0 (P(A) \ P(B)) = (P(A) \ {/0})? Lemma 3.4.7,. Proposition A,B sets. (P(A \ B) \ {/0}) (P(A) \ P(B)). (P(A \ B) \ {/0}) = (P(A) \ P(B)) A \ B = /0 A B = /0. Proof. 前 (P(A \ B) \ {/0}) (P(A) \ P(B)). A \ B /0 A B /0 (P(A)\P(B)) (P(A\B)\{/0}). (P(A)\P(B)) = (P(A\B)\{/0}) A\B = /0 A B = /0., A \ B = /0 A B = /0 (P(A \ B) \ {/0}) = (P(A) \ P(B)).

50 46 3. Set A \ B = /0, Lemma 3.4.7(1) (P(A) \ P(B)) = /0. P(A \ B) = P(/0) = {/0},, (P(A \ B) \ {/0}) = {/0} \ {/0} = /0 = (P(A) \ P(B)). A B = /0, Lemma 3.4.7(2) (P(A)\P(B)) = (P(A)\{/0})., A \ B = A \ (A B) = A \ /0 = A, (P(A \ B) \ {/0}) = (P(A) \ {/0}) = (P(A) \ P(B)) Cartesian Product., {1,2} {2,1}. S 1 = {{1},{1,2}} S 2 {{2},{1,2}}, {1} S 1 {1} S 2, S 1 S 2., 1, 2.. Definition A,B sets. a A,b B, ordered pair (a,b) = {{a},{a,b}}. A B = {(a,b) : a A,b B}, the Cartesian product of A and B. ordered pair, 數,,. 前, (1,2) = {{1},{1,2}}, (2,1) = {{2},{1,2}}, (1,2) (2,1). a,a A, b,b B. a = a, b = b,, (a,b) = {{a},{a,b}} = {{a },{a,b }} = (a,b ). (a,b) = (a,b ) {{a},{a,b}} = {{a },{a,b }}. a b, {a,b}, (a,b) = (a,b ), {a,b } ( {{a },{a,b }}, {{a},{a,b}}).,, {a} = {a } {a,b} = {a,b }. a = a b = b. {a,b}, a = b. {a,b} = {a}, (a,b) = (a,a) = {{a},{a,b}} = {{a},{a}} = {{a}}., (a,b) = (a,b ) b = a = a, a = a b = b.. Proposition A,B sets, a,a A b,b B (a,b) = (a,b ) a = a b = b.

51 3.4. Power Set and Cartesian Product 47, a A, b B, {{a},{a,b}}. {a,b}, A B. {a}, {a,b} A B subset, {a} {a,b} P(A B). {{a},{a,b}} P(A B), {{a},{a,b}} P(P(A B)). (a,b) P(P(A B)). (a,b) {{a},{a,b}},. Proposition , (a,b). (a,b) A B, (a,b) = (a,b ) A B. Example (1) A = {a,b}, B = {1,2,3}. A B A B = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}. A {/0} = {(a, /0),(b, /0)}. (2) S = {(x,y) R R : x 2 + y 2 1}. S R R subset, A R, B R S = A B., S = A B, (1,0) S, 1 A. (0,1) S, 1 B. (1,1) A B = 2 > 1, (1,1) S. S = A B, A R, B R S = A B. A /0 A {/0}. (x,y) A {/0} x A y {/0}, {/0} /0, y = /0. (x,y) A /0 x A y /0, /0, y. A /0, A /0 = /0. /0 B = /0.. Proposition A,B sets, A B = /0 A = /0 B = /0. Proof. A B = /0, A = /0 B = /0. contrapositive method, A /0 B /0. a A b B, (a,b) A B. A B /0. A,B finite sets, Example A B. a A, (a,y) A B. Proposition , y B, (a,y). A B (a,y) #(B). a, A B #(A) #(B),. Proposition A,B finite sets. #(A B) = #(A) #(B). #(/0) = 0, Proposition #(A /0) = #(A) #(/0) = 0. 論 Proposition A /0 = /0 論. Cartesian product., set A, B = /0, A B = /0 A B A B A,A. A B A,B /0.. Proposition A,B,C,D sets A /0 B /0. A C B D (A B) (C D).

52 48 3. Set Proof. ( ) : A C B D. (x,y) A B, x A y B, A C B D x C y D. (x,y) C D, (A B) (C D). ( ) : (A B) (C D). x A, B /0, b B. (x,b) A B. (A B) (C D), (x,b) C D. x C, A C., y B, A /0, a A. (a,y) A B. (A B) (C D), (a,y) C D. y D, B D. Question Proposition , A /0 B /0? A C B D? Cartesian product intersection. Proposition A,B,C,D sets. (A C) B = (A B) (C B) and A (B D) = (A B) (A D). Proof. (A C) A (A C) C Proposition ((A C) B) (A B) ((A C) B) (C B) ( Proposition ). Corollary 3.2.4(1) ((A C) B) (A B) (C B)., (x,y) (A B) (C B), (x,y) A B (x,y) C B. x A x C y B, x A C y B, (x,y) (A C) B. (A B) (C B) (A C) B, (A C) B = (A B) (C B). A (B D) = (A B) (A D). Proposition (A C) (B D). Proposition B B D, (A C) (B D) = (A (B D)) (C (B D)). A (B D) = (A B) (A D) C (B D) = (C B) (C D), (A C) (B D) = (A B) (A D) (C B) (C D). (3.3) (x,y) (A B) (C D) (x,y) A B ( x A, y B) (x,y) C D ( x C, y D), (x,y) A D ( x A, y D) (x,y) C B ( x C, y B). (x,y) (A D) (C B), ((A B) (C D)) ((A D) (C B)). Proposition (3.3) (A C) (B D) = ((A B) (C D)) ((A D) (C B)) = (A B) (C D).. Corollary A,B,C,D sets. (A C) (B D) = (A B) (C D). Question Corollary (A C) (B D) = (A D) (C B)? Corollary

53 3.4. Power Set and Cartesian Product 49, Cartesian products operations Cartesian product., Cartesian products Cartesian product. (A B) (C D) Cartesian product S T. Corollary S = A C, T = B D, (A B) (C D) = S T., Cartesian products Cartesian product. Question (A B) (C D) = (A D) (C B). Question {A i, i I}, {B i, i I} I index set indexed family. i B i ) = ( i I(A A i ) ( B i ). i I i I Cartesian product union Proposition Proposition A,B,C,D sets. (A C) B = (A B) (C B) and A (B D) = (A B) (A D). Proof. A (A C) C (A C) Proposition (A B) ((A C) B) (C B) ((A C) B). Corollary 3.2.4(2) (A B) (C B) ((A C) B)., (x,y) (A C) B, x A C y B, x A x C y B. x A, y B (x,y) A B, x C, y B (x,y) C B. (x,y) A B (x,y) C B, (x,y) (A B) (C B). ((A C) B) (A B) (C B), (A C) B = (A B) (C B). A (B D) = (A B) (A D) Proposition (A C) (B D). Proposition B B D, (A C) (B D) = (A (B D)) (C (B D)). A (B D) = (A B) (A D) C (B D) = (C B) (C D),. Corollary A,B,C,D sets. (A C) (B D) = (A B) (A D) (C B) (C D). (A C) (B D) Corollary (A C) (B D) (A B) (C D). A D (A B) (C D) ( A C D B). A C D B,. A,D /0 B = C = /0, (A C) (B D) = A D /0 ( Proposition ), (A B) (C D) = /0 /0 = /0. (A C) (B D) (A B) (C D). Question (A C) (B D) (A B) (C D). Cartesian product Cartesian product. (A B) (C D) Cartesian product S T? A,B,C,D /0, (A B) (C D) /0,., Corollary

54 50 3. Set S,T (A B) (C D) = (S T ) s S,t T, (s,t) (A B) (C D), s A, t B s C, t D. s A C t B D, s A C t B D. S A C T B D. x A C, x A x C 論. x A, b B ( B /0), (x,b) A B, (x,b) (A B) (C D) = (S T ) x S. x C, D /0, x S. A C S, S = A C. T = B D. A,B,C,D /0, (A B) (C D) = (S T) S = A C T = B D. Corollary (A B) (C D) = (A C) (B D) (A D) (C B) (A B) (C D). A C D B, a A\C d D\B. (a,d) A D (a,d) A B (a,d) C D, (a,d) (A B) (C D). (A D) (A B) (C D). (A B) (C D) = (A C) (B D), A C D B. C A B D, (c,d) C D, c C \ A b B \ D, (C D) (A B) (C D). (A B) (C D) = (A C) (B D), C A B D.. Proposition A,B,C,D sets. S,T sets (A B) (C D) = S T A,B,C,D : (1) A,B,C,D /0. (2) A = C (3) B = D (4) A C B D (5) C A D B Proof. ( ): (1), A,B,C,D /0, 前 S,T (A B) (C D) = S T, S = A C T = B D. (A B) (C D) = (A C) (B D), 前 論 A C D B C A B D. ( (A C) (D B) ) ( (C A) (B D) )., ( 1.3), ( ((A C) (D B)) (C A) ) ( ((A C) (D B)) (B D) )., ((A C) (C A)) ((D B) (C A)) ((A C) (B D)) ((D B) (B D)). (A C) (C A) A = C, (D B) (B D) B = D, (2), (3), (4), (5). ( ): (1), (A B) (C D) /0, S,T (A B) (C D) = S T. (2) Proposition (A B) (C D) = (A B) (A D) = A (B D),

55 3.4. Power Set and Cartesian Product 51 S = A,T = (B D). (3) Proposition (A B) (C D) = (A B) (C B) = (A C) B, S = (A C),T = B. (4) Proposition (A B) (C D), (A B) (C D) = (C D). S = C, T = D. (5) Proposition (C D) (A B), (A B) (C D) = (A B). S = A, T = B. Cartesian product set difference. Proposition A,B,C,D sets. (C \ A) B = (C B) \ (A B) and A (D \ B) = (A D) \ (A B). Proof. (x,y) (C \ A) B, x C \ A y B. x C x A y B. (x,y) C B (x,y) A B ( (x,y) A B 導 x A ). (x,y) (C B) \ (A B), (C \ A) B (C B) \ (A B)., (x,y) (C B) \ (A B), (x,y) C B ( x C, y B) (x,y) A B ( x A y B). (x,y) C B y B, (x,y) A B x A ( x A y B (x,y) A B ). x C x A y B, (x,y) (C \A) B, (C B)\(A B) (C \A) B. (C \A) B = (C B)\(A B). A (D \ B) = (A D) \ (A B). Proposition (C \ A) (D \ B). Corollary (C \ A) (D \ B) = ((C \ A) C) (D (D \ B)) = ((C \ A) D) (C (D \ B)). Proposition (C \ A) D = (C D) \ (A D) C (D \ B) = (C D) \ (C B). (C \ A) (D \ B) = ((C D) \ (A D)) ((C D) \ (C B)). Proposition (3), ((C D) \ (A D)) ((C D) \ (C B)) = (C D) \ ( (A D) (C B) ).. Corollary A,B,C,D sets. (C \ A) (D \ B) = ((C \ A) D) (C (D \ B)) = (C D) \ ( (A D) (C B) ). Cartesian product Cartesian product. (C D) \ (A B) S T?,

56 52 3. Set., (C D)\(A B) = (C D)\((C D) (A B)) ( Question 3.11). Corollary , (C D) (A B) = (C A) (D B) = (C B) (A D). (C D) \ (A B) = (C D) \ ((C B) (A D)). (3.4) Proposition (2) (C D) \ ((C B) (A D)) = ((C D) \ (C B)) ((C D) \ (A D)). (3.5) Proposition (C D) \ (C B) = C (D \ B) and (C D) \ (A D) = (C \ A) D. (3.6) (3.4), (3.5), (3.6). Corollary A,B,C,D sets. (C D) \ (A B) = (C (D \ B)) ((C \ A) D). Corollary Corollary Corollary , Proposition S,T S T = (C D) \ (A B). Proposition (C (D \ B)) ((C \ A) D) S T, : (1) C,D,(D \ B),(C \ A) /0, D B C A ( C D /0 ). (2) C = C \ A, A C = /0. (3) D = D \ B, B D = /0. (4) C (C \ A) (D \ B) D. (D \ B) D, C (C \A), C = C \A, (2). (5) D (D\B) (C \A) C. (4). (3). 論. Proposition A,B,C,D sets. S,T sets (C D) \ (A B) = S T A,B,C,D : (1) D B. (2) C A. (3) A C = /0. (4) B D = /0. Question Proposition S,T? 論 Cartesian product complement., Cartesian product. A X, B Y, 論 A B. A B X Y. A complement A c X complement, A c = X \ A. B c B Y complement, B c = Y \ B. A B complement (A B) c, A B X Y complement, (A B) c = (X Y ) \ (A B).

57 3.4. Power Set and Cartesian Product 53, complement universal sets complement., Corollary C = X D = Y (A B) c = (X Y ) \ (A B) = (X (Y \ B)) ((X \ A) Y ) = (X B c ) (A c Y ). X = A A c Y = B B c, Proposition X B c = (A A c ) B c = (A B c ) (A c B c ), A c Y = (A c B) (A c B c ).. Proposition A,B sets. (A B) c = (A B c ) (A c B c ) (A c B)., 論 Cartesian product.,.

58

59 Chapter 4 Relation and Order relation. Relation relation relation. set relation. relation, equivalence relation. Equivalence relation, equivalence relation set. 學 relation. relation, order. Order ( ), set Relation sets X,Y. S X Y nonempty subset, S relation from X to Y., X X nonempty subset S relation on X. relation S, x y (x,y) S. x y x y, relation. relation, (x,y) S,. Example (1) X = {1,0, 1}, Y = {0,1,2}. S = {(x,y) X Y : y = x 2 +1}. S X Y relation. relation 1 2, (2) X = {1,0, 1}. S = {(x,x ) X X : x > x }. S X relation. relation 1 0, Question 4.1. X nonempty set. X relation S. S = X X x,y X x y. relation, Example 4.1.1(1) X,Y 數 f (x) = x relation. relation,, Example 4.1.1(2) X relation. 55

60 56 4. Relation and Order relation X Y, S X,Y. X,Y, S X Y. 論 relation. Example ( 數, ) S.. Example X relation X? relation X, X power set P(X) relation. S P(X) P(X) A B (A,B) S. S = {(A,B) P(X) P(X) : A B}. relation A B A B., 論 relation. S relation on X,, relation. Reflexive: S x X x x, (x,x) S, x X, relation reflexive. Symmetric: S x,y X x y, y x, (x,y) S (y,x) S, relation symmetric. Transitive: S x,y,z X x y y z, x z, ((x,y) S) ((y,z) S) (x,z) S, relation transitive.,. (1) S reflexive x X (x,x) S. x X (x,x) S reflexive. (x,y) S x = y. 言, S reflexive, X x, (x,x) S, (x,y) x y. (2) S symmetric (x,y) S (y,x) S. (x,y) (y,x) S symmetric. 言, S symmetric, (x,y) S (y,x) S. symmetric, symmetric. (3) S transitive (x,y) (y,z) S, (x,z) S. (x,y),(y,z) (x,z) S transitive. (x,y) S z X (y,z) S. S (x,y) S transitive. 言