# Thread: Determining number of relations on a set

1. ## 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.

2. 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?

3. O

4. 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.

5. What it mean to be reflexive?
Is $\Delta_A$ itself a reflexive relation on A?

6. 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$.

7. 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.

8. 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?

9. 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.

10. I have to be ready, these are mock questions for mods exams :S
But thanks a lot, I get it now

,
,

,

,

,

,

,

,

,

,

,

# how many relations are there on a set with n elements

Click on a term to search for related topics.