Homework # 15

Due November 9, 2005

Name ___________________

ℕ = set of all nonnegative integers (note that 0 ∈ ℕ)

ℤ= set of all integers

ℚ= set of all rational numbers

ℝ= set of all real numbers

ℂ= set of all complex numbers

1. S = {a,b,c} What is the Cartesian product of the set S with itself? (i.e. what is S X S?)

SXS = { (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a) , (c,b), (c,c)}

2. For each of the following binary relations R on ℕ decide which of the given ordered pairs belong to R.

a. x R y ↔x = y + 1: (2,2), (2,3), (3,3), (3,2)

R = { (3,2) }

b. x R y ↔x divides y; (2,4), (2,5), (2,6)

R = { (2,4), (2,6)}

c. x R y ↔x is odd; (2,3), (3,4), (4,5), (5,6)

R = { (3,4), (5,6)}

3. Let S = { 1,2,3}

a. If a relation R on S is reflexive, what ordered pairs must belong to R?

R = { (1,1), (2,2), (3,3) }

b. If a relation R on S is symmetric and if (a,b) ∈R, then what other ordered pair must

belong to R?

R = { (b,a)}

c. If a relation R on S is antisymmetric and if (a,b) and (b,a) belong to R, what must be

true?

a = b

4. Let S = { 0,1,2,4,6} Test the following binary relations on S for reflexivity, symmetry, antisymmetry and transitivity. Tell why the relation R is not reflexive, symmetric, antisymmetric, or transitive if it isn't.

a. R = { (0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6) }

R is reflexive

R is not symmetric because (1,0) not in R

R is antisymmetric

R is not transitive because (6,4) not in R

b. R = { (0,1), (1,0), (2,4), (4,2), (4,6), (6,4) }

R is not reflexive because (1,1) is not in R

R is symmetric

R is not antisymmetric because (2,4) in R and (4,2) is in R and 2 /= 4

R is not transitive because (2,4) is in R, (4,2) is in R but (2,2) is not in R

5. Give an example of a binary relation R on set S = {1,2,3} that is neither reflexive nor irreflexive.

R2 = { (2,2) }

6. Give an example of a binary relation R on set S = {1,2,3} that is neither symmetric nor asymmetric.

R= {1,2), (2,1), (1,3)} on the set S = (1,2,3}