Prove there is only 3 non transitive relations on {a,b} 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
 A: 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?
A: 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.
