Thread: logic 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

What is the definition of R*? Sometimes the properties you mention hold by definition.

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)

Then your claims hold by definition: 1) when n = 0 and 2) when n = 1.

Originally Posted by scubasteve123

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)

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*.