Relations Question

Printable View

December 4th 2009, 08:38 AM
dre

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
December 4th 2009, 09:05 AM
Plato

Quote:

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?
December 5th 2009, 07:46 AM
oldguynewstudent

Quote:

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
December 5th 2009, 08:08 AM
Plato

Quote:

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$
December 5th 2009, 09:07 AM
oldguynewstudent

I think I get it now

Quote:

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! (Pizza)