# Determining number of relations on a set

• December 8th 2010, 09:30 AM
worc3247
Determining number of relations on a set
Let A = {1,2,...,n}.
(a) How many relations are there on the set A?
(b) How many reflexive relations are there on the set A?
(c) How many symmetric relations are there on the set A?
(d) How many relations are there on the set A which are both reflexive and symmetric?

I think that the answer to (a) is $n^2$ because it will be ther number of ordered pairs, but this is just a guess.
If someone could point me in the right direction.
• December 8th 2010, 09:48 AM
Plato
Quote:

Originally Posted by worc3247
Let A = {1,2,...,n}.
(a) How many relations are there on the set A?
(b) How many reflexive relations are there on the set A?
(c) How many symmetric relations are there on the set A?
(d) How many relations are there on the set A which are both reflexive and symmetric?

A relation is any set of ordered pairs, (some say any non-empty set) so the answer to part (a) is $2^{n^2}(\text{ or }2^{n^2}-1)$.

$\Delta_A=\{(1,1),(2,2),\cdots,(n,n)\}$ A relation is reflexive if and only if $\Delta_A$ is a subset of the relation. SO?

How many pairs are on the diagonal or above it?
2 to that power answers (c). WHY?
• December 8th 2010, 09:59 AM
worc3247
O
• December 8th 2010, 09:59 AM
worc3247
Ok so now I am getting answers of $2^{n^2-n}$ and $2^{(n^2-n)/2}$ for (b) and (c) respectively. But what I don't understand is why a relation is reflexive only if $\Delta_A$ is a subset of the relation.
• December 8th 2010, 10:03 AM
Plato
What it mean to be reflexive?
Is $\Delta_A$ itself a reflexive relation on A?
• December 8th 2010, 10:12 AM
worc3247
Reflexive is when sRs (R is the relation) $\forall s \epsilon S$. So yes, $\Delta_A$will be an equivalence relation. But then surely the answer to (b) would be $2^n$ because there are n elements in $\Delta_A$.
• December 8th 2010, 10:17 AM
Plato
Quote:

Originally Posted by worc3247
But then surely the answer to (b) would be $2^n$ because there are n elements in $\Delta_A$.

How many subsets of $(A\times A)\setminus \Delta_A$ are there?
Unite each of those with $\Delta_A$ to get a reflexive relation.
• December 8th 2010, 10:28 AM
worc3247
Quote:

Originally Posted by Plato
How many subsets of $(A\times A)\setminus \Delta_A$ are there?

$n^2 - n$. So the answer is $2^{n^2-n}$?

So a symmetric relation is when: if sRt, tRs for $s,t \epsilon S$.
But how are you suppose to determine what is a symmetric relation without knowing what the relation is?
• December 8th 2010, 10:37 AM
Plato
Quote:

Originally Posted by worc3247
$n^2 - n$. So the answer is $2^{n^2-n}$? So a symmetric relation is when: if sRt, tRs for $s,t \epsilon S$.
But how are you suppose to determine what is a symmetric relation without knowing what the relation is?

Are you sure that you are ready to do these?
A relation $\mathcal{S}$ is symmetric if and only if $\mathcal{S}=\mathcal{S}^{-1}$.
Any subset of pairs from the diagonal or above is a relation. Unite that subset with its inverse. Then we have a symmetric relation.
• December 8th 2010, 10:42 AM
worc3247
I have to be ready, these are mock questions for mods exams :S
But thanks a lot, I get it now :)