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!

Related General Discussion News on Phys.org

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.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving