1. ## Relations Question

Let A be the set {a, b, c, d, e, 1, 2, 3, 4, 5, x, y, z, w}

How many different reflexive relations are there and how many different symmetric relations are there? I know the total would be 2^196 because of the power set rule but how can I figure out how many reflexive and symmetric relations there are?

2. Originally Posted by dre
Let A be the set {a, b, c, d, e, 1, 2, 3, 4, 5, x, y, z, w}
How many different reflexive relations are there and how many different symmetric relations are there?
The set of pairs $\Delta _A = \left\{ {\left( {\alpha ,\alpha } \right):\alpha \in A} \right\}$ is known a the diagonal from the table of ordered pairs.
There are $14^2$ pairs in that table so $\left| {\Delta _A } \right| = 14$
Therefore there are $14^2-14$ off diagonal pairs.
Any reflexive relation on $A$ must contain ${\Delta _A }$.
So any reflexive relation is the union of ${\Delta _A }$ with any subset of off diagonal pairs.
How many of those are there?

Any symmetric relation on $A$, $\mathcal{S}$, has the property that $\mathcal{S}=\mathcal{S}^{-1}$.
There are $\frac{(14)(15)}{2}$ pairs either on the diagonal or above it.
Any subset of those pairs corresponds to a symmetric relation.
Just take that subset and unite it with its inverse.
How many are there?

3. Originally Posted by Plato
The set of pairs $\Delta _A = \left\{ {\left( {\alpha ,\alpha } \right):\alpha \in A} \right\}$ is known a the diagonal from the table of ordered pairs.
There are $14^2$ pairs in that table so $\left| {\Delta _A } \right| = 14$
Therefore there are $14^2-14$ off diagonal pairs.
Any reflexive relation on $A$ must contain ${\Delta _A }$.
So any reflexive relation is the union of ${\Delta _A }$ with any subset of off diagonal pairs.
How many of those are there?

Any symmetric relation on $A$, $\mathcal{S}$, has the property that $\mathcal{S}=\mathcal{S}^{-1}$.
There are $\frac{(14)(15)}{2}$ pairs either on the diagonal or above it.
Any subset of those pairs corresponds to a symmetric relation.
Just take that subset and unite it with its inverse.
How many are there?
Thank you for this explanation, but I am still confused about something in ROSEN: I understand that the number of subsets from A with n elements is $2^n$, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total $n^2$ - n. But I don't see why the number of reflexive relations equal $2^q$ where q = $n^2$ - n ? Why isn't the number of reflexive relations just equal to $2^r$ where r = $n^2$?

Thanks

4. Originally Posted by oldguynewstudent
Thank you for this explanation, but I am still confused about something in ROSEN: I understand that the number of subsets from A with n elements is $2^n$, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total $n^2$ - n. But I don't see why the number of reflexive relations equal $2^q$ where q = $n^2$ - n ? Why isn't the number of reflexive relations just equal to $2^r$ where r = $n^2$?
If you will give me the exact reference in Rosen's book I will look at it.

As for your other concern, if $|A|=n$ then how many subsets of $A\times A$ contain $\Delta_A$?

Do you understand that $\left|(A\times A)\setminus \Delta_A\right|=n^2-n?$

How many subsets of $A\times A\setminus \Delta_A$ are there?

Uniting any of those with $\Delta_A$ we get a reflexive relation on $A$

5. ## I think I get it now

Originally Posted by Plato
If you will give me the exact reference in Rosen's book I will look at it.

As for your other concern, if $|A|=n$ then how many subsets of $A\times A$ contain $\Delta_A$?

Do you understand that $\left|(A\times A)\setminus \Delta_A\right|=n^2-n?$

How many subsets of $A\times A\setminus \Delta_A$ are there?

Uniting any of those with $\Delta_A$ we get a reflexive relation on $A$
Thanks for your patience. We skipped the combinatorics chapters. The reference is on p 525 6th edition, example 16. So because there are n members in the diagonal we have by the product rule these n combined with the n - 1 other (rows or columns in the matrix) to give n(n - 1) ways to combine. Then we raise 2 to that power to get the number of relations.

I still have to think it over further to solidify the concept. But at least now I can follow the reasoning.

Happy Holidays!