Natural Deductions

[kodachrome22]

I am having trouble with some homework on natural deductions. I just don't know how to approach the problems. For example, one problem is to show that irreflexivity and transitivity imply asymmetry. Any strategies on how to reason the deductions would be great (the rules are simple enough, knowing how to decide how to do the problem is where I have trouble).

Thanks, and apologies if this belongs in the HW forum. I only saw physics problems there so I thought I'd get a better response here. Thanks!

[Stevo]

I like picturing these sorts of things.

So, imagine you have two points a and b, and an arrow between them which represents a relation R. Assume that R is irreflexive and transitive. Now, because R is transitive, we can go from a to b via R and then back from b to a via R, and this is equivalent to going from a to a via R. However, because R is irreflexive, there is no closed R curve from a to a. We've missed something.

In going from a to b via R and then from b to a via R, we're clearly assuming that R is also symmetric. So, it's possible that we've made two mistakes. Either R is not transitive, in which case not all "broken journeys" can be collapsed to a "shortcut", or R is asymmetric.

So we've killed two birds with one stone. An irreflexive symmetric relation must be intransitive, and an irreflexive transitive relation must be asymmetric.