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

Write $C^c=\mathcal{U}\setminus C$. The rules for set difference, set intersection, and complement of a set giveThe second step is De Morgan's laws; the third distributes set intersection over set union. The fourth uses $A\cap A^c=\varnothing$.

Using set difference as intersection with a complement of a set, then De Morgan's laws and distribution, givesFor the third equality, expand the two set unions: the terms $A\cap C^c$ and $A\cap B$ are absorbed by $A$, and $A\cap A=A$. This proves the required identity entirely by set algebra.

By definition the symmetric difference is $A\oplus B=(A\setminus B)\cup (B\setminus A)$. Put $D=A\oplus B$ and $E=A\cap B$. Distribution of set intersection over set union givesFor disjoint sets, set difference removes nothing, so $D\oplus E=(D\setminus E)\cup (E\setminus D)=D\cup E$. ConsequentlyHere the second equality combines $A\cap B^c$ with $A\cap B$; the last uses $A\cup A^c=\mathcal{U}$.

A function $f:A\to B$ is onto, or a surjective function, when every $b\in B$ has a preimage: $\forall b\in B\exists a\in A:f(a)=b$. It is one-to-one, or an injective function, when $f(a)=f(a^{\prime })$ implies $a=a^{\prime }$ for all $a,a^{\prime }\in A$. It is bijective, a bijection, when both properties hold.

An inverse function is a function $f^{-1}:B\to A$ satisfyingFor a bijection, $f^{-1}(b)$ is the unique $a$ with $f(a)=b$: existence follows from surjectivity and uniqueness from injectivity. This is a two-sided inverse function, rather than just a left or right inverse.

The function composition $g\circ f:A\to C$ is defined by $(g\circ f)(a)=g(f(a))$. Suppose $f(a)=f(a^{\prime })$. Applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Since the composite is an injective function, $a=a^{\prime }$. Thus $f$ is an injective function.

For each $c\in C$, surjectivity of the function composition gives $a\in A$ such that $g(f(a))=c$. Taking $b=f(a)\in B$ supplies a preimage of $c$ under $g$. Thus $g$ is a surjective function.

Let $h:B\to A$ be a two-sided inverse function of $f$. If $f(a)=f(a^{\prime })$, apply $h$ and use $h\circ f={\mathrm{id}}_A$ to obtain $a=a^{\prime }$, proving injectivity. For any $b\in B$, the other identity gives $b=f(h(b))$, proving surjectivity. Therefore $f$ is a bijection. Both inverse identities matter: a one-sided inverse alone would establish only the corresponding one of these two properties.

Replace $x$ by $1/x$, which stays in the domain of the functional equation. Writing $u=f(x)$ and $v=f(1/x)$ gives the linear systemTwice the second equation minus the first gives $3u=2/x-x$, so the only possible function isTo check existence as well as uniqueness, substitute this expression: $f(x)+2f(1/x)=(2/x-x+4x-2/x)/3=x$.

The algebraic identitysuggests $f(t)=t^3-3t$ for every $t>0$, and substitution verifies the functional equation.

In fact $x+1/x\ge 2$, since $(x-1{)}^2/x\ge 0$. Conversely, for each $t\ge 2$, the quadratic equation $x^2-tx+1=0$ has a positive root $(t+\sqrt{t^2-4})/2$. Thus the functional equation forces $f(t)=t^3-3t$ exactly on $[2,\infty )$; its values on $(0,2)$ are arbitrary. The displayed function is one convenient choice on the full required domain.