Exercise 8.1 - Answers

 

1

(i)

Impossible. If we were allowed to have a empty domain, the combination would be possible. But in a non-empty domain no reflexive relation can be asymmetric. For, suppose that the relation is expressed by Rxy, and that that a is one of the things is the domain. Then, if it is reflexive, Raa is true. But in that case it is not true that "x"y[Rxy®¬Ryx], because it is not true that [Raa®¬Raa]. To put it another way: if a relation is reflexive, and the domain is not empty, there are loops in its graph; but loops are double arrows; so it is not asymmetric.

 
(ii)

This is possible as long as the relation is empty. If the relation is not empty it is not possible. For, suppose such a relation is expressed by Rxy. If it is not empty it must be that (say) Rab (where a and b may or may not be the same thing). Since the relation is symmetric it must also be that Rba. But then, since the relation is transitive, it follows that Raa. ([[RabÙRba]®Raa]). So it is not irreflexive. (If it is not empty there is an arrow from a to b. Since it is symmetric the arrow is double. So there is an arrow from a to b, and an arrow from b to a. So there is a short cut from a to a. So the relation is not irreflexive.)

 
(iii)

Impossible. For, suppose such a relation is expressed by Rxy. Since it is non-symmetric, it must be that (say) Rab and Rba (where a and b may or may not be the same thing). Since the relation is transitive, it follows that Raa must be true. (So must Rbb.) So the relation is not irreflexive.

 
(iv)

This is possible. For instance the relation expressed by x>y fits the bill.

 
(v)

This is impossible. For, suppose such a relation is expressed by Rxy. Since it is non-reflexive, it must be that Raa (say) and ¬Rbb (say), where a and b must, to course, be different. Since it is connected, therefore, either Rab or Rba must be true. But since it is symmetric, if either is true, so must the other be; so Rba and Rab. But then, if it is transitive, Rbb must be true.  But it isn't.

 

(vi)

This is possible, as long as the relation is empty and the domain has just one member - otherwise, because it is connected, the relation can't be empty.

 

(vii)

This is possible. An example would be a relation whose graph contained  two dots with a loop on one and a single arrow from one to the other. (For an actual example one could always draw such a graph, and let the domain consist of the dots in it, and let the relation hold between x and y just if there is an arrow from x to y.)

2

(i)

Irreflexive; symmetric; non-transitive; not connected. (It is not transitive, because there are some broken journeys without short cuts: suppose that John is Mary's brother; then Mary is John's sister; so there is a broken journey from John to John, but John is not his own brother or sister.)

  (ii)

Irreflexive; symmetric; intransitive; not connected.

  (iii)

Irreflexive; asymmetric; both transitive and intransitive; not connected. (It is both transitive and intransitive because there are no broken journeys, since if a is b's wife, b must be a man, and therefore no one's wife.)

 

(iv)

Irreflexive; asymmetric; transitive; not connected.

 

(v)

Reflexive; non-symmetric; non-transitive; connected. (It is not transitive: suppose that John is four inches taller than Peter, and that Peter is four inches taller than James, then John is eight inches taller than James; so he is at least six inches taller than him.

  (vi)

This relation is empty in the given domain (no one being more than ten feet tall). So it is: irreflexive; symmetric and asymmetric; transitive and intransitive; not connected.

 

(vii)

This holds between x and y whatever x and y are. So it is: reflexive; symmetric; transitive; connected.

  (viii)

Let us suppose that it is true that John plays in the same team as Mary as long as there is a team they both play in, even if there is a team that Mary plays in but John does not play in. Then the relation is: non-reflexive (not reflexive, because some people do not play in any teams at all); symmetric; non-transitive (not transitive, because, given what we are supposing, John may play in the same team as Mary, and Mary in the same team as Peter, without its being true that John plays in the same team as Peter, if Mary plays in different teams); not connected.


3

(i)

Irreflexive; symmetric; non-transitive; connected.

  (ii)

The relation is empty in this domain; so it is: irreflexive; symmetric and asymmetric; transitive and intransitive; connected.

  (iii)

Irreflexive; symmetric; intransitive; connected. (It is intransitive because, given that there are only two things in the domain, if x is not the same person as y and y is not the same person as z, x must be z.)

Close Window