∞Intro to the Theory of Sets Unit 4 – Equivalence Relations & Partial Orders

Key Concepts and Definitions

• An equivalence relation is a binary relation that satisfies reflexivity, symmetry, and transitivity properties
• Reflexivity states that every element is related to itself ($a \sim a$ for all $a \in A$)
• Symmetry implies if $a$ is related to $b$, then $b$ is also related to $a$ ($a \sim b \implies b \sim a$)
• Transitivity means if $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$ ($a \sim b$ and $b \sim c \implies a \sim c$)
• A partial order is a binary relation that is reflexive, antisymmetric, and transitive
  • Antisymmetry states if $a \leq b$ and $b \leq a$, then $a = b$
• An equivalence class of an element $a$ under an equivalence relation $\sim$ is the set of all elements equivalent to $a$, denoted as $[a] = \{x \in A : x \sim a\}$
• A partition of a set $A$ is a collection of non-empty, pairwise disjoint subsets whose union is $A$

Properties of Equivalence Relations

• Equivalence relations are reflexive, symmetric, and transitive
• The reflexive property ensures every element is related to itself
• Symmetry guarantees the relation holds in both directions between two elements
• Transitivity allows the relation to be extended across multiple elements
• Equivalence relations partition a set into disjoint equivalence classes
• Elements in the same equivalence class are equivalent to each other
• Elements in different equivalence classes are not equivalent
• The equivalence class of an element contains all elements equivalent to it

Equivalence Classes and Partitions

• An equivalence relation on a set induces a partition of the set into equivalence classes
• Each element of the set belongs to exactly one equivalence class
• Equivalence classes are disjoint, meaning no element can belong to more than one class
• The union of all equivalence classes is the original set
• Two elements are equivalent if and only if they belong to the same equivalence class
• The set of all equivalence classes under an equivalence relation is called the quotient set
  • Denoted as $A/\sim$ or $A/R$, where $A$ is the original set and $\sim$ or $R$ is the equivalence relation

Examples of Equivalence Relations

• Equality ($=$) on any set is an equivalence relation
  • Reflexive: $a = a$ for all $a$
  • Symmetric: if $a = b$, then $b = a$
  • Transitive: if $a = b$ and $b = c$, then $a = c$
• Congruence modulo $n$ ($\equiv_n$) on integers is an equivalence relation
  • $a \equiv_n b$ if and only if $a - b$ is divisible by $n$
  • Equivalence classes are congruence classes modulo $n$
• Similarity of triangles is an equivalence relation
  • Reflexive: every triangle is similar to itself
  • Symmetric: if triangle $A$ is similar to triangle $B$, then $B$ is similar to $A$
  • Transitive: if triangle $A$ is similar to $B$ and $B$ is similar to $C$, then $A$ is similar to $C$
• Having the same birthday is an equivalence relation on a group of people
  • Reflexive: every person has the same birthday as themselves
  • Symmetric: if person $A$ has the same birthday as person $B$, then $B$ has the same birthday as $A$
  • Transitive: if person $A$ has the same birthday as $B$ and $B$ has the same birthday as $C$, then $A$ has the same birthday as $C$

Introduction to Partial Orders

• A partial order is a binary relation that is reflexive, antisymmetric, and transitive
• Reflexivity: every element is related to itself ($a \leq a$ for all $a$)
• Antisymmetry: if $a \leq b$ and $b \leq a$, then $a = b$
• Transitivity: if $a \leq b$ and $b \leq c$, then $a \leq c$
• A set with a partial order is called a partially ordered set or poset
• In a poset, some elements may be incomparable, meaning neither $a \leq b$ nor $b \leq a$ holds
• A total order is a partial order in which every pair of elements is comparable

Properties of Partial Orders

• Partial orders satisfy reflexivity, antisymmetry, and transitivity
• The reflexive property ensures every element is related to itself
• Antisymmetry implies that if two elements are related in both directions, they must be equal
• Transitivity allows the relation to be extended across multiple elements
• Minimal element: an element $a$ is minimal if there is no element $b$ such that $b \leq a$ and $b \neq a$
• Maximal element: an element $a$ is maximal if there is no element $b$ such that $a \leq b$ and $a \neq b$
• Least element: an element $a$ is the least element if $a \leq b$ for all elements $b$ in the set
• Greatest element: an element $a$ is the greatest element if $b \leq a$ for all elements $b$ in the set

Hasse Diagrams and Visualization

• A Hasse diagram is a graphical representation of a partially ordered set
• Elements of the poset are represented as vertices or nodes in the diagram
• If $a \leq b$ in the poset and there is no element $c$ such that $a \leq c \leq b$, then there is an edge drawn from $a$ to $b$
  • This edge represents a "covers" relation, denoted as $a \prec b$ or $b \succ a$
• The edges are directed upwards, so if $a \leq b$, then $a$ appears below $b$ in the diagram
• Transitive relations are not explicitly shown as edges in the Hasse diagram
• Incomparable elements are not connected by an edge and are placed side-by-side
• Hasse diagrams provide a clear visual representation of the order relations and structure of a poset

Applications and Real-World Examples

• Partial orders have numerous applications in computer science, mathematics, and real-world scenarios
• Subset relation ($\subseteq$) on a collection of sets is a partial order
  • Reflexive: every set is a subset of itself
  • Antisymmetric: if $A \subseteq B$ and $B \subseteq A$, then $A = B$
  • Transitive: if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$
• Divisibility relation ($|$) on positive integers is a partial order
  • Reflexive: every positive integer divides itself
  • Antisymmetric: if $a | b$ and $b | a$, then $a = b$
  • Transitive: if $a | b$ and $b | c$, then $a | c$
• Precedence relations in scheduling tasks or events form a partial order
  • Task $A$ precedes task $B$ if $A$ must be completed before $B$ can start
• Hierarchical structures, such as family trees or organizational charts, can be modeled using partial orders
• Partial orders are used in version control systems to represent the history and relationships between different versions of files or projects