These 2 questions come from my homework for Discrete Structu

These 2 questions come from my homework for Discrete Structures and i have no idea how to do either of them. If someone could please help me with these I would very much appreciate it!

1) How many different relations are there on a set with n elements if:

a) n = 1

b) n = 2

c) n = 3

a) How many unique relations are there on A (in terms of n)?

b) the complement relation is defined as

c) How many reflexive relations are there on a set size n? Briefly justify your answer.

d) How many symmetric relations are there on a set of size n? Briefly justify your answer.

Solution

1)

a) A set with 1 element has 2 ( 1 2 + 1 ) / 2 = 2 symmetric relations

b) A set with 2 elements has 2 ( 2 2 + 2 ) / 2 = 8 symmetric relations

c) A set with 3 elements has 2 ( 3 2 + 3 ) / 2 = 64 symmetric relations.

2) a) Let R be the set with n elements. Then RxR has n^2 elements in it, and the relations on R correspond exactly to the subsets of RxR, giving us 2^(n^2) relations in general.

c) Let us first understand how to count the total number of relations on a set A containing n elements. A relation is simply a subset of the cartesian product A×A.

If A={a1,a2,....,an}, then
                A×A={(a1,a1),(a1,a2),....,(a1,an),
                                   (a2,a1),(a2,a2),....,(a2,an),
                                   ....
                                   (an,a1),(an,a2,)....,(an,an)}

Clearly, this set of ordered pairs contains n² such pairs. We can construct an arbitrary subset of this set in 2^{n^2}ways. This will be the total number of possible relations on A.

Now, we want to count the number of reflexive relations. Recall that a relation R on A is reflexive if (x,x)R, xA. So we have to construct subsets of A×A such that they must include all n diagonal pairs in the above cartesian product. But you have a choice as to whether or not to include all the remaining n²n ordered pairs. Since there are two choices for each of those (include/exclude), it gives us a total of 2^{n^2}n reflexive relations on A.

d) For symmetric, for every nn there are nn options, multiply all of them and remove all the duplicates we\'ll get n²n.

Symmetric relations: you have to decide if the members of the couple (x,y)(x,y) are in relation. There are (n/2)+n such couples, up to order. So there are 2^n/2+n symmetric relations.