0% found this document useful (0 votes)
7 views3 pages

Equivalence Relations and POSET Proofs

The document provides detailed proofs of equivalence relations and partially ordered sets (POSETs), including examples such as congruence modulo 5 and divisibility. It defines equivalence relations and partial orders, illustrating their properties through various mathematical sets. The proofs demonstrate reflexivity, symmetry, transitivity for equivalence relations, and reflexivity, antisymmetry, transitivity for POSETs.

Uploaded by

ryanpaul31887
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
7 views3 pages

Equivalence Relations and POSET Proofs

The document provides detailed proofs of equivalence relations and partially ordered sets (POSETs), including examples such as congruence modulo 5 and divisibility. It defines equivalence relations and partial orders, illustrating their properties through various mathematical sets. The proofs demonstrate reflexivity, symmetry, transitivity for equivalence relations, and reflexivity, antisymmetry, transitivity for POSETs.

Uploaded by

ryanpaul31887
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Detailed Proofs: Equivalence Relations and Partially Ordered

Sets (POSETs)

Alka Munjal

September 27, 2025

Contents
1 Preliminaries: Definitions 1

2 Equivalence Relation Examples: Detailed Proofs 1


2.1 Example: Congruence modulo 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Example: Equality of absolute value . . . . . . . . . . . . . . . . . . . . . . . . . 2

3 POSET Examples: Detailed Proofs 2


3.1 Example: Usual order on Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.2 Example: Divisibility on N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.3 Example: Divisibility on a finite set {1, 2, 4, 8} . . . . . . . . . . . . . . . . . . . 3

1 Preliminaries: Definitions
Definition 1.1 (Equivalence relation). A relation ∼ on a set A is an equivalence relation if it
is
(a) reflexive: ∀x ∈ A, x ∼ x;

(b) symmetric: ∀x, y ∈ A, x ∼ y ⇒ y ∼ x;

(c) transitive: ∀x, y, z ∈ A, x ∼ y and y ∼ z ⇒ x ∼ z.


Definition 1.2 (Partial order and POSET). A relation ≤ on a set P is a partial order if it is
(a) reflexive: ∀x ∈ P, x ≤ x;

(b) antisymmetric: ∀x, y ∈ P, x ≤ y and y ≤ x ⇒ x = y;

(c) transitive: ∀x, y, z ∈ P, x ≤ y and y ≤ z ⇒ x ≤ z.


A partially ordered set or POSET is a pair (P, ≤) where ≤ is a partial order on P .

2 Equivalence Relation Examples: Detailed Proofs


2.1 Example: Congruence modulo 5
Set: Z.
Relation: a ∼ b ⇐⇒ a ≡ b (mod 5) (i.e. 5 | (a − b)).
Claim: ∼ is an equivalence relation on Z.
Proof:

1
• Reflexive: For any a ∈ Z, a − a = 0 and 5 | 0, so a ≡ a (mod 5). Therefore a ∼ a.

• Symmetric: Suppose a ∼ b. Then 5 | (a − b), so there exists k ∈ Z such that a − b = 5k.


Then b − a = −5k, hence 5 | (b − a) and b ∼ a.

• Transitive: Suppose a ∼ b and b ∼ c. Then 5 | (a − b) and 5 | (b − c), so a − b = 5k and


b − c = 5ℓ for some k, ℓ ∈ Z. Adding, a − c = (a − b) + (b − c) = 5(k + ℓ), so 5 | (a − c)
and a ∼ c.

Thus ∼ is reflexive, symmetric and transitive, i.e. an equivalence relation.


Equivalence classes: There are five classes corresponding to residues 0, 1, 2, 3, 4 mod 5: for
example [0] = {. . . , −10, −5, 0, 5, 10, . . . } and [1] = {. . . , −9, −4, 1, 6, 11, . . . }. The collection of
all classes partitions Z into five disjoint infinite sets.

2.2 Example: Equality of absolute value


Set: R.
Relation: a ∼ b ⇐⇒ |a| = |b|.
Claim: ∼ is an equivalence relation on R.
Proof:

• Reflexive: For any a ∈ R, |a| = |a|, hence a ∼ a.

• Symmetric: If |a| = |b|, then trivially |b| = |a|, so b ∼ a.

