# 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?

• 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)
All times are GMT -8. The time now is 04:16 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 48, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9396694898605347, "perplexity_flag": "head"}