6. Partial Ordering and Mathematical Induction¶

³ Relations¶

Let A and B be sets. A relation from A to B is a subset of the Cartesian product A x B, we denote it by R.
- R = {(a, b) | a ∈ A and b ∈ B}
- R ⊆ A x B
- a R b denotes (a, b) ∈ R
- a \(\not{R}\) b denotes (a, b) ∉ R
Relation on A: A relation from A to A.
- R ⊆ A x A
- Example Let Rel = {(a,b,) | a divides b} on the set A={1,2,3,4,5,6}
  - Rel={(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6)}
The number of relations on a set A = |P(A x A)| = 2^(n^2)
- Let |A| = n, then |A x A| = n^2
- The number of subsets of A is equal to |P(A)| = 2^n, where P(A) is the power set of A
- The number of subsets of A x A is 2^(n^2) which is the cardinality of the power set of A x A or |P(A x A)|
- The number of relations on A is 2^(n^2)
Relation summary
Relation representation ⁶

⁴ Reflexive Relation¶

Reflexive Relation:
- \(\forall a \in A, aRa\)
- \(\forall a \in A, (a,a) \in R\)
- A relation R on a set A is reflexive if a R a for all a ∈ A.
- Every element in the set is related to itself.
Example Let Rel1={(1,1), (2,2), (3,3), (4,4)} on the set A={1,2,3,4}
- We can see that every element in the set is related to itself (belongs to the relation with itself), thus it is reflexive.
Example Let Rel2 = {(a,b,) | a divides b} on the set A={1,2,3,4}
- Rel2={(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), (3,3), (3,6), (4,4))}
- Rel2 is reflexive because every element in the set is related to itself.
Example Let Rel3={(1,2), (2,1), (2,2), (3,1), (4,4)} on the set A={1,2,3,4}
- Rel3 is not reflexive because 3 is not related to itself.

⁴ Irreflexive Relation¶

Irreflexive Relation:
- \(\forall a \in A, \neg(aRa)\)
- \(\forall a \in A, (a,a) \notin R\)
- A relation R on a set A is irreflexive if a \(\not{R}\) a for all a ∈ A.
- No element in the set is related to itself.
Example on the set A={1,2,3}
- Let Rel4={(1,2), (2,1), (2,2), (3,1), (3,2)} is Not irreflexive because 2 is related to itself.
- Let Rel5={(1,2), (2,1), (3,1), (3,2)} is irreflexive because no element is related to itself.

⁴ Symmetric Relation¶

Symmetric Relation:
- \(\forall (a,b) \in A, aRb \implies bRa\)
- \(\forall (a,b) \in A, (a,b) \in R \implies (b,a) \in R\)
- A relation R on a set A is symmetric if a R b implies b R a for all a, b ∈ A.
- If a is related to b, then b is related to a for all a, b ∈ A.
Example on the set A={1,2,3}
- Let Rel6={(1,2), (2,1), (2,2), (3,2), (2,3), (3,3)} is symmetric because:
  - Each pair (a,b) has a corresponding pair (b,a) in the relation.
  - (1,2) has (2,1). (2,2) has (2,2). (3,2) has (2,3). (3,3) has (3,3).
- Let Rel7={(1,2), (2,1), (3,1), (3,2)} is Not symmetric because:
  - Not every pair has a corresponding pair in the relation.
  - Exactly, pairs (3,1) and (3,2) do not have a corresponding pair in the relation.
  - Notice that (1,2)§ has (2,1), but this is not enough to make the relation symmetric.

⁴ Antisymmetric Relation¶

Antisymmetric Relation:
- \(\forall (a,b) \in A, aRb \land bRa \implies a=b\)
- \(\forall (a,b) \in A, (a,b) \in R \land (b,a) \in R \implies a=b\)
- For every pair of distinct elements a and b in A, if a is related to b and b is related to a, then a must equal b.
- Whenever we have the pair (a,b) in R, we cannot have the pair (b,a) in R unless a=b.
Example Let Rel8={(1,1), (2,1)} on A={1,2,3}
- Rel8 is antisymmetric because the pair (2,1) is not in the relation.
- The pair (1,1) is fine because a=b.
- If the pair (2,1) was in the relation, then the relation would not be antisymmetric because a would not equal b and we still have both (1,2) and (2,1) in the relation.
Example Let Rel9={(2,1), (1,2), (1,1)} on A={1,2,3}
- Rel9 is Not antisymmetric because the pair (1,2) is in the relation, although 1 ≠ 2.

⁵ Transitive Relation¶

Transitive Relation:
- \(\forall (a,b,c) \in A, (a,b) \in R \land (b,c) \in R \implies (a,c) \in R\)
- \(\forall (a,b,c) \in A, aRb \land bRc \implies aRc\)
- If the pair (a,b) and the pair (b,c) are in the relation, then the pair (a,c) must be in the relation to be transitive.
Example Let Rel10={(2,1), (3,1), (3,2), (4,4)}
- Notice that (a,b) = (3,2) and (b,c) = (2,1) are in the relation, and (a,c) = (3,1) is also in the relation.
- The pair (4,4) is fine because a=c.
- Thus, Rel10 is transitive.
Example Let Rel11={(2,1), (1,3)}
- Notice that (a,b) = (1,2) and (b,c) = (1,3) are in the relation, but (a,c) = (2,3) is not in the relation.
- Thus, Rel11 is Not transitive.

