Finding 8 Relations on a Set of 3 Elements with the Same Symmetric Closure

[MrWarlock616]

Homework Statement

Show that if a set has 3 elements, then we can find 8 relations on A that all have the same symmetric closure.

Homework Equations

Symmetric closure $R^* = R \cup R^{-1}$

The Attempt at a Solution

If the symmetric closures of n relations are the same then we have,

$R_1 \cup R_1^{-1} = R_2 \cup R_2^{-1} = ... = R_n \cup R_n^{-1}$

I have to prove n=8 for |A| = 3

Also, $R_1$, $R_2$,...,$R_n$ can't be symmetric. A friend told me to use power sets but I don't see how that applies here.

Do I have to write down all possible relations that can occur from A={a,b,c} or is there a better way to prove this one?

Any help would be appreciated.

 

[Dick]

Homework Statement

Show that if a set has 3 relations, then we can find 8 relations on A that all have the same symmetric closure.

Homework Equations

Symmetric closure $R^* = R \cup R^{-1}$

The Attempt at a Solution

If the symmetric closures of n relations are the same then we have,

$R_1 \cup R_1^{-1} = R_2 \cup R_2^{-1} = ... = R_n \cup R_n^{-1}$

I have to prove n=8 for |A| = 3

Also, $R_1$, $R_2$,...,$R_n$ can't be symmetric. A friend told me to use power sets but I don't see how that applies here.

Do I have to write down all possible relations that can occur from A={a,b,c} or is there a better way to prove this one?

Any help would be appreciated.

I would imagine a symmetric relation on A and then try to picture how you could delete elements of the relation to get the 8 different $R_i$. Suppose the relation you start with is the one where all of the elements of A are related to each other? That gives you lots of options. I think you can find more than 8.

 

[MrWarlock616]

Sorry I wrote 3 relations instead of 3 elements in the question.

This problem has appeared twice in previous years exams. My gut tells me to use permutation and combinations but I've forgot most of it.