Relations and Functions Continued

David Lu
July 30, 2018

Recall that the answers are in the comments of the .md file. Replace the .html with .md to view it.

Functions Examples and Exercises

Some definitions first.

Functions are ordinarily denoted by symbols. Suppose that for each element of a set $A$, the domain, we assign a unique element of a set $B$, the codomain. The collection of these assignments is called a function from $A$ to $B$. Let $f$ denote that function. We write:

$f: A \to B$

We can also say that $f$ maps $A$ to $B$.

Functions are often expressed by means of a mathematical formula. For example, consider the function which maps each real number to its square. We can denote this function by writing

• $f(x) = x^2$
• $x \mapsto x^2$
• $y = x^2$

In the first notation, $x$ is called a variable or argument and the letter $f$ denotes the function.
In the second, the barred arrow $\mapsto$ is read "goes to" or "maps to". (The LaTeX command is \mapsto).
In the last, $x$ is called the independent variable and $y$ is called the dependent variable since the value of $y$ depends on the value of $x$.

Exercises:
Find the domain $D$ of each of the following real-valued functions of a real variable:

(a) $f(x) = \frac{1}{x-2}$

(b) $f(x) = x^2 - 3x - 4$

(c) $f(x) = \sqrt{25-x^2}$

Functions as Relations

Every function $f: A \to B$ defines a relation from $A$ to $B$ called the graph of $f$

Graph of $f = \{\langle a, b \rangle | a \in A,f(a) = b \in B\}$

Two functions $f: A \to B$ and $g: A \to B$ are equal if for every $a \in A$, $f(a) = g(a)$, i.e. they have the same graph.

Exercise: Map the function $f(x) = x^2 - 2x - 3$

Classes of Functions

A function is injective (one-to-one) if each element of the codomain is mapped to by at most one element of the domain.
That is, for all $x, x' \in A$, $f(x) = f(x') \to x = x'$

A function is surjective (onto) if each element of the codomain is mapped to by at least one element of the domain.
That is, for all $y \in B$, there exists an $x \in A$ such that $f(x) = y$

A function is bijective (one-to-one and onto or one-to-one correspondence) if each element of the codomain is mapped to by exactly one element of the domain.

Exercises:
Consider functions $f: A \to B$ and $g: B \to C$. Prove the following:
(a) if $f$ and $g$ are injective (one-to-one), then the composition function $g \circ f$ is injective (one-to-one)$.

(b) if $f$ and $g$ are surjective (onto) functions, then $g \circ f$ is an surjective (onto) function.

Determine if each function is injective (one-to-one):
(c) To each person on the earth, assign the number which corresponds to her or his age.
(d) To each country in the world, assign the latitude and longitude of its capital.
(e) To each book written by only one author, assign the author.
(f) To each country in the world which has a prime minister, assign its prime minister.

Sets, Logic, Computation

Problem 3.1. Show that if $f$ is bijective, an inverse $g$ of $f$ exists. (define such a $g$ show that it is a function, and show that it is an inverse of $f$.)

Proof.
Let $f: A \to B$ be bijective. We'll define a function $g: A \to B$ = $f^{-1}$ as follows. Let $b \in B$. since $f$ is surjective, there exists $a \in A$ such that $f(a) = b$. Let $g(b) = a$. Since $f$ is injective, this $a$ is unique, so $g$ is a well-defined function.

Next, we show that $g$ is the inverse of $f$. First, we show that $g \circ f = id_A$.
First, let $a \in A$. Let $b = f(a)$. Then by definition $g(b) = a$. then $g \circ f(a) = g(f(a)) = g(b) = a$.
Second, show that $f \circ g = id_B$. Let $b \in B$ and $f^{-1}(b) = g(b) = a$. By definition, $f(a) = b$. It follows that $f \circ g(b) = f(g(b)) = f(a) = b$.