Schum's Finite Mathematics By Lipschutz

Propositions and Truth Tables STATEMENTS A statement (or verbal assertion) is any collection of symbols (or sounds) which is either true o r false, but not both. Statements will usually be denoted by the letters P , (7, r ,

...

The truth o r falsity of a statement is called its truth value. Example 1.1:

Consider the following expressions: (i) Paris is in England. (ii) 2

+2 = 4

(iii) Where a r e you going? (iv) P u t the homework on the blackboard.

6)

The expressions (i) and a r e statements; the first is false and the second is true. The expressions (iii) and [iv) a r e not statements since neither is either true or false.

COMPOUND STATEMENTS Some statements are composite, that is, composed of substatements and various logical connectives which we discuss subsequently. Such composite statements a r e called compound statements. Example 2.1:

"Roses a r e red and violets a r e blue" is a con~poundstatement with substatements "Roses a r e red" and "Violets a r e blue".

Example 2.2:

"He is intelligent or studies every night" is, implicitly, a compound statement with substatements "He is intelligent" and "He studies every night".

The fundamental property of a compound statement is that its truth value is completely determined by the truth values of its substatements together with the way in which they are connected to form the compound statement. We begin with a study of some of these connectives. CONJUNCTION, p A q Any two statements can be combined by the word "and" to form a compound statement called the conjunction of the original statements. Symbolically, P A 4

denotes the conjunction of the statements p and q, read " p and q". Example 3.1:

Let p be "It is raining" and let q be "The sun is shining". Then p A q denotes the statement "It is raining and the sun is shining".

