4.1 Sets, Their Properties and Applications

Basic Skills

1. Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 3, 4, 5 \}[/latex]. Find
   1. [latex]A \cup B[/latex]
   2. [latex]A \cap B[/latex]
   3. [latex]A - B[/latex]
2. Determine whether the following sets are equal: [latex]A = \{ x \in \mathbb{N} \; | \; x < 5 \}[/latex] and [latex]B = \{ 1, 2, 3, 4 \}[/latex].
3. Let [latex]A = \{ a, b, c, d \}[/latex]. Write the power set of [latex]A[/latex], but only include subsets that contain at least two elements, and do not contain both [latex]a[/latex] and [latex]d[/latex] together.
4. Let [latex]A = \{ 1, \{ 1 \} , \{ 2, 3\} , 4 \}[/latex] and [latex]B = \{ \{ 1 \} , \{ 2, 3 \} \}[/latex].
   1. Is [latex]\{ 1 \} \in A[/latex]?
   2. Is [latex]\{ 1 \} \subseteq A[/latex]?
   3. Is [latex]1 \in A[/latex]?
   4. Is [latex]1 \in B[/latex]?
   5. Is [latex]\{ 2, 3 \} \subseteq A[/latex]?
   6. Is [latex]\{ 2, 3 \} \in A[/latex]?
   7. Is [latex]B \subseteq A[/latex]?
   8. Is [latex]B \in A[/latex]?
5. Let [latex]U = \{ 1, 2, 3, 4, 5 \}[/latex] and [latex]A = \{ 2, 4 \}[/latex]. Find [latex]A^{c}[/latex].

Applications

6. A streaming service tracks users who like action ([latex]A[/latex]), comedy ([latex]C[/latex]), and drama ([latex]D[/latex]). If [latex]A = \{ 1, 2, 3 \}[/latex], [latex]C = \{ 2, 3, 4 \}[/latex], and [latex]D = \{ 3, 4, 5 \}[/latex], find
   1. Users who like all three genres
   2. Users who like only comedy
7. Prove that [latex]A \cap (B \cup C) = (A \cap B) \cup (A \cap C)[/latex] using a Venn diagram.
8. Roster form is a way of representing a set by explicitly listing all of its elements, separated by commas and enclosed in curly braces. Let [latex]A = \{ x \in \mathbb{Z} \; | \; x^{2} < 10 \}[/latex]. Write [latex]A[/latex] in roster form.
9. Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 3, 4, 5 \}[/latex]. Are [latex]A[/latex] and [latex]B[/latex] disjoint? Justify.
10. Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 2, 3, 4 \}[/latex]. Find [latex]A \cup (B - A)[/latex] and interpret the result.

Challenge Problems

11. Let [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], and [latex]D[/latex] be arbitrary sets. Prove the following identity using set identities and laws: [latex]A \cup (B \cap (C \cup D)) = (A \cup B) \cap (A \cup C \cup D)[/latex]
12. Let [latex]A = \{ x \in \mathbb{Z} \; | \; x^{2} < 10 \}[/latex] and [latex]B = \{ x \in \mathbb{Z} \; | \; x \text{ is even } \}[/latex]. Find [latex]A \cap B[/latex] and explain its significance.
13. Let [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex] be subsets of a universal set [latex]U[/latex]. Prove the following identity: [latex](A \cup B \cup C)^{c} = A^{c} \cap B^{c} \cap C^{c}[/latex]
14. Let [latex]A[/latex] be any set, and let [latex]\mathcal{P}(A)[/latex] denote the power set of [latex]A[/latex]. Prove the following two-part statement:
    1. [latex]\emptyset \subseteq A[/latex] for any set [latex]A[/latex]
    2. [latex]\emptyset \in \mathcal{P}(A)[/latex] for any set [latex]A[/latex]
15. Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ 2, 3, 4 \}[/latex], and [latex]C = \{ 3, 4, 5 \}[/latex]. Find [latex](A \cup B) \cap C[/latex] and interpret the result.

4.2 Relations, their Properties and Applications

Basic Skills

16. Let [latex]A = \{ 1, \{ 2 \} \}[/latex] and [latex]B = \{ x, \{ y \} \}[/latex].
    1. List all elements of [latex]A \times B[/latex].
    2. Explain the difference between elements like [latex](1, x)[/latex] and [latex]( \{ 2 \} , \{ y \} )[/latex].
    3. Determine whether [latex]\{ (1, x) \} \subseteq A \times B[/latex].
    4. Determine whether [latex](1, x) \in A \times B[/latex].
