1. ## Relations

Let A be the set with n elements. How many elements does the set of relations on A have? (How to calculate tihs?)

2. A relation R on A is a subset of the carthesian product of A with itself, that is: $R\subset A\times A$. How many elements does $\mathcal{P}(A\times A)$ have?

3. I am not sure you're right.

now I have to found all relation: I think that I have to do something like this

R_1={(a,b)} there are n*n different options
R_2={(a,b),(c,d)} I think there are (n*n)*((n-1)*n + (n-1)) = n^2*(n-1)*(n+1)
.
.
.

(this is something about combinatorics-I think so)

4. Originally Posted by tinaa
I am not sure you're right.
The first reply is absolutely correct.
As for you statement “We don't talk about sets but about ordered pairs” that is incorrect.
Almost all of basic ideas in mathematics are about sets.
An ordered pair is a set of sets.
A relation on a set is a subset of the cross product of the set with itself as was stated.

If we have a finite set $A$ then the number of relations on $A$ is $2^{|A|^2}$.

5. What you are basically doing is trying to find all $R\subset A\times A$.

you start out by looking for all $R_1\subset A\times A$ then $R_2 \subset A\times A$ etc...

So you're trying to find all elements of $\mathcal{P}(A\times A)$

$A\times A$ is the set of all ordered pairs $(a,b)$ wich has $n^2$ elements. Thus $\mathcal{P}(A\times A)$ has $2^{n^2}$ elements.

(edit: Sorry, I see Plato allready responded)

6. thank you