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 in this unit.

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.

The set of all functions

Once functions have been defined as sets of ordered pairs, we can also make a set whose elements are functions. If $A$ and $B$ are sets, the notation

B^A

means the set of all functions from $A$ to $B$ .

This notation is not accidental. When $A$ is finite with n elements and $B$ is finite with m elements, a function $A \to B$ is made by choosing one of m outputs for each of the n inputs. Hence there are $m^n$ such functions. For example, if $A = \{a,b,c\}$ and $B=\{0,1\}$ , then $B^A$ has $2^3=8$ functions. This is the same counting principle behind $|P(A)| = 2^{|A|}$ .

Worked example

Read $B^A$ as a function set

Let $A=\{a,b\}$ and $B=\{0,1\}$ . Then $B^A$ contains exactly four functions:

\begin{array}{c|cc} & a & b \\ \hline f_1 & 0 & 0\\ f_2 & 0 & 1\\ f_3 & 1 & 0\\ f_4 & 1 & 1 \end{array}

Each row is one whole function, not one value of a single function.

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

Theorem

Finite self-maps: a left inverse already forces an inverse

Let $X$ be finite and let $g : X \to X$ . If there exists $h : X \to X$ with $h \circ g = id_X$ , then g is bijective and h is also a right inverse of g.

Proof

Proof idea

Cardinality and operation language

Cardinality means size, but in set theory the correct comparison is not always ordinary counting. Two sets $X$ and $Y$ have the same cardinality when there is a bijection between them:

|X| = |Y| \quad \text{means there exists a bijection } X \to Y.

For finite sets, this agrees with the usual number of elements. For infinite sets, the definition is more subtle and will become important later.

Worked example

A first bijection between $N$ and $Z$

One explicit way to list all integers using natural-number indices is

0, 1, -1, 2, -2, 3, -3, \ldots

This corresponds to a function $f : N \to Z$ such as

f(0)=0,\qquad f(2k+1)=k+1,\qquad f(2k+2)=-(k+1).

Every integer appears exactly once in this list, so this is a bijective enumeration.

Worked example

An injection from $N \times N$ into $N$

The worksheet asks whether one can encode an ordered pair of natural numbers by a single natural number. A clean answer is

F(m,n)=2^m3^n.

This defines a function $F : N \times N \to N$ , because $2^m3^n$ is a natural number for every pair (m,n).

To see that $F$ is injective, suppose

F(m,n)=F(m',n').

Then

2^m3^n = 2^{m'}3^{n'}.

Unique prime factorization says that a positive integer has only one factorization into powers of primes. Therefore the exponent of 2 must agree on both sides, and the exponent of 3 must agree on both sides:

m=m', \qquad n=n'.

So two different ordered pairs cannot be sent to the same natural number.

Definition

Operations as functions

An n-ary operation on a set $S$ is a function

S^n \to S.

For example, addition is a binary operation because it takes a pair of inputs and returns one output in the same set.

A 0-ary operation may look strange at first. It is a function with no input slot and one value in $S$ , so it can be read as choosing a distinguished element of $S$ .

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

The subset relation as a small poset

Let $X=\{a,b\}$ and consider P(X), the set of all subsets of $X$ . Order P(X) by inclusion.

The bottom element is $\varnothing$ , the top element is \{a,b\}, and the two middle elements are \{a\} and \{b\}. The only immediate covering relations are

\varnothing \subset \{a\},\quad \varnothing \subset \{b\},\quad \{a\}\subset \{a,b\},\quad \{b\}\subset \{a,b\}.

A Hasse diagram draws only these immediate covers; all longer comparisons are then understood by transitivity.

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

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

The set of all functions

Read BAB^ABA as a function set

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

Finite self-maps: a left inverse already forces an inverse

Proof idea

Cardinality and operation language

A first bijection between NNN and ZZZ

An injection from N×NN \times NN×N into NNN

Operations as functions

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

The subset relation as a small poset

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 AAA has three elements and BBB has two elements, how many functions are in BAB^ABA?

Answer

If g:X→Xg : X \to Xg:X→X has a left inverse and XXX is finite, what property of g comes first in the proof that g is invertible?

Answer

Why does F(m,n)=2m3nF(m,n)=2^m3^nF(m,n)=2m3n define an injection from N×NN \times NN×N to NNN?

Answer

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

Answer

Why this unit matters later

Section mastery checkpoint

Prerequisites

Key terms in this unit

Premium learning add-ons

More notes in this series

Read $B^A$ as a function set

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

A first bijection between $N$ and $Z$

An injection from $N \times N$ into $N$

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

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

If $A$ has three elements and $B$ has two elements, how many functions are in $B^A$ ?

If $g : X \to X$ has a left inverse and $X$ is finite, what property of `g` comes first in the proof that `g` is invertible?

Why does $F(m,n)=2^m3^n$ define an injection from $N \times N$ to $N$ ?