Thread: 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?

Please help

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 $\displaystyle \Delta _A = \left\{ {\left( {\alpha ,\alpha } \right):\alpha \in A} \right\}$ is known a the diagonal from the table of ordered pairs.
There are $\displaystyle 14^2$ pairs in that table so $\displaystyle \left| {\Delta _A } \right| = 14$
Therefore there are $\displaystyle 14^2-14$ off diagonal pairs.
Any reflexive relation on $\displaystyle A$ must contain $\displaystyle {\Delta _A }$.
So any reflexive relation is the union of $\displaystyle {\Delta _A }$ with any subset of off diagonal pairs.
How many of those are there?

Any symmetric relation on $\displaystyle A$, $\displaystyle \mathcal{S}$, has the property that $\displaystyle \mathcal{S}=\mathcal{S}^{-1}$.
There are $\displaystyle \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?

Originally Posted by Plato

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

Any symmetric relation on $\displaystyle A$, $\displaystyle \mathcal{S}$, has the property that $\displaystyle \mathcal{S}=\mathcal{S}^{-1}$.
There are $\displaystyle \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 $\displaystyle 2^n$, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total $\displaystyle n^2$ - n. But I don't see why the number of reflexive relations equal $\displaystyle 2^q$ where q = $\displaystyle n^2$ - n ? Why isn't the number of reflexive relations just equal to $\displaystyle 2^r$ where r = $\displaystyle n^2$?

Thanks

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 $\displaystyle 2^n$, I can see that the diagonal of the cartesian product will contain n elements and that all other elements will total $\displaystyle n^2$ - n. But I don't see why the number of reflexive relations equal $\displaystyle 2^q$ where q = $\displaystyle n^2$ - n ? Why isn't the number of reflexive relations just equal to $\displaystyle 2^r$ where r = $\displaystyle 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 $\displaystyle |A|=n$ then how many subsets of $\displaystyle A\times A$ contain $\displaystyle \Delta_A$?

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

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

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

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 $\displaystyle |A|=n$ then how many subsets of $\displaystyle A\times A$ contain $\displaystyle \Delta_A$?

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

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

Uniting any of those with $\displaystyle \Delta_A$ we get a reflexive relation on $\displaystyle 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!