Finding all reflexive binary relations of a set

Question

Let A = $\{1,2,3\}$. What is the total number of reflexive binary relations on $P(A)$?

What I've tried to do is: Let $R$ a relation on $P(A)$. For it to be reflexive, the following must be true: $$\forall a \in A , (a,a) \in R$$

There are ${{2^{2}}^3}^2$ total possible relations on $P(A)$. I just can't seem to understand what do I need to subtract from that value to get the answer.

Answer 1

The general answer for the number of reflexive binary relations on any finite set $X$ is as follows. Consider every relation as turning on/off squares in a grid of size $|X| \times |X|$.

In every such relation, we must have $(x, x)$ set to "on" (or "true", or $1$, or whatever you like to represent that it's in the relation).

So, we only have $|X|^2 - |X|$ choices to turn on or off.

So, the answer is:

$$2^{|X|^2 - |X|}$$

Now, in your case, $X$ is the powerset of $A$, i.e. $P(A)$, and the powerset size is always given by

$$|P(A)| = 2^{|A|}= 2^3 = 8$$

So you just plug it in to the above formula for your result, i.e.

$$2^{|P(A)|^2 - |P(A)|} = 2^{|P(A)|(|P(A)| - 1)} = 2^{(2^3)(2^3 - 1)} \\ = 2^{8(8-1)} = 2^{56}$$

---

Visually, you can see that the $|X|^2 - |X| = |X|(|X| - 1)$ term makes sense from the following grid. Imagine shifting the bottom-right triangle of grid cells upwards to make a rectangle of size $|X|(|X| - 1)$.

What does this grid represent? Well, this particular one is a starting point for representing any reflexive binary relation on a set with $7$ elements. But the same approach can be used to represent any binary relation on a finite set. As it stands, this is the identity relation, mapping all elements to themselves only. A red square at position $(x, y)$ denotes that $x$ is related to $y$. Starting from the identity relation, we can build any relation whatsoever by colouring $0$ or more of the remaining white squares in red. How many ways are there to do this? Well, there are $2$ choices, red and white, so combinatorics would tell us that there are $2^s$ ways to do this, where $s$ is the number of white squares remaining.

Answer 2

We have $P(A) = \big\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}$. So $P(A) \times P(A)$ has $8 \cdot 8 = 64$ elements. In these $64$ elements, as in your definition for reflexivity, $8$ of them must be in our reflexive relation, namely $$\big\{\{\},\{\}\big\},\big\{\{1\},\{1\}\big\}, \big\{\{2\},\{2\}\big\},\big\{\{3\},\{3\}\big\},\big\{\{1,2\},\{1,2\}\big\},\big\{\{1,3\},\{1,3\}\big\}, \big\{\{2,3\},\{2,3\}\big\},\big\{\{1,2,3\},\{1,2,3\}\big\}$$

For other $64-8 = 56$ elements of $P(A)\times P(A)$, there are two options for each element (either in the relation set or not) so in total, we have $2^{56}$ reflexive relations on $P(A)$.