2.2 Functions and relations

An ordered pair $(x,y)$ records a directed connection from an element of $X$ to an element of $Y$. A collection of such connections is therefore a subset of the Cartesian product $X\times Y$. Some connections assign exactly one output to every input; others allow several outputs or none. The general set language lets us distinguish these possibilities.

Definition 2.2.1

(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$.

Functions are special relations

Definition 2.2.2

(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$.

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 $\{(x,f(x)):x\in X\}$, the set of pairs with input $x\in X$ and output $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.

How to test a proposed graph

For a subset $\Delta \subset X \times Y$ to be the graph of a function $X \to Y$, every $x \in X$ must occur in exactly one pair $(x,y) \in \Delta$. There are two separate failure modes. A missing input has no corresponding output, so it violates existence. An input paired with two different outputs violates uniqueness. The entire stated domain must be covered exactly once.

For example, $\Delta=\{(n+10,n):n\in\mathbb N\}$ viewed as a subset of $\mathbb N\times\mathbb Z$ misses input $0$, since $n+10=0$ would require $n=-10$. It is therefore not a graph of a function from $\mathbb N$. By contrast, $\{(n+10,n):n\in\mathbb Z\}$ is a graph from $\mathbb Z$ to $\mathbb Q$: for each integer $x$, the unique choice is $n=x-10$. The set $\{(x^2,x^3):x\in\mathbb Q\}$ is also not a graph from $\mathbb Q$ to $\mathbb Q$; it misses negative inputs and has both $(1,1)$ and $(1,-1)$ as pairs for input $1$.

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|}$. If $A$ is empty there is exactly one function, the empty function, including when $B$ is empty; this count uses the combinatorial convention $0^0=1$.

Worked example 2.2.3

(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 2.2.4

(The square function has repeated outputs)

Take $f:\mathbb R\to\mathbb R$ defined by $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$.

The graph of a function is a very special subset of a product: every vertical line through an allowed input hits the graph exactly once.

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.

For $f:X\to Y$ and $g:Y\to Z$, composition is the function $g\circ f:X\to Z$ defined by

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

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

Worked example: computing compositions

Let $f,g,h:\mathbb R\to\mathbb R$ be given by $f(x)=x+1$, $g(x)=x^2$, and $h(x)=x-7$. Direct substitution gives

$$\begin{aligned} f\circ f&:x\mapsto x+2, & f\circ g&:x\mapsto x^2+1, & f\circ h&:x\mapsto x-6,\\ g\circ f&:x\mapsto (x+1)^2, & g\circ g&:x\mapsto x^4, & g\circ h&:x\mapsto (x-7)^2,\\ h\circ f&:x\mapsto x-6, & h\circ g&:x\mapsto x^2-7, & h\circ h&:x\mapsto x-14. \end{aligned}$$

The rightmost function is applied first.

Image and preimage identities

Let $f:X\to Y$, $A,B\subset X$, and $C,D\subset Y$. The image of a union satisfies

$$f(A\cup B)=f(A)\cup f(B).$$

For the inclusion from left to right, take $y\in f(A\cup B)$. Then $y=f(x)$ for some $x\in A\cup B$. If $x\in A$, then $y\in f(A)$; if $x\in B$, then $y\in f(B)$. Thus $y\in f(A)\cup f(B)$. Conversely, if $y\in f(A)\cup f(B)$, it has a preimage in $A$ or in $B$, and that preimage also lies in $A\cup B$; hence $y\in f(A\cup B)$.

For intersections only inclusion is guaranteed:

$$f(A\cap B)\subset f(A)\cap f(B).$$

Indeed, a value obtained from an input in $A\cap B$ is obtained from an input in each of $A$ and $B$. Equality can fail when two different inputs collide. Take $X=\{1,2\}$, $Y=\{0\}$, $f(1)=f(2)=0$, $A=\{1\}$, and $B=\{2\}$. Then $f(A\cap B)=\varnothing$, while $f(A)\cap f(B)=\{0\}$.

Preimages preserve both unions and intersections, with full membership proofs:

$$f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D), \qquad f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D).$$

For the union, $x\in f^{-1}(C\cup D)$ means $f(x)\in C\cup D$, so $f(x)\in C$ or $f(x)\in D$; this is exactly $x\in f^{-1}(C)\cup f^{-1}(D)$. Reading the same equivalence backwards proves the reverse inclusion. For the intersection, $x\in f^{-1}(C\cap D)$ means $f(x)\in C$ and $f(x)\in D$, which is exactly $x\in f^{-1}(C)\cap f^{-1}(D)$; again both directions are the same membership equivalence.

