Discrete Mathematics Partial Ordering Relations

Discrete Mathematics: Partial Ordering Relations

In the field of discrete mathematics, partial ordering relations play a significant role in understanding the relationships between elements in a set. A partial ordering relation is a binary relation that satisfies certain properties, allowing us to compare and classify elements based on their order. In this article, we will explore the concept of partial ordering relations and provide examples to illustrate their application.

Definition of Partial Ordering Relations

A partial ordering relation, also known as a partial order, is a binary relation that is reflexive, antisymmetric, and transitive. Let’s take a closer look at each of these properties:

Reflexivity

A relation R on a set A is reflexive if every element in A is related to itself. In other words, for every element a in A, (a, a) is an element of R. This property ensures that every element has a relationship with itself.

For example, consider the set of integers A = {1, 2, 3}. The relation “less than or equal to” (≤) is reflexive because for every element a in A, (a, a) is an element of the relation. In this case, (1, 1), (2, 2), and (3, 3) are all elements of the relation.

Antisymmetry

A relation R on a set A is antisymmetric if for every pair of distinct elements (a, b) in R, it is not the case that (b, a) is also in R. In other words, if (a, b) is in R and (b, a) is in R, then a must be equal to b.

Continuing with the previous example, the relation “less than or equal to” (≤) is antisymmetric because if (a, b) is an element of the relation and (b, a) is also an element of the relation, then a must be equal to b. For instance, (2, 3) is in the relation, but (3, 2) is not. This property ensures that there are no two distinct elements that are related in both directions.

Transitivity

A relation R on a set A is transitive if for every triple of elements (a, b, c) in R, if (a, b) is in R and (b, c) is in R, then (a, c) must also be in R. In other words, if there is a chain of relationships between elements, we can extend that chain to include the transitive relationship.

Let’s consider the set of positive integers A = {1, 2, 3}. The relation “divides” (|) is transitive because if a number divides another number and that number divides a third number, then the first number also divides the third number. For example, if 2 divides 4 and 4 divides 8, then 2 also divides 8. This property allows us to establish indirect relationships between elements based on the existing relationships.

Example of Partial Ordering Relations

Now, let’s explore a real-world example to illustrate the concept of partial ordering relations. Consider a set A = {books} containing a collection of books. We can define a partial ordering relation on this set based on the publication year of the books.

Let’s denote the relation as R, where (a, b) is in R if book a was published before or in the same year as book b. This relation satisfies the properties of a partial ordering relation:

1. Reflexivity: Every book is published before or in the same year as itself.
2. Antisymmetry: If book a was published before or in the same year as book b, and book b was published before or in the same year as book a, then book a and book b must have the same publication year.
3. Transitivity: If book a was published before or in the same year as book b, and book b was published before or in the same year as book c, then book a was published before or in the same year as book c.

Using this partial ordering relation, we can compare and classify the books based on their publication years. For example:

• Book A: Published in 2000
• Book B: Published in 1995
• Book C: Published in 2010

In this example, we can say that Book B is related to Book A because it was published before Book A. Similarly, Book A is related to Book C because it was published before Book C. However, there is no direct relationship between Book B and Book C. This partial ordering relation allows us to establish a partial order among the books based on their publication years.

Conclusion

Partial ordering relations are a fundamental concept in discrete mathematics that allow us to compare and classify elements in a set based on their order. These relations possess the properties of reflexivity, antisymmetry, and transitivity, which ensure a consistent and meaningful ordering. By understanding and applying partial ordering relations, we can analyze and organize various elements in a structured and logical manner.