17. In graph theory, a strongly connected directed graph is one in which every vertex is reachable from every other vertex via a directed path. Let [latex]A = \{ 1, 2, 3, 4 \}[/latex] and define the relation [latex]R = \{ (1, 2), (2, 3), (3, 1), (2, 2), (4, 4) \}[/latex]. Draw the directed graph for [latex]R[/latex], identify all cycles, and determine whether the graph is strongly connected.
18. Let [latex]R = \{ (1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3) \}[/latex] on [latex]A = \{ 1, 2, 3 \}[/latex]. Determine whether [latex]R[/latex] is reflexive, symmetric, antisymmetric, and/or transitive. For each property, provide a counterexample if it fails, and a justification if it holds.
19. Let [latex]A = \{ a, b, c, d \}[/latex] and define [latex]R = \{ (a, b), (b, c), (c, d), (a, d) \}[/latex].
    1. Represent [latex]R[/latex] as a 4 x 4 matrix using the order [latex][a, b, c, d][/latex].
    2. Draw the directed graph.
    3. Determine whether the matrix is transitive by checking if for all [latex]i, j, k, R_{ij} = 1[/latex] and [latex]R_{jk} = 1[/latex] implies [latex]R_{ik} = 1[/latex]
20. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 1) \}[/latex] on [latex]A = \{ 1, 2, 3, 4 \}[/latex].
    1. Compute the transitive closure [latex]R^{+}[/latex].
    2. Represent the closure as a matrix.
    3. Explain whether the resulting relation is strongly connected and justify your answer.

Applications

21. In a social network, define a relation “follows” on users [latex]A[/latex] = {Aiden, Benjamin, Chloe, Daniel}. Define a relation [latex]F[/latex] where Aiden follows Benjamin and Daniel, Benjamin follows Chloe, Chloe follows Aiden, and Daniel follows no one.
    1. Represent this relation as a directed graph and a 4 x 4 matrix.
    2. Determine whether the graph is strongly connected.
    3. Compute the transitive closure of the relation and interpret what it means in terms of indirect following.
22. Let [latex]R = \{ (a, b), (b, c), (c, d) \}[/latex] and [latex]S = \{ (b, x), (c, y), (d, z) \}[/latex].
    1. Compute [latex]S \circ R[/latex] and list all resulting pairs.
    2. Represent the composition as a directed graph from the domain or [latex]R[/latex] to the codomain of [latex]S[/latex].
    3. Explain how this composition models a real-world scenario, such as a multi-step recommendation system or supply chain.
23. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 1) \}[/latex].
    1. Find the inverse relation [latex]R^{-1}[/latex].
    2. Represent [latex]R[/latex] and [latex]R^{-1}[/latex] as directed graphs.
    3. Represent both as matrices and explain how the matrix of [latex]R^{-1}[/latex] relates to the transpose of the matrix of R (the rows become columns and the columns become rows).
24. Let [latex]E[/latex] = {CEO, Manager, TeamLead, Developer}. Define a relation [latex]R[/latex] where [latex](x, y) \in R[/latex] means “[latex]x[/latex] reports to [latex]y[/latex].”
    1. Define [latex]R[/latex] explicitly using ordered pairs.
    2. Determine whether [latex]R[/latex] is reflexive, symmetric, antisymmetric, and/or transitive.
    3. Compute the transitive closure of [latex]R[/latex] and explain what it represents in terms of indirect reporting.
25. In a cloud-based system, let [latex]U[/latex] = {Aiden, Benjamin, Chloe}, [latex]R[/latex] = {Admin, Editor, Viewer}, and [latex]P[/latex] = {Read, Write, Delete}. Define the relations [latex]A \subseteq U \times R[/latex] and [latex]B \subseteq R \times P[/latex].
    1. Compute the composition [latex]B \circ A[/latex] to determine each user’s effective permissions.
    2. Represent the result as a table mapping users to permissions.
    3. Discuss how this model supports scalability and security in large systems.
    4. Extend the model to include transitive permission inheritance (e.g., Admin inherits Editor’s permission).

Challenge Problems

26. Construct a relation on [latex]A = \{ 1, 2, 3 \}[/latex] that is reflexive and symmetric but not transitive.
27. Prove that the inverse of a symmetric relation is also symmetric.
28. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 1), (2, 2), (4, 4) \}[/latex].
    1. Find the transitive closure of [latex]R[/latex], denoted [latex]R^{+}[/latex].
    2. Explain the process used to compute the closure.
    3. Represent both the original relation and its transitive closure as a directed graph and a relation matrix.
    4. Determine whether the resulting relation is strongly connected.
