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

For the first set inclusion, take $x\in (A\cap B)\setminus C$. By the definitions of set intersection and set difference, $x\in A$, $x\in B$ and $x\notin C$. Consequently $x\in A\setminus C$ and $x\in B\setminus C$, so $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, take $x\in (A\setminus C)\cap (B\setminus C)$. Membership in the first set difference gives $x\in A$ and $x\notin C$, while membership in the second gives $x\in B$ and $x\notin C$. Thus $x\in A\cap B$ and $x\notin C$, proving $x\in (A\cap B)\setminus C$. The two inclusions establish the required equality.

The set difference $\varnothing \setminus \varnothing$ is the empty set. Its power set contains exactly one element, the empty set itself. Therefore the cardinality is $1$, not zero.

A binary relation on $A$ is any subset of the Cartesian product $A\times A$. There are $n^2$ ordered pairs, and each can independently be included or omitted. Hence the number of binary relations is $2^{n^2}$. This also gives one relation when $n=0$, namely the empty set.

The function is injective and surjective, with inverse function $f^{-1}(y)=1-y$. Equality $1-x=1-x^{\prime }$ forces $x=x^{\prime }$. For any $y\in (0,1)$, the input $x=1-y$ also lies in $(0,1)$ and satisfies $f(x)=y$. Applying the function twice returns the original input.

It is neither injective nor surjective onto $\mathbb{R}$, so it has no inverse function on the stated domain and codomain. The distinct inputs $0$ and $\pi /3$ both lie in the domain and both give zero. All values lie in $[-1,1]$, so, for example, the real number $2$ has no preimage.

It is surjective but not injective; there is no global inverse function. Noninjectivity follows fromFor surjectivity, restrict to $x<1$, whereThis restriction is a continuous function, tends to $-\infty$ as $x\to -\infty$ and to $+\infty$ as $x\to 1^{-}$. The intermediate value theorem therefore supplies a preimage for every real number. The additional branch $x>1$ destroys global injectivity but cannot destroy surjectivity.

The iterated function is $f^{(n)}(x)=\sqrt{x^2+n}$ for every positive integer $n$. The exponent here denotes repeated function composition, not an ordinary power or a derivative.

For the base case $n=1$, the formula is the definition. If it holds at $n$, thenThis proves the claim by mathematical induction, for every real input $x$.

There are six functions: the four power maps $x\mapsto x^k$ for $k=1,2,3,4$, and the two constant maps $0,1$. All calculations in this part are in the finite field ${\mathbb{Z}}_5$.

Put $e=f(1)$. Multiplicativity gives $e^2=e$, so the absence of zero divisors forces $e=0$ or $e=1$. If $e=0$, then $f(x)=f(x)f(1)=0$ for every $x$, giving only the constant-zero map.

Suppose $e=1$. For nonzero $x$, the equality $f(x)f(x^{-1})=1$ shows $f(x)\ne 0$. The nonzero elements form a cyclic group generated by $2$, in the order $1,2,4,3$. Choosing $a=f(2)$ determines every value on this group by $f(2^j)=a^j$. Each $a\in \{1,2,3,4\}$ satisfies $a^4=1$, so all four choices give consistent group homomorphisms.

Finally, $z=f(0)$ satisfies $z^2=z$ and $z=zf(x)$ for every $x$. The choice $z=0$ works for all four group maps. The choice $z=1$ forces every nonzero value to be $1$, giving one extra map, the constant-one map. Thus the count is $1+4+1=6$. The four zero-preserving possibilities are exactly the four displayed power maps. This is the special case with five elements of multiplicative self-maps of a finite field.