Thread: Problem with understanding binary relations

Hi there!

I can't understand an exercise with binary relations, could somebody explain it to me?

For each of the following binary relations on A={1,2,3,4,5} draw its directed graph. Then by examining the graph decide whether the relation is 1) reflexive, 2) symmetric, 3)antisymmetric, 4) transitive.

a)SquareOf defined by , when

How do I do it? How do I draw a graph? I'm looking through my notes,but can't find the answer :-( Please help

The graph of the relation SquareOf has A as the set of vertices and an arrow from m to n iff n= m^2. So you need to draw five nodes labeled by 1, 2, 3, 4, 5 and for every ordered pair of nodes (including the same node/label taken twice), check if there is an arrow from the first element of the pair to the second. I believe there are only two arrows, one of which is a loop (an arrow from a node to itself).

Ok, that's what I thought, but then none of the properties is true.....is this normal? Should I just write down "this relation does not have any special properties"?

First, you are asked only about the four listed properties. This relation may have other properties that someone may deem "special".

Look carefully at antisymmetry and transitivity and recall that an implication is vacuously true if its premise is false. In particular, if you can't find a, b and c such that SquareOf(a, b) and SquareOf(b, c), then what does it say about transitivity?

Note, by the way, that SquareOf considered on the set of all natural numbers is not transitive, of course: for example, SquareOf(2, 4) and SquareOf(4, 16) are true, but SquareOf(2, 16) is false.

Ok,now I understand, thanks very much ;-)