Show that the ancestral R* of a relation R has the following properties:

1)for every a R*aa

2)for all a and b if Rab then R*ab

Printable View

- Jan 29th 2010, 04:04 PMscubasteve123logic proof
Show that the ancestral R* of a relation R has the following properties:

1)for every a R*aa

2)for all a and b if Rab then R*ab - Jan 29th 2010, 11:16 PMemakarov
What is the definition of R*? Sometimes the properties you mention hold by definition.

- Jan 30th 2010, 10:25 AMscubasteve123
definition of an ancestor is that

R*xy holds when there is a finite

chain of objects a1,...,an, where x=a1 and y=an, such that

R(a1,a2),...,R(an-1,an) - Feb 12th 2010, 02:26 AMemakarov
Then your claims hold by definition: 1) when n = 0 and 2) when n = 1.

- Feb 12th 2010, 08:23 AMMoeBlee
Usually we say 'sequence' rather than 'chain', as usually 'chain' is a different notion.

Also, I take it that n greater than 0.

Anyway, as far as I can tell, what you are being asked to show is not true:

Counterxample:

Let R = {<a b>} with a not equal to b.

Then R* = {<a b>} and neither <a a> nor <b a> are in R*.