2.2 Functions and relations

This unit is the bridge from set language to almost everything that follows. Functions, relations, and quotient constructions all start with the same idea: take a product set, then specify which pairs are allowed.

The point is not just to know the vocabulary. It is to understand what kind of statement each definition is making, because later chapters will build $N$ , $Z$ , $Q$ , orders, and classes from exactly this language.

Functions are special relations

Definition

A function

A function from $X$ to $Y$ is a subset of $X \times Y$ such that every $x \in X$ is paired with exactly one $y \in Y$ .

This is the set-theoretic definition used throughout the local notes.

The same information can be read in several equivalent ways:

$X$ is the domain, the set of allowed inputs.
$Y$ is the target, the set of possible outputs.
The graph of f is the set of pairs (x, y) with $y = f(x)$ .
The image of a set is the set of outputs reached by that set.
The preimage of a set is the set of inputs that land there.

Common mistake

A function must not send one input to two outputs

A relation may connect one input to many outputs. A function cannot. Every input must have exactly one output.

Common mistake

The domain may depend on context

The formula 1/x is not a single function unless you specify a domain. It can be a function on $R \setminus \{0\}$ , on $Q \setminus \{0\}$ , or on another domain where division by zero is excluded.

Reading a function carefully

Worked example

The square function has repeated outputs

Take the rule $f(x) = x^2$ .

Then $f(-2) = 4$ and $f(2) = 4$ , so different inputs may share the same output. That is allowed.

What is not allowed is a single input having two different outputs.

For example, the relation “ $y^2 = x$ ” on $Z \times Z$ is not a function if you read it as a rule from x to y, because $x = 4$ allows both $y = 2$ and $y = -2$ .

Solution

What to remember

Image, preimage, and composition

For a function $f : X \to Y$ , the course uses the word image in three related ways:

f(x) is the image of the single input x.
If $A \subset X$ , then $f(A) = {f(x) \mid x \in A}$ is the image of the set.
f(X) is the full image of f, meaning the actual outputs that appear.

The preimage of a set $B \subset Y$ is

f^{-1}(B) = \{x \in X \mid f(x) \in B\}.

This exists even when f does not have an inverse function.

Composition is defined by

(g \circ f)(x) = g(f(x)).

The order matters: $g \circ f$ means “first f, then g”.

Worked example

Compare image and preimage for $f(x)=x^2$

Let $f : R \to R$ be given by $f(x) = x^2$ , and let

A = \{-2, -1, 0, 1, 2\}, \qquad B = \{0, 1, 4\}.

Then

f(A) = \{0, 1, 4\}.

Also,

f^{-1}(B) = \{-2, -1, 0, 1, 2\},

because every element of $A$ maps into $B$ .

If we instead take $C = \{4\}$ , then

f^{-1}(C) = \{-2, 2\}.

Solution

Why this distinction matters

Injective, surjective, bijective

Definition

Three useful words

Injective means different inputs never collide.
Surjective means every target value is hit.
Bijective means both injective and surjective.

Equivalent formulations are often useful:

f is injective if $f(x1) = f(x2)$ implies $x1 = x2$ .
f is surjective if $f(X) = Y$ .
f is bijective if every element of the target is hit exactly once.

These words matter because they tell you whether an inverse function can exist.

Theorem

Inverse functions exist exactly for bijections

For a function $f : X \to Y$ , an inverse function exists if and only if f is bijective.

Proof

Why a bijection has an inverse

Worked example

Construct injective and non-injective examples

The function $n \mapsto n + 1$ on $Z$ is injective and surjective, so it is bijective.

The function $x \mapsto x^2$ on $R$ is not injective because 1 and $-1$ have the same image.

The function $x \mapsto e^x$ on $R$ is injective but not surjective onto $R$ , because it never reaches nonpositive numbers.

Solution

What to look for first

Common mistake

Do not confuse preimage with inverse function

$f^{-1}(B)$ always makes sense as a preimage. The inverse function $f^{-1}$ only exists when f is bijective.

Left and right inverses

There is a useful distinction here.

A left inverse h satisfies $h \circ f = id$ .
A right inverse g satisfies $f \circ g = id$ .

These conditions are not the same in general.

Worked example

One map with a left inverse but no right inverse

Let $X = {a, b, c}$ and $Y = {α, β, γ, δ}$ . Define

f_1(a)=α,\qquad f_1(b)=β,\qquad f_1(c)=γ.

This map is injective but not surjective, because δ is never hit. So it can have a left inverse, but it cannot have a right inverse.

For instance, define $h : Y \to X$ by

h(α)=a,\qquad h(β)=b,\qquad h(γ)=c,\qquad h(δ)=a.

Then $h \circ f_1 = id_X$ .

Solution

Why the missing output blocks a right inverse

Worked example

One map with a right inverse but no left inverse

Define $f_2 : Y \to X$ by

f_2(α)=a,\qquad f_2(β)=a,\qquad f_2(γ)=b,\qquad f_2(δ)=c.

This map is surjective but not injective, so it can have a right inverse but no left inverse.

A right inverse is given by $g : X \to Y$ with

g(a)=α,\qquad g(b)=γ,\qquad g(c)=δ.

Then $f_2 \circ g = id_X$ .

Solution

Why collisions block a left inverse

Relations

Definition

A relation

A relation on a pair of sets $X$ and $Y$ is any subset of $X \times Y$ .

If $X = Y$ , we simply call it a relation on $X$ .

We write xRy to mean $(x, y) \in R$ .

This is the broader notion. A function is just a relation with the extra rule that every input has exactly one output.

For a relation $R \subset X \times Y$ :

