Introduction: Relations & Functions

What is a Relation?

A relation between two sets A and B is any subset of the Cartesian product A × B. If an ordered pair (x, y) belongs to that subset, we say x is related to y. In symbols, a relation R from A to B is R ⊆ A × B and (x, y) ∈ R means "x is related to y by R".

Example. Let A = {Kuala Lumpur, Jakarta, Canberra, Washington DC} and B = {Malaysia, Indonesia, Australia, USA}. Define the relation

R = {(x, y) : x is the capital city of the country y, x ∈ A, y ∈ B}.

Then

• R = {(Kuala Lumpur, Malaysia), (Jakarta, Indonesia), (Canberra, Australia), (Washington DC, USA)}.

Relations are often represented in different ways: as a set of ordered pairs, as an arrow diagram, as a matrix, or by a rule.

Domain, Range and Codomain

Let R be a relation from A to B (that is R ⊆ A × B).

• The domain of R is the set of all first elements of ordered pairs in R, i.e. {x ∈ A : there exists y ∈ B with (x, y) ∈ R}. The domain is a subset of A and need not equal A.
• The range (also called image) of R is the set of all second elements of ordered pairs in R, i.e. {y ∈ B : there exists x ∈ A with (x, y) ∈ R}. The range is a subset of B.
• The codomain is the set B when we consider a relation R ⊆ A × B; it is the target set from which the range is taken.

For the example above, Domain = {Kuala Lumpur, Jakarta, Canberra, Washington DC}, Range = {Malaysia, Indonesia, Australia, USA}, Codomain = B = {Malaysia, Indonesia, Australia, USA}.

Empty and Universal Relations

Empty relation: A relation R is called the empty relation (written R = ∅) on A × B if R has no elements.

Universal relation: A relation R on A × B is called the universal relation if R = A × B, that is every possible ordered pair (a, b) with a ∈ A and b ∈ B belongs to R.

Examples:

• Let A be the set of all students in a boys' school. Define R = {(a, b) : a and b are sisters}. Since there are no sisters in a boys' school, R = ∅. Thus R is the empty relation on A.
• With the same set A, define R' = {(a, b) : the height of a and b is greater than 10 cm}. Since every student has height greater than 10 cm, every ordered pair of students satisfies the condition. Therefore R' = A × A and is the universal relation on A.

Reflexive, Symmetric and Transitive Relations

Certain properties of relations are central in mathematics. Three important properties are:

• Reflexive: A relation R on a set A is reflexive if (a, a) ∈ R for every a ∈ A.
• Symmetric: A relation R on A is symmetric if whenever (a, b) ∈ R then (b, a) ∈ R for all a, b ∈ A.
• Transitive: A relation R on A is transitive if whenever (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A.

If a relation is reflexive, symmetric and transitive, it is called an equivalence relation.

Example 1

Let R be a relation on A = {1, 2, 3} given by

R = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)}.

Solution:

Check reflexive:
(1,1), (2,2) and (3,3) are all in R, so R is reflexive on A.

Check symmetric:
(1,2) ∈ R but (2,1) ∉ R, so R is not symmetric.

Check transitive:
(1,2) ∈ R and (2,3) ∈ R and (1,3) ∈ R, so transitivity holds for these elements; checking all required cases shows R is transitive.

What is a Function?

A function (also called a mapping) from a set X to a set Y is a relation f ⊆ X × Y with the property that every element of X is related to exactly one element of Y. We write f : X → Y and write y = f(x) when (x, y) ∈ f.

Key points for a function f : X → Y:

• Every element of X (the domain) must have an image in Y.
• Each element of X must be associated with only one element of Y (no element of X may map to two or more images).
• Different elements of X may map to the same element of Y (this is allowed).

Illustrative diagrams

Consider the sets A = {1, 2, 3, 4, 5} and B = {2, 4, 6, 8, 1} with a mapping shown in the diagram below.

To decide whether the diagram represents a function, check whether each element of A has exactly one arrow pointing to some element of B. If any element of A is not mapped, or is mapped to more than one element of B, the relation is not a function.

