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

The image of a function $f:A\to B$ isThe function is surjective, or onto, exactly when every $b\in B$ equals $f(a)$ for at least one $a\in A$, equivalently $f(A)=B$. It is injective, or one-to-one, exactly whenThus surjectivity concerns whether the entire codomain is reached; injectivity concerns whether distinct inputs have distinct outputs.

Since $x^2+1\ge 2|x|$, the image of a function is contained in $[-1/2,1/2]$. Both endpoints occur, at $x=-1$ and $x=1$. By continuity and the intermediate value theorem applied on $[-1,1]$, every intermediate value occurs too. HenceIt is not surjective onto $\mathbb{R}$ because, for example, $1$ is not attained. It is not injective because $f(2)=f(1/2)=2/5$ although $2\ne 1/2$.

If $0\le x<y$, then $\sqrt{x}<\sqrt{y}$ and $x<y$, so $\sqrt{x}+x<\sqrt{y}+y$. Thus the function is strictly increasing on its domain and is injective. Its values are nonnegative, so it is not surjective onto $\mathbb{R}$:If ${\mathbb{R}}_{+}$ means $(0,\infty )$ its image of a function is $(0,\infty )$; if it includes zero its image of a function is $[0,\infty )$. Indeed, for any $u>0$, set $t=(\sqrt{1+4u}-1)/2>0$ and $x=t^2$; then $\sqrt{x}+x=t+t^2=u$. This convention does not change the classification.

With the convention $\mathbb{N}=\{0,1,2,\dots \}$, the even inputs $2j$ map to $j$ for $j\ge 0$, while the odd inputs $2j+1$ map to $-(j+1)$ for $j\ge 0$. These two images of a function are disjoint and together equal $\mathbb{Z}$. Within either class there are no repeated outputs. More explicitly the inverse function isConsequently $f$ is both injective and surjective, hence a bijection. If instead $\mathbb{N}=\{1,2,\dots \}$, the input zero is absent: $f$ remains injective but its image of a function is $\mathbb{Z}\setminus \{0\}$, so it is not onto. The printed paper does not specify this convention; the zero-based convention gives the apparent intended bijection.

Take every complement of a set relative to $\mathcal{U}$. By set difference, De Morgan's laws, and distribution of set intersection over set union,Here the middle term is the empty set, since a set and its complement of a set are disjoint.

Use set difference, associativity of set intersection, and De Morgan's laws:

The commutativity and associativity of set intersection giveEquivalently, part (ii) reduces both sides to removal of the same set union $B\cup C=C\cup B$.

For every set $S$, the definition of a power set givesEquality by identical membership therefore provesThe essential observation is that being a subset of a set intersection means being a subset of both factors.

First suppose the sets are finite, with cardinalities $a=|A|\ge 2$ and $b=|B|\ge 2$. The power set and Cartesian product counting rules giveSince $ab-a-b=(a-1)(b-1)-1\ge 0$, the desired inequality follows.

The power-set product cardinality inequality also has an injection proof that does not assume finiteness. Choose distinct $a_0,a_1\in A$ and distinct $b_0,b_1\in B$. For $S\subseteq A$ and $T\subseteq B$, define the subset of $A\times B$These three encoding regions are disjoint. The row with second coordinate $b_0$ recovers $S$; the column with first coordinate $a_0$ and second coordinate different from $b_0$ recovers $T\setminus \{b_0\}$; the extra position $(a_1,b_1)$ records whether $b_0\in T$. Thus $\Phi$ is injective, proving for arbitrary setsEncoding by $S\times T$ alone would fail: all pairs with either factor empty would have the same output.