Relations in set with 2 elements

Question

$$A = \{\{\sim\}, *\}$$

find 4 reflexive relations:

$$R_{1} = \{(\{\sim\}, \{\sim\})\}$$

$$R_{2} = \{(*, *)\}$$

$$R_{3} = \{(\{\sim\}, \{\sim\}), (*, *)\}$$

$$R_{4} = \{(\{\sim\}, \{\sim\}), (*, *), (\{\sim\}, *)\}$$

find 2 symmetric relations:

$$R_{1} = \{(\{\sim\}, *), (*, \{\sim\})\}$$

$$R_{2} = \{(*, *)\}$$

find 1 transitive relation:

$$R = \{(\{\sim\}, *), (*, \{\sim\}), (\{\sim\}, \{\sim\})\}$$

I'm not sure about that because of 2 elements in set $A$.

Answer 1

A reflexive relation over $\{\{\sim\},\ast\}$ must include at least both $\langle\{\sim\},\{\sim\}\rangle$ and $\langle\ast,\ast\rangle$ as elements.

Try again. Only $R_3$ and $R_4$ are reflexive.

---

You have two symmetric relations.

---

In a transitive relation, if $\langle\{\sim\},\ast\rangle$ and $\langle\ast,\{\sim\}\rangle$ are included, so to must $\langle\{\sim\},\{\sim\}\rangle$.

In a transitive relation, if $\langle\ast,\{\sim\}\rangle$ and $\langle\{\sim\},\ast\rangle$ are included ...

Answer 2

Big picture. A relationship on $A$ is any subset set of $P(A\times A)$.

Although this isn't asked for $|A\times A| = 2\times 2 = 4$ and $|P(A\times A)| = 2^4 =16$ so there are exactly $16$ possible relations.

1) Reflexive:

That means for every $a \in A$ then $(a,a) \in R$.

So $(\{\sim\},\{\sim\}), (*,*) \in R$ all other ordered pairs ($(\{\sim\},*)$ and $(*,\{\sim\})$) may or may not be.

There are $4$ options as to whether $(\{\sim\},*)$ are $(*,\{\sim\})$ in $R$ so there are $4$ reflexive relations.

They are

$\{(\{\sim\},\{\sim\}), (*,*)\}$

$\{(\{\sim\},\{\sim\}), (*,*),(\{\sim\},*)\}$

$\{(\{\sim\},\{\sim\}), (*,*),(*,\{\sim\})\}$

$\{(\{\sim\},\{\sim\}), (*,*),(\{\sim\},*)(*,\{\sim\})\}$

2) Symmetric.

Means if $(a,b)\in R$ then $(b,a)\in R$. So if $(*,\{\sim\})\in R$ then $(\{\sim\},*)$ must be also. But neither have to be. (Obviously if any $(a,a)\in R$ then.....$(a,a)\in R$ and we needn't worry about twin pairs.)

So of the pairs. $(*,*)$, $(\{\sim\},\{\sim\})$ and the "glued" pair of pairs $(*,\{\sim\})|(\{\sim\},*)$ each may or may not be in $R$ so there are $2^3 =8$ possible symmetric pairs.

They are:

$\emptyset$, $\{(*,*)\}$, $\{(\{\sim\},\{\sim\})\}$, $\{(*,*),(\{\sim\},\{\sim\})\}$ and

$\{(*,\{\sim\}),(\{\sim\},*)\},\{(*,\{\sim\}),(\{\sim\},*),(*,*)\}, \{(*,\{\sim\}),(\{\sim\},*),(\{\sim\},\{\sim\})\} ,\{(*,\{\sim\}),(\{\sim\},*), (*,*),(\{\sim\},\{\sim\})\}$

3) Transitive....

Okay... a different tack.

If we have no $(a,b);a\ne b$ in $R$ then $r$ must be transitive as the only we we can have $(a,b)$ and $(b,c)\in R$ is if $a=b$ and $b=c$ and if $(a,a)\in R$ then .... $(a,a)\in R$.

So of those type we may or may not have $(*,*)$ or $(\{\sim\},\{\sim\})$ in $R$ so there are $4$ if these vacuous like transitive relation.

$\emptyset$,$\{(*,*)\}$, $\{(\{\sim\},\{\sim\})\}$, and $\{(*,*),(\{\sim\},\{\sim\})\}$

If we have $(a,b)$ but not $(b,a)$ then well that's transitive too. If $(a,a)$ is or is not in $R$ then $(a,b)$ is in $R$ and if $(b,b)$ is or is not in $R$ then $(a,b)$ is in $R$.

So there are $2$ choices for $(a,b);a\ne b$ and $4$ options if the twin pairs are include or not so there are $8$ of these type function.

$\{(*,\{\sim\})\}$, $\{(*,*),(*,\{\sim\})\}$, $\{(\{\sim\},\{\sim\}),(*,\{\sim\})\}$, and $\{(*,*),(\{\sim\},\{\sim\}),(*,\{\sim\})\}$

And

$\{(\{\sim\},*)\}$,$\{(*,*),(\{\sim\},*)\}$, $\{(\{\sim\},\{\sim\}),(\{\sim\},*)\}$, and $\{(*,*),(\{\sim\},\{\sim\}),(\{\sim\},*)\}$

ANd if we have both $(a,b)$ and $(b,a)$ then we must have $(a,a)$ and $(b,b)$ and there is one that will do that

$\{(*,*),(*,\{\sim\}), (\{\sim\},*),(\{\sim\},\{\sim\})$.

There are $13$ transitive relations so only $3$ that aren't!

They are the ones containing both $(a,b)$ and $(b,a)$ but not both $(a,a)$ and $(b,b)$.

...

The question didn't ask but of the $4$ reflexive, $8$ symmetric and $13$ transitive the only ones that are all three are

$\{(\{\sim\},\{\sim\}), (*,*)\}$ and $\{(\{\sim\},\{\sim\}), (*,*),(\{\sim\},*)(*,\{\sim\})\}$

Those are the two equivalence relationships.

The first has two equivalence classes: $C_1 = \{*\}$ and $C_2= \{\{\sim\}\}$. i.e elements are only related to themselves.

The other has one equivalence class $C= \{*,\{\sim\}\} = A$. i.e. Everything is related to everything.