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)∣x∈set}$
Reflexive Relation
A relation $R$ over a set is reflexive if for every element $x$ in the set, $(x,x)∈R$.
Example: Reflexivity of $ic∘ip$ and $ip∘ic$

$ic∘ip$ (child of parent of): This relation is reflexive. Everyone is a child of their parent. $id⊆ic∘ip$

$ip∘ic$ (parent of child of): This relation is not reflexive. Not everyone is a parent. $id⊆ip∘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=y$, so symmetry trivially holds.
 Transitive: Since no pairs $(x,y)$ exist with $x=y$, transitivity also holds.
Example 2: Equality on $R$
The relation “is equal to” $(=)$ on real numbers $R$ is an equivalence relation because:
 Reflexive: For every $x∈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 $θ$ on a set $A$, the equivalence class of $a∈A$ is:
$[a]_{θ}:={b∈A∣bθa}$Modular Congruency
Integers $a$ and $b$ are congruent modulo $m$ ($a≡b(modm)$) if $m$ divides $(a−b)$.
$a≡_{m}b⟺m∣(a−b)$ $[a]_{≡_{m}}={…,a−2m,a−m,a,a+m,a+2m,…}$Example:
$[0]_{≡_{3}}={…,−6,−3,0,3,6,…}$Partition of a Set
An equivalence relation divides a set into distinct, nonoverlapping 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 nonempty subsets of $A$ such that:
 Nonoverlapping: No two subsets have elements in common.
 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/θ$ (read as “A modulo theta” or “A mod theta”), arises when you have a set $A$ and an equivalence relation $θ$ defined on it. Remember, an equivalence relation partitions the set $A$ into distinct, nonoverlapping 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 $θ$ on $A$, the quotient set $A/θ$ is defined as:
$A/θ={[a]_{θ}∣a∈A}$where $[a]_{θ}$ represents the equivalence class of element $a$ under the relation $θ$. Recall that an equivalence class $[a]_{θ}$ is the set of all elements in $A$ that are related to $a$ by $θ$:
$[a]_{θ}={b∈A∣bθa}$Example: Modular Arithmetic
Let $A=Z$ (the set of integers) and let $θ$ be the congruence modulo 3 relation, denoted $≡_{3}$. This means that two integers $a$ and $b$ are related ($a≡_{3}b$) if their difference is divisible by 3:
$a≡_{3}b⟺3∣(a−b)$This equivalence relation divides the integers into three distinct equivalence classes:
 $[0]_{≡_{3}}={…,−6,−3,0,3,6,…}$ (integers divisible by 3)
 $[1]_{≡_{3}}={…,−5,−2,1,4,7,…}$ (integers leaving a remainder of 1 when divided by 3)
 $[2]_{≡_{3}}={…,−4,−1,2,5,8,…}$ (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 $Z/≡_{3}$ is then the set of these equivalence classes:
$Z/≡_{3}={[0]_{≡_{3}},[1]_{≡_{3}},[2]_{≡_{3}}}$So, the quotient set in this case has only three elements, even though the original set $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=Z×(Z∖{0})$, and define the relation $(a,b)∼(c,d)⟺ad=bc$. We aim to prove that $∼$ is an equivalence relation by verifying the three required properties: reflexivity, symmetry, and transitivity.
Reflexiv:
Rigorous:
 $(a,b)∼(a,b)⟺˙ ab=ba$ (Definition of $∼$)
 $⟺˙ ab=ab$ (Commutativity of multiplication)
Simple: To show that $(a,b)∼(a,b)$:
 By the definition of $∼$, we have $(a,b)∼(a,b)⟺ab=ba$, which is trivially true because multiplication is commutative.
Symmetry:
Simple: To show that if $(a,b)∼(c,d)$, then $(c,d)∼(a,b)$:
 Assume $(a,b)∼(c,d)$, meaning $ad=bc$.
 Rearranging this, we get $bc=ad$, which is exactly the condition for $(c,d)∼(a,b)$.
 Therefore, symmetry holds.
Transitivity:
Rigorous:
 Given: (1): $(a,b)∼(c,d)$; (2): $(c,d)∼(e,f)$
 To prove: (1)(2) $⟹(a,b)∼(e,f)$ (S)
 (3): (1) $⟺˙ ad=bc$ (Definition of $∼$)
 (4): (2) $⟺˙ cf=de$ (Same as above)
 (5): (3),(4) $⟹˙ adcf=bcde$ (Multiplication is a common function)
 (6): (5) $⟹˙ acf=bce$ (cancel $d=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⟹˙ acf=bce=0$ (if $c=0$ then trivially the latter is true)
 (8): $c=0⟹˙ $ (6) $⟹af=be$ (cancel $c=0$)
 (9): (7) and (3) $⟹˙ a=0$ (since $d=0$)
 (10): (7) and (4) $⟹˙ e=0$ (since $d=0$)
 (11): (7) and (10) $⟹˙ af=be$ (since both $a=e=0$)
 (12): (8) or (11) $⟹˙ af=eb$
Simple: To show that if $(a,b)∼(c,d)$ and $(c,d)∼(e,f)$, then $(a,b)∼(e,f)$:

Assume $(a,b)∼(c,d)$ and $(c,d)∼(e,f)$. This means:
 $ad=bc$
 $cf=de$

We want to prove that $(a,b)∼(e,f)$, i.e., $af=be$. To do this:
 Multiply the two conditions: $ad⋅cf=bc⋅de$
 This simplifies to: $acf=bce$
 Now, cancel $c$ (if $c=0$), and we are left with $af=be$, which is the desired condition for $(a,b)∼(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 $∼$ 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 nonzero):
$Q=(Z×(Z∖{0}))/∼$This means each rational number corresponds to an equivalence class $[(a,b)]$ where $a$ and $b$ are integers, and $b=0$, under the relation $(a,b)∼(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:

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

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

Transitive: For all elements $x$, $y$, and $z$, if $(x,y)∈R$ and $(y,z)∈R$, then $(x,z)∈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” $≤$) 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≺b$ is used to indicate that $a$ strictly precedes $b$ in the partial order. This means that $a⪯b$ but $a=b$ (i.e., $a$ is not equal to $b$).
 Formally, we write: $a≺b⟺a⪯b∧a=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 $≺$
Is $≺$ transitive? Answer: Yes, but we need to prove it.
Proof:

Given:
 (1): $a≺b$
 (2): $b≺c$
 We need to prove that $(1)$ and $(2)$ imply $a≺c$.

Definitions:
 By definition of $≺$, we have: $a≺c⟺(a≤c)∧(a=c)$
Steps to Prove:

Proving $a≤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≤c$

Proving $a=c$:
 From (1), we know $a=b$.
 From (2), we know $b=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⪯bandb⪯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=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=c$
Final Step:
 From the substeps, we have shown that:
 $a≤c$ (from step 1)
 $a=c$ (from step 2)
 Thus, we conclude: $a≺c$
Continue here: 10 Posets, Hasse Diagrams, Lexicographical Ordering, Special Elements, Functions, Countability, Infinities