logic proof

• Jan 29th 2010, 04:04 PM
scubasteve123
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
• Jan 29th 2010, 11:16 PM
emakarov
What is the definition of R*? Sometimes the properties you mention hold by definition.
• Jan 30th 2010, 10:25 AM
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)
• Feb 12th 2010, 02:26 AM
emakarov
Then your claims hold by definition: 1) when n = 0 and 2) when n = 1.
• Feb 12th 2010, 08:23 AM
MoeBlee
Quote:

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