09 Equivalency Relation and Classes, Partitions, Partially Ordered Sets

Lecture from: 16.10.2024 | Video: Videos ETHZ

Relations Repetition

In this lecture, we’ll focus on relations defined over the same set.

Let:

• ip denote the relation: ”$x$ is parent of $y$”.
• ic denote the relation: ”$x$ is child of $y$“.

Identity Relation

The identity relation $id$ over a set is defined as:

$id=\{(x,x)\mid x\in \text{set}\}$

Reflexive Relation

A relation $R$ over a set is reflexive if for every element $x$ in the set, $(x,x)\in R$.

Example: Reflexivity of $\text{ic}\circ \text{ip}$ and $\text{ip}\circ \text{ic}$

• $\text{ic}\circ \text{ip}$ (child of parent of): This relation is reflexive. Everyone is a child of their parent. $id\subseteq \text{ic}\circ \text{ip}$

• $\text{ip}\circ \text{ic}$ (parent of child of): This relation is not reflexive. Not everyone is a parent. $id⊈\text{ip}\circ \text{ic}$

Note: The lecturer initially made a mistake switching these two examples, but the corrected explanation is presented above.

Relation Properties

See: [[08 Relations, Compositions and Properties#Properties and Rules#4. Reflexivity, Symmetry, Antisymmetry, Transitivity, Asymmetry]]

Equivalence Relation

An equivalence relation on a set satisfies reflexivity, symmetry, and transitivity.

Example 1: Identity Relation

The identity relation on any set is an equivalence relation because:

• Reflexive: Every element is related to itself.
• Symmetric: There is no pair $(x,y)$ where $x\ne y$, so symmetry trivially holds.
• Transitive: Since no pairs $(x,y)$ exist with $x\ne y$, transitivity also holds.

Example 2: Equality on $\mathbb{R}$

The relation “is equal to” $(=)$ on real numbers $\mathbb{R}$ is an equivalence relation because:

• Reflexive: For every $x\in \mathbb{R}$, $x=x$.
• Symmetric: If $x=y$, then $y=x$.
• Transitive: If $x=y$ and $y=z$, then $x=z$.

Thus, it satisfies all conditions of an equivalence relation.

Equivalence Class

Given an equivalence relation $\theta$ on a set $A$, the equivalence class of $a\in A$ is:

Modular Congruency

Integers $a$ and $b$ are congruent modulo $m$ ($a\equiv b(\mathrm{mod}m)$) if $m$ divides $(a-b)$.

Example:

Partition of a Set

An equivalence relation divides a set into distinct, non-overlapping subsets, known as equivalence classes. Together, these equivalence classes form a partition of the set.

A partition of a set $A$ is a collection of non-empty subsets of $A$ such that:

1. Non-overlapping: No two subsets have elements in common.
2. Complete: Every element of $A$ belongs to one of these subsets.

Therefore, an equivalence relation on a set $A$ is essentially the same thing as a partition of $A$, where each equivalence class forms one of the subsets in the partition.

Quotient Set

The quotient set, denoted $A/\theta$ (read as “A modulo theta” or “A mod theta”), arises when you have a set $A$ and an equivalence relation $\theta$ defined on it. Remember, an equivalence relation partitions the set $A$ into distinct, non-overlapping subsets called equivalence classes. The quotient set is simply the set of all these equivalence classes.

Formal Definition

Given a set $A$ and an equivalence relation $\theta$ on $A$, the quotient set $A/\theta$ is defined as:

where $[a{]}_{\theta }$ represents the equivalence class of element $a$ under the relation $\theta$. Recall that an equivalence class $[a{]}_{\theta }$ is the set of all elements in $A$ that are related to $a$ by $\theta$:

Example: Modular Arithmetic

Let $A=\mathbb{Z}$ (the set of integers) and let $\theta$ be the congruence modulo 3 relation, denoted ${\equiv }_3$. This means that two integers $a$ and $b$ are related ($a{\equiv }_{3}b$) if their difference is divisible by 3:

This equivalence relation divides the integers into three distinct equivalence classes:

• $[0{]}_{{\equiv }_3}=\{\dots ,-6,-3,0,3,6,\dots \}$ (integers divisible by 3)
• $[1{]}_{{\equiv }_3}=\{\dots ,-5,-2,1,4,7,\dots \}$ (integers leaving a remainder of 1 when divided by 3)
• $[2{]}_{{\equiv }_3}=\{\dots ,-4,-1,2,5,8,\dots \}$ (integers leaving a remainder of 2 when divided by 3)

Notice that these three equivalence classes are disjoint (they have no elements in common) and they cover all the integers.

The quotient set $\mathbb{Z}/{\equiv }_3$ is then the set of these equivalence classes:

So, the quotient set in this case has only three elements, even though the original set $\mathbb{Z}$ is infinite. Each element of the quotient set represents a whole class of integers. This is a powerful way to group together related elements and work with the groups (equivalence classes) rather than individual elements.

The quotient set takes a set and an equivalence relation, and it gives you a new set whose elements are the equivalence classes formed by that relation. It’s a way of “reducing” a set by grouping together equivalent elements.

Example: Definition of Rational Numbers

Let $A=\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})$, and define the relation $(a,b)\sim (c,d)⟺ad=bc$. We aim to prove that $\sim$ is an equivalence relation by verifying the three required properties: reflexivity, symmetry, and transitivity.

Reflexiv:

Rigorous:

• $(a,b)\sim (a,b)\dot{⟺}ab=ba$ (Definition of $\sim$)
• $\dot{⟺}ab=ab$ (Commutativity of multiplication)

Simple: To show that $(a,b)\sim (a,b)$:

• By the definition of $\sim$, we have $(a,b)\sim (a,b)⟺ab=ba$, which is trivially true because multiplication is commutative.

Symmetry:

Simple: To show that if $(a,b)\sim (c,d)$, then $(c,d)\sim (a,b)$:

• Assume $(a,b)\sim (c,d)$, meaning $ad=bc$.
• Rearranging this, we get $bc=ad$, which is exactly the condition for $(c,d)\sim (a,b)$.
• Therefore, symmetry holds.

Transitivity:

Rigorous:

• Given: (1): $(a,b)\sim (c,d)$; (2): $(c,d)\sim (e,f)$
• To prove: (1)(2) $⟹(a,b)\sim (e,f)$ (S)
• (3): (1) $\dot{⟺}ad=bc$ (Definition of $\sim$)
• (4): (2) $\dot{⟺}cf=de$ (Same as above)
• (5): (3),(4) $\dot{⟹}adcf=bcde$ (Multiplication is a common function)
• (6): (5) $\dot{⟹}acf=bce$ (cancel $d\ne 0$)
• Now we might think that we can simply cancel $c$, but we don’t know if it’s 0 or not. So here we’d need to do case distinction.
  • (7): $c=0\dot{⟹}acf=bce=0$ (if $c=0$ then trivially the latter is true)
  • (8): $c\ne 0\dot{⟹}$ (6) $⟹af=be$ (cancel $c\ne 0$)
  • (9): (7) and (3) $\dot{⟹}a=0$ (since $d\ne 0$)
  • (10): (7) and (4) $\dot{⟹}e=0$ (since $d\ne 0$)
  • (11): (7) and (10) $\dot{⟹}af=be$ (since both $a=e=0$)
• (12): (8) or (11) $\dot{⟹}af=eb$

Simple: To show that if $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$, then $(a,b)\sim (e,f)$:

• Assume $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$. This means:

  1. $ad=bc$
  2. $cf=de$

• We want to prove that $(a,b)\sim (e,f)$, i.e., $af=be$. To do this:

  • Multiply the two conditions: $ad\cdot cf=bc\cdot de$
  • This simplifies to: $acf=bce$
  • Now, cancel $c$ (if $c\ne 0$), and we are left with $af=be$, which is the desired condition for $(a,b)\sim (e,f)$.

• If $c=0$, then from $ad=bc$, we get $a=0$, and from $cf=de$, we get $e=0$. Hence, $af=be$ trivially holds since both sides are $0$.

Thus, transitivity holds.

Conclusion

Since reflexivity, symmetry, and transitivity are all satisfied, the relation $\sim$ is an equivalence relation. Notice how this relation resembles the structure of rational numbers. We can use this relation as a foundation for defining rational numbers.

Thus, the set of rational numbers can be represented as the set of equivalence classes of pairs of integers (where the second element is non-zero):

This means each rational number corresponds to an equivalence class $[(a,b)]$ where $a$ and $b$ are integers, and $b\ne 0$, under the relation $(a,b)\sim (c,d)⟺ad=bc$.

Partially Ordered Sets (Posets)

A poset is a set with a partial order relation $⪯$ that is reflexive, antisymmetric, and transitive.

A partially ordered set (or poset) is a set equipped with a partial order relation $⪯$ that is reflexive, antisymmetric, and transitive. A partial order describes how elements within the set are ordered in a way that might not allow comparison between all elements, meaning that some elements could be incomparable.

Properties of a Partial Order

For a relation $R$ to be considered a partial order, it must satisfy the following three properties:

1. Reflexive: For every element $x$ in the set, $(x,x)\in R$. This means every element is related to itself.

2. Antisymmetric: For all elements $x$ and $y$, if $(x,y)\in R$ and $(y,x)\in R$, then $x=y$. In other words, if two elements mutually “cover” each other, they must be identical.

3. Transitive: For all elements $x$, $y$, and $z$, if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$. The relation can “pass through” intermediate elements.

Example: Covering Relationship of Convex Polygons

Let’s consider a partial order based on the covering relationship between convex polygons (where lines between any two points within the polygon are straight). A polygon $A$ is said to cover polygon $B$ if $B$ can fit entirely inside $A$ without any overlap beyond $A$‘s boundary.

Now, let’s check the three properties of a partial order:

• Reflexive: Any polygon covers itself, so the relation is reflexive.
• Antisymmetric: If polygon $A$ covers polygon $B$ and polygon $B$ covers polygon $A$, then $A$ and $B$ must be the same polygon. This makes the relation antisymmetric.
• Transitive: If polygon $A$ covers polygon $B$, and polygon $B$ covers polygon $C$, then polygon $A$ will also cover polygon $C$. This satisfies transitivity.

Symbol for Partial Order

We commonly use the symbol "$⪯$" (a “curvy” $\le$) to denote a partial order relation. If we write: $A⪯B$ It means that polygon $A$ is related to polygon $B$ in the sense of our defined “covering” relationship, i.e., polygon $A$ either covers $B$ or is equal to $B$.

Other Symbols for Partial Order Relations

In addition to the $⪯$ symbol for partial orders, there are other symbols used to describe specific types of relationships within a partially ordered set:

• Strict Precedes: The symbol $a\prec b$ is used to indicate that $a$ strictly precedes $b$ in the partial order. This means that $a⪯b$ but $a\ne b$ (i.e., $a$ is not equal to $b$).
  • Formally, we write: $a\prec b⟺a⪯b\wedge a\ne b$
• Incomparable: If two elements $a$ and $b$ cannot be compared (i.e., neither $a⪯b$ nor $b⪯a$), they are said to be incomparable. This is common in partial orders where not all elements have a defined order relative to each other.

Exam Question: Transitivity of $\prec$

Is $\prec$ transitive? Answer: Yes, but we need to prove it.

Proof:

• Given:

  • (1): $a\prec b$
  • (2): $b\prec c$
  • We need to prove that $(1)$ and $(2)$ imply $a\prec c$.

• Definitions:

  • By definition of $\prec$, we have: $a\prec c⟺(a\le c)\wedge (a\ne c)$

Steps to Prove:

1. Proving $a\le c$:

   • From (1), we have $a⪯b$.
   • From (2), we have $b⪯c$.
   • By the transitivity of $⪯$, if $a⪯b$ and $b⪯c$, then: $a⪯c$
   • Therefore: $a\le c$

2. Proving $a\ne c$:

   • From (1), we know $a\ne b$.
   • From (2), we know $b\ne c$.

   Now, assume, for the sake of contradiction, that: $a=c$

   • What does this assumption imply?: If $a=c$, then from the definition of $⪯$, we have: $a⪯b\text{and}b⪯a$ This implies: $a⪯b⪯a$

   • Using the antisymmetric property: The antisymmetric property of $⪯$ states that if $a⪯b$ and $b⪯a$, then: $a=b$ However, this contradicts our earlier conclusion that $a\ne b$ from (1).

   • Contradiction: Thus, assuming $a=c$ leads to a contradiction.

   • Conclusion: Therefore, we must reject the assumption that $a=c$, which implies: $a\ne c$

Final Step:

• From the substeps, we have shown that:
  • $a\le c$ (from step 1)
  • $a\ne c$ (from step 2)
• Thus, we conclude: $a\prec c$

Continue here: 10 Posets, Hasse Diagrams, Lexicographical Ordering, Special Elements, Functions, Countability, Infinities