Functions & Relations: Definitions, Types, and Applications

1. Introduction to Functions

1.1 Definition and Notation

A function $f:A\to B$ maps each element of set $A$ (domain) to exactly one element in set $B$ (codomain).

• Notation: $f(a)=b$ means $b$ is the image of $a$ under $f$.
• Example: $f(x)=2x+1$ maps integers to integers.

1.2 Types of Functions

Worked Example: Determine if $f:\mathbb{Z}\to \mathbb{Z},f(x)=x-1$ is injective/surjective/bijective.

• Injective? Yes, because $f(a)=f(b)⟹a-1=b-1⟹a=b$.
• Surjective? Yes, because for any $y\in \mathbb{Z}$, $y=f(y+1)$.
• Bijective? Yes (both injective and surjective).

1.3 Function Operations

• Sum: $(f+g)(x)=f(x)+g(x)$ Example: $f_1(x)=x^2,f_2(x)=x-x^2$ $(f_1+f_2)(x)=x^2+x-x^2=x$
• Product: $(f\cdot g)(x)=f(x)\cdot g(x)$ $(f_1\cdot f_2)(x)=x^2(x-x^2)=x^3-x^4$
• Composition: $(f\circ g)(x)=f(g(x))$ Example: $f(x)=x+2,g(x)=3x$ $(f\circ g)(x)=3x+2$

1.4 Special Functions

Worked Example: Find $\lfloor -2.3\rfloor$ and $\lceil 4.9\rceil$.

• $\lfloor -2.3\rfloor =-3$ (greatest integer $\le -2.3$)
• $\lceil 4.9\rceil =5$ (smallest integer $\ge 4.9$)

---

2. Relations and Their Properties

2.1 Definition of a Relation

A relation $R$ from set $A$ to $B$ is a subset of $A\times B$.

• Example: $R=\{(1,2),(2,3),(3,1)\}$ on $A=\{1,2,3\}$.

2.2 Types of Relations

2.3 Relation Closures

Worked Example: Find the symmetric closure of $R=\{(1,1),(1,2),(2,3),(3,1)\}$.

• Add missing symmetric pairs: $(2,1)$ and $(3,2)$.
• Symmetric closure: $\{(1,1),(1,2),(2,1),(2,3),(3,2),(3,1)\}$.

2.4 Matrix Representation of Relations

A relation $R$ on $A=\{a,b,c\}$ can be represented as a zero-one matrix:

   a b c
a 1 1 0
b 0 0 1
c 1 0 0

• Example: $R=\{(a,a),(a,b),(b,c),(c,a)\}$.

2.5 Hasse Diagrams

A Hasse diagram visually represents a partially ordered set (poset) by omitting reflexive and transitive edges. Worked Example: Draw the Hasse diagram for the divisible relation on $\{1,2,5,8,16,32\}$.

      32
     /  \
    16   8
   /    /
  2    1
   \  /
    5

• Maximal element: 32 (no element above it).
• Minimal element: 5 (no element below it).
• Greatest element: 32 (divisible by all others).
• Least element: 1 (divides all others).

---

3. Applications in Computer Science

3.1 Functions in Algorithms

• Injective functions ensure unique keys in databases.
• Bijective functions enable encryption/decryption (e.g., Caesar cipher).
• Recursive functions define self-similar structures (e.g., fractals).

3.2 Relations in Databases

• Foreign keys model relations between tables.
• Equivalence relations define partitioning in clustering.

3.3 Graph Theory

• Adjacency matrices represent relations between nodes.
• Hasse diagrams model hierarchical data (e.g., file systems).

---

Exam Tip

Common Pitfalls & Strategies

✅ For functions:

• Always check domain and codomain before classifying (injective/surjective).
• Composition is not commutative: $f\circ g\ne g\circ f$.
• Floor/ceiling questions often test integer arithmetic.

✅ For relations:

• Closures require systematic addition of missing pairs.
• Hasse diagrams must omit reflexive/transitive edges to avoid clutter.
• Matrix representation is useful for automata theory (next unit).

❌ Avoid:

• Assuming a function is bijective without proof.
• Forgetting to include all required pairs in closures.
• Misidentifying maximal vs. greatest elements in posets.

High-Scoring Techniques

1. For function proofs:

   • Use definition-based reasoning (e.g., "Assume $f(a)=f(b)$, then...").
   • Draw mapping diagrams for clarity.

2. For relations:

   • List all possible pairs before computing closures.
   • Label Hasse diagrams clearly (e.g., "divisible by").

3. For past exam questions:

   • Set representation: $\{3,6\}$ (multiples of 3 not exceeding 6 in $U=\{1,...,10\}$).
   • Recurrence relations (Unit 4) often appear in function-related problems.

---

End of Note