2024-01-22 13:19:04 -04:00
|
|
|
Lecture Topic: Relation examples
|
|
|
|
|
|
|
|
|
|
# Relation Example 1
|
|
|
|
|
$R = \{(i,j) | i \in \mathbb{Z}, j \in \mathbb{Z}, i-j =5n \text{ for some integer n}\}$
|
|
|
|
|
e.g $(22,7) \in R$ because $22-7 = 5(3)$
|
|
|
|
|
e.g $(7,22) \in R$ because $7-22 = -15 = 5(-3)$
|
|
|
|
|
e.g $(22,9) \notin R$ because $22-9 = 13$, which is not a multiple of 5
|
|
|
|
|
|
|
|
|
|
Reflexive? Yes
|
|
|
|
|
For every integer a, $a-a = 0 = 5(0)$
|
|
|
|
|
Therefor $(a,a) \in R$ for every integer a
|
|
|
|
|
|
|
|
|
|
Symmetric? Yes
|
|
|
|
|
Let a, b be any integer, such that (a,b) is in the relation (can we prove that (b,a) is in relation as well?)
|
|
|
|
|
|
|
|
|
|
Since (a,b) is in the relation, $a-b = 5n$, so, $b-a = -5(n) = 5(-n)$
|
|
|
|
|
Note: $(b-a) = -(a-b)$
|
|
|
|
|
|
|
|
|
|
Transitive? Yes
|
|
|
|
|
Let a,b,c be any integers such that $(a,b) \in R$ and $(b,c) \in R$
|
|
|
|
|
Can we prove that $(a,c) \in R$ ?
|
|
|
|
|
|
|
|
|
|
Since $(a,b) \in R$, we know $a-b=5n$ for some $n \in \mathbb{Z}$
|
|
|
|
|
Since $(b,c) \in R$, we know $b-c=5p$ for some $n \in \mathbb{Z}$
|
|
|
|
|
|
|
|
|
|
Now, $(a-c) = (a-b) + (b-c) = 5n + 5p = 5(np)$
|
|
|
|
|
Therefore, $(a-c) \in R$
|
|
|
|
|
Note: This is an integer because it is the sum of integers
|
|
|
|
|
|
|
|
|
|
# Relation Example 2
|
|
|
|
|
$R = \{(i,j) | i \in \mathbb{R}, j \in \mathbb{R}, i + 2 > j\}$
|
|
|
|
|
|
|
|
|
|
Examples:
|
|
|
|
|
- $(5,2) \in R$ because $(5+2) > 2$
|
|
|
|
|
- $(3,4) \in R$ because $(3+2) > 4$
|
|
|
|
|
- $(0,7) \notin R$ because $(0+2) \ngtr 7$
|
|
|
|
|
|
|
|
|
|
Reflexive? Yes
|
|
|
|
|
Symmetric? No
|
|
|
|
|
Transitive? No
|
|
|
|
|
|
|
|
|
|
Proof: We need to find real numbers where $a,b,c$ where $(a,b) \in R$ and $(b,c) \in R$ but $(a,c) \notin R$
|
|
|
|
|
|
|
|
|
|
For example, a = 1, b = 2, c = 3
|
|
|
|
|
$(1,2) \in R$ because $1+2 > 2$
|
|
|
|
|
$(2,3) \in R$ because $2+2 > 3$
|
|
|
|
|
|
|
|
|
|
But $(1,3) \notin R$ because $(1+2) \ngtr 3$
|
|
|
|
|
$\therefore$ R is not transitive
|
|
|
|
|
|
|
|
|
|
# Equivalence relations
|
|
|
|
|
Equivalence relations have all three of these properties
|
|
|
|
|
Any equivalence relation R on a set A induces a partition of A
|
|
|
|
|
- Splits A into equivalence classes
|
|
|
|
|
- Each class contains elements that are related to themselves and to each other, but to nothing outside the class
|
|
|
|
|
|
|
|
|
|
So, for the above relation:
|
|
|
|
|
$$R = \{(i,j) | i \in \mathbb{Z}, j \in \mathbb{Z}, i-j =5n \text{ for some integer n}\}$$
|
|
|
|
|
This forms an equivalence relation
|
|
|
|
|
|
|
|
|
|
So for the set of all integers, this forms 5 equivalence classes:
|
|
|
|
|
- $..., 0, 5, 10, ...$
|
|
|
|
|
- $..., 1, 6, 11, ...$
|
|
|
|
|
- $..., 2, 7, 12, ...$
|
|
|
|
|
- $..., 3, 8, 13, ...$
|
|
|
|
|
- $..., 4, 9, 14, ...$
|
|
|
|
|
|
|
|
|
|
## Example
|
|
|
|
|
$A = \{-3, -2, -1, 0, 1, 2, 3\}$
|
|
|
|
|
$R = \{(i,j) | i \in \mathbb{A}, j \in \mathbb{A}, i^2 = j^2\}$
|
|
|
|
|
|
|
|
|
|
So the equivalence classes induced by this relation:
|
|
|
|
|
- -3, 3
|
|
|
|
|
- -2, 2
|
|
|
|
|
- -1, 1
|
|
|
|
|
- 0
|
