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

By De Morgan's laws, taking a set difference from a union requires exclusion from both sets, while taking a set difference from an intersection requires exclusion from at least one:For example, $x$ belongs to the first left-hand side precisely when $x\in A$, $x\notin B$ and $x\notin C$; these are exactly the membership conditions on the first right-hand side. For the second identity, replace the two exclusions by their logical disjunction.

Prove both identities by mathematical induction. The base case $n=2$ is the two-set form of De Morgan's laws. For the union identity, suppose the result holds for $n$. Applying the two-set identity and then the inductive hypothesis givesFor the intersection identity, the corresponding step isThese close the two inductions.

Apply the two identities already proved with $A=\mathcal{U}$. Every $B_i$ is a subset of the common universe, and a complement is the set difference from that universe. ThereforeReplacing each set difference from $\mathcal{U}$ by its complement notation gives the claimed finite forms of De Morgan's laws.

Function composition is not always commutative. The reversed function composition may be undefined when the necessary domain of a function and codomain do not match. A counterexample using functions $\mathbb{R}\to \mathbb{R}$ avoids that issue: let $f(x)=x+1$ and $g(x)=2x$. ThenBoth function compositions exist, and their values differ at every real $x$.

For every $x\in \mathbb{R}$, the definition of function composition givesThe functions agree at every argument, so function extensionality proves the associative property of function composition.

The real cube root in the denominator vanishes at $x=-1$, so the printed rule needs the domain of a function $D_1=\mathbb{R}\setminus \{-1\}$. On its actual domain of a function, the second iterated function simplifies toThis suggestsFor the induction step, assume the formula at $n$ and restrict to arguments for which its value is not $-1$. Its cube is $x^3/(1+n{x}^3)$, so another application givesReal cube roots are multiplicative, including for negative arguments. The newly excluded point satisfies $x^3/(1+n{x}^3)=-1$, hence $x^3=-1/(n+1)$; all earlier exclusions remain. This proves both the formula and the domain of a function by mathematical induction. The inherited exclusions are essential for an iteration of a partial function: cancellation in the final expression cannot repair an undefined intermediate application.

Set $y=f(x)$ and cube the equation. Solving for $x^3$ givesConsequently the inverse function isThe value $y=1$ is impossible in the original equation. Conversely, every real $y\ne 1$ gives exactly one real $x$ by the displayed cube root, and this $x$ cannot equal $-1$. Direct substitution verifies both inverse identities. Thus the corrected bijection is $f:\mathbb{R}\setminus \{-1\}\to \mathbb{R}\setminus \{1\}$.