Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 1

A function $f:X\to Y$ is injective if, for all $x,x^{\prime }\in X$, $f(x)=f(x^{\prime })$ implies $x=x^{\prime }$. Thus distinct elements of the domain of a function have distinct images.

A function $f:X\to Y$ is surjective if every element of its codomain has a preimage: for every $y\in Y$, there is some $x\in X$ such that $f(x)=y$.

A function is bijective if it is both injective and surjective. Equivalently, each element of the codomain has exactly one preimage.

Not injective; surjective. Indeed, $f(0)=f(-1)=-9$ although $0\ne -1$. This polynomial is continuous, with $f(x)\to -\infty$ as $x\to -\infty$ and $f(x)\to \infty$ as $x\to \infty$. For any prescribed real $y$, choose $a<b$ with $f(a)<y<f(b)$; the intermediate value theorem supplies a preimage between $a$ and $b$.

Both injective and surjective. The natural logarithm is strictly increasing on the positive real numbers, so it is injective. For every $y\in \mathbb{R}$, $x=e^y>0$ satisfies $\ln x=y$; hence the function is surjective, with the exponential function as its inverse function.

Not injective; its image of a function is exactly $\{1,2,3,\dots \}$. For example, both $x=e^{-1}$ and $x=e^{-1/2}$ give the ceiling function value $1$. Since $0<x<1$, $(\ln x{)}^2>0$, so the value $0$ is never attained. For every positive integer $j$,Each such interval is nonempty and contained in $(0,1)$, with the upper endpoint $1$ excluded when $j=1$. Thus the answer concerning surjectivity depends on the convention for the natural numbers: onto if $\mathbb{N}=\{1,2,\dots \}$, and not onto if $0\in \mathbb{N}$. The source does not settle that convention.

Not injective; surjective. The equal values $f(0)=f(2)=1$ disprove injectivity. For any $y>0$, take $x=1+y^{-1/2}>1$. This lies in the stated domain of a function, andConsequently every member of the codomain has a preimage.

Suppose $g(y)=g(y^{\prime })$. Applying $f$ and using the right inverse identity givesThis is exactly injectivity, so every right inverse is injective.

For each $y\in Y$, surjectivity makes the fiber of a function $f^{-1}(\{y\})$ nonempty. Choose one element $x_y$ of each such fiber of a function and define $g(y)=x_y$. Then $f(g(y))=y$ for every $y$, proving $f\circ g=I_Y$. For arbitrary sets, the simultaneous selection invokes the usual axiom of choice; this is the right-inverse characterization of the axiom of choice. For finite $Y$ only finitely many choices are needed. If $Y$ is empty, the unique empty function gives the same conclusion.

Put $B=T\cap S$. By distributivity, $g(A)=B\cup (T\cap A)$ and $B\subseteq T$. Consequently,Here we used associativity, distributivity, and idempotence of set intersection and set union. The equality holds for every $A\in \mathcal{P}(U)$, so $g\circ g=g$: $g$ is an idempotent function.