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

The set difference consists of elements belonging to the first set but not the second:The symmetric difference consists of elements belonging to exactly one of the two sets:In particular, the two sets in this union are disjoint sets.

Every complement of a set is taken in the same universal set $\mathcal{U}$. Apply De Morgan's laws for propositional logic to the membership propositions. For every $x\in \mathcal{U}$,Equality of membership for every element proves the set identities

Using set difference as an intersection with a complement of a set, and using double negation, givesInterchanging the two sets simply interchanges the two terms of this union, whose commutativity gives

We use a double inclusion proof. First, let $x\in \overline{A\oplus B}$. If $x\in A$, then $x\in B$, since otherwise $x\in A\setminus B\subseteq A\oplus B$. Hence in this case $x\in A\cap B$. If $x\notin A$, then $x\notin B$, since otherwise $x\in B\setminus A\subseteq A\oplus B$. Hence in this case $x\in \overline{A\cup B}$. This proves the first set inclusion.

Conversely, an element of $A\cap B$ belongs to neither $A\setminus B$ nor $B\setminus A$. An element of $\overline{A\cup B}$ also belongs to neither set difference. Thus every element of $(A\cap B)\cup \overline{A\cup B}$ lies outside $A\oplus B$, proving the reverse set inclusion. Therefore

The identity function fixes every element, and function composition means applying the inner function first:

If $f(x)=f(y)$, applying the function $f$ gives $f(f(x))=f(f(y))$. Since $f\circ f={\mathrm{id}}_A$, this implies $x=y$, proving injectivity. Also every $y\in A$ is the image of $f(y)$, because $f(f(y))=y$, proving surjectivity.

Thus $f$ is a bijection and its inverse function is itself:Such a function is an involution.

Take the functionThen $f(f(x))=-(-x)=x$ for every real number $x$, while $f(1)=-1\ne 1$. Thus it is an involution different from the identity function.

Seek an affine function $f(x)=cx+d$. Its function composition with itself isEquating coefficients requires $c^2=a$ and $(c+1)d=b$. Because $a>0$ and $a\ne 1$, either choice $c=\sqrt{a}$ or $c=-\sqrt{a}$ has $c+1\ne 0$. Thus two valid functions areSubstitution into $c^{2}x+(c+1)d$ verifies each answer. These provide the requested maps; no assumption that every possible solution is affine function is needed.

Try a linear function $f(x)=cx$. The functional equation becomes $c^{2}x=(c+1)x$ for all $x$, so $c$ must be a root of a polynomial $c^2-c-1$. Its two roots of a polynomial giveFor either choice, $c^2=c+1$ proves the required equality directly. The positive coefficient is the golden ratio.