29. The identity relation on a set [latex]A[/latex] is the relation in which every element is related only to itself, that is, [latex]I_{A} = \{ (a, a) | a \in A \}[/latex]. Show that if a relation is both symmetric and antisymmetric, then it must be a subset of the identity relation.
30. Let [latex]A = \{ 1, 2, 3, 4 \}[/latex] and define the relation [latex]R = \{ (1, 2), (2, 3), (1, 3), (3, 4), (1, 4), (2, 2), (3, 3) \}[/latex].
    1. Determine whether [latex]R[/latex] is transitive. Justify your answer by checking all necessary combinations of pairs. If it is not transitive, identify which pairs are missing to make it transitive.
    2. Represent the relation as a directed graph and explain how the graph helps visualize transitivity.

4.3 Pairs and Tuples and Cartesian Products

Basic Skills

31. Let [latex]A = \{ 1, \{ 2 \} \}[/latex] and [latex]B = \{ x, \{ y \} \}[/latex].
    1. Write out all elements of [latex]A \times B[/latex] and [latex]B \times A[/latex].
    2. Are [latex]A \times B[/latex] and [latex]B \times A[/latex] equal as sets? Why or why not?
32. Let A = [latex]\{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b \}[/latex], and [latex]C = \{ x, y, z \}[/latex].
    1. How many elements are in [latex]A \times B \times C[/latex]?
    2. How many of those 3-tuples contain at least one repeated element (e.g., [latex](1, 1, x)[/latex])?
    3. How many 3-tuples contain only distinct elements, assuming all sets are disjoint?
33. Let [latex]A = \{ 1, 2 \}[/latex], [latex]B = \{ x, y \}[/latex], and [latex]C = \{ a, b \}[/latex].
    1. List all 3-tuples in [latex]A \times B \times C[/latex].
    2. How many of these tuples have a second element equal to “[latex]y[/latex]”?
    3. How many tuples have the first and third elements both being numbers?
34. Let [latex]A[/latex] and [latex]B[/latex] be finite sets with [latex]|A| = 5[/latex], [latex]|B| = 3[/latex], and [latex]A \cap B = \{ 1, 2 \}[/latex].
    1. What is the cardinality of [latex]A \times B[/latex]?
    2. What is the cardinality of [latex](A \cup B) \times (A \cap B)[/latex]?
    3. If [latex]A = B[/latex], how many elements are in [latex]A \times A[/latex] that are of the form [latex](x, x)[/latex]?
35. Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \emptyset[/latex], and [latex]C = \{ x, y \}[/latex].
    1. What is [latex]A \times B \times C[/latex]? Explain the result using the definition of the Cartesian product.
    2. If any one of the sets in a Cartesian product is empty, what is the result? Prove it.

Applications

36. A university database stores student records as 5-tuples: (ID, Name, Major, GPA, EnrollmentStatus).
    1. Construct a tuple for a student named “Liam Smith” with ID 100037777, majoring in Finance, GPA 3.7, and currently enrolled.
    2. Explain how this tuple would differ if the student were on academic probation.
    3. How would the tuple structure change if the university added a sixth field for “Expected Graduation Year”?
37. Complete the following:
    1. Describe how tuples are used to represent rows in a relational database table, and how they relate to the table’s schema.
    2. A foreign key is a column in one table that references the primary key in another table. Given a table schema Employee(ID, Name, Department, Salary, ManagerID), write a valid 5-tuple and explain how foreign key constraints might apply.
    3. Discuss how tuple-level constraints (e.g., GPA must be between 0.0 and 4.0) are enforced in a database system.
38. Let [latex]A[/latex] = {Customer1, Customer2, Customer3} and [latex]B[/latex] = {ProductA, ProductB, ProductC}.
    1. Describe a real-world scenario modelled by [latex]A \times B[/latex], where each pair represents a potential purchase.
    2. Define a relation [latex]R \subseteq A \times B[/latex] that includes only actual purchases.
    3. Represent [latex]R[/latex] as a matrix and explain how this model could be used in a recommendation system.
39. You are given a 5-tuple: (100001023, “Olivia Chen”, “Marketing”, 3.85, “Graduated”).
    1. Identify the likely schema of the table this tuple belongs to.
    2. A composite key is a type of primary key that consists of two or more columns in a database table. Suppose the database enforces a composite key on the (Name, Major) pair. What are the implications for data integrity?
    3. How would you modify the tuple structure to support multiple majors per student?
40. Consider the tuples (123, “Emma Brown”, “CS”, 3.9) and (“Emma Brown”, 123, 3.9, “CS”).
    1. Explain why these are not equivalent, even if they contain the same values.
    2. In a database schema, what risks arise if tuple order is not expected during data entry or retrieval?
    3. Design a tuple-based data structure for a hospital patient record and explain how the order of fields affects interpretation and processing.

Challenge Problems

