Natural Deductions

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!
 
112
1
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.
 

Related Threads for: Natural Deductions

  • Posted
Replies
6
Views
3K
  • Posted
Replies
13
Views
3K
  • Posted
Replies
2
Views
4K
  • Posted
Replies
2
Views
7K
Replies
1
Views
1K
Replies
6
Views
5K
  • Posted
Replies
2
Views
15K
  • Posted
2 3 4
Replies
78
Views
5K

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

Hot Threads

Top