Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it 16 (2^4)?

I completely forgot how to calculate the number of relations on a given set.

share|improve this question
1  
How do $a$ and $b$ relate to $16$, $2$, and $4$? This question needs a lot of editing before anyone can understand what you are talking about. –  Gerry Myerson Nov 23 '12 at 2:42
    
@GerryMyerson I just read the words "set", "$16$" and "$2^4$" and concluded that the OP had some issue with counting the number of functions from a $4$ element set to a $2$ element set. Anyway I have now deleted my answer since I didn't read the question properly. –  user17762 Nov 23 '12 at 2:49
add comment

2 Answers

up vote 5 down vote accepted

If you mean $S = \{a, b\}$, a set with $2$ elements, then a relation is simply an element of the powerset of $S^2$. So your answer is correct.

share|improve this answer
4  
Good job of mind-reading. –  Gerry Myerson Nov 23 '12 at 2:45
    
Haha thank you. –  beauby Nov 23 '12 at 2:45
add comment

Suppose $X$ is a set of $n$ elements. Then for any ordered pair $(x,y)$ of elements of $X$, we can say Yes or No to the question of whether $(x,y)$ is in the (binary) relation on $X$. There are $2^{n^2}$ ways to make the choices, and therefore $2^{n^2}$ binary relations on $X$.

If $X$ is the $2$-element set $\{a,b\}$, the number of relations on $X$ is therefore $2^{(2^2)}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.