6

Why is the formula for finding the total number of binary relations in a set A equal to $2^{A^2}$ ?

I have looked on the web (including here) and find the answer is because the relation can be in or out. This is the exact thing my professor told me but did not explain meaning in or out. I asked what that and he looked at me like I was stupid and did not explain further.

My understanding is if the set is in you have for example

A = {a,b} so a relation could be (a,a) which would be in

But what if the relation is out would that not be the empty set?

So for an example I had A is a set of 2 elements. So that would mean the number of binary relations would be $2^4$ which is 16 but this is what I got -only 14 elements.

(a), (b), (a,b), (a,a), (b,b), (a,b,a), (a,b,b), (b,b,b), (a,a,a,), (b,a,b,b), (b,a,b,a), (b,a,a,a), (b,b,b,b), (a,a,a,a)

What are the only two elements? Is the empty set a part of this? What does it mean to be in or out?

Andrés E. Caicedo
  • 79,201
Jinzu
  • 819

1 Answers1

11

A binary relation $R$ on a set $A$ looks like a bunch of statements of the form $a\ R\ b$ for $a, b \in A$.

So for each pair $(a,b)$ you have two choices: does $a\ R\ b$ or not?

Supposing $A$ has size $n$, there are $n^2$ possible pairs $(a,b)$, and for each of these pairs you have two choices of whether or not they appear in your relation. So the number of possible relations is $$\underbrace{2 \times 2 \times \cdots \times 2}_{\text{one for each of the}\ n^2\ \text{pairs}} = 2^{n^2}$$

Comment: In your list:

(a), (b), (a,b), (a,a), (b,b), (a,b,a), (a,b,b), (b,b,b), (a,a,a,), (b,a,b,b), (b,a,b,a), (b,a,a,a), (b,b,b,b), (a,a,a,a)

I'm not sure what these are meant to represent... they're certainly not binary relations.

Clive Newstead
  • 64,925
  • The list represents the subset I could make from a two element set such as A X A where A = {a,b}. So for understanding, if the element is out then why is it still counted? Does that not mean the element is out of the set? – Jinzu Nov 24 '13 at 15:59
  • 1
    @Jinzu: They're not subsets either. For instance, as sets, ${a,b,a}={a,b}$. What you have there is an (incomplete) list of sequences of length $\le 4$, which don't have much to do with what you're trying to find. Relations, on the other hand, are sets of pairs of elements. I've re-worded my answer to make it clearer; take another look. – Clive Newstead Nov 24 '13 at 16:01
  • Ok your answer is becoming clearer. But would explain why the set is still counted if it is out? – Jinzu Nov 24 '13 at 16:07
  • $(a,b)$ being in means in the set, being out means not being in the set. If it is in, we have $a R b$. If it is out, we have $\lnot a R b$. That is how the set is defining the relation. – Ross Millikan Nov 24 '13 at 16:10
  • @RossMillikan thanks I understand now. – Jinzu Nov 24 '13 at 16:11