Transitive Relation over Set - Feedbacks on proofwriting skills

You could be a bit more explicit by saying "Since yPx and zPy are false, we know that zPx is false by negative transitivity of P. Therefore, xRz by definition of R." But that's just a stylistic preference. Overall, your proof is clear and concise. In summary, the conversation discusses the proof of the transitivity of a binary relation R defined on a set X, given that the relation P on X is negatively transitive. It is proven that if xRy and yRz, then xRz, thus showing that R is transitive. The proof is clear and concise, with the use of negative transitivity of P and the definition of R.
  • #1
Kolmin
66
0

Homework Statement



Assume a relation [itex]P[/itex] that is negatively transitive on a set [itex]X[/itex] that is not empty.
Define the binary relation [itex]R[/itex] on [itex]X[/itex] by [itex]xRy[/itex] iff [itex] y P x [/itex] is false.

Prove that [itex]R[/itex] is transitive.

Homework Equations



Negative Transitivity: [itex]xPz \rightarrow xPy \vee yPz [/itex]

Like in the previous thread (Complete Relation), I think I have a proof, but I am really looking forward to any feedback on the style of this proof. I tried to incorporate the stylistic feedbacks of Michael Redei and pasmith who kindly gave me feedbacks on the previous attempt.

The Attempt at a Solution



Proof:
Let [itex]x[/itex], [itex]y[/itex] and [itex]z[/itex] be arbitrary and assume [itex]xRy[/itex] and [itex]yRz[/itex]. By definition of [itex]R[/itex] it follows that [itex]yPx[/itex] and [itex]zPy[/itex] are both false. Since [itex]P[/itex] is negatively transitive, this implies that [itex]zPx[/itex] is false. Thus, again by definition of [itex]R[/itex], the falsity of [itex]zPx[/itex] implies [itex]xRz[/itex], which proves that the relation [itex]R[/itex] is transitive.
 
Last edited:
Physics news on Phys.org
  • #2
Kolmin said:
Negative Transitivity: [itex]xPy \rightarrow xPy \vee yPz [/itex]
I think you mean xPy → xPz V zPy, or somesuch.
 
  • #3
haruspex said:
I think you mean xPy → xPz V zPy, or somesuch.

I hate typos... :smile:

I edited the previous post: it is [itex]xPz \rightarrow xPy \vee yPz[/itex]
 
  • #4
With that correction, your proof looks fine.
 

1. What is a transitive relation over a set?

A transitive relation over a set is a mathematical concept that describes a relationship between two elements in a set such that if the first element is related to a second element, and the second element is related to a third element, then the first element is also related to the third element. In other words, if A is related to B, and B is related to C, then A is also related to C.

2. Why is understanding transitive relations important?

Understanding transitive relations is important in many areas of mathematics, including set theory, algebra, and graph theory. It allows us to make logical conclusions and deductions based on the relationships between elements in a set. It also provides a foundation for more complex mathematical concepts and proofs.

3. How can I prove that a relation is transitive?

To prove that a relation is transitive, you must show that for any three elements A, B, and C in the set, if A is related to B and B is related to C, then A is also related to C. This can be done by using a direct proof, indirect proof, or proof by contradiction. It is important to carefully define the relation and its properties before attempting to prove transitivity.

4. Are there any real-life examples of transitive relations?

Yes, there are many real-life examples of transitive relations. One example is the "is a sibling of" relation. If person A is a sibling of person B, and person B is a sibling of person C, then person A is also a sibling of person C. Another example is the "greater than" relation in mathematics. If a number A is greater than a number B, and the number B is greater than a number C, then the number A is also greater than the number C.

5. What are some tips for improving proofwriting skills?

Some tips for improving proofwriting skills include practicing regularly, carefully defining all terms and symbols, using clear and concise language, providing examples and counterexamples, and checking for logical errors. It can also be helpful to read and study well-written proofs and to seek feedback from others. Additionally, breaking down a proof into smaller steps and using diagrams or visual aids can make the process easier and more effective.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
8
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
7K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Precalculus Mathematics Homework Help
Replies
20
Views
3K
Back
Top