The corresponding difference and complement laws must state their ambient sets:

$$f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D), \qquad f^{-1}(Y\setminus C)=X\setminus f^{-1}(C).$$

For example, $x$ belongs to the first left side exactly when $f(x)\in C$ and $f(x)\notin D$, which is the condition on the right. In the complement law, $Y\setminus C$ is the complement inside the target $Y$, while $X\setminus f^{-1}(C)$ is the complement inside the domain $X$.

Worked example 2.2.5

(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\},$$

Every listed point maps into $B$. Conversely, if $x^2\in\{0,1,4\}$, then $x^2=0$, $x^2=1$, or $x^2=4$. Factoring each equation gives respectively $x=0$, $x=\pm1$, or $x=\pm2$. Hence there are no other real preimages.

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

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

Injective, surjective, bijective

Definition 2.2.6

(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, for all $x_1,x_2\in X$, $f(x_1)=f(x_2)$ implies $x_1=x_2$.
• $f$ is surjective if $f(X) = Y$.
• $f$ is bijective if every element of the target is hit exactly once.

Worked examples: injectivity and surjectivity

First consider the finite map $X=\{0,1,3,5\}$, $Y=\{5,7,11\}$, with values $f(0)=7$, $f(1)=5$, $f(3)=11$, and $f(5)=5$. The value $5$ is attained by two inputs, so the map is not injective. All three elements of $Y$ occur, so it is surjective.

Next consider $f:\{-2,-1,0,1,2\}\to\mathbb Z$ defined by $f(x)=x^5+3x+1$. Its five values are

$$f(-2)=-37,\quad f(-1)=-3,\quad f(0)=1,\quad f(1)=5,\quad f(2)=39.$$

They are distinct, so this map is injective. It is not surjective onto $\mathbb Z$, since, for example, $0$ is not among the values.

Finally, $f:\mathbb Z\to\mathbb Z$, $f(x)=x^2+x$, is not injective: $f(0)=f(-1)=0$ with $0\ne-1$. It is not surjective either, because $x^2+x=x(x+1)$ is always even, so no odd integer can be an output.

Read the arrows to distinguish the definitions

An arrow diagram tests unique outputs, collisions, and whether the target is covered.

Theorem 2.2.7

(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

If $f$ is injective and surjective, then for every $y \in Y$ there is a unique $x \in X$ with $f(x) = y$.

That uniqueness lets us define a new function $g : Y \to X$ by declaring $g(y)$ to be the unique $x$ satisfying $f(x)=y$.

By construction, $g(f(x)) = x$ and $f(g(y)) = y$, so $g$ is the inverse of $f$.

Proof: uniqueness and existence of inverses

Suppose $g,h:Y\to X$ are both inverses of $f:X\to Y$. Using associativity of composition and both inverse equations,

$$g=g\circ id_Y=g\circ(f\circ h)=(g\circ f)\circ h=id_X\circ h=h.$$

Thus an inverse, when it exists, is unique. Composition is associative: if $f:X\to Y$, $g:Y\to Z$, and $k:Z\to W$, then for every $x\in X$,

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

The later inverse-implications proof establishes necessity: an inverse makes $f$ bijective. The construction above gives the inverse of a bijection.

Worked example 2.2.8

(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.

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

For $f:X\to Y$, the inverse equations have different domains:

• A left inverse $h:Y\to X$ satisfies $h \circ f = id_X$.
• A right inverse $g:Y\to X$ satisfies $f \circ g = id_Y$.

These conditions are not the same in general.

Worked example 2.2.9

(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$.

The missing value $δ$ rules out $f_1\circ g=id_Y$, so no right inverse exists.

Worked example 2.2.10

(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$.

The collision $f_2(α)=f_2(β)$ rules out a left inverse.

Theorem 2.2.11

(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: a finite self-map with a left inverse

The equation $h \circ g = id_X$ says that $g$ is injective: if $g(x_1)=g(x_2)$, then applying $h$ gives $x_1=x_2$.

For a finite set, an injective map from $X$ to itself is automatically surjective. Thus $g$ has a two-sided inverse $g^{-1}$. Using $h\circ g=id_X$,

$$h=h\circ id_X=h\circ(g\circ g^{-1})=(h\circ g)\circ g^{-1}=g^{-1}.$$

Therefore $g\circ h=id_X$ as well. The argument also covers the empty set, whose only self-map is the empty function.

Proof: inverse implications and their converses

For $f:X\to Y$ and $h:Y\to X$, if $h\circ f=\operatorname{id}_X$, then $f(x)=f(x')$ implies $x=h(f(x))=h(f(x'))=x'$. Thus a left inverse implies injectivity. If $f\circ h=\operatorname{id}_Y$, each $y$ equals $f(h(y))$, so a right inverse implies surjectivity.

Conversely, suppose $f$ is injective and $X\ne\varnothing$. Fix one $x_0\in X$. Define $h(y)$ as the unique preimage when $y\in f(X)$ and as $x_0$ otherwise. This is a left inverse and uses no axiom of choice: one fixed fallback value suffices. For $X=\varnothing$, the injection into a nonempty $Y$ has no left inverse, since no map $Y\to\varnothing$ exists. When both sets are empty, the empty map is its own inverse.

For a surjection, constructing a right inverse means choosing one element from each fibre $f^{-1}(\{y\})$. Explicit choices or finite choices require no general choice axiom. The assertion that every arbitrary surjection has a right inverse invokes the axiom of choice. This differs from the unique preimages of a bijection, which require no such selection principle.

Worked example 2.2.12

(An infinite inclusion with a total left inverse)

Let $i:\mathbb N\to\mathbb Z$ be $i(n)=n$, with $0\in\mathbb N$. Define $h:\mathbb Z\to\mathbb N$ by $h(z)=z$ for $z\ge0$ and $h(z)=0$ for $z<0$. Then $h(i(n))=n$ for every $n$. There is no right inverse because a negative integer, such as −1, has no preimage under $i$.

Relations without the function condition

A function covers each input exactly once. Dropping that restriction allows us to compare objects by order, divisibility or a shared property, without choosing one output for each input.

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

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 2.2.13

(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.

Relations let us talk about connections without forcing uniqueness. That is exactly what we need for order relations and equivalence relations later on.

Relations on one set

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

Theorem 2.2.14

(Four properties used constantly)

A relation on $X$ may have these properties, each required for all indicated elements of $X$:

• 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 2.2.15

(The divisibility relation is a partial order)

On the positive integers $\mathbb Z_{\gt0}$, 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.

The qualification “positive” matters. On all of $\mathbb Z$, both $1\mid-1$ and $-1\mid1$, although $1\ne-1$, so antisymmetry would fail there.

Posets are not just a vocabulary item. They let us organize objects by how one contains, refines, or divides another.

Relation tests and counterexamples

Let $X=\mathcal P(\{1,2,3,4\})$ and define $xRy$ by $x\cap y=\varnothing$. This relation is not reflexive: a nonempty set such as $\{1\}$ does not have empty intersection with itself. It is symmetric because intersection is symmetric. It is not transitive: with $x=\{1\}$, $y=\varnothing$, and $z=\{1\}$, we have $xRy$ and $yRz$, but not $xRz$. It is not antisymmetric: $\{1\}R\{2\}$ and $\{2\}R\{1\}$, although the two sets are different.

Now test the following relations on the integers:

• $x-y$ odd is not reflexive, since $x-x=0$; it is symmetric, but not transitive, since $0R1$ and $1R2$ while $0$ is not related to $2$.
• $x+y$ even is an equivalence relation. Reflexivity and symmetry are immediate, and if $x+y$ and $y+z$ are even, then $(x+z)=(x+y)+(y+z)-2y$ is even. Its two classes are the even integers and the odd integers.
• $x+y=0$ is not reflexive (except at $0$) and is not transitive: $1R(-1)$ and $(-1)R1$, but $1$ is not related to itself.
• The condition $x|y|=|x|y$ is reflexive and symmetric because it is equivalent to saying that $x$ and $y$ have the same sign, or that at least one is zero. It is not transitive: $1R0$ and $0R(-1)$, but $1$ is not related to $-1$. Therefore it is not an equivalence relation, and it has no equivalence classes to list.

These examples show why each relation property must be tested separately; a single failed property is enough to rule out equivalence.

Worked example 2.2.16

(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 2.2.17

(A simple equivalence relation)

For a positive integer $m$, congruence modulo $m$ is an equivalence relation on $Z$: integers are related when they have the same remainder. Modulo $3$, the three classes contain the integers congruent to $0$, $1$, and $2$, and these classes partition $Z$.

Proof: congruence modulo $m$

Fix $m\in\mathbb Z$ with $m\gt0$. Define $a\equiv b\pmod m$ when $m\mid(a-b)$. This is an equivalence relation on $\mathbb Z$.

It is reflexive because $a-a=0$ and every positive $m$ divides $0$. It is symmetric because if $m\mid(a-b)$, then $m\mid-(a-b)=b-a$. It is transitive: if $m\mid(a-b)$ and $m\mid(b-c)$, then $m$ divides their sum $(a-b)+(b-c)=a-c$. Thus all three required properties hold.

The class of $a$ is

$$[a]_m=\{b\in\mathbb Z:m\mid(a-b)\},$$

so the classes are exactly the residue classes modulo $m$.

Equivalence classes and quotient sets

Modulo $3$, the integers $1$, $4$ and $-2$ have the same remainder. They are different integers, but the congruence relation deliberately ignores their differences by multiples of $3$. If that is the information we want to retain, we need one object representing all these equivalent integers.

Choosing the label $1$ is convenient, but another representative such as $4$ should identify the same object. The set of all integers related to $1$ provides that object: replacing $1$ by $4$ gives exactly the same set. An equivalence class makes this independence of the representative part of the construction.

For a general relation, the collections attached to two elements might overlap without being equal. Reflexivity, symmetry and transitivity rule out that ambiguity. The partition theorem below proves precisely why classes of an equivalence relation can be treated as separate new objects.

Definition 2.2.18

(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 2.2.19

(Quotient set)

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

Theorem 2.2.20

(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: overlapping equivalence classes are equal

Reflexivity gives $xRx$, hence $x\in[x]_R$ for every $x\in X$. Thus the classes cover $X$.

Suppose $z\in[x]_R\cap[y]_R$. Then $zRx$ and $zRy$. If $u\in[x]_R$, we have $uRx$; symmetry gives $xRz$, and transitivity gives $uRz$ and then $uRy$. Hence $u\in[y]_R$, proving $[x]_R\subseteq[y]_R$.

Conversely, if $v\in[y]_R$, then $vRy$; symmetry gives $yRz$, so transitivity yields $vRz$ and then $vRx$. Thus $v\in[x]_R$, proving $[y]_R\subseteq[x]_R$. Two inclusions give equality. Therefore unequal classes cannot intersect, and the distinct classes form a partition of $X$.

The integer construction and rational construction use this method on pairs. After forming the classes, arithmetic needs a further check: choosing a different representative must give the same output class. The partition theorem defines the objects; well-definedness makes operations on those objects legitimate.

Comparing sets by bijections

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.$$

Worked example 2.2.21

(A first bijection between $N$ and $Z$)

$$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 2.2.22

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

One useful countability test is whether an ordered pair of natural numbers can be encoded 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.

The later cardinality note develops these comparisons for infinite sets.

Combining elements by functions

A function can also supply an operation: it takes a tuple of elements of one set and returns another element of that same set. Specifying this type records both the number of inputs and closure of the result.

Definition 2.2.23

(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.

For $n=0$, $S^0$ is the singleton containing the empty tuple. A function $S^0\to S$ therefore chooses one distinguished element of $S$; no such function exists if $S$ is empty. Binary operations and the laws they may satisfy are studied in monoids and groups.

Common mistakes

Common mistake

(Symmetric is not the same as antisymmetric)

On $\mathbb R$, $≤$ is antisymmetric but not symmetric. Equality is both symmetric and antisymmetric, while divisibility on $\mathbb Z_{\gt0}$ 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

It is a relation, because it is a subset of $R \times R$. It is not a function, because one input $x$ is related to many possible values of $y$.

Quick check

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

Separate preimage notation from inverse-function notation.

Solution · Answer

Yes. The preimage always exists.

Quick check

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

Choose one output in $B$ for each input in $A$.

Solution · Answer

There are $2^3 = 8$ functions.

Quick check

(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?)

Use the equation $h \circ g = id_X$.

Solution · Answer

First prove that $g$ is injective. Since $X$ is finite, injective then implies surjective, so $g$ is bijective.

Quick check

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

Use the exponents of the primes $2$ and $3$.

Solution · Answer

If $2^m3^n = 2^{m'}3^{n'}$, unique prime factorization forces $m=m'$ and $n=n'$. Therefore equal outputs imply equal ordered pairs, so $F$ is injective.

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

It is an equivalence relation.