Lecture 17: Equivalence Relations and Partial Orders
In this lesson on Equivalence Relations and Partial Orders, students will learn about the different types of relations, including equivalence relations and partial orders. Equivalence relations are transitive, reflexive, and symmetric, and are used to model the equals relationship. Partial orders, on the other hand, are used to model the less than or equals to relationship and are also transitive and reflexive but not necessarily symmetric. The lesson also covers composing and finding the transitive closure of relations.
Learn what an equivalence relation is, what partial orders are, and how they fit into Discrete Math.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
- Lecture Notes - Lecture Notes from the course
- Problem Set 7 - A problem set with some problems from this lecture
- What does mod or modulo mean and how does it relate to number theory and discrete math?
- What does it mean for numbers to be equivalent modulo 3?
- What does it mean for a set to be a subset of another set?
- What are some properties of relations?
- What does it mean for a relation to be symmetric or anti-symmetric?
- What does it mean for a relation to be reflexive?
- What does it mean for a relation to be transitive?
- If a relation is not transitive, how can you make it transitive?
- What is transitive closure of a relation?
- What are equivalence relations?
- How can you prove that something is an equivalence relation?
- What are partial orders?
- What are Hasse diagrams?
- What is total ordering of a set?
- What is an interval order?
- How can you determine how many planes are needed to cover a certain number of routes with various intervals using partial ordering?
- What is an antichain and how can you determine the size of an antichain?
- What are posets and what do they have to do with scheduling problems?
-
Staff Review
This lesson starts off explaining the reflexive, symmetric, and transitive properties of relations. Then, equivalence relations are explained along with partial orders. Some really important basic ideas of relations are covered in this lecture. Also, an application to plane flights is included at the end of the lecture, which is quite interesting.
