How can a set with only two elements have 8 symmetric relations?

Question

In the question thread "how many symmetric relations are there on a set with 5 elements", user MJD offers the following answer:

$$ \begin{array}{rclrrl} \text{A set with} & 0 & \text{elements has} & 2^{(0^2+0)/2} = & 1 & \text{symmetric relation}\\ \text{A set with} & 1 & \text{element has} & 2^{(1^2+1)/2} = & 2 & \text{symmetric relations}\\ \text{A set with} & 2 & \text{elements has} & 2^{(2^2+2)/2} = & 8 & \text{symmetric relations}\\ \text{A set with} & 3 & \text{elements has} & 2^{(3^2+3)/2} = & 64 & \text{symmetric relations}\\ \end{array} $$

What I'm wondering is, could you show me the symmetric relations for the sets with 0, 1, and 2 elements?

I get that $\text{R={(1,1),(2,1),(1,2),(2,2)}}$ is symmetric, as $\text{R(a,b) = R(b,a)}$ what I don't get is how a set with zero elements can have 1 symmetric relation, and a set with 1 have 2? Here is my guess: $$\text{Set with 0 elements: } \text{{∅} = 1 relation}$$ $$\text{Set with 1 element: } \text{{∅,(1,1)} = 2 relations}$$ $$\text{Set with 2 elements: } \text{{∅,(1,1),(1,2),(2,1)(2,2)} $\ne$ 8 relations }$$

Am I misunderstanding the concept of relations here? Help is much appreciated.

Answer 1

A relation is not a pair, but a set of pairs.

In particular:

• Set with 0 elements: 1 relation

  1. $\emptyset$

• Set with 1 elements: 2 relations

  1. $R_0 = \emptyset$
  2. $R_1 = \{(1,1)\}$ (note: not $(1,1)$)

• Set with 2 elements: 8 relations

  1. $R_0 = \emptyset$
  2. $R_1 = \{(1,1)\}$
  3. $R_2 = \{(2,2)\}$
  4. $R_3 = R_1\cup R_2 = \{(1,1), (2,2)\}$
  5. $R_4 = \{(1,2),(2,1)\}$
  6. $R_5 = R_1\cup R_4 = \{(1,1), (1,2), (2,1)\}$
  7. $R_6 = R_2\cup R_4 = \{(1,2), (2,1), (2,2)\}$
  8. $R_7 = R_1\cup R_2\cup R_4 = \{(1,1), (1,2), (2,1), (2,2)\}$

  Note that there are $3=\frac{2\cdot 3}{2}$ minimal non-empty symmetric relations that are pairwise disjoint (namely $R_1$, $R_2$ and $R_4$), and all other are unions of sets of those "elementary" symmetric relations.

Note that this principle holds for any size: There is a set of minimal non-empty symmetric relations, which are all of the form $\{(a,b),(b,a)\}$ (note that for $a=b$ this is just the set $\{(a,a)\}$). For $n$-element sets, there are $N={n\choose 2}=\frac{n(n+1)}{2}$ such "basic" relations.

Each basic relation may or may not be a subset of a symmetric relation, therefore if there are $N$ such basic relations, there are $2^N$ symmetric relations in total. Therefore the total number of symmetric relations is $2^{n(n+1)/2} = 2^{(n^2+n)/2}$.

Answer 2

You're working one level down from the question. A relation is a description across the whole set of which elements are related. The possible symmetric relations for $\{A,B\}$ are:

$ \{\} \\ \{(A,A)\} \\ \{(B,B)\} \\ \{(A,A),(B,B)\} \\ \{(A,B), (B,A)\} \\ \{(A,A),(A,B), (B,A)\} \\ \{(A,B), (B,A),(B,B)\} \\ \{(A,A),(A,B), (B,A),(B,B)\} \\ $

characterized by whether or not to include or exclude the reflexives $(A,A)$ , $(B,B)$ and the symmetric pair $(A,B)$ and $(B,A)$

Answer 3

A relation on an set $X$ is a collection of ordered pairs $R \subset X \times X$. A symmetric relation is one that satisfies $(x,y) \in R \implies (y,x)\in R$.

If $X = \{1,2\}$ there are four ordered pairs in $X\times X$ namely $(1,1),(1,2),(2,1),$ and $(2,2)$. So the total number of relations is $2^4 = 16$ since for each ordered pair we can independently choose whether to include it or not.

However for a symmetric relation if we put $(1,2)$ in $R$ we must also put in $(2,1)$ and vice-versa. So now we get $2^3=8$ symmetric relations corresponding to the independent choices of whether or not to include $(1,1)$, whether or not to include $(2,2)$, and whether or not to include both $(1,2)$ and $(2,1).$