Problem 4 - Applied Discrete Structures

Question

Determine which of the following are equivalence relations and/or partial ordering relations for the given sets: (a) \(A=\\{\) lines in the plane \(\\}\), and \(r\) defined by \(x r y\) if and only if \(x\) is parallel to \(y\). Assume every line is parallel to itself. (b) \(A=\mathbb{R}\) and \(r\) defined by \(x r y\) if and only if \(|x-y| \leq 7\).

Step-by-Step Solution

Answer

(a) An equivalence relationship; (b) Neither an equivalence relation nor a partial ordering.

Step 1: Understand Equivalence Relations

An equivalence relation on a set must satisfy three properties: reflexivity, symmetry, and transitivity. - **Reflexivity**: Every element is related to itself. - **Symmetry**: If one element is related to a second, the second is related to the first. - **Transitivity**: If the first element is related to the second, and the second is related to a third, then the first is related to the third.

Step 2: Understand Partial Ordering Relations

A partial order relation on a set must satisfy three different properties from equivalence relations: reflexivity, antisymmetry, and transitivity. - **Reflexivity**: Every element is related to itself. - **Antisymmetry**: If one element is related to a second and the second to the first, then both elements must be identical. - **Transitivity**: If the first element is related to the second, and the second is related to a third, then the first is related to the third.

Step 3: Analyze Relation for Problem (a)

Given set: Lines in the plane. Relation: A line is parallel to itself and other lines parallel to it. - **Reflexivity**: Every line is parallel to itself (given). - **Symmetry**: If line x is parallel to line y, then line y is parallel to line x. - **Transitivity**: If line x is parallel to line y, and line y is parallel to line z, then line x is parallel to line z. Therefore, the relation is an equivalence relation, but not a partial order since it lacks antisymmetry.

Step 4: Analyze Relation for Problem (b)

Given set: Real numbers \(\mathbb{R}\). Relation: \(|x-y| \leq 7\).- **Reflexivity**: \(|x-x| = 0 \leq 7\) for all \(x\), so reflexive.- **Symmetry**: If \(|x-y| \leq 7\), then \(|y-x| = |x-y| \leq 7\).- **Transitivity**: Assuming \(|x-y| \leq 7\) and \(|y-z| \leq 7\), \(|x-z|\) can be at most \(14\), which does not satisfy \(|x-z| \leq 7\) necessarily.This relation meets reflexivity and symmetry, but not transitivity, thus it is neither an equivalence relation nor a partial order.

Key Concepts

Partial Ordering Relations

Partial ordering relations help us organize and compare elements in a set, and are very important in various fields such as mathematics and computer science. A relation is considered a partial ordering if it satisfies the properties of reflexivity, antisymmetry, and transitivity.

• Reflexivity: Each element must relate to itself. This means for any element \(a\) in the set, \(a\) is related to \(a\).
• Antisymmetry: This property is a bit different from symmetry. Here, if an element \(a\) is related to an element \(b\) and \(b\) is related to \(a\), then \(a\) and \(b\) must be the same element.
• Transitivity: If an element \(a\) is related to \(b\), and \(b\) is related to \(c\), then \(a\) should be related to \(c\).

Understanding partial ordering relations helps in exploring the hierarchy and organization within a dataset. Unlike equivalence relations, partial orders allow asymmetric relationships, perfect for scenarios like sorting and structuring data without needing every pair of elements to be comparable.

Reflexivity

Reflexivity is a crucial property for both equivalence relations and partial orders. It ensures that every element in a set is connected to itself, forming the foundation for relations to build upon.
In simple terms, reflexivity means that for any element \(x\) in a set \(A\), \(x\) is related to \(x\) under the given relation. For example, consider a set of lines where we define a relation based on parallelism. Every line is always parallel to itself, fulfilling the reflexivity condition.
Reflexivity might seem straightforward, as it simply states that everything can relate to itself, but it is essential for more complex properties like symmetry and transitivity. Without reflexivity, the relation cannot be an equivalence relation or partial order.

Symmetry

Symmetry is a property exclusive to equivalence relations. It assures that if one element relates to another, then the latter also relates back to the former.
To visualize, imagine we have a set of lines, and we say that a line \(a\) is parallel to a line \(b\). Symmetry ensures that if \(a\) is parallel to \(b\), then \(b\) must be parallel to \(a\) too. Parallels not only work one way!
This reciprocal relationship creates a two-way connection between elements. Symmetry helps in forming equivalence classes, where a single relation groups multiple elements together. However, this property is not required in partial ordering relations, where directional relationships can exist.

Transitivity

Transitivity is a property necessary for both equivalence relations and partial orders. It creates chain connections among elements in a relation. Think of it as the 'domino effect' of relations.

• In essence, transitivity states: if \(x\) is related to \(y\), and \(y\) is related to \(z\), then \(x\) must be related to \(z\). It allows extending relationships further through intermediates.

For example, with lines being parallel, transitivity guarantees that if one line is parallel to a second, and that second line is parallel to a third, then the first line remains parallel to the third.
This chain-orientated property ensures any form of ordering or equivalency is consistently propagated. However, as shown in problem (b), if transitivity is absent, the relation can neither be an equivalence nor a partial order.