Functions and Relations

🧩 Functions and Relations

In discrete mathematics, Relations and Functions describe how elements from different sets are connected. In computer science, these concepts underpin everything from database schemas to functional programming.

---

🟢 Part 1: Binary Relations

A binary relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$.

1. Representation

• Ordered Pairs: $\{(a_1, b_1), (a_2, b_2), \dots \}$
• Directed Graph: Nodes represent elements, and arrows represent the relationship.
• Matrix: A boolean matrix where $M_{ij} = 1$ if $(a_i, b_j) \in R$.

2. Properties of Relations

• Reflexive: $\forall a \in A, (a, a) \in R$.
• Symmetric: $(a, b) \in R \implies (b, a) \in R$.
• Transitive: $(a, b) \in R \land (b, c) \in R \implies (a, c) \in R$.
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive. This is used for Data Clustering and defining equivalent states.

---

🟡 Part 2: Functions

A function $f: A \to B$ is a special type of relation where every element in $A$ is related to exactly one element in $B$.

1. Key Terminology

• Domain ($A$): The set of all possible inputs.
• Codomain ($B$): The set of all potential outputs.
• Range ($f(A)$): The actual set of outputs produced by the function.

2. Types of Functions (The Big Three)

Understanding these is critical for maintaining Data Integrity in databases.

• Injective (One-to-One): Each element in $B$ is mapped to by at most one element in $A$.
  • CS Context: This is the definition of a Unique Constraint or Primary Key.
• Surjective (Onto): Every element in $B$ is mapped to by at least one element in $A$.
  • CS Context: Ensuring that a lookup table covers all possible return categories.
• Bijective (One-to-One Correspondence): Both injective and surjective.
  • CS Context: Necessary for Encryption/Decryption and Data Encoding.

---

🔴 Part 3: Composition and Inverse

1. Function Composition

$(g \circ f)(x) = g(f(x))$. In software engineering, this is the essence of building modular systems. A complex data pipeline is simply a chain of function compositions.

2. Inverse Functions ($f^{-1}$)

Only bijective functions have an inverse. If $f(x) = y$, then $f^{-1}(y) = x$. Application: Lossless data compression algorithms must be invertible.

Caution

Determinism: In computer science, we usually require functions to be deterministic. If you call $f(x)$ twice, it must return the same result both times. Functions that rely on global state or random numbers are “impure.”

---

💻 Programming Example: Mapping and Injections

# A simple function (deterministic mapping)
def square(n):
    return n * n

# Injective check: Are all outputs unique for these inputs?
inputs = [1, 2, 3, 4]
outputs = [square(i) for i in inputs]

is_injective = len(set(inputs)) == len(set(outputs))
print(f"Is the mapping injective for these inputs? {is_injective}")

Database Analogy

• Relation: A SQL table where one user can have multiple orders.
• Function: A SQL table where each user has exactly one profile.
• Injective Function: A SQL table where each user has a unique, non-shared email address.