How many relations are there on a how many reflexive

Question

Problem

1. Suppose A is a set having n elements.

a. How many relations are there on A?

b. How many reflexive relations are there on A?

c. How many symmetric relations are there on A?

d. How many relations are there on A that are both reflexive and symmetric?

2. Suppose R is a relation on a nonempty set A.

a. Define R' = R ∪ {(x, y) | yRx}. Show that Rs is symmetric and is the smallest symmetric relation on A containing R (i.e., for any symmetric relation R₁ with R ⊆ R₁, R' ⊆ R₁.

b. Define Rt to be the intersection of all transitive relations on A containing R. Show that Rt is transitive and is the smallest transitive relation on A containing R

c. Let equal to the set Rt in part R'' = R ∪ {(x, y) | ∃z (xRz and zRy} equal to the aet Rt in part

(b)? Either prove that it is, or give an example in which it is not. The relations Rs and Rt are called the symmetric closure and transitive closure of R, respectively.