Four people Alan Bob Clara and Diana are to sit around a cir

Four people, Alan, Bob, Clara and Diana, are to sit around a circular table on four chairs that are numbered 1 to 4. Identifying the people by the first letter of their first name, a seating plan can be described as follows.

1 2 3 4

C A B D

The above seating plan means that Clara occupies Chair number 1, Alan occupies Chair number 2, Bob occupies Chair number 3 and Diana occupies Chair number 4. A more concise way is to write CABD, where the chairs are implicitly numbered from left to right.

Definition 1. Let S = {A, B, C, D}. The set P of possible seating plans is defined as follows.

P = {(X, Y, Z, T) S × S × S × S | X Y X Z X T Y Z Y T Z T}

You may notice that there are 24 elements in P.

Let us consider the relation R between seating plans such that a seating plan is in relation with another seating plan obtained by moving everyone one seat to the right.

Definition 2. The relation R on P is defined as follows.

(X, Y, Z, T) P ((X, Y, Z, T) R (T, X, Y, Z))

The purpose of the next three questions is to study a new relation S that we define as follows.

Definition 3. The relation S on P is the transitive closure of R.

(a) Give an intuitive description in English of the relation S.

(b) We claim that S is an equivalence relation. How many distinct equivalence classes are there for S? Give a representative (i.e. any member) of each class.

(c) (Prove that S is an equivalence relation.

Solution

(A)

we know that S is not relation

P , R are relation defined on set S

The relation P on set S is the set of all permutation on set S

It will be set of all permutations with four letters {A,B,C,D}

so, total number of permutation in this would be 4! =4*3*2*1=24...........Answer

(B)

Assume R is an equivalence relation on set S

R is not an equivalence relation on P

hence , equivalnce relation or classes can not be formed

Example: (ABCD) R (DABC)

(DABC) R (CDAB) R (BCDA) R (ABCD)

so,

class1 = class([ABCD])

class2=class([ABCD]) ={(ABCD) , (CABD) , (DCAB) , (BDCA) }

class3 = class([ACBD]) ={(ACBD) , (BACD) , (DBAC) , (CDBA)}

class4=clas[(ACDB)]={((ACDB), (BACD), (DABC) , (DBAC) , (CDBA)}

class5=class[(ADBC)]={(ADBC) , (CADB) , (BCAD) , (DBCA) }

class6=class[(ADCB)]={(ADCB), (BADC) , (CBAD) , (DCBA)}

We can see that there are six equivalence classes and each classes are disjoint .......Answer

(C)

we can see that

Reflexive relation

(ABCD) R (ABCD) for all (ABCD) in P

we know that after four i moving position right

operation will return to the starting position.

that\'s why , R is reflexive

Symmetric:

(ABCD) R (A\'B\'C\'D\')

It means that (A\'B\'C\'D\') R (ABCD) too, for all (ABCD) in P

that\'s why R is symmetric

Transitive:

(ABCD) R (A\'B\'C\'D\'), (A\'B\'C\'D\') R (A\'\'B\'\'C\'\'D\'\')

It means that (ABCD) R (A\'\'B\'\'C\'\'D\'\'), for all (ABCD) in P

that\'s why R is transitive

Therefore , R is an equivalence relation...........Answer