List all relations on {a,b}

Question

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

Answer 1

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?

Answer 2

Good start!

First of all, you are missing one relation, namely the empty relation, $\emptyset$. Here's a general formula for the number of relations in a set $X$ of size $n$: A relation on $X$ is by definition a subset of $X\times X$. Well the size of $X\times X$ is $n^2$, so the size of its power set (i.e., the number of subsets of $X\times X$) is $2^{n^2}$. (In your case, this comes out to 16.)

As an example, your relations $\{(a, b)\}$ and $\{(b, a)\}$ are antisymmetric, and transitive! The reason is that the things you need to check for reflexivity, antisymmetry, and transitivity to hold never occur, so the conditions are satisfied by default (see Noah Schweber's example of elephants).

I haven't checked the others, but you might want to check your other answers for vacuously true conditions like these.