數學導論 學數學

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

Chapter 1 Basic Logic 學 數學 學 言., logic. 學 學,, 學., 學 數學. 數學 論 statement. 2 > 0 statement, 3 < 2 statement x > 0 statement ( x ). 1.1. Connectives 數 statements statement, statements connectives. connectives statement. 1.1.1. 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

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. 1.1.2. Or. P Q statement, P Q P or Q statement. or. :,., ; 105. 105, 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.

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,. 1.1.3. 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 數.

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 > 3 2 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.

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 ) 1.1.4. 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,

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. 前

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 1.2.1. (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 1.2.2. A,B statement forms. A B logically equivalent A B tautology.

8 1. Basic Logic 前, A B A B tautology ( A B A B tautology), A B tautology A B. Proposition 1.2.2 A B A B tautology. Question 1.9. A,B statement forms. A B A B tautology? A B tautology A B? Question 1.10. A,B,C statement forms. A B B C tautology, A C tautology? tautology contradiction ( ). statement form. contradiction, not. Question 1.11. A,B statement forms. (1) A tautology, (A B) B A B tautology. (2) A contradiction, (A B) B A B contradiction. 1.3. 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)

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 1.12. 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 1.13. 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

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 1.2.2. Proposition 1.3.1. A,B statement forms. A B logically equivalent A B contradiction.

1.4. Quantifiers 11 1.4. 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,

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.14. (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 1.15. x, y,x + y = y statement, y, x,x + y = y,? x, y,x + y = y y, x,x + y = y,? Question 1.16. 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),

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

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