⁵ Asymmetric Relation¶

Asymmetric Relation:
- \(\forall (a,b) \in A, aRb \implies \neg(bRa)\)
- \(\forall (a,b) \in A, (a,b) \in R \implies (b,a) \notin R\)
- A relation R on a set A is asymmetric if a R b implies b R a for all a, b ∈ A.
- If a is related to b, then b is not related to a for all a, b ∈ A.
- If pair (a,b) is in the relation, then the pair (b,a) must not be in the relation.
Example Rel12={(1,1), (1,2), (1,3)} on A={1,2,3}
- Thus, Rel12 is NOT asymmetric, because of the pair (a,b) = (1,1) is in the relation, and the pair (b,a) = (1,1) is also in the relation.

¹ ⁷ Equivalence Relations¶

Equivalence relation is a tool that helps us categorize or group elements in a set based on a particular characteristic that defines the sameness among them.
A relation is equivalence if it is: reflexive, symmetric, and transitive and is denoted by ~.
- Reflexive: Every element a in the set, the pair (a,a) is in the relation.
- Symmetric: For each pair (a,b) in the relation, the pair (b,a) is also in the relation.
- Transitive: If (a,b) and (b,c) are in the relation, then (a,c) is also in the relation.
Example: Let’s consider the set of all people in the world.
- We can define an equivalence relation, “being of the same age”.
- This relation is reflexive (you are of the same age as yourself),
- symmetric (if you are of the same age as someone else, that person is also of the same age as you)
- transitive (if you are the same age as person A, and person A is the same age as person B, then you are of the same age as person B).
- Using this relation, we can divide the set of all people into equivalence classes. Each class contains people who are of the same age. So, all people born in the same year belong to the same class, because they are “equivalent” in terms of their age.

² ⁹ Partial Ordering¶

A relation is R on a set S is a partial ordering if it is: reflexive, antisymmetric, and transitive.
- Reflexive: For Each element a, the pair (a,a) is in the relation.
- Antisymmetric: if the pair (a,b) is in the relation, then the pair (b,a) is not in the relation unless a=b.
- Transitive: if the pair (a,b) and the pair (b,c) are in the relation, then the pair (a,c) is also in the relation.
POSET: Set S with a relation R that is a partial ordering.
Partial in partial ordering means that not every pair of elements in S is comparable.
- Comparable: a R b or b R a
- Incomparable: Neither a R b nor b R a

⁸ Congruence Modulo m¶

Two integers a and b are said to be congruent modulo m if a%m = b%m and denoted by \(a \equiv b (mod m)\) iff m divides (a-b).

Summary¶

Name	Meaning	English * (approximation, not very accurate)
Reflexive	\(∀a∈A,(a,a)∈R\)	Every element in the set is related to itself
Irreflexive	\(\forall a∈A,(a,a)∉R\)	No element in the set is related to itself
Symmetric	\(∀ (a,b) \in A, (b,a) ∈ A\)	If a is related to b, then b is related to a
Antisymmetric	\(∀ (a,b) \in A, (a,b) ∈ R \land (b,a) ∈ R \implies a=b\)	If a is related to b and b is related to a, then a must equal b
Transitive	\(\forall (a,b,c) \in A, (a,b) \in R \land (b,c) \in R \implies (a,c) \in R\)	If a is related to b and b is related to c, then a is related to c

Relation Type	Reflexive	Transitive	Symmetric	Antisymmetric
Equivalence	Yes	Yes	Yes
Partial order	Yes	Yes		Yes

References¶

Discrete Math - 9.5.1 Equivalence Relations. https://www.youtube.com/watch?v=ZgcTX16borA ↩
Introduction to Partial Ordering. https://www.youtube.com/watch?v=saAkSk_arPA ↩
Introduction to Relations https://www.youtube.com/watch?v=4Caxyh0zt_o&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=100 ↩
Types of Relations 1. https://www.youtube.com/watch?v=GvNGf9Gki7o&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=100 ↩↩↩↩
Types of Relations 2. https://www.youtube.com/watch?v=O19RpfoxQpA&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=101 ↩↩
Relation representation https://www.youtube.com/watch?v=U3wEJbqQziE&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=108 ↩
Equivalence Relation https://www.youtube.com/watch?v=cJ9x3aWibhI&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=116 ↩
Congruence Modulo m. https://www.youtube.com/watch?v=-SpWfD4WsmM&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=121 ↩
Introduction to Partial Ordering. https://www.youtube.com/watch?v=saAkSk_arPA&list=PLBlnK6fEyqRhqJPDXcvYlLfXPh37L89g3&index=125 ↩

6. Partial Ordering and Mathematical Induction¶

3 Relations¶

4 Reflexive Relation¶

4 Irreflexive Relation¶

4 Symmetric Relation¶

4 Antisymmetric Relation¶

5 Transitive Relation¶

5 Asymmetric Relation¶

1 7 Equivalence Relations¶

2 9 Partial Ordering¶

8 Congruence Modulo m¶

Summary¶

References¶

³ Relations¶

⁴ Reflexive Relation¶

⁴ Irreflexive Relation¶

⁴ Symmetric Relation¶

⁴ Antisymmetric Relation¶

⁵ Transitive Relation¶

⁵ Asymmetric Relation¶

¹ ⁷ Equivalence Relations¶

² ⁹ Partial Ordering¶

⁸ Congruence Modulo m¶