Note: For a function defined as f : A → B, the domain is A (every element of A must be assigned an image). The range (image) is the subset of B that actually contains values f(x) for x ∈ A.

Example 1 (Mapping diagram)

Each element of the domain in this diagram is paired with one and only one element of the range. Even though two domain elements (5 and 10 here) may share the same image (2), the rule of exactly one image per domain element is satisfied. Therefore the relation shown is a function.

Example 2

In this diagram, each domain element also points to a single range element. Several domain values can share a common range value; this relation is also a function.

Example 3

If any single element of the domain is paired with more than one element of the range (one domain element with multiple arrows to different range elements), the relation is not a function.

Example 4

If any element of the domain has no arrow (no image), the correspondence is not even a relation defined as a function from that domain. Hence it is neither a relation (as a function from the whole domain) nor a function.

Types of Functions

Functions may be classified according to how elements of the domain and codomain correspond.

One-one (Injective) and Many-one

One-one (injective): A function f : X → Y is one-one if different inputs give different outputs. Formally, f is injective if f(x1) = f(x2) implies x1 = x2 for all x1, x2 ∈ X. Equivalently, no two distinct elements of X have the same image in Y.

Many-one: If two or more distinct elements of X map to the same element of Y, the function is many-one (not injective). Many-one functions are acceptable as functions, they are just not injective.

How to check injectivity - Method 1 (Finite sets)

Check each element of the domain manually. If every element of X has a unique image (no repeats among images for distinct inputs), the function is one-one. This method is practical when X is small and presented as a table or diagram.

Ques 1: Check if the following is a one-one function?

Since each domain element has a distinct image, the mapping shown is a one-one function.

Ques 2:

Elements 2, 3 and 4 share the same image 6. Thus the mapping is not one-one; it is a many-one function.

How to check injectivity - Method 2 (Infinite or algebraic domains)

When domains are infinite (for example ℕ, ℤ, or ℝ) or functions are given by a formula, use algebraic reasoning:

Set f(x1) = f(x2) and simplify. If you can deduce x1 = x2 for all x1, x2 in the domain, then f is injective. If you obtain x1 ≠ x2 for some solutions, it is not injective.

Onto (Surjective)

Onto (surjective): A function f : X → Y is onto if every element of Y is the image of at least one element of X. That is, for every y ∈ Y there exists x ∈ X such that f(x) = y. The range of f equals the codomain Y.

How to check surjectivity - Method 1 (Finite sets / diagrams)

Examine whether every element of the codomain Y has at least one pre-image in X. If all elements of Y are "hit" by f, the function is onto.

Ques 1: Check whether the following is an onto function?

Solution: Every element of the codomain B shown in the diagram has a pre-image in A, so the mapping is onto.

Ques 2:

Solution: Since the element b in the codomain has no pre-image in the diagram, the mapping is not onto.

How to check surjectivity - Method 2 (Algebraic)

When f : X → Y is given by a formula and X, Y are infinite sets like ℕ, ℤ or ℝ:

• Set y = f(x).
• Solve for x in terms of y.
• If for every y ∈ Y the solution x belongs to X, then f is onto. If some y ∈ Y gives no valid x ∈ X, f is not onto.

Many-to-One Function

A function is called many-one if two or more distinct elements of the domain map to the same element of the codomain. This is simply the negation of one-one; many-one functions are valid functions provided each domain element still has exactly one image.

Bijective Function

A function f : X → Y is bijective if it is both one-one (injective) and onto (surjective). A bijection establishes a perfect pairing between elements of X and Y; thus X and Y have the same cardinality.

Ques 1: Check whether the following is a bijective function?

Solution: Every element of the domain has a unique image and every element of the codomain has a pre-image; therefore the mapping shown is both injective and surjective. Hence it is bijective.

Ques 2: Find if the following is a bijective function?

Solution: The mapping is injective because every element of the domain maps to a distinct image in the codomain, but it is not surjective because the element s in the codomain has no pre-image from the domain. Therefore the function is not bijective.