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, 05: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 30th 2010, 12:16 AMemakarov
What is the definition of R*? Sometimes the properties you mention hold by definition.

- Jan 30th 2010, 11: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, 03:26 AMemakarov
Then your claims hold by definition: 1) when n = 0 and 2) when n = 1.

- Feb 12th 2010, 09: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*.