2.2 Functions and relations

Functions and relations turn product sets into structured mathematical objects: functions impose unique outputs, while relations record general connections.

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

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

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

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.

Composition is defined by

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

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

Worked example: computing compositions

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

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

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.

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

Use one arrow diagram to keep domain, target, image, preimage, injectivity, surjectivity, and composition distinct.

1. Domain and target

   A function f:X->Y is a relation where every input in X has exactly one output in the target Y.

2. Graph as ordered pairs

   The graph stores the same arrows as ordered pairs inside X x Y, with one pair for each input.

3. Image and preimage

   Image is read forward to reached outputs; preimage is read backward from an output set to the inputs that land there.

4. Injective

   Injective means no collision: if two inputs have the same output, they must have been the same input.

5. Surjective

   Surjective means the actual image equals the whole target, so no target element is missed.

6. Composition

   For g o f, first apply f and then feed the resulting output into g.

The same arrow diagram separates the main definitions. A function gives each input exactly one output, injectivity forbids collisions, surjectivity covers the target, and composition feeds one output into the next map.

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

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

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

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

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

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

The collision $f_2(α)=f_2(β)$ rules out 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: 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$ is bijective. Since its inverse is unique and $h$ already undoes $g$ on the left, $h$ must be the inverse function. Therefore $g \circ h = id_X$ as well.

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

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

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.

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

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

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

An equivalence relation declares which differences we will ignore. Before constructing a new object from its equivalence class, we must prove that every representative gives the same class. The partition theorem below makes that step precise; the integer and rational constructions will reuse it.

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

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

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

Worked example

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

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.

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

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

Checkpoint

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

Checkpoint

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

Separate preimage notation from inverse-function notation.

Solution · Answer

Yes. The preimage always exists.

Checkpoint

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.

Checkpoint

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.

Checkpoint

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.

Checkpoint

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.