Prove there is only 3 non transitive relations on {a,b}

Question

I know the 3 relations that aren't transitive

$${A=\{(a,b) , (b,a)\}\\ B=\{(a,b) , (b,a) , (a,a)\}\\ C=\{(a,b) , (b,a) , (b,b)\}}$$

I can't use brute force as my proof and I'm stuck

Answer 1

The first relation is not transitive.   $(a,b)\in A, (b,a)\in A$ but $(a,a)\notin A$, so we have a counter example for that.

Now find the counter examples for relations $B$ and $C$?

What do you notice about these counter examples?

Answer 2

Here is an attempt, I am not sure if this would be considered brute force or not though.

First of all, a relation is just an element of the power set of {a,b}$^2$ so there are 16 relations in total to consider. (15 if we dont consider the empty relation to be a valid relation) The equality relation is transitive, and any relation which contains only 1 pair of elements will be trivially transitive. Also the empty relation is trivially transitive, so either way its out. There are 4 relations with only a single element, so we are now down to 10 possible relations.

We can see that any relation which contains both {a,a} and {b,b} will be transitive, since for a relation $R$ to be non transitive, you need some $x,y,z$ such that $(x,y)\in R$, $(y,z)\in R$ and $(x,z)\notin R$. Since we are considering a domain with only 2 elements, $x=z$ or $y=z$ must be true. In the first case, we get $(x,x)\notin R$ and in the second case we get $(y,y)\notin R$. which means $R$ cannot contain both pairs.

There are 4 relations which contain both pairs, but one of them is the identity relation which we already removed, so we can remove 3 more, to get 7 relations left.

there are 4 relations which contain neither $(a,a)$ nor $(b,b)$, but only 1 of them contains at least 2 elements, so that is the only possible one that can be transitive.

There are 6 relations which contain either $(a,a)$ or $(b,b)$ but not both, as well as at least 1 other element. WLOG we can consider the relation which contains $(a,a)$ and not $(b,b)$. However, such a relation will be transitive if it contains only 1 other element. so our remaining relation must contain both other elements. ie they must be {$(a,a),(a,b),(b,a)$} and {$(b,b),(a,b),(b,a)$}.

So we get 3 relations in total.

If you think this is still to brute force, then you can prove there are only 3 possible relations by proving the following things. 1: a non transitive relation must contain more than 1 element. 2: a non transitive relation must contain at least 2 elements of the form $(x,y)$ with $x\neq y$ 3: a non transitive relation on a set of 2 variables, cannot contain both pairs $(a,a)$ and $(b,b)$. these 3 facts should give you only 3 possible relations, without it looking like you checked the other 13 possibilities.