41. Prove that [latex]|A \times B| = |A| \times |B|[/latex] for finite sets [latex]A[/latex] and [latex]B[/latex].
42. Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ x, y \}[/latex], and [latex]C = \{ a, b \}[/latex].
    1. List all elements of [latex]A \times B \times C[/latex].
    2. Filter the list to include only those 3-tuples where the first element is odd, and the third element is not equal to “[latex]b[/latex]”.
    3. How many such filtered tuples are there?
43. Explain why [latex](a, b) \neq (b, a)[/latex] in general, and give a real-world example where order matters.
44. A database join is an operation in relational databases that combines rows from two or more tables based on a related column between them. Let [latex]A = \{ 1, 2 \}[/latex], [latex]B = \emptyset[/latex]. Prove that [latex]A \times B = \emptyset[/latex] and explain why this is important in database joins.
45. A university maintains a relational database with the following schema: Students = (ID, Name, Major), Courses = (CourseID, Title, Department), Enrollments = (StudentID, CourseID, Grade). Each relation is a set of tuples, and the database enforces the following constraints: (i) No two tuples in the Students or Courses table can have the same ID. (ii) Every StudentID and CourseID in Enrollments must exist in the Students and Courses tables, respectively. (iii) No student can be enrolled in the same course more than once.
    1. Prove that the Enrollments relation is a subset of the Cartesian product: Enrollments [latex]\subseteq[/latex] StudentID x CourseID x Grade
    2. Suppose there are 100 students, 10 courses, and 5 possible grades. What is the maximum possible size of the Cartesian product StudentID x CourseID x Grade?
    3. What is the maximum number of tuples that can legally exist in the Enrollments table under the given constraints?
    4. Explain why the Cartesian product is not used directly to represent the Enrollments table in practice, and how tuples help enforce data integrity in relational databases.

4.4 Domain, Range, Field and Graphical Representation of Relations

Basic Skills

46. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 1), (2, 2), (5, 6) \}[/latex].
    1. Find the domain, range, and field of [latex]R[/latex].
    2. Determine whether [latex]R[/latex] is reflexive, symmetric, or transitive on the set [latex]A = \{ 1, 2, 3, 4, 5, 6 \}[/latex].
    3. Identify isolated elements in the field (elements that appear only once and not in both domain and range).
47. Let R = [latex]\{ (a, b), (b, c), (c, a), (a, a), (b, b) \}[/latex].
    1. Draw the directed graph of [latex]R[/latex].
    2. Identify any cycles in the graph.
    3. Determine whether the graph represents a strongly connected relation (see Exercise 17).
48. Let [latex]R = \{ (x, y), (y, z), (z, x), (x, x) \}[/latex].
    1. What are the domain, range, and field of [latex]R[/latex]?
    2. If [latex]x[/latex], [latex]y[/latex], and [latex]z[/latex] are distinct elements, is [latex]R[/latex] symmetric? Transitive?
    3. What would change if [latex]x = y[/latex]? Recalculate the domain and range.
49. Let [latex]R = \{ (1, 1), (2, 2), (3, 3), (4, 5), (5, 6) \}[/latex].
    1. Find the field of [latex]R[/latex].
    2. Is [latex]R[/latex] reflexive on the set [latex]A = \{ 1, 2, 3, 4, 5, 6 \}[/latex]? Justify.
    3. What additional pairs must be added to make [latex]R[/latex] reflexive on [latex]A[/latex]?
50. You are given the following relation matrix [latex]M[/latex] for a relation [latex]R[/latex] on the set [latex]A = \{ 1, 2, 3, 4 \}[/latex]: [latex]M = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{bmatrix}[/latex]
    1. Extract the ordered pairs in [latex]R[/latex].
    2. Determine the domain, range, and field.
    3. Is the relation reflexive? Transitive?

Applications

51. In a messaging app, define a relation [latex]M \subseteq U \times U[/latex], where [latex](x, y) \in M[/latex] means “[latex]x[/latex] messaged [latex]y[/latex].” Let [latex]M[/latex] = {(Aiden, Benjamin), (Benjamin, Chloe), (Chloe, Aiden), (Aiden, Aiden)}.
    1. Find the domain, range, and field of [latex]M[/latex].
    2. Is the relation reflexive, symmetric, or transitive on the set [latex]U[/latex] = {Aiden, Benjamin, Chloe}?
    3. Construct the transitive closure of [latex]M[/latex] and interpret its meaning in the context of indirect messaging.
52. You are to design a directed graph on a set of 4 users [latex]U = \{ A, B, C, D \}[/latex] such that (i) each user sends exactly one message to another user, (ii) no user messages themselves, and (iii) the graph contains at least one cycle.
    1. Draw the graph and list the relation [latex]R \subseteq U \times U[/latex].
    2. Is the relation symmetric? Transitive?
    3. How many such distinct relations are possible under these constraints?
