Ch 4. Relations
4.5 Properties of Binary Relations and Equivalence Relations
A binary relation between two sets is a subset of their Cartesian product. Using our notation in this chapter, for [latex]a \in A[/latex] and [latex]b \in B[/latex], a binary relation [latex]R[/latex] is a set of ordered pairs [latex](a, b)[/latex].
A function between two sets is a special type of binary relation where each element of one set is related to exactly one element of the other set. That is, for every [latex]a \in A[/latex], there exists a unique [latex]b \in B[/latex] such that [latex](a, b) \in f[/latex], where [latex]f[/latex] is a function from a set [latex]A[/latex] to a set [latex]B[/latex].
Note that every function is a binary relation, but not every binary relation is a function.
Example 4.65
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b, c \}[/latex], and define [latex]f = \{ (1, a), (2, b), (3, c) \}[/latex]. This is a function because each element in [latex]A[/latex] is related to (or maps) to exactly one element in [latex]B[/latex].
Let [latex]R = \{ (1, a), (1, b), (2, c) \}[/latex]. This is not a function because [latex]1[/latex] is related to both [latex]a[/latex] and [latex]b[/latex].
The domain of a function is the set of all inputs. That is, for [latex]f: A \rightarrow B, \text{Dom}(f) =[/latex] the set of all inputs from [latex]A[/latex].
The codomain of a function is the set of all possible outputs. That is, [latex]\text{Cod}(f) = B[/latex].
The range of a function is the set of actual outputs. That is, [latex]\text{Ran}(f) = \{ f(a) \mid a \in A \} \subseteq B[/latex].
Example 4.66
Let [latex]f: \{ 1, 2, 3 \} \rightarrow \{ a, b, c, d \}[/latex] be defined by [latex]f = \{ (1, a), (2, b), (3, c) \}[/latex]. The domain is [latex]\{ 1, 2, 3 \}[/latex], the codomain is [latex]\{ a, b, c, d \}[/latex], and the range is [latex]\{ a, b, c \}[/latex].
An arrow diagram visually represents a function or relation by drawing arrows from elements in set [latex]A[/latex] to elements in set [latex]B[/latex].
Example 4.67
Let [latex]f = \{ (1, a), (2, b), (3, c) \}[/latex]. The arrow diagram is shown in the figure below.
The graph of a function is the set of ordered pairs [latex](a, f(a))[/latex]. It is a visual or tabular representation of the function.
Example 4.68
If [latex]f(x) = x^{2}[/latex], then the graph includes points like [latex](1, 1), (2, 4), (3, 9)[/latex].
The modulus operator (mod) returns the remainder when one number is divided by another. In IT, it is used in hashing, cyclic structures, and cryptography.
Formally, for any integers [latex]a[/latex] and [latex]b[/latex] (with [latex]b > 0[/latex]), the expression [latex]a \text{ mod } b[/latex] gives the remainder when [latex]a[/latex] is divided by [latex]b[/latex].
Example 4.69
17 mod 5 = 2. This means that when 17 is divided by 5, 2 is left over.
Example 4.70
A hash table stores key and value pairs, such as a student ID corresponding to a student record, using hash functions that map keys to array indices. It is important to check that a hash value fits within the bounds of the array, and this is achieved using the modulus operator. For example,
index = hash(key) mod table_size
If hash(“apple”) = 12345 and the table size is 100, then 12345 mod 100 = 45. So, “apple” is stored at index 45.
In Section 3.6, floor and ceiling functions were introduced. They were defined as
[latex]\text{floor}(x) = \lfloor x \rfloor[/latex]: the greatest integer [latex]\leq x[/latex]
[latex]\text{ceiling}(x) = \lceil x \rceil[/latex]: the smallest integer [latex]\geq x[/latex]
Example 4.71
The floor of [latex]3.7[/latex] is [latex]\lfloor 3.7 \rfloor = 3[/latex]. The ceiling of [latex]3.7[/latex] is [latex]\lceil 3.7 \rceil = 4[/latex].
Example 4.72
In systems like round-robin CPU scheduling and rotating backups, tasks repeat in cycles. To determine the current task or time slot
current_slot = (current_time / slot_duration) mod num_slots
If each slot is 5 minutes and there are 4 slots, then at minute 17
[latex]\left\lfloor \frac{17}{5} \right\rfloor = 3 \Rightarrow 3 \text{ mod } 4 = 3[/latex]
The system is in slot 3.
Recall the Quotient-Remainder Theorem (Theorem 3.4):
For any integer [latex]a[/latex] and positive integer [latex]d[/latex], there exist unique integers [latex]q[/latex] and [latex]r[/latex] such that
[latex]a = dq + r[/latex], where [latex]0 \leq r < d[/latex]
The concepts of modulus operators and floor and ceiling functions can be demonstrated using this theorem.
Example 4.73
Let [latex]a = 17[/latex] and [latex]d = 5[/latex]. Then
[latex]17 = 5 \cdot 3 + 2[/latex]
So, [latex]q = 3, r = 2, \left\lfloor \frac{17}{5} \right\rfloor = 3[/latex], and [latex]17 \text{ mod } 5 = 2[/latex].
Example 4.74
Modular arithmetic is fundamental in public-key cryptography (e.g., RSA). In RSA, encryption and decryption involve exponentiation modulo a large number.
[latex]c = m^{e} \text{ mod } n[/latex]
If [latex]m = 42[/latex], [latex]e = 3[/latex], and [latex]n = 55[/latex], then [latex]c = 42^{3} \text{ mod } 55 = 74,088 \text{ mod } 55 = 3[/latex]. This allows secure encryption and decryption using modular arithmetic, which is computationally efficient and secure.
We now look at the following five properties of functions:
- injective
- surjective
- bijective
- inverse
- composition
The first property for a function is that it is injective (or one-to-one) if no two elements in the domain relate to the same element in the codomain. We write this as [latex]f: A \rightarrow B[/latex] is injective if
[latex]\forall a_{1}, a_{2} \in A, f(a_{1}) = f(a_{2}) \rightarrow a_{1} = a_{2}[/latex]
Example 4.75
Let [latex]f(x) = 2x + 1[/latex], where [latex]f: \mathbb{R} \rightarrow \mathbb{R}[/latex]. This is injective because different inputs yield different outputs.
Example 4.76
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ 3, 5, 7 \}[/latex], and define [latex]f = \{ (1, 3), (2, 5), (3, 7) \}[/latex]. The arrow diagram in the figure below shows that each input relates to a unique output.
Example 4.77
Claim
[latex]f(x) = 3x + 2[/latex] is injective.
Proof
Assume [latex]f(x_{1}) = f(x_{2})[/latex]. Then [latex]3x_{1} + 2 = 3x_{2} + 2 \rightarrow x_{1} = x_{2}[/latex], so [latex]f[/latex] is injective.
[latex]\square[/latex]
A function is not injective if two or more distinct inputs relate to the same output. Formally, a function [latex]f: A \rightarrow B[/latex] is not injective if
[latex]\exists a_{1}, a_{2} \in A, a_{1} \neq a_{2} \rightarrow f(a_{2}) = f(a_{2})[/latex]
Example 4.78
Let [latex]f(x) = x^{2}[/latex], where [latex]f: \mathbb{R} \rightarrow \mathbb{R}[/latex]. Then [latex]f(2) = 4[/latex] and [latex]f(-2) = 4[/latex], so [latex]f[/latex] is not injective.
Example 4.79
Let [latex]A = \{ -2, 2 \}[/latex], [latex]B = \{ 4 \}[/latex], and define [latex]f = \{ (-2, 4), (2, 4) \}[/latex]. In the arrow diagram in the figure below, two arrows from different input points point at the same output, demonstrating that [latex]f[/latex] is not injective.
Example 4.80
Claim
[latex]f(x) = x^{2}[/latex] is not injective.
Proof
Assume [latex]x_{1} = -2[/latex] and [latex]x_{2} = 2[/latex]. Then [latex]f(-2) = f(2) = 4[/latex], but [latex]-2 \neq 2 \Rightarrow f[/latex] is not injective.
[latex]\square[/latex]
The second property of a function is that it is surjective (or onto) if every element of the codomain is related to at least one element of the domain. We write this as [latex]f: A \rightarrow B[/latex] is surjective if
[latex]\forall b \in B, \exists a \in A[/latex] such that [latex]f(a) = b[/latex]
Example 4.81
Let [latex]f(x) = x^{3}[/latex], where [latex]f: \mathbb{R} \rightarrow \mathbb{R}[/latex]. Every real number has a cube root, so [latex]f[/latex] is surjective.
Example 4.82
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b \}[/latex], and define [latex]f = \{ (1, a), (2, b), (3, a) \}[/latex]. The arrow diagram in the figure below shows that every element of [latex]B[/latex] is mapped to.
Example 4.83
Claim: [latex]f(x) = 2x + 1[/latex] is surjective from [latex]\mathbb{R} \rightarrow \mathbb{R}[/latex].
Proof: Let [latex]y \in \mathbb{R}[/latex] and solve [latex]y = 2x + 1[/latex]. Then [latex]x = \frac{y – 1}{2} \in \mathbb{R}[/latex] and [latex]f[/latex] is surjective.
[latex]\square[/latex]
A function [latex]f: A \rightarrow B[/latex] is not surjective if
[latex]\exists b \in B[/latex], such that [latex]\nexists a \in A[/latex] with [latex]f(a) = b[/latex]
This means some elements in the codomain are not related to.
Example 4.84
Let [latex]f(x) = x^{2}[/latex], where [latex]f: \mathbb{R} \rightarrow \mathbb{R}[/latex]. There is no [latex]x \in \mathbb{R}[/latex] such that [latex]f(x) = -1[/latex], so [latex]f[/latex] is not surjective.
Examples 4.85
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ 1, 4, 9, 16 \}[/latex], and define [latex]f = \{ (1, 1), (2, 4), (3, 9) \}[/latex]. In the arrow diagram in the figure below, the element [latex]16[/latex] in [latex]B[/latex] is not mapped to.
Example 4.86
Claim
[latex]f(x) = x^{2}[/latex] is not surjective from [latex]\mathbb{R} \rightarrow \mathbb{R}[/latex].
Proof
Let [latex]y = -1 \in \mathbb{R}[/latex]. There is no real [latex]x[/latex] such that [latex]x^{2} = -1 \Rightarrow f[/latex] is not surjective.
[latex]\square[/latex]
The third property of a function is that it is bijective if it is both injective and surjective.
Example 4.87
Let [latex]f(x) = x + 1[/latex], where [latex]f: \mathbb{Z} \rightarrow \mathbb{Z}[/latex]. It is both injective and surjective.
Example 4.88
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b, c \}[/latex], and define [latex]f = \{ (1, a), (2, b), (3, c) \}[/latex]. In the arrow diagram in the figure below, each element in [latex]A[/latex] maps to a unique element in [latex]B[/latex], and all elements in [latex]B[/latex] are used.
Example 4.89
Claim
[latex]f(x) = 5x - 4[/latex] is bijective.
Proof: If [latex]f(x_{1}) = f(x_{2})[/latex], then [latex]x_{1} = x_{2}[/latex] so [latex]f[/latex] is injective. For any [latex]y, x = \frac{y+4}{5} \in \mathbb{R}[/latex] so [latex]f[/latex] is surjective.
[latex]\square[/latex]
The fourth property of a function is that if [latex]f: A \rightarrow B[/latex] is bijective, then the inverse function [latex]f^{-1}: B \rightarrow A[/latex] satisfies [latex]f^{-1}(f(a)) = a[/latex].
Example 4.90
If [latex]f(x) = 2x + 3[/latex], then [latex]f^{-1}(y) = \frac{y - 3}{2}[/latex].
Example 4.91
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ 5, 7, 9 \}[/latex], and [latex]f = \{ (1, 5), (2, 7), (3, 9) \}[/latex]. Then the inverse function [latex]f^{-1}[/latex] is [latex]f^{-1} = \{ (5, 1), (7, 2), (9, 3) \}[/latex]. The arrow diagram shown in the figure below reverses the arrows of the original function.
Example 4.92
Claim
Let [latex]f(x) = 3x - 4[/latex]. Then [latex]f^{-1}(x) = \frac{x+4}{3}[/latex] is the inverse.
Proof
First, show [latex]f^{-1}(f(x)) = x[/latex].
[latex]f^{-1}(f(x)) = f^{-1}(3x - 4) = \frac{(3x – 4) + 4}{3} = \frac{3x}{3} = x[/latex]
Then, show [latex]f(f^{-1}(x)) = x[/latex].
[latex]f(f^{-1}(x)) = f\left( \frac{x+4}{3} \right) = 3 \cdot \frac{x+4}{3} - 4 = x + 4 - 4 = x[/latex]
Both conditions are satisfied, so [latex]f^{-1}(x) = \frac{x+4}{3}[/latex] is indeed the inverse of [latex]f(x) = 3x - 4[/latex].
[latex]\square[/latex]
The fifth property of a function is that given [latex]f: A \rightarrow B[/latex], and [latex]g: B \rightarrow C[/latex], the composition of [latex]f[/latex] and [latex]g[/latex], denoted [latex]g \circ f: A \rightarrow C[/latex] is defined by
[latex](g \circ f)(x) = g(f(x))[/latex]
Example 4.93
Let [latex]f(x) = x + 1[/latex] and [latex]g(x) = 2x[/latex]. Then [latex](g \circ f)(x) = 2(x + 1) = 2x + 2[/latex].
Example 4.94
Here, we will see how to visualize a function's composition. Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b, c \}[/latex], and [latex]C = \{ x, y, z \}[/latex]. Define the functions [latex]f: A \rightarrow B[/latex] and [latex]g: B \rightarrow C[/latex] as follows:
[latex]f = \{ (1, a), (2, b), (3, c) \}, \quad g = \{ (a, x), (b, y), (c, z) \}[/latex]
Note that if [latex]g[/latex] is evaluated at [latex]f(1)[/latex], then [latex]g(f(1)) = g(a) = x[/latex]. Similarly, [latex]g(f(2)) = y[/latex] and [latex]g(f(3)) = z[/latex].
Then the composition [latex]g \circ f: A \rightarrow C[/latex] is [latex]g \circ f = \{ (1, x), (2, y), (3, z) \}[/latex]. The arrow diagram below visualizes this function.
Example 4.95
Claim
Let [latex]f(x) = x + 1[/latex] and [latex]g(x) = 2x[/latex]. Then [latex]g \circ f[/latex] is a function.
Proof
We can show that [latex]g \circ f[/latex] is a function by proving that it is well-defined and has a unique output. First, note that
[latex](g \circ f)(x) = g(f(x)) = g(x + 1) = 2(x + 1) = 2x + 2[/latex]
This function is well-defined since for every [latex]x \in \mathbb{R}, f(x) \in \mathbb{R}[/latex], and [latex]g(f(x)) \in \mathbb{R}[/latex]. This function has a unique output since both [latex]f[/latex] and [latex]g[/latex] are functions; their composition is also a function.
[latex]\square[/latex]
Binary and unary operators are fundamental in IT and computer science because they are the building blocks of how computers perform operations on data.
An operator that acts on two operands is called a binary operator. It takes two outputs and combines them to produce a result. Examples of binary operators are addition, multiplication, modulus, logical AND ([latex]\land[/latex]) and set union ([latex]\cup[/latex]).
Example 4.96
An operator that acts on a single operand is called a unary operator. It modifies or evaluates that one input. Examples of unary operators are negation, logical NOT ([latex]\neg[/latex]), absolute value, floor function, and ceiling function.
Example 4.97
For [latex]-7[/latex], [latex]-[/latex] is a unary operator applied to [latex]7[/latex].
We conclude this section with the concept of equivalence relations. Equivalence relations are foundational in classification, clustering, database normalization, and version control.
Recall from Section 4.2 the definitions of reflexive, symmetric, antisymmetric, and transitive. Let [latex]R \subseteq A \times A[/latex] be a relation on a set [latex]A[/latex]. Then [latex]R[/latex] is
reflexive if [latex]\forall a \in A, (a, a) \in R[/latex]
symmetric if [latex]\forall a, b \in A, (a, b) \in R \rightarrow (b, a) \in R[/latex]
antisymmetric if [latex]\forall a, b \in A, (a, b) \in R \land (b, a) \in R \rightarrow a = b[/latex]
transitive if [latex]\forall a, b, c \in A, (a, b) \in R \land (b, c) \in R \rightarrow (a, c) \in R[/latex]
An equivalence relation on a set [latex]A[/latex] is a relation [latex]R \subseteq A \times A[/latex] that is reflexive, symmetric, and transitive.
This type of relation partitions the set [latex]A[/latex] into equivalence classes (see Section 4.6), where each class contains elements that are all related to each other under [latex]R[/latex].
Example 4.98
Let [latex]A = \{ 1, 2, 3, 4 \}[/latex], and define a relation [latex]R \subseteq A \times A[/latex] as
[latex]R = \{ (1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1) \}[/latex]
To see if [latex]R[/latex] is an equivalent relation, we check to see if it is reflexive, symmetric, and transitive. Notice that all [latex](a, a) \in R[/latex], so [latex]R[/latex] is reflexive. For the element [latex](1, 3) \in R[/latex], we also have [latex](3, 1) \in R[/latex], so [latex]R[/latex] is symmetric. For the elements [latex](1, 3), (3, 1) \in R[/latex], we also have [latex](1, 1) \in R[/latex], so [latex]R[/latex] is transitive. We can conclude that [latex]R[/latex] is an equivalent relation.
Example 4.98
Let [latex]A = \{ 1, 2, 3, 4 \}[/latex], [latex]B = \{ a, b \}[/latex], and define [latex]f = \{ (1, a), (2, b), (3, a), (4, b) \}[/latex]. We can define a relation [latex]R_{f}[/latex] on [latex]A[/latex] by
[latex](a, b) \in R_{f}[/latex] if and only if [latex]f(a) = f(b)[/latex]
Then [latex]R_{f} = \{ (1, 1), (1, 3), (3, 1), (3, 3), (2, 2), (2, 4), (4, 2), (4, 4) \}[/latex]. This can be verified as an equivalent relation by using the method in Example 4.98.
Real-World Example 4.5: File Type Grouping
When working with an operating system or cloud storage system, you will find that files are grouped by type using their extensions. Let [latex]F[/latex] be the set of all files, and define a relation [latex]R[/latex] on [latex]F[/latex] such that
[latex](f_{1}, f_{2}) \in R[/latex] if and only if [latex]\text{filetype}(f_{1}) = \text{filetype}(f_{2})[/latex]
This relation is reflexive, since every file has the same type as itself. It is symmetric, since if [latex]f_{1}[/latex] has the same type as [latex]f_{2}[/latex], then [latex]f_{2}[/latex] has the same type as [latex]f_{1}[/latex]. It is transitive, since if [latex]f_{1}[/latex] and [latex]f_{2}[/latex] have the same type, and [latex]f_{2}[/latex] and [latex]f_{3}[/latex] have the same type, then [latex]f_{1}[/latex] and [latex]f_{3}[/latex] do too. Thus, [latex]R[/latex] is an equivalence relation, and the equivalence classes correspond to file type groups (e.g., all .pdf files, all .jpg files, etc.).
