# Relations and sets

1) Find a relation R on a set S that is neither Symmetric nor antisymmetric

2) Let S be a set containing exactly n elements. How many antisymmetric relations on S are there.

3) give a recursive definition of X^n for any positive integer n

4) give a recursive definition of the nth odd positive integer

5) Let g: Z -> Z be defined by g(x)= ax + b, where Z denotes the set of integers and a,b E Z with a not equal 0

a) prove that g is one-to-one

b) what must be true about a and b if g is onto?

6) let S be a set of people. For x, y E S, define xRy to mean that x = y or x is a decendant of y. Prove that R is a partial order on S

#### Solution Preview

1) Find a relation R on a set S that is neither Symmetric nor antisymmetric

Let S = {a,b,c}, the relation on S is defined as R = {(a,b), (b,a), (a,c)}

Then R is not symmetric because (a,c) is in R but (c,a) is not in R.

R is not antisymmetric because (a,b) and (b,a) are in R but a is not equal to b.

2) Let S be a set containing exactly n elements. How many antisymmetric relations on S are there.

Suppose R is an antisymmetric relation on S, for a,b in S and a is not equal to b, if (a,b) is in R, then (b,a) is not in R.

Because if (b,a) is in R, by antisymmetry, we have a = b. That is not true.

Let X = {(a,b) | a, b are in S}. Any relation R is a subset in X. S has n elements, then X has n^2 elements.

Assume S = {a_1, a_2, ..., a_n}, let X_ij = {(a_i, a_j), (a_j, a_i)}, i<j.

Let X_0 = X_11 U X_22 U ... U X_nn, then X_0 has n elements. Each X_ij (i<j) has 2 elements.

So X = X_0 U X_12 U ... U X_1n U X_23 U X_24 U ... U X_2n U ... U X_(n-1)n

There ...

#### Solution Summary

This shows how to find relations for given characteristics, and complete proofs regarding sets.