53. You are designing a relational database with two tables: Users(UserID, Name), Messages(SenderID, ReceiverID, Timestamp)
    1. Explain how the domain and range of the Messages relation relate to the Users table.
    2. If a user appears in the domain but not in the range, what does that imply about their behaviour?
    3. Referential integrity ensures that a foreign key in one table correctly references a primary key in another table. How would you enforce referential integrity between these tables using foreign key constraints?
54. Let [latex]R \subseteq A x A[/latex] be a relation represented by a directed graph.
    1. Explain what a loop represents in terms of reflexivity and real-world behaviour (e.g., self-messaging, self-approval).
    2. Construct a relation on [latex]A = \{ 1, 2, 3 \}[/latex] that is not reflexive, but contains some loops.
    3. Can a relation be transitive without being reflexive? Justify with an example.
55. Suppose you have a directed graph representing a relation [latex]R \subseteq A x A[/latex].
    1. Describe a graph-based method to determine whether [latex]R[/latex] is symmetric.
    2. Construct a relation on [latex]A = \{ x, y, z \}[/latex] that is symmetric but not reflexive.
    3. Construct a relation on [latex]A = \{ x, y, z \}[/latex] that is reflexive but not symmetric.
    4. How would the relation matrix of a symmetric relation differ from that of a non-symmetric one?

Challenge Problems

56. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 1), (2, 2), (3, 3) \}[/latex].
    1. Draw the directed graph of [latex]R[/latex].
    2. Identify the domain, range, and field.
    3. Determine whether the graph is reflexive, symmetric, or transitive on [latex]A = \{ 1, 2, 3, 4 \}[/latex].
    4. In a directed graph, a cycle follows the direction of arrows. Identify any cycles and explain their significance.
57. Prove that the field of a relation [latex]R[/latex] is equal to the union of its domain and range.
58. You are given the following relation matrix for a relation [latex]R[/latex] on the set [latex]A = \{ a, b, c, d \}[/latex]: [latex]M = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{bmatrix}[/latex]
    1. Determine whether [latex]R[/latex] is reflexive.
    2. Is the relation symmetric? Justify using the matrix.
    3. Identify all loops and cycles in the graph.
59. Construct a relation [latex]R \subseteq A \times A[/latex] on the set [latex]A = \{ 1, 2, 3, 4 \}[/latex] such that (i) the graph of [latex]R[/latex] forms a single directed cycle involving all elements and (ii) the relation is not reflexive, not symmetric, but transitive.
60. Let [latex]R = \{ (a, b), (b, c), (c, d), (d, e), (e, a), (f, g) \}[/latex].
    1. Find the domain, range, and field.
    2. Draw the directed graph.
    3. A disconnected component is a group of vertices that can reach each other but cannot reach any vertices outside the group. Identify any disconnected components, whether the graph is strongly connected, and whether the relation is transitive.

4.5 Properties of Binary Relations and Equivalence Relations

Basic Skills

61. Define a function [latex]f: A \rightarrow B[/latex] where [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ a, b, c \}[/latex]. Prove that [latex]f = \{ (1, a), (2, b), (3, c) \}[/latex] is bijective.
62. Let [latex]f(x) = \frac{2x+1}{x - 3}[/latex], defined for [latex]x \in \mathbb{R} - \{ 3 \}[/latex].
    1. Find the inverse function [latex]f^{-1}(x)[/latex], and state its domain and range.
    2. Verify that [latex]f(f^{-1}(x)) = x[/latex] and [latex]f ^{-1}(f(x)) = x[/latex] for all valid [latex]x[/latex].
    3. Discuss whether [latex]f[/latex] is injective and/or surjective over [latex]\mathbb{R} - \{ 3 \}[/latex].
63. Let [latex]f(x) = x^{2}[/latex].
    1. Prove that [latex]f[/latex] is not injective over [latex]\mathbb{R}[/latex] but is injective over [latex]\mathbb{R}_{0}^{+}[/latex] (the set of non-negative real numbers).
    2. Define a new function [latex]g(x) = x^{2}[/latex] with domain [latex][-2, 2][/latex]. Is [latex]g[/latex] injective? Justify.
    3. Find the largest subset of [latex]\mathbb{R}[/latex] on which [latex]f(x) = x^{2}[/latex] is injective.
64. Let [latex]f: \mathbb{R} \rightarrow \mathbb{R}[/latex] be defined by [latex]f(x) = 3x - 4[/latex].
    1. Prove that [latex]f[/latex] is bijective.
    2. Let [latex]g(x) = \frac{x+4}{3}[/latex]. Show that [latex]g = f ^{-1}[/latex].
    3. Define [latex]h(x) = f(f(x))[/latex]. Find [latex]h(x)[/latex] and determine whether [latex]h[/latex] is bijective.
