List the symmetric relations on the set {0,1}.

Question

I think the answer should be this, but not sure. Can anyone help me?

{ }, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0), (0,1)}, {(0,0), (1,0)}, 

{(0,1), (1,0)}, {(0,1), (1,1)}, {(1,0), (1,1)}, {(0,0), (0,1), (1,1)}, {(0,0), (1,0), (1,1)},

{(0,0), (0,1), (1,0), (1,1)}

Answer 1

Try to approach this in a systematic way. What is the possible size of a relation on a two-element set $S$? Well, it can't have more then $4$ elements, which is the relation $S\times S$. So, the possibilities are $0,1,2,3,4$. The case of $0$ elements gives just the empty relation, which is symmetric. The case of $1$ element entails looking at, e.g., $\{(0,0)\}$, which is symmetric, but also at $\{(0,1)\}$ which is not symmetric. The other two possibilities are very similar and you can probably suspect what you'll get already. Continue in this manner and you'll see the general pattern, and you'll make sure you did not miss any cases.

Answer 2

$\newcommand{\l}{\langle}\newcommand{\r}{\rangle}$I will list the relations that you wrote down that are not symmetric:

$$\begin{align*} &\{\l 0,1\r\}\\ &\{\l 0,0\r,\l 0,1\r\}\\ &\{\l 0,1\r,\l 1,1\r\}\\ &\{\l 0,0,\r,\l 0,1\r,\l 1,1\r\}\\ &\\ &\{\l 1,0\r\}\\ &\{\l 0,0\r,\l 1,0\r\}\\ &\{\l 1,0\r,\l 1,1\r\}\\ &\{\l 0,0,\r,\l 1,0\r,\l 1,1\r\}\\ \end{align*}$$

The first four fail to be symmetric because they include $\l 0,1\r$ but not the reversed pair $\l 1,0\r$; the last four fail to be symmetric because they include $\l 1,0\r$ but not the reversed pair $\l 0,1\r$. A symmetric relation must contain either both $\l x,y\r$ and $\l y,x\r$ or neither; it cannot contain just one of the two.

Your relations $\{\l 0,1\r,\l 1,0\r\}$ and $\{\l 0,0\r,\l 0,1\r,\l 1,0\r,\l 1,1\r\}$ are symmetric, because they contain both $\l 0,1\r$ and $\l 1,0\r$; the relations $\{\l 0,0\r,\l 0,1\r,\l 1,0\r\}$ and $\{\l 0,1\r,\l 1,0\r,\l 1,1\r\}$, which you omitted, are also symmetric, for the same reason. Note that symmetry doesn’t say anything about pairs like $\l x,x\r$: the reversed pair is identical, so if you have $\l x,x\r$, you automatically have its reversal $\l x,x\r$.

To build a symmetric relation on $\{0,1\}$, therefore, you need to decide three things:

• Will it include $\l 0,1\r$ and $\l 1,0\r$, or will it include neither of them?
• Will it include $\l 0,0\r$?
• Will it include $\l 1,1\r$?