I have this problem:
You are given the set A = {a, b, c, d, e}. Find the number of relations R ⊆ A × A, which are 10pt simultaneously reflexive and symmetric.
and this is my solution:
We have set A = {a, b, c, d, e} and R ⊆ A × A (this is a Cartesian product)
1) First, we need to find the number of relations R1 ⊆ A × A that are reflexive: R1 = { (a,a); (b,b); (c,c); (d,d); (e,e) }
2) Next we find the number of relations R2 ⊆ A × A which are symmetric: R2 = { (a,b); (b,a); (a;c); (c,a); (a,d); (d,a); (a,e); (e,a); (b,c); (c,b); (b,d); (b,d); (b,e); (e,b); (c,d); (d,c); (c,e); (e,c); (d,e); (e,d) }
3) To find the number of relations R ⊆ A × A, which are simultaneously reflexive and symmetric, we have to check the union of R1 with R2: R1 U R2 = #R1 + #R2 = 5+ 20 = 25
As a conclusion, the number of relations R ⊆ A × A, which are simultaneously reflexive and symmetric, is 25.
Is this correct or not?
Thank you
It is not quite correct. A relation is not a pair of elements, but a set of pairs, so this is what I would do:
If the relation is reflexive, it must contain (a, a), (b, b), (c, c), (d, d) and (e, e).
If the relation is also symmetric, for any other elements $x, y\in A$ the following must hold: $$xRy\Leftrightarrow yRx$$
As there are $\binom{5}{2}=10$ pairs of disctint elements of $A$ and each pair may or may not be, there are $2^{10}$ ways to choose relations whithin them, and therefore the number of possible relations that are both reflexive and symmetric is $2^{10}=1024$.