Functions as Relations

A function is a special relation between two sets. If A and B are sets, then a function f assigns to every element in A exactly one element in B. This means that the function is a subset of the Cartesian product A × B, but the assignment is unique.

By definition: ∀a ∈ A, ∃! b ∈ B such that (a,b) ∈ f. That is, for every a, there is exactly one b.

Example

Let A = {1,2,3}, B = {a,b,c}, and define the function f: f(1)=a, f(2)=b, f(3)=c. This means that the relation f = {(1,a), (2,b), (3,c)}. This is a function because every element in A is assigned exactly one element in B.

Function or Not a Function?

Not every relation is a function. For example, if g = {(1,a), (1,b), (2,c)}, then this is not a function because the element 1 is assigned two different outputs (a and b).

Types of Functions

• Injective (one-to-one): different inputs go to different outputs.
• Surjective (onto): every element in B has at least one preimage in A.
• Bijective: both injective and surjective → one-to-one correspondence.

Solved Example

Let A = {1,2,3,4}, B = {x,y}, and examine the following assignment: h = {(1,x), (2,y), (3,y), (4,y)}.

• Every element in A is assigned exactly one element in B → so this is a function.
• This function is not injective because multiple different elements in A (e.g., 2 and 3) are assigned the same output (y).
• It is surjective because every element in B (x and y) has a preimage.
• Thus, the function is surjective but not injective, so not bijective.

Applications

• Mathematics: functions are used to describe relationships between quantities.
• Computer Science: in programs, we assign one output to each input.
• Real Life: personal ID number assigned to a person → each person has exactly one number.

Summary

A function is a special relation: each input has exactly one output. There are different types (injective, surjective, bijective) that determine the properties of the function.

Practice Exercise