How many relations can be defined the this power set

Question

Let $A=\{1,2,3\}$

What is the number of reflexive relations the can be defined on $P(A)$?

I first thought the number is 3, but it seems I'm wrong.

How can someone solve this problem?

Thanks

Answer 1

$$P(A) = \{\emptyset,1,2,3,\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$$ Now, a relation $R$ on a set $X$ is reflexive if for all $x \in X$, we have that $(x,x) \in R$. This means that any reflexive relation on $P(A)$ must at least contain the pairs $$(\emptyset,\emptyset),(1,1),(2,2),(3,3),(\{1,2\},\{1,2\}),(\{2,3\},\{2,3\}),(\{1,3\},\{1,3\}),(\{1,2,3\},\{1,2,3\}).$$ How many subsets of $P(A) \times P(A)$ exist that contain these pairs?

Answer 2

To extend mrp's answer: $|\mathcal P (A)\times\mathcal P (A)|=2^{2^3}=256.$ We take the $8$ pairs we are interested in, and put them into a bag. This bag is a relation. Now, we can add any other element of $\mathcal P (A) \times \mathcal P (A)$ and add it to our bag to create a new relation. This can be achieved in

$$\sum\limits_{i=0}^{256-8}\binom{256-8}{i}\tag{1}$$

ways. This is: the ways we can pick $i$ elements from the $256-8$ elements that are not the $8$ pairs we are interested in. This number of ways is the number of relations. So $(1)$ yields:

$$\sum\limits_{i=0}^{256-8}\binom{256-8}{i}1^i1^{256-8-i}=(1+1)^{256-8}.$$