Homework #

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?)

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)

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

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

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

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

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

belong
to R?

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

true?

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) }

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

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

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