For this problem set we define A = {a₁, a₂, , a_n} to be a set of n elements. A relation R over A is a subset of A A.

Relations can be represented in a variety of ways. One method that is conceptually convenient is to represent a relation as a boolean matrix. As an example, when n= 4 we have the following:

R= {(a₁,a₂ ), (a₁,a₃ ), (a₂,a₁ ), (a₂,a₂ ), (a₃,a₄ ), (a₄,a₁)}

M= 0 1 1 0

1 1 0 0

0 0 0 1

1 0 0 0

Here, the entry in the i^th row and j^th column of the matrix, M_ij, is 1 iff the ordered pair (a_i,a_j ) R , and is 0 otherwise. Note that this defines a bijection between the set of relations on A and the set of nn matrices with 0/1 entries.

Problem 1. What is the number of distinct relations over the n-element set A ?

Problem 2. A relation R over A is reflexive if, for every a_i A the ordered pair (a_i, a_i) R. What is the value of every diagonal entry M_ii in the matrix corresponding to R?

Problem 3. What is the number of reflexive relations over the n-element set A?

Problem 4. A relation R over A is symmetric if, for every ordered pair (a_i, a_j) R the ordered pair (a_j, a_i) R. What is the number of symmetric relations over the n-element set A?

Problem 5. How many relations over A are both reflexive and symmetric?

Problem 6. A relation R over A is transitive if, for every i,j,k: (a_i, a_j) R and (a_j, a_k) R implies that (a_i, a_k) R. Is the relation in the example above transitive?