• Transitive: If |a| = |b| and |b| = |c|, then |a| = |c|, hence a ∼ c.

Therefore ∼ is reflexive, symmetric and transitive.


Equivalence classes: For each nonnegative real number r, the class [r] equals {r, −r} when
r > 0, and [0] = {0}. Thus classes are pairs of opposite nonzero reals and the singleton {0}.

3 POSET Examples: Detailed Proofs


3.1 Example: Usual order on Z
Set: Z.
Relation: ≤ is the usual numerical order.
Claim: (Z, ≤) is a POSET.
Proof:

• Reflexive: For any a ∈ Z, by definition a ≤ a.

• Antisymmetric: Suppose a ≤ b and b ≤ a. Then a = b because the only way two real (in
fact integer) numbers can be both ≤ each other is equality. Formally, a ≤ b and b ≤ a
imply a − b ≤ 0 and b − a ≤ 0, hence a − b = 0 and so a = b.

• Transitive: If a ≤ b and b ≤ c, then by the transitive property of the usual order a ≤ c.

Therefore ≤ is a partial order on Z.


Remarks: This order is actually a total (linear) order because for any a, b either a ≤ b or
b ≤ a.

2
3.2 Example: Divisibility on N
Set: N = {1, 2, 3, . . . }.
Relation: a ≤ b ⇐⇒ a | b (i.e. ∃k ∈ N with b = ak).
Claim: (N, |) is a POSET.
Proof:

• Reflexive: For any a ∈ N, a | a because a = a · 1.

• Antisymmetric: Suppose a | b and b | a. Then there exist m, n ∈ N with b = am and


a = bn. Substituting gives a = (am)n = a(mn) so a(1 − mn) = 0. Since a ≥ 1 we deduce
mn = 1, hence m = n = 1, and therefore b = a.

• Transitive: If a | b and b | c, say b = ak and c = bℓ, then c = a(kℓ), so a | c.

Hence divisibility is a partial order on N.


Remarks: Divisibility is not a total order (for example 2 and 3 are incomparable). The Hasse
diagram illustrates the covering relations (e.g. 1 covers nothing, 2 and 3 cover 1 etc.).

3.3 Example: Divisibility on a finite set {1, 2, 4, 8}


Set: A = {1, 2, 4, 8}.
Relation: a ≤ b iff a | b.
Claim: (A, |) is a POSET.
Proof: All verifications are immediate specializations of the divisibility example above.

• Reflexive: Each element divides itself.

• Antisymmetric: If a | b and b | a for a, b ∈ A, then a = b by the divisibility argument.

• Transitive: If a | b and b | c in A then a | c.

Hence (A, |) is a POSET.


Hasse diagram (informal):

8
|
4
|
2
|
1

Here each edge shows a cover relation (for instance 2 covers 1, 4 covers 2, 8 covers 4). The
diagram shows the chain 1 < 2 < 4 < 8.

Common questions

Powered by AI

The usual numeric order on integers (Z, ≤) and divisibility on natural numbers (N, |) both serve as examples of POSETs because they satisfy reflexivity, antisymmetry, and transitivity. However, they illustrate different characteristics of partial orders. The numeric order is a total order, meaning any two integers are comparable. In contrast, divisibility on natural numbers forms a partial order where not all elements are comparable (e.g., 2 and 3 are incomparable in terms of divisibility). Thus, while both are structurally POSETs, the numeric order represents a more restricted, linear hierarchy compared to the tree-like structure of the divisibility relation .

Congruence modulo 5 and equality of absolute values both demonstrate the concept of equivalence classes by partitioning their respective sets into well-defined subsets based on specific criteria. Congruence modulo 5 partitions the integers into classes based on the remainder when divided by 5, resulting in five distinct, infinite classes corresponding to residues 0 through 4. Equality of absolute values partitions real numbers into pairs of numbers with the same magnitude, resulting in classes of the form {r, -r} for each positive real r and the singleton class {0}. These partitions differ significantly in their structure; congruence classes represent a modular arithmetic structure of regular intervals, while absolute value classes are pairs of reals that highlight magnitude regardless of sign .