the domain of $R$ is the set of x that relate to at least one y;
the image or range of $R$ is the set of y that are hit by at least one x.

Worked example

A relation need not be a function

Let $X$ be the set of countries and $Y$ the set of cities.

The relation “y is a capital city of x” is a relation on $X \times Y$ . Whether it is a function depends on the historical period and the country.

The relation $y^2 = x$ on $Z \times Z$ is also a relation. It is not a function when read from x to y, because one input may have multiple outputs.

Solution

Why the relation language is still useful

Relations on one set

Relations $R \subset X \times X$ are especially important.

Theorem

Four properties used constantly

A relation on $X$ may have these properties:

Reflexive: xRx for every $x \in X$
Symmetric: xRy implies yRx
Antisymmetric: if xRy and yRx, then $x = y$
Transitive: if xRy and yRz, then xRz

Two special kinds of relations appear everywhere in later chapters:

a partial order is reflexive, antisymmetric, and transitive;
an equivalence relation is reflexive, symmetric, and transitive.

The difference between symmetric and antisymmetric is easy to blur:

symmetric says the arrows go both ways whenever one goes one way;
antisymmetric says two-way arrows force equality.

Worked example

The divisibility relation is a partial order

On positive integers, write $a \mid b$ when a divides b.

This relation is reflexive because every number divides itself. It is antisymmetric because if $a \mid b$ and $b \mid a$ , then $a = b$ for positive integers. It is transitive because divisibility passes through chains.

So divisibility is a partial order.

Solution

Why this matters

Worked example

A simple equivalence relation

Congruence modulo m is an equivalence relation on $Z$ .

The idea is that two integers belong to the same class if they have the same remainder modulo m.

For example, modulo 3 the integers split into three classes:

numbers congruent to 0
numbers congruent to 1
numbers congruent to 2

Those classes partition the whole set.

Equivalence classes and quotient sets

Definition

Equivalence class

Let $R$ be an equivalence relation on $X$ . For $x \in X$ , the equivalence class of x is

[x]_R = \{y \in X \mid yRx\}.

Definition

Quotient set

If $\sim$ is an equivalence relation on $X$ , then the set of equivalence classes is written X / \sim.

Equivalence classes are the reason quotient constructions work. Instead of tracking every representative separately, we package all equivalent representatives into one object.

Theorem

Equivalence classes partition the set

If $R$ is an equivalence relation on $X$ , then the equivalence classes cover $X$ , and any two classes are either equal or disjoint.

Proof

Why the classes do not overlap partially

This is the mechanism behind the later constructions of the integers and the rationals from equivalence classes of pairs.

Common mistakes

Common mistake

Do not treat preimage as inverse function

$f^{-1}(B)$ is always a subset of the domain. It does not require f to be bijective.

Common mistake

Symmetric is not the same as antisymmetric

$≤$ is antisymmetric but not symmetric. Equality is both symmetric and antisymmetric, while divisibility is antisymmetric but not symmetric.

Common mistake

A relation can fail to be a function in several ways

It may send one input to many outputs, or it may leave some inputs with no output at all.

Quick checks

Quick check

Is $x ≤ y$ on the real numbers a relation? Is it a function?

First ask whether it is a subset of $R \times R$ . Then ask whether every input has exactly one output.

Solution

Answer

Quick check

Is $f^{-1}(B)$ defined when `f` is not bijective?

Separate preimage notation from inverse-function notation.

Solution

Answer

Quick check

If a relation is reflexive, symmetric, and transitive, what is it called?

Recall the special name for a relation that partitions the set into classes.

Solution

Answer

Why this unit matters later

The rest of the course repeatedly uses these ideas:

$N$ is built using set language and induction.
$Z$ and $Q$ are built from equivalence classes.
$≤$ on numbers is a partial order.
Quotient sets explain why the same object can have many representatives.

If this unit is clear, the later constructions become much easier to read because the notation is no longer doing hidden work.

2.2 Functions and relations

MATH1090: Set theory

Functions are special relations

A function

A function must not send one input to two outputs

The domain may depend on context

Reading a function carefully

The square function has repeated outputs

What to remember

Image, preimage, and composition

Compare image and preimage for f(x)=x2f(x)=x^2f(x)=x2

Why this distinction matters

Injective, surjective, bijective

Three useful words

Inverse functions exist exactly for bijections

Why a bijection has an inverse

Construct injective and non-injective examples

What to look for first

Do not confuse preimage with inverse function

Left and right inverses

One map with a left inverse but no right inverse

Why the missing output blocks a right inverse

One map with a right inverse but no left inverse

Why collisions block a left inverse

Relations

A relation

A relation need not be a function

Why the relation language is still useful

Relations on one set

Four properties used constantly

The divisibility relation is a partial order

Why this matters

A simple equivalence relation

Equivalence classes and quotient sets

Equivalence class

Quotient set

Equivalence classes partition the set

Why the classes do not overlap partially

Common mistakes

Do not treat preimage as inverse function

Symmetric is not the same as antisymmetric

A relation can fail to be a function in several ways

Quick checks

Is x≤yx ≤ yx≤y on the real numbers a relation? Is it a function?

Answer

Is f−1(B)f^{-1}(B)f−1(B) defined when f is not bijective?

Answer

If a relation is reflexive, symmetric, and transitive, what is it called?

Answer

Why this unit matters later

Prerequisites

Key terms in this unit

More notes in this series

Compare image and preimage for $f(x)=x^2$

Is $x ≤ y$ on the real numbers a relation? Is it a function?

Is $f^{-1}(B)$ defined when `f` is not bijective?