[Math] Reflexive, symmetric, anti-symmetric and transitive relations on a set {0,1}

discrete mathematicselementary-set-theoryrelations

The question has 3 parts:

a) How many distinct relations are in the set {0,1}

b) How many of those relations have the pair (0,1)

c) For each of them tell which are reflexive, symmetric, antisymmetric and/or transitive

First parte is quite simple, there are four pairs (0,1), (1,0), (0,0) and (1,1), so the answer is $2^4$

Second question is ok as well. Doing the relations I have:

  • $\emptyset$
  • One element $(4)$: {(0,1)}, {(1,0)}, {(1,1)}, {(0,0)}
  • Two elements $(3)$: {(0,1),(1,0)}, {(0,1),(0,0)}, {(0,1),(1,1)}
  • Two elements $(3)$: {(0,0), (1,0)}, {(0,0), (1,1)}, {(1,0), (1,1)}
  • Three elements $(4)$: {(0,1), (1,0), (0,0)}, {(0,1), (1,0), (1,1)}, {(0,1), (1,1), (0,0)}, {(1,0), (0,0), (1,1)}
  • Four elements $(1)$: {(0,1),(1,0), (0,0),(1,1)}

1+4+3+3+4+1 = 16, all the pairs are there; So pairs with (0,1): 8 pairs

The third question is the one that I do not understand. I know what a reflexive, symmetric, antisymmetric and transitive relations are, but in this case I don't see how I should apply the definition to the pairs above.

Could someone please give me a hint, maybe with an example?

Thanks

Best Answer

$2$ can be done more easily in the manner of $1$:

There are $4$ pairs. We must include the pair $(0,1)$ in our relations. The remaining $3$ may or may not be in our relations as we choose. So there are $2^3$ such relations that most include $(0,1)$ but have no other requirement.

$3$ is a matter of looking at the eight relations and seeing which are reflexive, symmetric, antisymmetric and/or transitive.

You write "but in this case I don't see how I should apply the definition to the pairs above". I'm not sure I understand your confusion. You have $8$ relations and suddenly you are asking how to apply the definition of refl, symm, etc to the pairs. Why do you think we are apply them to pairs? I don't see why you made that assumpition.

Take the relations 1 at a time:

1) $\{(0,1)\}$.

This is not reflexive as it does not include both $(0,0)$ nor $(1,1)$.

This is not symmetric as for every $(a,b)$ contained (only $(0,1)$ is contained) then $(b,a)$ is not contained. ($(1,0)$ is not contain.)

It is antisymmetric as for any $(a,b); a\ne b$ contained (That's only $(0,1)$), then $(b,a)$ is not contained ($(1,0)$ is not contained).

And it is transitive as for any $(a,b)$ and $(b,c)$ contained (there are none; we have $(0,1)$ but we do not have $(1,x)$ at all), then $(a,c)$ is contained. This is vacuously true as there are no $(y,0)$ or $(1,x)$.

2) $ \{(0,1),(1,0)\}$

Not reflexive as it does not contain either $(0,0)$ nor $(1,1)$.

Is symmetric as for ever $(a,b)$ then $(b,a)$ is contained.

Not antisymetric as both $(1,0)$ and $(0,1)$ is contained.

Not transitive $(0,1)$ is contained and $(1,0)$ is contained but $(0,0)$ is not.

.....

And so on.

Six more to go.

====

Alternatively it will probably by easier to list the relations that have properties by the properties.

Reflexive.

$(a,a)$ is contained for all $a\in \{0,1\}$ so we must pick the relations that have both $(0,0)$ and $(1,1)$.

They are $\{(0,0),(1,1),(0,1)\}$ and $\{(0,0),(1,1),(0,1),(1,0)\}$

Symmetric.

To be symmetric if it has $(a,b)$ it must have $(b,a)$. Now all $(a,a)$ are symmetric to itself so if it has an $(a,a)$ we don't have to check for its converse $(a,a)$. But if it has a $(a,b)a\ne b$ we must check for $(b,a)$. And $(0,1)$ and $(1,0)$ are the only unequal pairs, a relation will be symmetric if and only if it has both $(0,1)$ and $(1,0)$ or it has neither. As we are only checking the relations with $(0,1)$ the we must find those that have both.

$\{(0,1),(1,0)\}$ and $\{(0,1),(1,0),(0,0)\}$ and $\{(0,1),(1,0),(1,0)\}$ and $\{(0,1),(1,0),(0,0),(1,1)\}$

Antisymmetric. If it has $(a,b) a\ne b$ it can not have $(b,a)$. As we are only considering relations with $(0,1)$ we must exclude $(1,0)$. As $0, 1$ are the only unequal elements that's all we have to check.

$\{(0,1)\}, \{(0,1),(0,0)\}, \{(0,1),(1,1)\}, \{(0,1),(0,0),(1,1)\}$.

Transitive. We have $(0,1)$. if we have any $(1,x)$ we must also have $(0,x)$ And if we have $(x,0)$ we must also have $(x,1)$. But we needn't have either of those.

So $\{(0,1)\}$. And $\{(0,1),(1,0),(0,0),(1,1)\}$. And $\{(0,1),(1,1)\}$ and $\{(0,1),(0,0)\}$.

Related Question