Chapter 2 Methods of Proof 學, 學..,,. 2.1. IF-Then 數學 P Q statement. statement, direct method, contrapositive method contradiction method. 2.1.1. Direct Method. direct method, P Q. (, P, Q ). P Q, P,.. Example 2.1.1. 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 2.1.2. 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

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 2.1.3. 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? 2.1.2. 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 2.1.4. x,y 數. if x y, then x 3 y 3.

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 + 1 2 y)2 + 3 4 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 2.1.5. 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 2.1.3 contrapositive method., (1 < x < 2) ( x 2 or x 1) (x 2 3x + 2 < 0) ( x 2 3x + 2 0).. Example 2.1.6. 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,? 2.1.3. 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, 導,

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 2.1.7. 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 2.1.5 m 數. m m = 2m, m 數. 4m 2 = 2n 2, n 2 = 2m 2. Example 2.1.5 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 2.1.8. 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 = 0. 2.1.4. If and Only If. P Q P Q Q P., 導 P Q, P Q.,,, P Q., 導. P Q P Q Q P.

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 2.1.5 ). (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,. 2.2. Existence and Uniqueness Existence, uniqueness. 數學., existence uniqueness..,., 論 existence uniqueness.

20 2. Methods of Proof 2.2.1. 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 2.2.1. 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 = 2 2 1 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,,., 學 導,. 學,. 導,, 導., 導,,,, (

2.2. Existence and Uniqueness 21 P Q ).,,.. Example 2.2.2. 數 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 2.2.3 (Pigeonhole Principle). n 數. n n.,. Proof., constructive method., statement, n n, n.. pigeonhole principle.,,. 6 數, 數 5 數. 6 數 6, 0 4. 5 數 0 0, 數 1 1,. 數 6 數 5,,. 數 5 數.. 16 數, 4 數 5 數. 數 5 數 0,1,2,3,4 3, 數 15, 16 數. Theorem 2.2.3,. Theorem 2.2.4. k,n 數. n kn., k. Question 2.5. Theorem 2.2.4, 數 數 ( ). 數 數. 數 數.,.

22 2. Methods of Proof 2.2.2. Uniqueness. 前..,,. Example 2.2.2 x x = 1,.,.. 前,.,. R 2. Example 2.2.5. 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 2.2.6. 數 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 2.1.4 3 = s 3 r 3 = 3. 數 s s 3 = 3. Example 2.2.6 x y, x,y,.., Example 2.2.6 數 r r 3 = 3,., 數 ( 數 f (x) = x 3 ). 3 1/3 r 3 = 3 數 r.

2.3. Mathematical Induction 23 2.3. Mathematical Induction 數學. 數學 數 axiom ( ), 論. 數學. 數學,,,. 數學 論 axiom ( ). 數學 前, well-ordering principle., 前. well-ordering principle.,. well-ordering, 數,. principle ( )!, 數 1,..,,., 數學. Theorem 2.3.1 (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 + 41. x = 1 f (1) = 43 數. x = 2, f (2) = 47 數. f (3) = 53, f (4) = 61,

24 2. Methods of Proof f (5) = 71 數. x 數 n f (n) 數. x = 39 數., f (k) 數 f (k + 1) 數, 數學., x = 40, f (40) = 40 2 + 40 + 41 = 40(40 + 1) + 41 41, 數. 數學. Example 2.3.2. 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 2.3.3. 數學 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). 論.

2.3. Mathematical Induction 25 n = 1, n 5, 2 n > n 2. 數學 1,., Theorem 2.3.1 論, 數學. Corollary 2.3.4 (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 2.3.1 n N, Q(n) = P(m + n 1). n m 數, P(n). extended mathematical induction Corollary, Theorem 2.3.1. m = 1 Corollary 2.3.4 Theorem 2.3.1, Theorem 2.3.1 Corollary 2.3.4 equivalent. Example 2.3.5. 數 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 2.3.6 (Strong Mathematical Induction). m 數. statement (1) P(m) (2) k m 數 P(m),P(m + 1),...,P(k 1),P(k), P(k + 1)

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 2.3.4 m 數 n Q(n). Q(n) P(m),P(m + 1),...,P(n 1),P(n), P(n), n m 數, P(n). Corollary 2.3.4 Corollary 2.3.6. P(k) P(k + 1) P(m),P(m + 1),...,P(k 1),P(k) P(k + 1), Corollary 2.3.6 Corollary 2.3.4. strong mathematical induction extended mathematical induction. Question 2.7. Corollary 2.3.6 Corollary 2.3.4. 前 extended mathematical induction mathematical induction, 數學.. strong mathematical induction. Example 2.3.7. 1 數 數. 學. 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,

2.3. Mathematical Induction 27 ( Example 2.3.3 )., k, k,,., 數學,,. Example 2.3.8. 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 = 2 + 1 = 3, F 4 = 3 < 2 4 2 = 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 = 2 4 3 ). k = 4, F k+1 = F 5 = F 4 + F 3 = 5 < 2 5 2 = 8,. Proof. F 4 = 3 < 2 4 2,F 5 = 5 < 2 5 2. 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 2 + 2 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,24 4 5 數, 數學. Example 2.3.9. n 數 n > 20, l,m 數 n = 4l + 5m. 前, n 0 數, 21 + 4n,22 + 4n,23 + 4n,24 + 4n 4l + 5m, l.m 數. 20 數. 21 = 4 4 + 5 1,. k 0 21 + 4k = 4l + 5m, l.m 數. 21+4(k+1) = (21+4k)+4 = 4l +5m+4 = 4(l +1)+5m,. n 0 數, 21 + 4n 4l + 5m, l.m 數. 22 = 4 3 + 5 2, 23 = 4 2 + 5 3 24 = 4 1 + 5 4, 數學. 數學, strong mathematical induction. Proof. 21 = 4 4 + 5 1, 22 = 4 3 + 5 2, 23 = 4 2 + 5 3 24 = 4 1 + 5 4 n = 21,22,23,24. k 24 21 i k 數 i,

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 數 數學.

Chapter 3 Set 論 數學 論. 論. 論,. 3.1. 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 3.1.1. 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

30 3. Set subset proper set,,. B A, B x, A, 數學 x B x A. A = B x B x A.,,,. : Example 3.1.2. 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 3.1.3. X universal set A set. A X /0 A.

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 3.1.4. 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 3.1.4 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 3.1.5. 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.

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 3.1.4 (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.

3.2. Set Operations 33 3.2. Set Operations set operation,. operations, intersection, union set difference, set operations. 3.2.1. Intersection and Union. intersection union. Definition 3.2.1. 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 3.2.2. 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 3.2.3. 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).

34 3. Set, A B A D, C = A Proposition 3.2.3 (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 3.2.3 導, corollary ( ). Corollary 3.2.4. 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 3.2.3... Proposition 3.2.5. 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 3.2.4 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 3.2.1 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.

3.2. Set Operations 35,, ((P Q) R) ((P R) (Q R)), ((P Q) R) ((P R) (Q R)),. Proposition 3.2.6. 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 3.2.3 ((A B) C) (A C). ((A B) C) (B C). Corollary 3.2.4 ((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 3.2.3 (A C) ((A B) C), (B C) ((A B) C). Corollary 3.2.4 (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 3.2.5 (1) (2) Proposition 3.2.6 Proposition 3.2.5 (2) (3). 3.2.2. Set Difference. set difference. Definition 3.2.7. 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 3.2.8. 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}.

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 3.2.9. 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 3.10. 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 3.2.10. A,B sets. A B B c A c. Definition 3.2.7 set difference not, 導 set difference,. Proposition 3.2.11. 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,

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 3.2.9 (C\A) (C\(A B)). (A B) B (C \ B) (C \ (A B)). Corollary 3.2.4 (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 3.11. Proposition 3.2.11 (2) C \ A = C \ (C A). Proposition 3.2.9 (C A) (C B) (C \ B) (C \ A). operations,, connectives,. operations 導., operations 導,.,, 導, 導., 學 導.. Example 3.2.12. 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 3.2.5. (C \ A) B, ((C \ A) B) = B.

38 3. Set (C \ A) B? B c A. C \ A = C A c, Corollary 3.2.10 B c A A c (B c ) c, Proposition 3.2.11 (1) A c B. (C \ A) = (C A c ) (C B) B. 3.3. Indexed Family 前,, operation., 論.,,. 前,.,,. 論, 數, 5 A,B,C,D,E, A B C D E.,.,.. 數, 前.,, 100, A 1,A 2,...,A 100 (, A i ). summation, 100 100 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 8 8 8 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

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 3.3.1. 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 3.3.2. 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 3.12. A i Example 3.3.2. m Z, p,q 數 p mq, p m, p,q 數, A p A q = Z. m N, A i = Z. i=m

40 3. Set Question 3.13. A i Example 3.3.2, m N, n 數 m < n A i = Q? i=m A i = Q. i=m, indexed family. Proposition 3.2.3. Proposition 3.3.3. {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 3.3.3 Corollary 3.2.4. Corollary 3.3.4. 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 3.3.5. 數 N index set indexed family {A i, i I}, i N A i+1 A i A i, A i = /0. i=1

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 3.2.6. Proposition 3.3.6. 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 3.2.4 (2) (( i I A i ) B) (A k B). k I, Corollary 3.3.4 (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 3.2.4 (1) (A k B) ( i I A i ) B. k I, Corollary 3.3.4 (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 3.14. 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

42 3. Set DeMorgan s laws (Proposition 3.2.11 (2)(3)). Proposition 3.3.7. 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 3.2.9 (C \A k ) (C \ A i ). i I i I Corollary 3.3.4 (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 3.2.11 (1), ( A c i ) c = A i. complement Proposition 3.2.11 (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 3.15. 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 前 (, ), ( ),.

3.4. Power Set and Cartesian Product 43 3.4.1. Power Set. power set. Definition 3.4.1. 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 3.4.2. /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 3.4.2 #(A) = 3, #(P(A)) = 2 3 = 8. finite set, 數, power set 數. Proposition 3.4.3. 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 3.4.4. A,B sets. A B P(A) P(B).

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 3.16. A,B sets. A B P(A) P(B)? Power set,. Proposition 3.4.5. A,B sets. P(A B) = P(A) P(B). Proof. (A B) A (A B) B Proposition 3.4.4 P(A B) P(A) P(A B) P(B). Corollary 3.2.4 P(A B) P(A) P(B)., S P(A) P(B) S P(A) S P(B), S A S B. Corollary 3.2.4 S (A B), S P(A B). P(A) P(B) P(A B), P(A B) = P(A) P(B). Question 3.17. {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 3.4.4 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 3.4.6. 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),

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 3.4.7. 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 3.2.9 (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 3.18. 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 3.4.8. 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)).

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)). 3.4.2. 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 3.4.9. 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 3.4.10. A,B sets, a,a A b,b B (a,b) = (a,b ) a = a b = b.

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 3.4.10, (a,b). (a,b) A B, (a,b) = (a,b ) A B. Example 3.4.11. (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. 1 2 + 1 2 = 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 3.4.12. 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 3.4.11 A B. a A, (a,y) A B. Proposition 3.4.10, y B, (a,y). A B (a,y) #(B). a, A B #(A) #(B),. Proposition 3.4.13. A,B finite sets. #(A B) = #(A) #(B). #(/0) = 0, Proposition 3.4.13 #(A /0) = #(A) #(/0) = 0. 論 Proposition 3.4.12 A /0 = /0 論. Cartesian product., set A, B = /0, A B = /0 A B A B A,A. A B A,B /0.. Proposition 3.4.14. A,B,C,D sets A /0 B /0. A C B D (A B) (C D).

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 3.19. Proposition 3.4.14, A /0 B /0? A C B D? Cartesian product intersection. Proposition 3.4.15. 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 3.4.14 ((A C) B) (A B) ((A C) B) (C B) ( Proposition 3.4.14 ). 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 3.4.15 (A C) (B D). Proposition 3.4.15 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.2.5 (3.3) (A C) (B D) = ((A B) (C D)) ((A D) (C B)) = (A B) (C D).. Corollary 3.4.16. A,B,C,D sets. (A C) (B D) = (A B) (C D). Question 3.20. Corollary 3.4.16 (A C) (B D) = (A D) (C B)? Corollary 3.4.16.

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 3.4.16. S = A C, T = B D, (A B) (C D) = S T., Cartesian products Cartesian product. Question 3.21. (A B) (C D) = (A D) (C B). Question 3.22. {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 3.4.15. Proposition 3.4.17. 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 3.4.14 (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 3.4.17 (A C) (B D). Proposition 3.4.17 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 3.4.18. A,B,C,D sets. (A C) (B D) = (A B) (A D) (C B) (C D). (A C) (B D) Corollary 3.4.16. (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 3.4.12), (A B) (C D) = /0 /0 = /0. (A C) (B D) (A B) (C D). Question 3.23. (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

50 3. Set 3.4.18. 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 3.4.18 (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 3.4.19. 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 3.4.17 (A B) (C D) = (A B) (A D) = A (B D),

3.4. Power Set and Cartesian Product 51 S = A,T = (B D). (3) Proposition 3.4.17 (A B) (C D) = (A B) (C B) = (A C) B, S = (A C),T = B. (4) Proposition 3.4.14 (A B) (C D), (A B) (C D) = (C D). S = C, T = D. (5) Proposition 3.4.14 (C D) (A B), (A B) (C D) = (A B). S = A, T = B. Cartesian product set difference. Proposition 3.4.20. 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 3.4.20 (C \ A) (D \ B). Corollary 3.4.16 (C \ A) (D \ B) = ((C \ A) C) (D (D \ B)) = ((C \ A) D) (C (D \ B)). Proposition 3.4.20 (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.2.11(3), ((C D) \ (A D)) ((C D) \ (C B)) = (C D) \ ( (A D) (C B) ).. Corollary 3.4.21. 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?,

52 3. Set., (C D)\(A B) = (C D)\((C D) (A B)) ( Question 3.11). Corollary 3.4.16, (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 3.2.11(2) (C D) \ ((C B) (A D)) = ((C D) \ (C B)) ((C D) \ (A D)). (3.5) Proposition 3.4.20 (C D) \ (C B) = C (D \ B) and (C D) \ (A D) = (C \ A) D. (3.6) (3.4), (3.5), (3.6). Corollary 3.4.22. A,B,C,D sets. (C D) \ (A B) = (C (D \ B)) ((C \ A) D). Corollary 3.4.21 Corollary 3.4.22. Corollary 3.4.22, Proposition 3.4.19 S,T S T = (C D) \ (A B). Proposition 3.4.19 (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 3.4.23. 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 3.24. Proposition 3.4.23 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).

3.4. Power Set and Cartesian Product 53, complement universal sets complement., Corollary 3.4.22 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 3.4.17 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 3.4.24. A,B sets. (A B) c = (A B c ) (A c B c ) (A c B)., 論 Cartesian product.,.

Chapter 4 Relation and Order relation. Relation relation relation. set relation. relation, equivalence relation. Equivalence relation, equivalence relation set. 學 relation. relation, order. Order ( ), set. 4.1. 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 4.1.1. (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, 0 1 1 2. (2) X = {1,0, 1}. S = {(x,x ) X X : x > x }. S X relation. relation 1 0, 1 1 0 1. 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 2 + 1 relation. relation,, Example 4.1.1(2) X relation. 55

56 4. Relation and Order relation X Y, S X,Y. X,Y, S X Y. 論 relation. Example 4.1.1 ( 數, ) S.. Example 4.1.2. 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. 言