A partially ordered set (POSET) is characterized by a set P together with a binary relation ≤ that is reflexive, antisymmetric, and transitive. Reflexivity ensures that every element is related to itself (∀x ∈ P, x ≤ x). Antisymmetry ensures that if two elements are mutually related, then they are equal (∀x, y ∈ P, x ≤ y and y ≤ x imply x = y). Transitivity ensures that if one element is related to a second, which is related to a third, the first element is related to the third (∀x, y, z ∈ P, x ≤ y and y ≤ z imply x ≤ z). An example of a POSET is the natural numbers N with the divisibility relation, where a ≤ b if and only if a divides b .

An equivalence relation is defined by three properties: reflexivity (each element is related to itself), symmetry (if one element is related to another, the reverse relationship holds as well), and transitivity (if one element is related to a second, and the second is related to a third, the first element is related to the third). A partial order, on the other hand, requires reflexivity, antisymmetry (if two elements are mutually related, they must be identical), and transitivity. The key difference lies in symmetry versus antisymmetry: equivalence relations allow for symmetric relations between distinct elements, while partial orders do not. Structural implications include equivalence relations forming partitions of sets into equivalence classes, whereas partial orders form hierarchies that can be visualized using Hasse diagrams .

Antisymmetry plays a crucial role in distinguishing partial orders from equivalence relations by ensuring that if two elements are mutually related, they must be the same element (x ≤ y and y ≤ x imply x = y). This prevents distinct elements from being symmetrically related, which is allowed in equivalence relations where symmetry is required. Thus, antisymmetry facilitates the formation of hierarchical structures in partial orders where elements are comparable in a one-directional manner, unlike the pairwise association of equivalence relations .

In equivalence relations, transitivity means that if an element is related to a second, which is related to a third, then the first is related to the third, supporting the construction of equivalence classes that fully partition the set. In partial orders, transitivity combines with antisymmetry to create a hierarchy where elements can be compared in a directional manner but without symmetry allowed for distinct elements. Structurally, these differences lead equivalence relations to form discrete partitions, while partial orders create a more linear or tree-like structure depending on the context, which can include incomparable elements visualized as nodes in a Hasse diagram .

The equality of absolute values is considered an equivalence relation on the set of real numbers because it satisfies reflexivity (|a| = |a| for all a ∈ R), symmetry (if |a| = |b|, then |b| = |a|), and transitivity (if |a| = |b| and |b| = |c|, then |a| = |c|). This implies that real numbers can be grouped into equivalence classes based on their absolute values, which include pairs of opposite nonzero reals {r, -r} for each positive r and a singleton {0} for zero. This partitioning into equivalence classes shows how real numbers can be thought of in terms of magnitude regardless of sign .

The usual numeric order on integers forms a total order because, for any integers a and b, either a ≤ b or b ≤ a, without any incomparability between distinct elements. This property satisfies the condition of totality, which states that every pair of elements is comparable. It is considered a special case of a POSET since it also meets the criteria of reflexivity, antisymmetry, and transitivity, which define a partially ordered set. However, a POSET can have elements that are not comparable, which is not the case in a total order like the numeric order on integers .

The relation of congruence modulo 5 is an equivalence relation because it satisfies three properties: reflexivity, symmetry, and transitivity. The relation is reflexive as any integer a satisfies a ≡ a (mod 5). It is symmetric since if a ≡ b (mod 5), then b ≡ a (mod 5). It is transitive as if a ≡ b (mod 5) and b ≡ c (mod 5), then a ≡ c (mod 5). The equivalence classes formed by this relation are based on the residues 0, 1, 2, 3, and 4 modulo 5, partitioning the set of integers Z into five disjoint infinite sets such as [0] = {..., -10, -5, 0, 5, 10, ...} .

The divisibility relation on a finite set such as {1, 2, 4, 8} illustrates the concept of a POSET by satisfying the conditions of reflexivity (each element divides itself), antisymmetry (if two elements mutually divide each other, they are equal), and transitivity (if an element divides a second and the second divides a third, the first divides the third). The Hasse diagram is significant because it visualizes the structure of the POSET, showing the hierarchical relationships without redundant lines, where each edge represents a cover relation (e.g., 8 covers 4, 4 covers 2, and 2 covers 1), effectively illustrating the partial order on the set .

You might also like