65. Let [latex]R = \{ (1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3) \}[/latex].
    1. Is [latex]R[/latex] an equivalence relation on the set [latex]A = \{ 1, 2, 3 \}[/latex]? If not, identify which property fails and provide a minimal set of pairs to add to make it an equivalence relation.
    2. Draw the directed graph of [latex]R[/latex] and explain how it reflects the relation’s properties.
66. Define a relation [latex]R[/latex] on [latex]\mathbb{Z}[/latex] where [latex]a \; R \; b[/latex] if [latex]a \equiv b \text{ mod } 4[/latex].
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. List the equivalence classes of [latex]R[/latex] for the set [latex]\{ 0, 1, 2, 3, 4, 5, 6, 7, 8 \}[/latex].
    3. How many distinct equivalence classes are there in [latex]\mathbb{Z}[/latex] under this relation? Justify.
67. Let [latex]R = \{ (a, a), (b, b), (c, c), (a, b), (b, a), (b, c) \}[/latex].
    1. Is [latex]R[/latex] reflexive, symmetric, or transitive? If transitivity fails, identify a specific counterexample.
    2. What is the transitive closure of [latex]R[/latex]? List the additional pairs needed.
68. Let [latex]R = \{ (1, 2), (2, 3), (3, 4) \}[/latex].
    1. Is [latex]R[/latex] transitive? Justify with reasoning or counterexamples.
    2. Compute the transitive closure of [latex]R[/latex].
    3. Represent the relation and its closure as directed graphs and compare.
69. Let [latex]R = \{ (x, y) \; | \; x \text{ and } y \text{ are siblings } \}[/latex].
    1. Is [latex]R[/latex] reflexive, symmetric, or transitive?
    2. Justify each property using real-world logic.
    3. Suppose we define a new relation [latex]R’[/latex] where [latex]x \; R’ \; y[/latex] if [latex]x[/latex] and [latex]y[/latex] are in the same family. Would [latex]R’[/latex] be an equivalence relation? Why or why not?

Applications

70. In a file system, define a relation [latex]R[/latex] on the set of files such that [latex](x, y) \in R[/latex] if and only if file [latex]x[/latex] and file [latex]y[/latex] have the same extension and are in the same directory.
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. Describe the equivalence classes for a directory containing report.docx, summary.docx, notes.txt, draft.txt, and image.png.
    3. How would the equivalence classes change if the relation only required the same extension, regardless of directory?
71. Let [latex]R[/latex] be a relation on a set of students such that [latex](a, b) \in R[/latex] if and only if students [latex]a[/latex] and [latex]b[/latex] are enrolled in at least one common course.
    1. Show [latex]R[/latex] is an equivalence relation by justifying each property.
    2. Suppose the enrollment data is Aiden: Math, History; Benjamin: Math Physics; Chloe: History; Daniel: Physics; Eve: Art. Identify the equivalence classes under [latex]R[/latex].
    3. How would the relation change if it required students to be enrolled in the same set of courses?
72. You are designing a clustering algorithm for customer segmentation based on purchase behaviour. Define a relation [latex]R[/latex] on customers such that [latex](a, b) \in R[/latex] if and only if [latex]a[/latex] and [latex]b[/latex] have identical purchase histories.
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. Explain how the equivalence classes correspond to clusters.
    3. How would the clustering change if the relation were based on similarity thresholds (e.g., 80% overlap)?
73. In systems like Git, Mercurial, or Subversion, files go through many versions. We define a relation [latex]R[/latex] on the set of file versions such that [latex](v_{1}, v_{2}) \in R[/latex] if and only if [latex]v_{1}[/latex] and [latex]v_{2}[/latex] are semantically equivalent. This relation can be based on having the same content (e.g., hash match), being derived from the same base commit, or belonging to the same feature branch or release tag.
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. Describe the equivalence classes in terms of branches or feature sets.
    3. How does this help in merging, conflict resolution, or rollback operations?
74. Define a relation [latex]R[/latex] on the set of people such that [latex](x, y) \in R[/latex] if and only if [latex]x[/latex] and [latex]y[/latex] have shaken hands.
    1. Prove that [latex]R[/latex] is reflexive and symmetric.
    2. Show that [latex]R[/latex] is not transitive with a real-world example.
    3. Modify the relation to make it transitive and describe the new interpretation.

Challenge Problems

75. Prove that a function is bijective if and only if it has an inverse.
76. Consider the proof of Theorem 4.5.
    1. Extend the proof to show that every partition of [latex]X[/latex] corresponds to exactly one equivalence relation.
    2. Apply this to a real-world scenario, grouping users by identical access permissions in a system.
77. Let [latex]A = \{ 1, 2, 3, 4, 5 \}[/latex] and define [latex]R = \{ (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2) \}[/latex].
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. List all equivalence classes.
    3. Represent the relation as a graph and explain how the connected components correspond to the equivalence classes.
