3.2 KiB
Types of Relations
| Relation | Explanation | Example |
|---|---|---|
| transitive |
"chain reaction", a information about a in relation to c can be inferred from the relations a -> b and b -> c |
a < b, b < c => a < c |
| reflexive | every element is related to itself with the given relation | a <= a, 5 = 5 |
| anti-reflexive | every element is NOT related to itself in the given relation | a < a |
| symmetric | the given relation work both ways | a = b => b = a |
| antisymmetric | the given relation only works both ways if a and b are the same |
a <= b, b <= a => a = b |
Equivalence Relations
A relation R is called equivalence relation when it is transitive, reflexive and symmetric.
Example:
Question: How many equivalence classes are there for the given equivalence relation?
& ~ "on" {0, 1, 2, 3}^(2) \
& "defined by" (x_1, y_1) ~ (x_2, y_2) <==> x_1 + y_1 = x_2 + y_2
[!INFO] Meaning: The pairs
(x_1, y_1)and(x_2, y_2)are equivalent to each other when the components of the pair added up have the same result.
Solving:
- Smallest possible sum:
(0 + 0) = 0 - Biggest possible sum:
(3 + 3) = 6 - All possible sums:
0, 1, 2, 3, 4, 5, 6
Each possible sum creates it's own equivalence class. So there are 7 equivalence classes.
Note
All equivalence classes:
[0]_(~) = {(0, 0)}[1]_(~) = {(0, 1), (1, 0)}[2]_(~) = {(0, 2), (1, 1), (2, 0)}[3]_(~) = {(0, 3), (1, 2), (2, 1), (3, 0)}[4]_(~) = {(1, 3), (2, 2), (3, 1)}[5]_(~) = {(2, 3), (3, 2)}[6]_(~) = {(3, 3)}
Binary Relation
A binary relation is a relation R between exactly two elements a in R and b in R. An example for a binary relation is a <= b
Converse Relation
C^top or C^(-1) is the relation that occurs if the elements of a binary relation are switched.
Composition of Relations - Example
"Compute" Q^top compose R "with:"\
Q = {(2, 2), (3, 3), (2, 1)} \
R = {(1, 2), (3, 3), (3, 1)} \
1. Apply converse to Q:
Q^top = {(2, 2), (3, 3), (1, 2)}
2. Perform Composition:
Look at each pair in R, check if Q^top has a pair starting with se second element in that pair:
(1, 2) -> (2, 2) => (1, 2) \
(3, 3) -> (3, 3) => (3, 3) \
(3, 1) -> (1, 2) => (3, 2)
3. Result:
Q^top compose R = {(1, 2), (3, 2), (3, 3)}
Orders
An Order is a mathematical way to sort, rank or compare elements within a set, where some elements come "before" and "after" others.
A binary relation is called an order if it is...
- [?] a reflexive relation
- [?] a antisymmetric relation
- [?] a transitive relation