Relations proof

1. Dec 15, 2013

MrWarlock616

1. The problem statement, all variables and given/known data
Show that if a set has 3 elements, then we can find 8 relations on A that all have the same symmetric closure.

2. Relevant equations

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

3. 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.

Last edited: Dec 15, 2013
2. Dec 15, 2013

Dick

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.

Last edited: Dec 15, 2013
3. Dec 15, 2013

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.