The truth value of the compound statement p ~ satisfies q the following property: [TI If p is true and q is true, then p A q is true; otherwise, 11 A q is false. I n other words, the conjunction of two statements is true only in the case when each substatement is true.

PROPOSITIONS AND TRUTH T A B L E S

Observe t h a t both propositions have the same t r u t h table.

illISCELLANEOUS PROBLEMS 1.11. Let Apq denote p ,;q and let Sp denote -p. using A and N instead of A and -.

(9

P

A

-q

( 4 -(-P (i)

p

A

(ii) -(-p (iii) -p (iv) -(p

= p

-q

A

A

(-q -q)

A 1.) A

q)

(-q A -q)

A

r)

A

(-q

A

A

-7,)

'Yq = ApNq

q) = -(.Vp A

A

(iii) -p (iv) - ( p

Rewrite the following propositions

A

= Np

(-q

q) = -(ASpq) (Nq

A

A

= -(ApXq)

-r)

= NANpq

r) = S p A

A

(ANqr) = A N p A L V q ~

( A N q S r ) = (NApNq)

A

( A S q S r ) = ANApNqANqXr

Observe t h a t there a r e no parentheses in the final answer when A and .V a r e used instead of A and -. In fact, i t has been proved t h a t parentheses a r e never needed in any proposition using A and N.

1.12. Rewrite the following propositions using

(i)

NAP^

NApq = S ( p A q) = -(p

(ii) ANpq = A(-p)q

= -p

(v) N A A S p q r = SAA(-p)qr (vi) A N p A q S r = ANpAq(-r)

A

A

and

-

instead of A and N.

(v) Iv'AANpql. (vi) A S p A qNr

(iii) ApNq (iv) ApAqr

(ii) ANpq (i)

A

q)

(iii) ApNq = Ap(-q)

q

= NA(-p = ANp(q

(iv) ApAqr = Ap(q fi

q)r = Nr(-p

A -7)

A

= A(-p)(q

q)

= p i\

7,)

/

A -1.)

A

-q

= p

A

(q A r )

r' = -:(-p

= -P

A

A

q)

A

r]

(9 A my)

Notice t h a t the propositions involving A and N a r e unraveled from right to left.

Supplementary Problems STATEMENTS 1.13.

Let p be "Marc is rich" and let q be "hlarc is happy". Write each of the following in symbolic form. (i)

Marc is poor but happy.

(ii) Marc is neither rich nor happy. (iii) Marc is either rich or unhappy. (iv) Marc is poor or else he is both rich and unhappy.

Algebra of Propositions TAUTOLOGIES AND CONTRADICTIONS Some propositions P(p, q, . . . ) ca,ntain only T in the last column of their truth tables, i.e. a r e true for any truth values of their variables. Such propositions are called tautologies. Similarly, a proposition P ( p ,(1, . . .) is called a cotlt~.adictionif it contains only F in the last column of its truth table, i.e. is false for any truth values of its variables. Example 1.1:

The proposition " p or not p", i.e. p v - p , is a tautology and the proposition " p and not p", i.e, p -11, is a contradiction. This is verified by constructing their t r u t h tables' 11 1 -11 p v -p T F

F I

T T

T

Since a tautology is always true, the negation of a tautology is always false, i.e. is a contradiction, and vice versa. That is, Theorem 2.1:

If P ( p , q , . . .) is a tautology then - P ( p , q , . . . ) is a contradiction, and conversely.

Now let P(j1,q , . . .) be a tautology, and let P l ( p ,q, . . .), P,(P, q , . . .), . . . be any propositions. Since P ( p ,q , . . . ) does not depend upon the particular truth values of its variables p, q, . . ., we can substitute P l for p, P , for q, . . . in the tautology P(p, q, . . .) and still have a tautology. In other words:

,

Theorem 2.2 (Principle of Substitution) : If P(p, q, . . .) is a tautology, then P(P,, P,, . . . ) is a tautology for any propositions P,, P,, . . . . LOGICAL EQUIVALENCE Two propositions P ( p , q, . . .) and Qjp, q , simply eqzlicnlel~tor equal, denoted by

P ( P ,(1, if they have identical truth tables. Example 2.1:

The t r u t h tables of

T

F

F F

T F

..

-(]I

F F F

. . .)

a r e said to be logically equivalelzt, or

= Q ( P , q, . . . )

q i and - p v - q follo~v.

;,

;

- p i - q

T

T

F

F

T T

F

T

T

F

F

F

T

T

Accordingly, the propositions - ( p -(p

A

A

q ) and -11 v - q q)

-11

V -Q

T

T T

are logically equivalent:

Set Theory SETS AND ELEMENTS The concept of a set appears in all branches of mathematics. Intuitively, a set is any well-defined list or collection of objects, and will be denoted by capital letters A, B, X, Y, . . . . The objects comprising the set are called its elements or menzbe~sand will be denoted by lower case letters a, b, x, y, . . . . The statement "p is a n element of A" or, equivalently, " p belongs to A" is written 11

EA

The negation of p E A is written p 6!A. There are essentially two ways to specify a particular set. One way, if i t is possible, is to list its members. For example,

A = {a, e, i, o, u ) denotes the set A whose elements are the letters a, e, i, o, u. Note that the elements are separated by commas and enclosed in braces { 1. The second way is to state those properties which characterize the elements in the set. For example,

B = {x : x is an integer, x

> 0}

which reads " B is the set of x such that x is an integer and x is greater than zero," denotes the set B whose elements are the positive integers. A letter, usually x, is used to denote a typical member of the set; the colon is read as "such that" and the comma a s "and". Example 1.1:

The set B above can also be written a s B = {1,2,3, . . .I. Observe t h a t -6 4 B, 3 E B and

Example 1.2:

.T

4 B.

The set A above can also be written a s

A = { x : a is a letter in the English alphabet,

:c

is a vowel)

Observe t h a t b 6Z A , e € A and p @ A . Example 1.3:

+

Let E = {x : x2 - 32 2 = 0). In other words, E consists of those numbers which a r e solutions of the equation x2- 3x 2 = 0, sometimes called the solution set of the given equation. Since the solutions of the equation a r e 1 and 2, we could also write E = {I,2).

+

Two sets A and B are equal, written A = B, if they consist of the same elements, i.e. if each member of A belongs to B and each member of B belongs to A. The negation of A = B is written A # B. Example 1.4:

Let E = {x : xz - 3x

+ 2 = 0),

F = {2,1) and G = {I, 2,2,1,6/3).

Then E = F = G. Observe that a set does not depend on t h e way in which its elements a r e displayed. A set remains the same if its elements a r e repeated or rearranged.

36

S E T THEORY

[CHAP. 5

F I N I T E AND I N F I N I T E SETS Sets can be finite o r infinite. A set is finite if i t consists of exactly n different elements, where 12 is some positive integer; other~visei t is infinite. Example 2.1:

Let M be the set of the days of the week. In other words, M = {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday] Then M is finite.

Example 2.2:

Let Y = { 2 , 4, 6, 8 ,

Example 2.3:

Let P = { T : r is a river on the earth). Although it may be difficult to count the number of rivers on the earth, P is a finite set.

. . .).

Then Y is infinite.

SUBSETS A set A is a subset of a set B or, equivalently, B is a sz~persetof A, written A C E or B > A iff each element in A also belongs to B ; that is, x € A implies x € B. We also say that A is contailzed in B or B contains A. The negation of A c B is written A $! B or B $ A and states that there is a n x E A such that x 6! B. Example 3.1:

Consider the sets A = { 1 , 3 5 , 7 , . .)

B = {5,10,15,20, . . .1 > 2 ) = {3, 5, 7, 11, ...) Then C c A since every prime number greater than 2 is odd. On the other hand, B @ A since 10 E B but 10 4 A. C = { . c : x i s prime, r

Example 3.2:

Let N denote the set of positive integers, Z denote the set of integers, Q denote the set of rational numbers and R denote the set of real numbers. Then

N c Z c Q c R Example 3.3:

The set E = {2,4,6] is a subset of the set F = {6,2,4), since each number 2, 4 and 6 belonging to E also belongs to F. In fact, E = F. I n a similar manner it can be shown that every set is a subset of itself.

As noted in the preceding example, A C B does not exclude the possibility that A = B. In fact, we may restate the definition of equality of sets as follows: Two sets A and B are equal if A

c B and E c A.

I n the case that A c B but A = B, n7e say that A is a proper subset of B or B contains A properly. The reader should be warned that some authors use the symbol C for a subset and the symbol c only for a proper subset. The following theorem is a consequence of the preceding definitions:

Theorem 5.1:

Let A, B and C be sets. Then: (i) A c A; (ii) if A C B and B A = B; and (iii) if A C B and B c C, then A c C.

C

A, then

UNIVERSAL AND NULL S E T S I n any application of the theory of sets, all sets under investigation a r e regarded as subsets of a fixed set. We call this set the universal set or universe o f discourse and denote it (in this chapter) by C. Example 1.1:

I n plane geometry, the universal set consists of all the points in the plane.

Example 4.2:

I n human population studies, the universal set consists of all the people in the world.

CHAP. 51

37

SET THEORY

I t is also convenient to introduce the concept of the empty or null set, that is, a set which contains no elements. This set, denoted by e), is considered finite and a subset of every other set. Thus, f o r any set A, @ c A c U. Then A is empty, i.e. A = @.

Example 4.3:

Let A = {x : 'x = 4, z is odd).

Example 4.4:

Let B be the set of people in the world who a r e older than 200 years. According to known statistics, B is the null set.

CLASS, COLLECTION, FAMILY Frequently, the members of a set are sets themselves. For example, each line in a set of lines is a set of points. To help clarify these situations, other words, such a s "class", "collection" and "family" are used. Usually we use class or collection f o r a set of sets, and family for a set of classes. The words subclass, subcollection and subfamily have meanings analogous to subset. {2,3), (2) and {5,6).

Example 5.1:

The members of the class {{2,3), {2), { 5 , 6 ) ) a r e the sets

Example 5.2:

Consider any set A. The power set of A , denoted by T ( A ) or Z A , is the class of all subsets of A. In particular, if A = { a , b, c ) , then T ( A ) = {A, { a , b), {a,c), (6, c ) , { a ) , Cb), {c), @)

In general, if A is finite and has n elements, then T ( A ) will have 2n elements.

SET OPERATIONS The union of two sets A and B, denoted by A U B, is the set of all elements which belong to A or to B: A U B = { x : x E A or x E B ) Here "or" is used in the sense of andlor. The intersection of two sets A and B, denoted by A n B, is the set of elements which belong to both A and B: A n B = { x : x E A and x E B ) If A f l B = 0,that is, if A and B do not have any elements in common, then A and B are said to be disjoint or non-intersecting. The relative co?nplernent of a set 5' with respect to a set A or, simply, the difference of A and B, denoted by A \ B , is the set of elements which belong to A but which do not belong to B: A \ B = {n:: x E A , x4B) Observe that A \ B and B are disjoint, i.e. (A \ B)

nB =

$3.

The absolute co~nplementor, simply, complement of a set A, denoted by Ac, is the set of elements which do not belong to A:

Ac = { x : x E U , x 4 A ) That is, Ac is the difference of the universal set U and A. Example 6.1:

The following diagrams, called Venn diagrams, illustrate the above set operations. Here sets a r e represented by simple plane areas and U , the universal set, by the area in the entire rectangle.

SET THEORY

Example 6.2:

[CHAP. 5

A u B is shaded.

A n B is shaded.

A \ B is shaded.

AC is shaded.

Let A = { 1 , 2 , 3 , 4 ) and B = {3,4,5,6) where 72 = {I,2,3,

A

U

A\B

B = {I, 2, 3, 4, 5, 61

. . .).

A n B = {3,4) Ac = (5, 6 , 7,

= {1,2)

Then:

. . .)

Sets under the above operations satisfy various laws or identities which are listed in Table 5.1 below. In fact we state:

Theorem 5.2:

Sets satisfy the laws in Table 5.1. LAWS OF THE ALGEBRA OF SETS

la. A u A = A 2a.

(AuB)uC = Au(BuC)

3a. A u B = B u A

Idempotent Laws lb. A n A = A Associative Laws 2b.

(AnB)nC = An(BnC)

Commutative Laws 3b. A n B = B n A

Distributive Laws 4a. A u ( B n C ) = ( A u B ) n ( A u C ) 4b. A n ( B u C ) = ( A n B ) u ( A n C ) 5a. A u @ = A

Identity Laws 5b. A n U = A

6a. A u U = U

6b. A n 8 = @

7a. A uAc = U 8a.

Complement Laws 7b. A n A c = @

(Ac)= ~ A

9a. ( A u B ) ~= Acn Bc

8b.

U C = 13,

gC= U

De Rlorgan's Laws 9b. ( A nB)c = AcuBc Table 5.1

Remark:

Each of the above laws follows from the analogous logical law in Table 2.1, Page 11. For example, A n B = { x : x E A and z E B ) = { x : x E B and x E A ) = B n A

CHAP. 51

39

SET THEORY

Here me use the fact that if 11 is ,x E A and q is x E B, then p A q is logically equivalent to q A p: p A q = Q A p. Lastly we state the relationship between set inclusion and the above set operations: Theorem 5.3:

Each of the following conditions is equivalent to A (i) A n B = A

(iii) Bc c A"

(ii) A U B = B

(iv) A n Bc = $3

c B: (v) B

u A"

= Lr

ARGUMENTS AND VENN DIAGRAMS Many verbal statements can be translated into equivalent statements about sets which can be described by Venn diagrams. Hence Venn diagrams are very often used to determine the validity of an argument. Example 7.1 :

Consider the following argument: S1: Babies are illogical. SP: Nobody is despised who can manage a crocodile. S3: Illogical people a r e despised. S:

Babies cannot manage crocodiles.

(The above argument is adapted from Lewis Carroll, Sumbolic Logic; he is also the author of Alice in Wo~zclerla~zd.)Now by S1, the set of babies is a subset of the set of illogical people:

babies

the set of illogical people is contained in the set of despised people:

Furthermore, by S 2 , the set of despised people and the set of people who can manage a crocodile a r e disjoint:

people who can manage crocodiles

But by the above Venn diagram, the set of babies is disjoint from the set of people who can manage crocodiles, or "Babies cannot manage crocodiles" is a consequence of S1, S z and S3. Thus the above argument, is valid.

S,,

sz, s3

+

s

S E T THEORY

Solved Problems SETS, ELEMENTS 5.1. Let A = ( x : 3 x = 6). Does A = 2 ? A is the set which consists of the single element 2, that is, A = ( 2 ) . The number 2 belongs to A; it does not equal A . There is a basic difference between a n element p and the singleton set { p ) .

5.2.

Which of these sets are equal:

{T,

t, s ) , { s , t, r, s ) , { t ,s, t, r ) , { s , r , s , t ) ?

They are all equal. Order and repetition do not change a set.

5.3.

M7hich of the following sets are finite? (iv) {x : x is an even number) (i) The months of the year. (ii) (1, 2, 3 , . . ., 99, 100) (v) {I,2 , 3 , . . . 1 (iii) The number of people living on the earth. The first three sets a r e finite; the last two sets a r e infinite.

5.4.

Determine which of the follo~vingsets are equal: @, { 0 ) , {PI. set

5.5.

Each is different from the other. The set ( 0 ) contains one element, the number zero. The contains no elements; it is the empty set. The set (0)also contains one element, the null set.

Determine whether or not each set is the null set: (i) X = { x : x2 = 9, 2x = 41, (ii) Y = { x : x # x), (iii) Z = { x : x (i)

There is no number which satisfies both

x2

+ 8 = 8) .

= 9 and 2 2 = 4; hence X is empty, i.e. X = 0.

(ii) We assume t h a t any object is itself, so Y is also empty. In fact, some texts define the null set as follows:

$3

=

{x:

X # X )

+

(iii) The number zero satisfies z 8 = 8; hence Z = (0). since i t contains 0 . That is, Z f @.

Accordingly, Z is not the empty set

SUBSETS 5.6. Prove that A = { 2 , 3 , 4 , 5 ) is not a subset of B = ( x : x is even). I t is necessary to show that a t least one element in A does not belong to B. Now 3 E A and, since E consists of even numbers, 3 6? B; hence A is not a subset of B.

5.7.

Prove Theorem 5.l(iii): If A C B and B c C, then A c C. We must show t h a t each element in A also belongs to C. Let x E A . Now A c B implies x E B. But B c C; hence x E C. We have shown t h a t x E A implies x E C, t h a t is, that A c C.

5.8.

Find the power set T(S) of the set S = { 1 , 2 , 3 ) . The power set T ( S ) of S is the class of all subsets of S ; these a r e ( 1 , 2 , 3 ) , ( 1 , 2 ) , ( 1 , 3 ) , { 2 , 3 ) ,

{I}, ( 2 1 , ( 3 ) and the empty set 0. Hence T(S) = {S, 11,3), {2,3), {1,2}, Note t h a t there a r e Z 3 = 8 subsets of S.

{ 2 ) , {3),

5.9.

41

SET THEORY

CHAP. 51

Let V = ( d ) , W = { c , d ) , X = (a,b , c), Y = {a, b ) and Z = (a, b , d ) . Determine whether each statement is true or false: (i) Y c X, (ii) TV Z, (iii) Z > 17, [iv) V c X, (v) X = W, (vi) W c Y .

-

(i)

Since each element in Y is a member of X, Y c X is true.

(ii) Now a E Z but

(1

4 W ; hence W

# Z

is true.

(iii) The only element in V is d and it also belongs to 2 ; hence Z > V is true. (iv) V is not a subset of X since d E V but d 4 X; hence V C X is false. (v) Now u E X but a 4 W; hence X = W is false.

(vi) W is not a subset of Y since c E 68 but c 4 Y ; hence W c Y is false.

6.10. Prove:

If A is a subset of the empty set e), then A = @.

The null set @ is a subset of every set; in particular, IZ) c A . hence A = 0.

But, by hypothesis, A c $3;

SET OPERATIONS 5.11. Let U = ( 1 , 2, . . . , 8,9), A = { 1 , 2 , 3 , 4 ) , B = [2,4,6,8) and C = { 3 , 4 , 5 , 6 ) . (i) A", (ii) A n C, (iii) (A n C)[, (iv) A U B, (v) B \ C. (i)

Find:

Ac consists of the elements in C that are not in A; hence A C = {5,6, 7,8,9).

(ii) A n C consists of the elements in both A and C; hence A n C = { 3 , 4 } . (iii) ( A n C)c consists of the elements in C that a r e not in A n C . Now by iii), A n C = { 3 , 4 ) and so ( A n C ) c = { 1 , 2 , 5 , 6 , 7 , 8 , 9 ) . (iv) A u B consists of the elements in A or B (or both): hence A L B = { 1 , 2 , 3 , 4 , 6 , 8 ) . (v) B \ C consists of the elements in B which a r e not in C; hence

5.12. In each Venn diagram below, shade:

(i)

B \ C = {2,8).

[i) A U B, (ii) A n B.

A L E consists of those elements which belong to A or B (or both); hence shade the area in A and in B as follows:

A u B is shaded. (ii) A n B consists of the area t h a t is common to both A and B. To compute A n B, first shade A with strokes slanting upward to the right ( / / / I )and then shade B with strokes slanting downward to the right (\\\\), as follows:

Then A n E consists of the cross-hatched area which is shaded below:

SET THEORY

A n B is shaded. Observe the following: ( a ) A n E is empty if A and E a r e disjoint. ( b ) A r E = B if B c A . ic) A ~ I = B A if A C E .

5.13. In the Venn diagram below, shade: (i) Bc, (ii) ( A L'B)<,(iii) ( B\A)"

(ii

(iv) A' n Bc.

BL consists of the elements which do not belong to B: hence shade the a r e a outside B a s follows:

Ec is shaded. (ii) F i r s t shade A

u B; then iA BjC is the a r e a outside A E: -1

AUB i s shaded. (iii, F i r s t shade B\A, E\A.

B \A

IJ

(A uE)Cis shaded.

the area in E which does not lie in A ; then (E\A)c

is shaded.

is the area outside

( E \ A)Cis shaded.

(ivr F i r s t shade AC, the area outside of A, with strokes slanting upward to the right i / l l / ) , and then ACOIE' is the then shade BC with strokes slanting downward to the right (\\\\I; cross-hatched area:

S E T THEORY

AQnd Bc a r e shaded.

Acn Bc is shaded.

Observe that ( A L B)c = Acn Bc, a s expected b y De Morgan's law.

5.14. I n the Venn diagram below, shade

(i)

(i) A n ( B U C), (ii) ( A n B) U ( An C).

First shade A with upward slanted strokes, and then shade BUC with downward slanted strokes; now A n (BUC) is the cross-hatched area:

A and B u C a r e shaded.

A n ( B u C) is shaded.

(ii) First shade A n B with upward slanted strokes, and then shade A n C with downward slanted strokes; now ( An 6 )u ( An C ) is the total area shaded:

A n B and A n C a r e shaded.

( An B ) u ( An C) is shaded.

Notice t h a t A n ( B uC) = ( An B ) u ( An C ) , as expected by the distributive law.

= B n A". Thus the set operation of difference can be written in 5.15. Prove: B\A terms of the operations of intersection and complementation.

B\A

= { x : x E B , .,;@A) =

{x: x E B , x E A C } = BnAc

44

SET THEORY

A n ( BU C) = ( An B ) U (A n C).

5.16. Prove the Distributive Law:

A n ( B u C ) ==-

{x : x € A ; x E B u C } { x : x E A ; x E B or x E C } { x : x E A , x E B ; or x E A , x E C } { r e : x E A n B or a E A n C } (AnB)u(AnC)

= 1-

= =

Observe t h a t in the third step above we used the analogous logical law (9 v r )

P

5.17. Prove:

=

(P A q) v ( P

A

4

(A \ B) f l B = @. (A\B)nB

=

{ x : xEA\B,xEB}

=

{x: xEA, x4B; zEB}

=

F1

The last step follows from the fact t h a t there is no element x satisfying z E B and z @ B .

Ac nBc.

5.18. Prove De Morgan's Law: (A UB)" ( A u B ) ~=

{x: x ~ A u B }

= {x: x4A, x4B) = { x : x E AC, x E BC} = ACnBC Observe that in the second step above we used the analogous logical law -(p

V

5.19. Prove: For any sets A and B, A n B

q)

-p

A

-q

c A c A U B.

Let z E A n B ; then x E A and x E B. I n particular, x E A. Since x E A n B implies x € A , A n B c A. Furthermore, if z E A , then x E A or x E B, i.e. x E A u B. Hence A c A u B. In other words, A n B c A c A u B .

5.20. Prove Theorem 5.3(i): A c B if and only if A n B = A . Suppose A c B. Let x E A ; then by hypothesis, x E B. Hence x € A and x E B, i.e. x E A n B. Accordingly, A c A n B . On the other hand, i t is always true (Problem 5.19) t h a t A n B c A. Thus A n B = A . Now suppose t h a t A n B = A. Then in particular, A C A n B. A n B c B. Thus A c A n B c B and so, by Theorem 5.1, A c B.

But i t is always true t h a t

ARGUMENTS AND VENN DIAGRAMS 5.21. Show that the following argument is not valid by constructing a Venn diagram in which the premises hold but the conclusion does not hold: Some students are lazy. All males are lazy.

.....................

Some students are males. Consider the following Venn diagram:

CHAP. 51

SET THEORY

lazy people students males

Notice t h a t both premises hold, but the conclusion does not hold. For a n argument to be valid, the conclusion nlust always be t r u e whenever the premises a r e true. Since the diagram represents a case in which the conclusion is false, even though the premises a r e true, the argument is false. I t is possible to construct a Venn diagram in which the preinises and conclusion hold, such a s

lazy people

students

males

5.22. Show that the following argument is not valid:

All students a r e lazy. Nobody svho is wealthy is a student.

................................ Lazy people are not wealthy. Consider the following Venn diagram:

wealthy people

Now the premises hold in the above diagram, but the conclusion does not hold; hence the argument is not valid.

5.23. F o r the following set of premises, find a conclusion such that the argument is valid: S,: All lawyers are wealthy. S,: Poets are temperamental. S,: No temperamental person is wealthy.

.................................... By S , , the set of lawyers is a subset of the set of wealthy people: ancl by S,, the set of wealthy people and the set of temperamental people a r e disjoint. Thus

temperamental people

46

S E T THEORY By S Y , the set of poets is a subset of the set of temperamental people; hence

Thus the statement "No poet is a lawyer" or equivalently "No lawyer is a poet" is a valid conclusion. The statements "No poet is wealthy" and "No lawyer is temperamental" conclusions which do not make use of all the premises.

are also valid

MISCELLANEOUS PROBLERlS 5.24. Let A = (2, ( 4 , 5 ) , 4). Which statements a r e incorrect and why? ( i 4 5 ) C A, (ii) { 4 , 5 ) E A, (iii) {{4,5}} C A. The elements of A a r e 2, 4 and the set {4,5). Therefore (iii is correct, but (i) is an incorrect statement. Furthermore, (iii) is also a correct statement since the set consisting of the single element { 4 , 5 $ which beiongs to A is a subset of A.

5.25. Let A = (2, {4,5), 4). lTThich statements are incorrect and why? (il 5 E A, (ii) ( 5 ) E A, (iii) { 5 ) c A. Each statement is incorrect. The elements of A are 2, 1 and the set {4,5}; hence (ii and (ii) are incorrect. There a r e eight subsets of A and (5) is not one of them; so (iii) is also incorrect.

5.26. Find the power set T(S) of the set

S = (3, { 1 , 4 ) ) .

Note first t h a t S contains two elements, 3 and the set { 1 , 4 ) .

Therefore T(S) contains

22 = 3 elen~ents: S itself, the empty set (3, and the two singleton sets which contain the elements 3 and { I , 4 ) respectively, i.e. {3) and {{I, 4)). I n other words,

TiS) =

{S,{3), {{I, 4)), 0)

Supplementary Problems SETS, SUBSETS 5.27.

Let A = { 1 , 2,..., 8,9), B = { 2 , 4 , 6 , 8 ) , C = { 1 , 3 , 5 , 7 , 9 ] , D = { 3 , 4 , 5 ) and E = { 3 , 5 ) . Which sets can equal X if we are given the following information? (i) X and E a r e disjoint. (ii) X c D but X B. (iii) X c A but X' C. (iv) X C C but X # A .

#

5.28.

State whether each statement is true or false: (ii Every subset of a finite set is finite, rii) Every subset of an infinite set is infinite.

5.29.

Find the power set T(A) of A = ( 1 , 2 , 3 , 4 ) and the power set T(B) of B = {I, { 2 , 3 ) , 4 ) .

CHAP. 51

5.30.

State whether each set is finite or infinite: (i) (ii) (iii) (iv) (v) (vi)

5.31.

S E T THEORY

The set of lines parallel to the r axis. The set of letters in the English alphabet. The The The The

set set set set

of of of of

numbers which a r e n~ultiplesof 5. animals living on the earth. numbers which are solutions of the equation x2' circles through the origin (0,O).

State whether each statement is true or false: (i) {1,4,3: = :3,4,1: (ii) {1,3,1,2,3,2) c {1,2,3} (iii) {1,2} = { 2 , 1 , 1 , 2 , 1 ]

(iv) C4) E {C4)) (v) (4) C CC4)) (vi) 8 c CC43)

SET OPERATIONS 5.32. Let U = { u , b , c , d , e , f , g ) , A = { a , b , c , d , e ) , B = {a,c,e,g) ( i ~A u C (iii) C \ B (v) C C n A iiir E n A (vi) (A \ (iv) B C ~ C 5.33.

+ 2 6 ~ -1 17x11 ~ + 7x3 - 10 = 0.

I n the Venn diagrams below, shade

(i) W \ V

(ii) VCUW

and C = {b,e,f,g). Find: ivii) (A \ BC)C iviii) (A nAc)c ( i i i ~V n WC

(a)

(iv) VC\ WC.

(b)

5.34.

Draw a Venn diagram of three non-empty sets A , B and C so t h a t A, B and C have the following properties: ( i ) A c B , C C B , A n C = (29 (iii) A c C , A # C , B n C = @ (iv) A c ( B n C ) , B c C , C # B , A Z C fii) A c B , C$B, A n C # O

5.35.

The formula A \ B = A nBc defines the difference operation in terms of the operations of intersection and complement. Find a formula that defines the union of two sets, A u B , in terms of the operations of intersection and complement.

5.36.

Prove Theorem 5.3iiii: A C B if and only if A UB = B.

5.37.

Prove:

If A ? E = (3, then A CBC.

5.38.

Prove:

Ac \ BC = b' \ A .

5.39.

Prove:

A c B implies A u (B \ A ) = B.

5.40.

Prove: A n (B \ C) = (A n B ) \ ( A ?C). Give an example to show t h a t A U (B \ C) f (A U B) \ (A C). (ii) (i)

-ARGUMENTS AND V E N S DIAGRAMS Determine the validity of each argument for each proposed conclusion. 5.41. No college professor is wealthy. Some poets a r e wealthy. (i) Some poets a r e college professors. (ii) Some poets a r e not college professors.

48 5.42.

SET THEORY Deter~ninethe validity of each argu111ent f o r each proposed conclusion. All poets a r e interesting people. Audrey is a n interesting person. IiI I

Audrey is a poet.

~ i iAudrey is not a poet.

Determine the validity of the a r g u i i i e ~ ~f to r each proposed conclusion. All poets a r e poor. I n order to be a teacher, one nus st graduate from college. No college graduate is poor. (i)

Teachers a r e not poor.

(ii) Poets a r e not teachers. (iii) If Marc is a college graduate, then he is not a poet. Determine the validity of the argument f o r each proposed conclusion. A11 mathematicians a r e interesting people. Some teachers sell insurance. Only uninteresting people become insurance salesmen. (i) (ii) (iii) (iv)

Insurance salesnlen a r e not mathematicians. Some interesting people a r e not teachers. Some teachers a r e not interesting people. Some riiathen~aticiansa r e teachers.

(v) Some teachers a r e not mathematicians. (vi) If Eric is a mathematician, then he does not sell insurance.

Answers to Supplementary Problems (i) C and E, (ii) D and E, [iii) A, E and D, (iv) None (i) T, (ii) F

(i) infinite, (ii) finite, (iii) infinite, (iv) finite, (v) finite, ( v i ) infinite (i) T, (ii) T, (iii) T, (iv) T, (v) F, (vi) T (i)

AuC=U

(ii) B n A = {a,c, e ) (iii) C \ B = { b , f) (iv) B C u C= { b , d , e , f , g }

(v)

CCn A = {a, c, d ) = CL

(vi) (A \ C)C= { b , e , f,g } (vii) (A \ Bc)c = { b , cl, t', g ) (viii) (A nAc)c = U

Vcu W

W\V

Observe that V cU W = U and 5.34.

(i)

5.40.

(ii)

49

SET THEORY

CHAP. 51

Vc \ W c

Vn Wc

V n T.Vc = O in case ( b ) where V c ti'.

@

A

L(E\

( A u B) \ (A u C) is shaded.

C) is shaded.

5.41.

(i) fallacy, (ii) valid

5.42.

(i) fallacy, (ii) fallacy

5.43.

(i) valid, (ii) valid, iiii) valid

5.44.

(i) valid, (ii) fallacy, riii) valid, (iv) fallacy,

I V valid, ~

(vi) valid

The following Venn diagrams show why (iij and (iv) a r e fallacies:

interesting insurance

0 mathematicians

u teachers

Product Sets ORDERED PAIRS An o r d e ~ e dpair consists of two elements, say a and b , in which one of them, say a, is designated as the first element and the other as the second element. Such an ordered pair is written (a, b ) Two ordered pairs (a, b ) and (c, d ) are equal if and only if a = c and b = d. Example 1.1:

The ordered pairs ( 2 , 3 ) and ( 3 , 2 ) a r e different.

Example 1.2:

The points in the Cartesian plane in Fig. 6-1 below represent ordered pairs of real numbers.

Example 1.3:

The set {2,3} is not an ordered pair since the elements 2 and 3 are not distinguished.

Example 1.4:

Ordered pairs can have the same first and second elements, such as (1,I), (4,4) and (5,5).

Remark:

An ordered pair (a, b ) can be defined rigorously as follows: (a, b ) = {{a), (a, b ) ) the key here being that {a} c {a, b J which we use to distinguish a as the first element. From this definition, the fundamental property of ordered pairs can be proven: (a, b) = (c, d ) if and only if a = c and b = d

PRODUCT SETS Let A and B be two sets. The p ~ o d u c tset (or Cartesian product) of A and B, written A x B, consists of all ordered pairs (a, b ) where a E A and b E B: A x B = {(a,b ) : a E A, b E B } The product of a set with itself, say A X A, is sometimes denoted by A2. Example 2.1:

The reader is familiar with the Cartesian plane R2 = R X R (Fig. 6-1 below). Here each point P represents a n ordered pair (u, b) of real numbers and vice versa; the vertical line through P meets the x axis a t a , and the horizontal line through P meets the 7~ axis a t b.

Fig. 6-1

Fig. 6-2

CHAP. 61

PRODUCT SETS

Example 2.2:

Let A = ( 1 , 2 , 3 ) and B = {a, h).

A

=

E

Then

C(1, a ) , (1,b ) , (2, a ) , (2, b ) , ( 3 ,a ) , (3, b ) )

Since A and B do not contain many elements, it is possible to represent A ,.(B by a coordinate diagram a s shown i n Fig. 6-2 above. Here the vertical lines through the points of A and the horizontal lines through the points of B meet in 6 points which represent A X B in the obvious way. The point P is the ordered pair (2, b).

I n general, if a finite set A has s elements and a finite set B has t elements, then A x B has s times t elements. If either A or B is empty, then A X B is empty. Lastly, if either A or B is infinite, and the other is not empty, then A x B is also infinite. PRODUCT S E T S I N GENERAL The concept of a product set can be extended to more than two sets in a natural way. The Cartesian product of sets A, B, C, denoted by A x B x C, consists of all ordered triplets (a, b, c ) where u E A, 2, E B and c E C: Analogously, the Cartesian product of n sets A,, A,, . . .,An, denoted by A, X A, consists of all ordered n-tuples (a,, a,, . . . , a , , ) where a, E A,, . . . , a n E An:

x A , x . . x An =

{(a1,. . . , a n ): a, E A,, . . ., a n €

X

.

X

An,

41

Here an ordered 71-tuple has the obvious intuitive meaning, that is, it consists of n elements, not necessarily distinct, in which one of then1 is designated as the first element, another a s the second element, etc. Furthermore, (a,..a

a, = b,, . . . , a,, = b,,

) = ( b , . . . , b ) iff

Example 3.1:

In three dimensional Euclidean geometry each point represents a n ordered triplet: its x-component, its y-component and its z-component.

Example 3.2:

Let A = { a , b}, B = { 1 , 2 , 3 ) and C = { x , y).

A A E

A

C

=

Then:

{ ( a ,I , % ) ,( a ,1,y), ( a ,2 , ~ (a, ) 2, ~ Y), ( a , 3 , x ) , ( a , 3 , ~ )( b, , l , s ) ,( b , l , y ) , (b, 2, x), (b,2, .Y), ( b ,3 , 2 ) , (b,3 , ~ ) )

TRUTH S E T S O F PROPOSITIONS Recall that any proposition P containing, say, three variables p, value to each of the eight cases below:

(r

and r , assigns a truth

T

Let U denote the set consisting of the eight 3-tuples appearing in the table above: U = {TTT, TTF, TFT, T F F , FTT, F T F , F F T , F F F ) (For notational convenience we have written, say, TTT for (T, T, T).)

52

[CHAP. 6

PRODUCT SETS

The truth set of a proposition P, written T(P), consists of those elements of U for which the proposition P is true. Following is the truth table of ( p + q )

Esample 1.1:

A (q

+

T):

?# F

F T

T F

F

F

T F

Accordingly, the truth set of (p -+ q ) T ( ( p+ q )

A

A

(q +r)) =

( q + T ) is

{TTT, FTT, F F T , F F F }

The next theorem shows the intimate relationship between the set operations and the logical connectives.

Theorem 6.1:

Let P and Q be propositions. Then: (i)

T ( P + Q) = T(P) n T(Q)

(ii) T ( P \ ) Q) = T ( P ) U T ( Q ) (iii) T(-P)

= (T(P)).

(iv) P logically implies Q if and only if T(P) c T(Q) The proof of this theorem follows directly from the definitions of the logical connectives and the set operations.

Solved Problems ORDERED P A I R S 6.1.

Let W = {John, Jim, Tom)

and let

V = {Betty, Mary}. Find W X V.

TV x V consists of all ordered pairs (a,b) where a € IT' and b E V .

W x V

6.2.

=

Suppose If

Hence,

{(John, Betty), (John, Mary), (Jim, Betty), (Jim, ilIaryi, (Tom, Betty), (Tom, Mary))

(x + y, 1) = (3, T - y). Find

( x - U, 1) = (3, x - y)

r and y.

then, by the fundamental property of ordered pairs, .r+y

= 3

and

1 = z-y

The solution of these simultaneous equations is giverrby .z: = 2, y = 1.

Relations RELATIONS A b i n u i 8 i7elotion ~ or, simply, r e l u f i o n R from a set A to a set B assigns to each pair (a, b) in A r B exactly one of the following statements: (i) "a is related to b", written a R b (ii) "a is not related to b", written a

4b

A relation from a set A to the same set A is called a relation in A. Example 1.1:

Set inclusion is a relation in any class of sets. For, given a n y pair of sets A and B, either A c B or A 2 E .

Example 1.2:

Marriage is a relation from t h e set M of men to the set W of women. F o r , given a n y man m E -ll and any woman w E TV, either 771 is married to ~ t .or )?z is not married to tc.

Example 1.3:

Order, symbolized by "<", or, equivalently, the sentence "x is less than y", is a relation in any set of real numbers. For, given any ordered pair ( a , b ) of real numbers, either a
Example 1.4:

Perpendicularity is a relation in the set of lines in the plane. For, given any pair of lines a and b, either a is perpendicular to b or a is not perpendicular to b.

RELATIOKS AS SETS OF ORDERED PAIRS Now any relation R from a set A to a set B uniquely defines a subset R" of A x B as follows: R:: = { ( a ,b ) : a is related to b ) = {(a,b ) : a R b )

On the other hand, any subset R,'of A x B defines a relation R from A to B as follows: a 1: 2, iff ( a , b ) € Rb' In view of the correspondence between relations R from A to B and subsets of A X B , we redefine a relation by

A relation R from A to B is a subset of A x B. Example 2.1:

Example 2.2:

Let R be the following relation from A = {I,2, 3) to B = { a , b): R = ( ( 1 ,a), (1,b ) , ( 3 , ~ ) ) Then 1R a , 2 @ b , 3 R a, and 3 $ b. The relation R is displayed on the coordinate diagram of A X B on the right. Let R be the following relation in W = { a , b , c]

R = ( ( a ,b), ( a , c), (c, 4 , ( c , b ) ) Then a $ a , u R b , c R c and c $ a .

a

b@

1

2

3

CHAP. 71 Example 2.3:

59

RELATIONS

Let A be a n y set. The i d e x t i t y relation in A, denoted by 1 o r P A , is the set of all pairs in A X A with equal coordinates: A, = { ( a ,a ) : a E A ) The identity relation is also called the diagonal by virtue of its position in a coordinate diagram of A x A.

INVERSE RELATION Let R be a relation from A to B. The inverse of R, denoted by R-l, is the relation from B to A which consists of those ordered pairs which when reversed belong to R: R-I = { ( b ,a ) : (a,b) E R ) Example 3.1 :

Consider the relation R = { ( 1 , 2 ) ,( 1 , 3 ) , ( 2 , 3 ) )

in A = {1,2,3}.

Then

R-' = ( ( 2 , I ) , (3,1), ( 3 , 2 ) ) Observe t h a t R and R-I a r e identical, respectively, to the relations in A, i.e., ( a , b ) E R iff a < b and ( d , b ) E R P 1 iff a > b

Example 3.2:

<

and

>

The inverses of the relations defined by "X

is the husband of y"

"x is taller than y"

and

a r e respectively

"x is the wife of y"

and

''3:

is shorter than

y"

EQUIVALENCE RELATIONS A relation R in a set A is called ~eflexiveif a R a , i.e. (a, a) E R, f o r every a E A. Example 4.1:

(i) Let R be the relation of similarity in the set of triangles in the plane. R is reflexive since every triangle is similar to itself.

Then

(ii) Let R be the relation < in any set of real numbers, i.e. ( a , b ) E R iff a < b. Then R is not reflexive since a 4 a f o r any real number a.

A relation R in a set A is called symnzetric if whenever a R b then b R a, i.e. if (a, b ) E R implies ( b , a ) E R. Example 4.2:

ii) The relation R of similarity of triangles is symmetric. similar to triangle 13, then ,8 is similar to a.

For if triangle

ct

is

(ii) The relation R = {(I,3 ) , ( 2 , 3 ) , (2,2), ( 3 , l ) ) in A = {I,2 , 3 ) is not symmetric since ( 2 , 3 ) E R but ( 3 , 2 ) 4 R.

A relation R in a set A is called transitive if whenever a R b and b R c then a R c , i.e. if (a,b) E R and ( b , c ) E R implies ( a , c) E R. Example 4.3:

(i) The relation R of similarity of triangles is transitive since if triangle similar to /3 and /3 is similar to y, then ol is similar to y.

ct

is

(ii) The relation R of perpendicularity of lines in the plane is not transitive. Since if line a is perpendicular to line b and line b is perpendicular to line c , then a is parallel and not perpendicular to c.

A relation R is an equivalence relafio?~if R is (i) reflexive, (ii) symmetric, and (iii) transitive. Example 4.4:

By the three preceding examples, the relation R of similarity of triangles is a n equivalence relation since it is reflexive, symmetric and transitive.

60

RELATIONS

[CHAP. 7

PARTITIONS A partition of a set X is a subdivision of X into subsets which a r e disjoint and whose union is X , i.e. such that each a € X belongs to one and only one of the subsets. The subsets in a partition are called cells. Thus the collection {A,,A,,

. . .,A,,,) of

subsets of X is a partition of X iff:

(i) X = A , U A , U - . . U A , , , ; (ii) for any Ai,Aj, either A i = A j or A i n A j = @ Example 5.1 :

Consider the following classes of subsets of X = {I,2, . . . ,8,9): (i)

[{I, 3,51, {2,6),{4,8,931

!ii)

[{I,3,51, {2,4,6,8),{5,7,91]

(iii) [{I,3,51, {2,4,6,8},(7,911 Then (i) is not a partition of X since 7 E X but 7 does not belong to any of the cells. Furthermore, (ii) is not a partition of X since 5 E X and 5 belongs to both {I, 3,5) and {5,7,9). On the other hand, (iii) is a partition of X since each element of X belongs to exactly one cell.

EQUIVALENCE RELATIONS AND PARTITIONS Let R be an equivalence relation in a set A and, for each a E A , let [a], called the equivale?zce class of A, be the set of elements to which a is related: [a] =

{X : (a, x) E R )

The collection of equivalence classes of A , denoted by A l R, is called the quotient of A by R:

AIR

=

{[a]: a E A j

The fundamental property of a quotient set is contained in the following theorem. Theorem 7.1:

Let R be a n equivalence relation in a set A. Then the quotient set A I R is a partition of A . Specifically, (i) a E [ a ] , f o r every a E A ; (ii) [a] = [b] if and only if (a, b) E R; (iii) if [a] # [b], then [a] and [b] are disjoint.

Example 6.1:

Let R, be the relation in Z, the set of integers, defined by x = y (mod 5) which reads "x is congruent to y modulo 5" and which means t h a t the difference x - y is divisible by 5 . Then R5 is a n equivalence relation in Z. There a r e exactly five distinct equivalence classes in Z I R5:

+

Observe t h a t each integer x which is uniquely expressible in t h e form x = 5q r where 0 5 r < 5 is a member of the equivalence A , where r is the remainder. Note t h a t the equivalence classes a r e pairwise disjoint and t h a t Z = A , u A , u A , u A , u A,

RELATIONS

CHAP. 71

Solved Problems RELATIONS 1 Let R be the relation < from A = {1,2,3,4) to B = {1,3,5), i.e. defined by "x is less than y". (i) Write R as a set of ordered pairs. (ii) Plot R on a coordinate diagram of '4 x B. (iii) Find the inverse relation R-'. (i)

R consists of those ordered pairs which a

< b;

(a, b) E A

A

E

for

hence

R = { ( 1 , 3 ) ,11,5),12,3), (2,5), (3,5), (4,51j (ii) R is sketched on the coordinate diagram of A X E a s shown in the figure. (iii) The inverse of R consists of the same pairs a s a r e in R hut in the reverse order: hence

R-I

= {13,lI, ( . ? , I ) ,( 3 , 2 ) , (5,2), ( 5 , 3 ) ,15,8)]

Observe t h a t R-I is the relation greater than y".

7.2.

>, i.e.

defined by

''7

is

Let R be the relation from E = :2,3,4,5) to F = (3,6,7,10) defined by "x: divides y". (i) Write IZ as a set of ordered pairs. (ii) Plot R on a coordinate diagram of E x F. (iii) Find the inverse relation R-'. (i)

(ii)

Choose from the sixteen ordered pairs in E X F those in which the first element divides the second; then R = {(2,61, (2,101, (3,3), (3,6), (5,101)

R i s sketched on the coordinate diagram of E

X

F as

shown in the figure.

10

7 6

3

(iii) To find the inverse of R, write the elements of R but in reverse order. R-I = :16,2), l10,2), (3,3), (6,3), (10, 5 ) )

Let 144 = {a,b, c, d ) and let R be the relation in ;12 consisting of those points which are displayed on the coordinate diagram of M x M on the right. (i) Find all the elements in '$1which are related to Z?, that is, {x : ( r ,b) E R J . (ii) Find all those elements in M to which d is related, that is, {x : (d, x) E R ) . (iii) Find the inverse relation R-'.

2

3

4

5

d C

b a

a

b

c

d

ii)

The horizontal line through b contains all points of R in which b appears a s the second element: (a, b), ( b , b ) and (cl, b). Hence the desired set is {a, b,d).

iii)

The vertical line through (1 contains all the points of R in which d appears a s the first element: ( d , a ) and ( t l , h ) . Hence { u , b\ is the desired set.

(iii) F i r s t \vrite R a s a set of ordered pairs, and then write the pairs in reverse order: = ',(a, b), (b, a ) , (6, b), (b, 4 , (c, c ) , ( d , (0, id, b)l R

R-' = {(b, a), (a, b), (b, b), (d,b), (c,c), (a, d), (b, cl):

62

[CHAP. 7

RELATIONS

EQUIVALENCE RELATIONS 7.4. Let R be the relation 6 in N = {1,2,3, . . .), i.e. (a, b) E R iff a b. Determine whether R is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) a n equivalence relation.

'

for every a € N. (i) R is reflexive since a'a (ii) R is not symmetric since, for example, 3 6 5 but 5 (iii) R is transitive since a

6

3, i.e. (3,5) E R b u t (5,3) 4 R.

b and b 6 c implies a 6 c.

(iv) R is not an equivalence relation since i t is not symmetric.

7.5.

Let R be the relation ( 1 (parallel) in the set of lines in the plane. Determine whether R is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) an equivalence relation. (Assume that every line is parallel to itself.) (i) R is reflexive since, by assumption, a 11 a f o r every line a. (ii) R is symmetric since if a ( 1 p then p 11 a, i.e. if the line a is parallel to the line /3 then /3 is parallel to a. iiii) R is transitive since if n 1 j p and /3 J J y then oc I)y. (iv) R is an equivalence relation since it is reflexive, symmetric and transitive.

7.6.

Let W = {1,2,3,4). Consider the following relations in W:

Rl = {(I,Z), (4,317 (2, Z), (2, 1))( 3 , l ) ) R, = {(2,2),(2,3), (3,211 R, = {(1,3)) Determine whether each relation is (i) symmetric, (ii) transitive. (i)

Now a relation R is not symmetric if there exists an ordered pair (a, b ) E R (b, a ) B R. Hence: R , is not symmetric since (4,3) E R1 but (3,4) 4 R1,

such that

R3 is not symmetric since (1,3) E R3 but (3,l) 4 R3. On the other hand, R, is symmetric. (ii) A relation R is not transitive if there exist elements a, b and c, not necessarily distinct, such that (a, b) E R and ( b , c ) E R but (a, c) 4 R Hence Rl is not transitive since (4,3) E R1 and (3,l) E R1 but

( 4 , l ) 4 R1

Furthermore, R, is not transitive since (3,2) E R, and (2,3) E R2 but

(3,3) 4 R2

On the other hand, R3 is transitive.

7.7.

Let R be a relation in A. Show that: (i) R is reflexive iff A (i)

Recall t h a t c R.

c R;

(ii) R is symmetric iff R = R-l.

A = {(a,a ) : a E A ) .

Thus R is reflexive iff

(a,a) E R f o r every a E A iff

A

(ii) Suppose R is symmetric. Let (a, b) E R, then ( b , a) E R by symmetry. Hence ( a ,b) E R-1, and so R c R-1. On the other hand, let (a,b) E R-1; then ( b , a) E R and, b y symmetry, (a, b) E R. Thus R-1 c R, and so R = R-1. Now suppose R = R-1. synln~etric.

Let

(a,b) E R;

then

(b, a) E R-1 = R.

Accordingly R is

CHAP. 71

7.8.

63

RELATIONS

Consider the relation R = ((1,I), ( 2 , 3 ) , ( 3 , 2 ) ) in X = { 1 , 2 , 3 ) . Determine whether or not El is (i) reflexive, (ii) symmetric, (iii) transitive. (i) R is not reflexive since 2 E X but 12,2) 4 R. (ii) R is synlmetric since R-1 = ((1,I), (3,2), (2,3)) = R. (iii) R is not transitive since ( 3 , 2 ) E R and 12,3) E R b u t (3,3)4 R.

7.9.

Let N = [ 1 , 2 , 3 , . . . ), and let R be the relation = in N (a, b ) ( c , d ) iff a d = bc Prove that R is an equivalence relation. F o r every (a, b ) E N

X

N, (a, b )

-

X

N defined by

(a, b ) since a b = ba; hence R is reflexive.

Suppose ( a , b ) = ( c , d). Then a d = bc, which implies t h a t c b = da. Hence (c, d) and so R is symmetric. Now suppose i a , b ) (c,d) and (c,d) = (e,f). Then ad = bc and cf = de. Thus

-

iatl)(cf) = (bc)(de)

(a, b )

-

and, by cancelling from both sides, at' = be. Accordingly, ( a , b ) (e, f ) and so R is transitive. Since R is reflexive, symmetric and transitive, R is a n equivalence relation.

a,

Observe t h a t if the ordered pair (a, b ) is written a s a fraction h then the above relation R is, a - c . in fact, the usual definition of equality between fractions, i.e. 7 - - lff ad = bc. d

7.10. Prove Theorem 7.1: Let R be an equivalence relation in a set A. Then the quotient set A IT: is a partition of A. Specifically, (i) a E [ a ] , for every a E A ; (ii) [a] = rbl if and only if ( a , b ) E R ; (iii) if [ a ]+ Ibl, then la] and [bl are disjoint. Proot o f (1). Since R is reflexwe, (a, a ) E R f o r every a E A and therefore a € [a]. Proof ot n). Suppose (a, b) E R. We want to show t h a t [a] = [ b ] . Let x E [b] ; then ( b , x) E R. But by hypothes~s(a, b) E R and so, by transitivity, (a, x) E R. Accordingly x € [a]. Thus [bl c [a]. To prove t h a t a c L b ] ,we observe t h a t (a, b ) E R implies, by symmetry, t h a t (b, a ) E R. Then by a similar argument, n e obtain [a] ~ [ b l .Consequently, [a] = [b]. On the other hand, if [a] = [b], then, by ( I ) , b E [b] = [a] ; hence (a, b ) E R. Proof ot ( n ~ i . We prove the equivalent contrapositive statement if 'a1 bl # @ then [a] = [bl

+

Hence (a, x) E R and If [a]r b ] $3, then there exists an element x E A with .c E [a] n jbl. (b, x) E R. By s y m n ~ e t r y ,(x, b) E R and by transitivity, (a, b) E R. Consequently by (ii), [a] = [bl.

PARTITIONS 7.11. Let X = { a , b , c, d, e, f , g ) , and let: (i) A , = { a , c , e ) , A,= { b ) , A,= { d , g ) ; (ii) B l = (a, e , g ) , B, = { c , d ) , B , = { b , e , f ) ; (iii) C l = ( a , b , e , g ) , C,= { c ) , C, = { d , j ) ; (iv) Dl = { a , b , c, d , e , f , g l . Which of { A , , A , , A , ) , {B,, B,, B , ) , JC,, C, C,), {Dl)are partitions of X ? (i) { A , , A,, A ,] is not a partition of X since t E X but f does not belong to either A l , A > , or A,. (ii) { E l ,E ? , E , ] IS not a partition of X slnce e E X belongs to both B1 and B,. (iii) {C,, C2,C ? ] is a partition of X since each element in X belongs to exactly one cell, X = C , d C, u C3 and the sets a r e pairwise disjoint. (iv) {D,i IS a partition of X.

i.e.

64

RELATIONS

[CHAP. 7

Find all the partitions of X = {a, b , c, d ) . Note first t h a t each partition of S contains either 1, 2, 3, or 4 distinct sets. The partitions a r e as follo\vs: (1) [{a, b, c, dl]

There a r e fifteen different partitions of X .

Supplementary Problems RELATIONS 7.13.

Let R be the relation in A = {2,3,4,5) defined by "x and y a r e relatively prime", i.e. "the only common divisor of x and y is 1". (i) Write R a s a set of ordered pairs. (ii) Plot R on a coordinate diagram of A X A. (iii) Find R-1.

7.14.

Let 'V = {1,2,3,

. . .)

and let R be the relation in N defined by z R = {(rr,y) : x , y E N , r + 2 y = 8 )

(i) Write R a s a set of ordered pairs. 7.15.

= 8, i.e.,

(ii) Find R-1.

Let C = {I, 2,3,4,5} and let R be the relation in C consisting of the points displayed in the following coordinate diagram of C x C:

(i)

State whether each is true or false:

(a) 1 R 4, (b) 2 R 5, (c? 3 $ 1, (d) 5

(ii) Find the elements of each of the following subsets of C: ( a ) Cn : 3 R x), (b) {x : (4, z) E RS, (c) (x : (x,2) 6? R}, 7.16.

+ 2y

Consider the relations diagonal relation.

<

and

5

in N = { 1 , 2 , 3 , . . .}.

(d) {x : x R 5).

Show t h a t


EQUIVALENCE RELATIONS 7.17.

Let TY = { I , 2,3,4}. Consider the following relations in W:

R I = {(I, 11, i l , 2 ) } R2 = {(1,1), (2,3), ( 4 , l ) ) R3 = {(1,3), (2,4)) Determine whether or not each relation is reflexive.

R4 = { ( I ,l),( 2 , 2 ) , (3,311 R, = T.Ti x W

= Q)

$ 3.

6

where 1 is the

RELATIONS

CHAP. 71

7.18.

Determine whether or not each relation in Problem 7.17 is symmetric.

7.19.

Determine whether or not each relation in Problem 7.17 is transitive.

7.20.

Let R be the relation I of perpendicularity in the set of lines in the plane. Determine whether R is ( i ) reflexive, (ii) symmetric, tiii) transitive, (iv) a n equivalence relation.

7.21.

Let N = { I , 2,3, . . . } and let r be the relation in N X N defined by (a, b)

-

(i) Prore r is a n equivalence relation.

(c, d )

iff

a

+d

= b

+c

(ii) Find the equivalence class of (2,5), i.e. [(2,5)].

7.22.

Prove: If R and S a r e equivalence relations in a set X, then R n S is also a n equivalence relation in X.

7.23.

(i)

Show t h a t if relations R and S a r e each reflexive and symmetric, then R U S is also reflexive and symmetric.

(ii) Give a n example of transitive relations R and S f o r which R U S is not transitive.

PARTITIONS 7.24. Let W = {I,2 , 3 , 4 , 5 , 6 ) .

Determine whether each of the following is a partition of TV:

(i) IC1,3,51, {2,4), C3,6) I

I 7.25.

Find all partitions of

7.26.

Let [ A , , A , ,

. . .,A,,,]

51, {21, {3, Q l

(iii) [{I, 51, {2}, C41, { I , 5}, {3,61] (iv) [{I, 2,3,4,5,6)1

V = {1,2, 3). and [B,, B2, . . ., B,] be partitions of a set X. Show t h a t the collection of sets

[A, n B, : i = l , ...,m,j=l,.. .,n] is also a partition (called t h e c ~ o s sp a r t i t i o n ) of X.

Answers to Supplementary Problems R =

R-1

= ~ ( 2 , 3 )(3, , 2), (2,5), (5,2), (3,4), (4,3), (3,5), (5,3), ( 4 , 5 ) , (5,4)} f

R = {(2,3), (4,2), (i) T, F, F , T.

R-'

= {(3,2), (2,4), (1,6))

(ii) (a) {1,4,51, ( b )

8,

( c ) '12,3,41, ( 4 (31

R, is the only reflexive relation.

R4, R5 and R, a r e the only symmetric relations. All the relations a r e transitive. (i) no, tii) yes, iiii) no, (iv) no (ii) [(2, 5)l = {(a,b) : a + 5 = b = {(a,a

+ 3) :

+ 2, a , b E N )

a E N l = { ( I ,4), (2,5), (3,6), (4,7), . . .I

(ii) R = { \ I ,21) and S = {(2,3)) (i) no, (iii no, (iii) yes, (iv) yes [{l, 2,3)], [{I:, C2, 3)], [{21, (1,311, [{3}, {1,2)1 and [{l}, {2:, (311

Functions DEFINITION OF A FUNCTION Suppose that to each element of a set A there is assigned a unique element of a set B ; the collection, f , of such assignments is called a functioz (or mapping) from (or on) A into B and is written f : + ~ B or A $ B The unique element in B assigned to a E A by f is denoted by J(a), and called the inzage of a under f or the value of f a t a. The dovlzain of f is A, the co-domain B. The ?.a?lge of J , denoted by f [ A ]is the set of images, i.e., flA] = { f ( a ) : a € A ) Example 1.1:

Let f assign to each real number its square, t h a t is, for every real number f(x) = x2. Then the image of -3 is 9 and so we may write f(-3) = 9 or f : -3

2

let 9.

+

Example 1.2:

Let f assign to each country in the world its capital city. Here the domain of f is the set of countries in the world; the co-domain is the list of cities of the world. The image of France is Paris, t h a t is, f\France) = Paris.

Example 1.3:

Let A = { a , b, c , d ) and B = {a, b, c}.

a-b,

The assignments

b-tc, c - c

and d + b

define a function f from A into B. Here f ( a ) = b, f(b) = c, f ( c ) = c and f(c1) = b. The range of f is {b, c ) , that is, f [ A ] = { b ,c ) . Example 1.4:

Let R be the set of real numbers, and let f : R + R assign to each rational number the number 1, and to each irrational number the number -1. Thus f(x)

=

1 if .?: is rational -1 if x is irrational

The range of f consists of 1 and -1: f [ R ]= {I, -1). Example 1.5:

Let A = {a, b , c , d ) and B = {x, y, 2 ) . f:A-,B.

The following diagram defines a function

Here f(a) = y, f(b) = N , f(c) = x and f(d) = y. and the co-domain a r e identical.

Also f [A]= B, t h a t is, the range

CHAP. 81

FCNCTIONS

GRAPH OF A FUNCTION To each function f : A B there corresponds the relation in A X B given by ((a,f ( a ) ) : a E A J We call this set the graph of f. Two functions f : A + B and g : A B a r e defined to be equal, written f = y, if f ( a ) = g ( a ) for every a € A , t h a t is, if they have the same graph. Accordingly, we do not distinguish between a function and its graph. The negation of f = g is written J = y and is the statement: there exists an a E A for which f ( a ) + g(a) -+

-+

A subset J of A x B, i.e. a relation from A to B, is a function if it possesses the follo\~ling property: [F] Each a E A appears a s the first coordinate in exactly one ordered pair (a, b) in f . Accordingly, if (a,b) E f, then j(a)= b. Example 2.1:

Let f : A -+ B be the function defined by the diagr'am in Example 1.5. Then the graph of f is the relation { ( a ,Y), ( b , x), (G,x ) , ( d . u)S

Example 2.2:

Consider the following relations in A = {1,2,3]: f = C(1,3), ( 2 , 3 ) ,( 3 , l ) ) cl = { ( I , 2 ) , ( 3 , l ) I Ft = { ( I , 31, ( 2 , I ) , ( 1 , Z), ( 3 , l ) I

f is a function from A into A since each member of A appears a s the first coordinate in exactly one ordered pair in f ; here f ( 1 ) = 3, f ( 2 ) = 3 and f ( 3 ) = 1 . g is not a function from A into A since 2 E A is not the first coordinate of any pair in g and so g does not assign any image to 2 . Also h is not a function from A into A since 1 E A appears as the first coordinate of two distinct ordered pairs in h , (1,3) and ( 1 , 2 ) . If h is to be a function i t cannot assign both 3 and 2 to the element 1 E A. Example 2.3:

A real-valued function f : R R of the form f ( r ) = ar t b (or: defined by y = a.c b ) is called a linear fuxctio?z: its graph is a line in the Cartesian plane R2, The graph of a linear function can be obtained by plotting ( a t least) two of its points. F o r example, to obtain the graph of %(.I.) = 2x - 1, set up a table with a t least two values of x and the corresponding values of f ( x ) a s in the adjoining table. The line through these points, ( - 2 , - 5 ) , (0, - 1 ) and (2,3), is the graph of f as shown in the diagram. +

Graph of f(x) = 2 x

+

-1

68

[CHAP. 8

FUNCTIONS A real-valued function f' : R + R of the f o n n . . . a,,-,:c f ( x ) = ( I ~ T f) ~alxn-l

+

+

+ a,

is called a poly?zo?i~iulf ~ c ? ~ c t i o n .The graph of such a function is sketched by plotting various points and drawing a smooth continuous curve through them. Consider, for example, the function f i x ) = .c' - 2.1: - 3. Set up a table of values for s and then find the corresponding values f o r f ( x ) a s in the adjoining table. The diagram shows these points and the sketch of the graph.

Graph of f ( x ) = xL

COMPOSITION FUNCTION Consider now functions f : A

+

22.1:- 3

B and g : B + C illustrated below:

Let a E A ; then its image f(a) is in B,the domain of g. Hence we can find the image of f(a) under the function g, i.e. g(f(a)). The function from A into C which assigns to each a € A the element g(f(a)) E C is called the composition or product of f and g and is denoted by g 0 f . Hence, by definition, ( g O f ) ( a )= g(f(a)) Example 3.1 :

Let f : A

+

E and g : B

C be defined by the following diagrams:

f

A

W e compute ( g o t') : A

-

+

B

C

g

C by its definition: ( g o f ) ( a ) = s(f(a)) = g(u) =

t

(gof)(b) = u(f(b)) = g(z) = r iuOf)(c)= u(f(c)) =

u(u)

= t

Notice t h a t the con~positionfunction g is equivalent to "following the arrows" from A to C in the diagrams of the functions J and g.

CHAP. 81 Example 3.2:

69

FUNCTIONS Let R be the set of real numbers, and let f : R + R and g : R follows: f ( 2 ) = x2 and g(x) = z 3

-+

R be defined a s

+

( f 0 g ) ( 2 ) = f ( g ( 2 ) ) = f ( 5 ) = 25 (sO f I ( 2 ) = s ( f ( 2 ) ) = g ( 4 ) = 7

Then

Observe t h a t the product functions f o g and g 0 f a r e not the same function. We compute a general formula f o r these functions:

+ 3 ) = + 3)2 = x2 + 6% + 9 g(x2) = z1 + 3

( f og)(z) = f(g(z)) = f(x

( g o f ) ( x ) = g ( J ( x ) )=

(.T

ONE-ONE AND ONTO FUNCTIONS A function f : A -, B is said to be one-to-one (or: one-one or 1-1)if different elements in the domain have distinct images. Equivalently, f :A + B is one-one if f ( a ) = f (a') Example 4.1:

implies

a = a'

Consider the functions f : A + B, g : B ing diagram:

A

f

B

+

C and h : C C

B

+

D defined by the followh

D

Now f is not one-one since the two elements a and c in its domain have the same image 1. Also, g is not one-one since 1 and 3 have the same image y. On the other hand, h is one-one since the elements in the domain, x, y and z, have distinct images.

A function f : A + B is said t o be onto (or: f is a function from A onto B o r f maps A onto B) if every Z, E B is the image of some a E A. Hence f : A B is onto iff the range of f is the entire co-domain, i.e. f [ A ]= B. +

Example 4.2:

Consider the functions f, g and h in the preceding example. Then f is not onto since 2 E B is not the image of a n y element in the domain A. On the other hand, both g and h a r e onto functions.

Example 4.3:

Let R be the set of real numbers and let f : R R, g : R + R and h : R defined a s follows: f ( ~ ) = 22, g ( x ) = 2 3 - x and h ( z ) = x2 +

The graphs of these functions follow:

f ( x ) = 2"

g(x) = 23 - x

h ( x ) = x2

+

R be

[CHAP. 8

FUNCTIONS

The function f is one-one; geometrically, this means t h a t each horizontal line does not contain more than one point of f. The function g is onto; geometrically, this means t h a t each horizontal line contains a t least one point of g. The function h is neither one-one or onto; f o r h(2) = h ( - 2 ) = 4, i.e. the two elements 2 and -2 have the same image 4, and h[R]is a proper subset of R; f o r example, -16 4 h [ R ] .

INVERSE AND IDENTITY FUNCTIONS I n general, the inverse relation f P 1 of a function f c A x B need not be a function. However, if f is both one-one and onto, then f P 1 is a function from B onto A and is called t,he inverse function. Example 5.1:

Let A = {a, b, c ) and B = { r , s, t } .

Then

f = { ( a ,s), ( b , t ) , (c, 4) is a function from A into B which is both one-one and onto. seen by the following diagram of f:

This can easily be

Hence the inverse relation

f-l =

((5, a),

( t ,b ) , ( r , 4)

is a function from B into A . The diagram of

Observe t h a t the diagram of ing the arrows.

f-I

f-I

follows:

can be obtained from the diagram of

f

by revers-

For any set A , the function f :A + A defined by f(x) = x, i.e. which assigns to each element in A itself, is called the i d e n t i t y function on A and is usually denoted by 1, or simply 1. Note that the identity function 1, is the same as the diagonal relation: 1, = A,. The identity function satisfies the follo~vingproperties: Theorem 8.1:

For any function f : A

-+

B,

Theorem 8.2: If f : A + B is both one-one and onto, and so has a n inverse function f -':B + A, then f-'of=l, and f o f P 1 = l g The converse of the previous theorem is also true: Theorem 8.3:

Let f : A

+

B and g : B

-+

A satisfy

g o f = 1,

and

f o g = 1,

Then f is both one-one and onto, and g = f - ' .