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

Write each set difference as an intersection with a complement of a set. Applying De Morgan's laws and then the distributive property givesThe complements turn the inner union into an intersection and vice versa. Thus

Apply the distributive property to the intersection with $\overline{C}$:In the first line the repeated factor $\overline{C}$ changes nothing. Rewriting in terms of set differences yields

Use De Morgan's laws to remove the complement of a set, then distribute the two unions:The first and last intersections in the middle line are the empty set. The remaining union is precisely the collection of elements belonging to exactly one of the original sets. Therefore both expressions define the same symmetric difference:

An algebraic way to prove the set identity is to show that $D=\overline{A}\cup \overline{B}$ is a complement of a set for $A\cap B$. By the distributive property,andA complement of a set is unique: if $D,E$ both complement $S$, then $D=D\cap (S\cup E)=D\cap E$, and similarly $E=D\cap E$. Consequently

Write the set difference as an intersection and use the fact that taking the complement of a set twice returns that set. The commutativity of intersection gives the reversible calculation

Use the symmetric difference formula from part (b), followed by the set difference identity from part (c)(ii):Taking both complements swaps the two ways to belong to exactly one set, leaving their union unchanged:

The image of a function is the set of values actually attained as its argument ranges over its domain of a function:It is a subset of the codomain $B$, and need not equal $B$.

The function is surjective, also called onto, when every element of its codomain has at least one preimage:The condition concerns the specified codomain, not just the formula defining the function.

The function is injective, also called one-to-one, when equal outputs force equal inputs:Equivalently, different elements of the domain of a function always have different images.

A bijection is a function that is both injective and surjective. Each element of the codomain then has exactly one preimage:This unique-preimage property allows the inverse function $f^{-1}:B\to A$ to be defined on all of $B$.

If $n$ is positive and odd, $n^2$ is odd. The function $x\mapsto x^{n^2}$ is a strictly increasing function on the real numbers, so it is injective. Every real $y$ has the real odd root $\mathrm{sgn}(y)|y{|}^{1/n^2}$, so the function is also surjective.

If $n$ is positive and even, the exponent is positive and even. Then $f(1)=f(-1)$, while $f(x)\ge 0$ for all real $x$. These facts disprove injectivity and surjectivity, respectively. ThereforeIf the convention $0\in \mathbb{N}$ is used, $n=0$ gives exponent zero. Interpreting $x^0$ as the constant polynomial $1$ makes the function neither injective nor surjective. If $0^0$ is left undefined, that case does not define the stated function on all the real numbers. Neither convention adds a qualifying value of $n$.

The function composition of two bijections is a bijection. Its inverse function is two-sided, soThis is exactly the defining cancellation property of an inverse function, with the whole function composition regarded as one function.

The inverse factors are generally in the wrong order. For a counterexample, take the bijections $f(x)=x+1$ and $g(x)=2x$, with inverse functions $f^{-1}(x)=x-1$ and $g^{-1}(x)=x/2$. ThenThusFor particular bijections that commute the equality can hold; the claim fails as a universal assertion.

Use the associativity of function composition to cancel adjacent inverse functions in the right order:Therefore

For the bijections $f(x)=x+1$ and $g(x)=2x$ used above, $f\circ g$ sends $x$ to $2x+1$. Its inverse function sends $x$ to $(x-1)/2$, whereas $f^{-1}\circ g^{-1}$ sends $x$ to $x/2-1$. Hence

The proposed inverse function cancels on both sides:The uniqueness of an inverse function therefore givesThe operation applied last must be undone first.