1

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

Graham Kemp
  • 129,094
RandomGuy57
  • 115
  • When you say that you cannot use brute force, does this mean you cannot exhaust the list of all relations in any way, or does it simply mean that you cannot do this by individually checking all 16 relations? – Moosh Nov 24 '20 at 23:48
  • I cant go out of my way to just check every relation more or less – RandomGuy57 Nov 24 '20 at 23:56

2 Answers2

0

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?

Graham Kemp
  • 129,094
  • 1
    I need to prove that these are the ONLY possible relations if that helps clarify the assignment is pretty vague, and im not allowed to just list all 16 possibilities and go through them 1 by 1 – RandomGuy57 Nov 24 '20 at 23:57
  • Well, there are only so many counter examples to transitivity that there could be over ${a,b}$. Show that these are the only relations that can be built with them. – Graham Kemp Nov 25 '20 at 00:03
0

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.

Moosh
  • 624