[Math] List all relations on {a,b}

discrete mathematicsrelations

I'm asked to list all possible relations on the set X = {a,b} and state which are reflexive, symmetric, antisymmetric, and transitive.

I'm using the following definitions:

reflexive – a relation R is reflexive if for all x in X, (x,x) is in R

symmetric – a relation is symmetric if for any x,y in X, (x,y) implies (y,x)

antisymmetric – a relation is antisymmetric if (x,y) and (y,x) imply x = y

transitive – a relation is transitive if (x,y) and (y,z) imply (x,z)

So far I have the following, but much of it is not correct. I don't understand how to tell if any of them are antisymmetric. Also, is the empty set also a relation on X? If so, I'm not sure which properties it would have.

{(a,a)} – symmetric, transitive

{(a,b)} – (none)

{(b,a)} – (none)

{(b,b)} – symmetric, transitive

{(a,a), (a,b)} – transitive

{(a,a), (b,a)} – transitive

{(a,a), (b,b)} – reflexive, symmetric, transitive

{(a,b), (b,a)} – symmetric

{(a,b), (b,b)} – transitive

{(b,a), (b,b)} – transitive

{(a,a), (a,b), (b,a)} – symmetric

{(a,a), (a,b), (b,b)} – reflexive, transitive

{(a,a), (b,a), (b,b)} – reflexive, transitive

{(a,b), (b,a), (b,b)} – symmetric

{(a,a), (a,b), (b,a), (b,b) – reflexive, symmetric, transitive

Best Answer

The emptyset is indeed a relation, and it's the only one you're missing. Remember that a "binary relation on $X$" is just "a subset of $X^2$" - the emptyset is definitely a subset of $X^2$!

As a relation, the emptyset is not reflexive, but it is symmetric and transitive; do you see why? (HINT: universal statements about the emptyset are "vacuously" true - e.g. "Every flying elephant is purple" is a true statement.)

As to antisymmetry, just look at the definition! A relation $R$ is antisymmetric iff $xRy$ and $yRx$ implies $x=y$. So:

  • $\{(a, b), (b, a)\}$ is not antisymmetric: we have $aRb$ and $bRa$ but $a\not=b$.

  • $\{(a, b)\}$ is antisymmetric - we never have $xRy$ and $yRx$ hold, so it trivially satisfies antisymmetry.

  • $\{(a, a)\}$ is antisymmetric - we only have $xRy$ and $yRx$ when $x, y=a$, and this means $x=y$.

Do you see how to check antisymmetry for the others, now?

Related Question