78. Construct a relation that is symmetric and transitive but not reflexive.
79. Let [latex]R[/latex] be a relation on [latex]\mathbb{Z}[/latex] defined by [latex]a \; R \; b[/latex] if [latex]a - b[/latex] is even.
    1. Prove that [latex]R[/latex] is an equivalence relation.
    2. What are the equivalence classes?
80. Show that if a relation is reflexive and transitive, it is not necessarily symmetric.

4.6 Partitions and Equivalent Classes and Closure of Relations

Basic Skills

81. Let [latex]A = \{ 1, 2, 3, 4, 5, 6, 7 \}[/latex]. Consider the collection [latex]\mathcal{P} = \{ \{ 1, 2 \}, \{ 3, 4, 5 \}, \{ 6, 6 \}[/latex].
    1. Is [latex]\mathcal{P}[/latex] a partition of [latex]A[/latex]? Justify by checking non-empty subsets, pairwise disjointness, and whether the union equals [latex]A[/latex].
    2. If not, modify [latex]\mathcal{P}[/latex] minimally to make it a valid partition.
    3. Construct the equivalence relation induced by the corrected partition.
82. Let [latex]A = \{ 1, 2, 3, 4 \}[/latex] and [latex]R = \{ (1, 2), (2, 3), (3, 4) \}[/latex].
    1. Find the reflexive, symmetric, and transitive closures of [latex]R[/latex].
    2. Represent each closure as a directed graph.
    3. How many additional pairs are needed for each closure?
    4. Is the final relation an equivalence relation? Why or why not?
83. Let [latex]A = \{ 1, 2, 3, 4, 5, 6 \}[/latex]. Suppose you are told that [latex][1] = \{ 1, 3, 5 \}[/latex] and [latex][2] = \{ 2, 4, 6 \}[/latex].
    1. List all ordered pairs in the equivalence relation [latex]R[/latex].
    2. Prove that [latex]R[/latex] is reflexive, symmetric, and transitive.
    3. Represent [latex]R[/latex] as a matrix and a graph.
84. Let [latex]A = \{ a, b, c, d, e, f \}[/latex]. Define a partition [latex]\mathcal{P} = \{ \{ a, b \}, \{ c, d, e \}, \{ f \} \}[/latex].
    1. Define the equivalence relation [latex]R[/latex] induced by [latex]\mathcal{P}[/latex].
    2. How many ordered pairs are in [latex]R[/latex]?
    3. Describe a real-world scenario (e.g., file types, user roles) that this partition could model.
85. Let [latex]R = \{ (1, 2), (2, 3), (3, 4), (4, 5) \}[/latex] on [latex]A = \{ 1, 2, 3, 4, 5 \}[/latex].
    1. Find the transitive closure [latex]R^{+}[/latex].
    2. How many new pairs are added?
    3. Prove that the closure is minimal and unique.
    4. A vertex [latex]v[/latex] is reachable from vertex [latex]u[/latex] if there exists a directed path from [latex]u[/latex] to [latex]v[/latex]. This means you can follow the arrows from [latex]u[/latex] to [latex]v[/latex] without violating their direction. Represent the closure as a matrix and explain how it reflects reachability in a graph.

Applications

86. A university groups students by major, but each major may have specializations (e.g., "Computer Science [latex]\rightarrow[/latex] AI, Systems, Theory").
    1. Show how grouping by major only forms a partition of the student set.
    2. Define an equivalence relation [latex]R[/latex] such that [latex]a \; R \; b[/latex] if students [latex]a[/latex] and [latex]b[/latex] have the same major.
    3. Extend the model by defining a hierarchical partition where equivalence classes are nested by specialization. Is this still an equivalence relation?
87. A subnet is a logically visible subdivision of an IP network. It’s a way to divide a large network into smaller, more manageable sections. In a network, define a relation [latex]R[/latex] on the set of devices [latex]D[/latex] such that [latex]a \; R \; b[/latex] if devices [latex]a[/latex] and [latex]b[/latex] are in the same subnet.
    1. Prove or disprove that [latex]R[/latex] is an equivalence relation.
    2. Suppose subnets change dynamically. How does this affect the stability of the equivalence classes?
    3. Model the relation using a graph where edges represent subnet membership. What do the connected components represent?
88. Database normalization is the process of organizing data in a relational database to reduce redundancy, improve data integrity, and simplify maintenance. Closures are used in database normalization to enforce functional dependencies (constraints between two sets of attributes in a relation).
    1. The attribute closure of a relation [latex]X[/latex], denoted [latex]x^{+}[/latex], is the set of all attributes that are functionally determined by [latex]X[/latex] using the dependencies in a set of functional dependencies [latex]F[/latex]. Explain how attribute closure is used to determine candidate keys in a relational schema.
    2. A redundant attribute is an attribute (column) in a table that can be derived from other attributes and therefore does not need to be stored explicitly. Given a set of functional dependencies [latex]F[/latex], describe how computing the transitive closure of [latex]F[/latex] helps identify redundant attributes.
    3. Apply this to a schema with attributes [latex]\{ A, B, C, D \}[/latex] and dependencies [latex]A \rightarrow B[/latex], [latex]B \rightarrow C[/latex], and [latex]C \rightarrow D[/latex].
    4. What is the closure of [latex]A[/latex]? What does this imply about normalization?
89. In a role-based access control (RBAC) system, users are grouped by access level.
    1. Define an equivalence relation [latex]R[/latex] on the set of users [latex]U[/latex] such that [latex]u_{1} \; R \; u_{2}[/latex] if they have identical access permissions.
    2. Show how the equivalence classes partition [latex]U[/latex] into access groups.
    3. Suppose permissions are updated dynamically. How would you efficiently recompute the equivalence classes?
    4. Extend this to partial equivalence: users share some but not all permissions. Is this still an equivalence relation?
90. Warshall’s algorithm computes the transitive closure of a relation represented as a matrix.
    1. Describe how Warshall’s algorithm works and prove its correctness using induction.
    2. Apply it to a directed graph representing dependencies between software modules. What does the transitive closure tell you?

Challenge Problems

91. Let [latex]A = \{ 1, 2, 3, 4, 5, 6, 7, 8 \}[/latex]. Define a partition [latex]\mathcal{P}[/latex] of [latex]A[/latex] such that (i) each subset has at least 2 elements and (ii) no subset contains both even and odd numbers.
    1. Construct such a partition [latex]\mathcal{P}[/latex]
    2. Define the corresponding equivalence relation [latex]R \subseteq A \times A[/latex].
    3. Represent R as a matrix and a graph.
92. Consider the proof of Theorem 4.6.
    1. Extend the proof to the case where class sizes are not equal. What condition must still hold?
    2. Apply this to a real-world scenario (e.g., grouping users by identical permissions).
93. Let [latex]R = \{ (1, 2), (2, 3) \}[/latex] on [latex]A = \{ 1, 2, 3, 4 \}[/latex].
    1. Find the reflexive, symmetric, and transitive closures of [latex]R[/latex].
    2. Represent each closure as a directed graph.
    3. How many new pairs are added in each closure?
    4. Is the final relation an equivalence relation? Why or why not?
94. Warshall’s algorithm computes the transitive closure of a relation represented as a matrix.
    1. Apply it to the matrix of a relation on [latex]A = \{ 1, 2, 3, 4 \}[/latex] with [latex]R = \{ (1, 2), (2, 3), (3, 4) \}[/latex].
    2. Implement Warshall’s algorithm to compute reachability in a network of 6 nodes (use pseudocode or a programming language of your choice). How would you optimize it for sparse graphs (a type of graph in which the number of edges is much smaller than the maximum possible number of edges)?
95. Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]R = \{ (1, 2), (2, 3) \}[/latex].
    1. What is the minimal set of pairs to add to make [latex]R[/latex] reflexive? Symmetric? Transitive?
    2. What is the union of all these additions to make [latex]R[/latex] an equivalence relation?
    3. Represent the final relation as a matrix and explain how each property is reflected in it.

4.7 Relational Model of Databases and Functions

Basic Skills

96.  Given a Students table with columns (ID, Name, Major) and a Grades table with columns (ID, Course, Grade):

1. Write a relational algebra expression to return the names of students who received an ‘A’ in any course.
2. Write a query to return the names of students majoring in ‘Computer Science’ who received a ‘B’ or higher in ‘Algorithms'.
3. Explain how the concept of a function applies to the relationship between ID and Name in the Students table.

Applications

97. In a database, the Students table has columns (ID, Name, Major). Write a join query to combine this with a Grades table (ID, Course, Grade) to list names and grades.
98. Explain how a function can be represented as a relation in a database.
99. Describe the difference between a function and a general relation in terms of database constraints.
100. Let [latex]f(x) = x + 1[/latex] and [latex]g(x) = 2x[/latex]. Find [latex](g \circ f)(x)[/latex] and interpret it in a database context.
101. How does the concept of injectivity relate to primary keys in relational databases?

Challenge Problems

102. Construct a function that is injective but not surjective and explain its database analogy.
103. Given two tables, Students(ID, Name) and Grades(ID, Course, Grade), write a query that lists the names of students and their grades in the course ‘Math’.
104. Explain how the composition of functions relates to multi-table joins in relational databases.