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

We prove both set inclusions, as required by a double inclusion proof. If $x\in A\setminus (B\cup C)$, then $x\in A$ and $x\notin B\cup C$. Thus $x\notin B$ and $x\notin C$, so $x\in A\setminus B$ and $x\in A\setminus C$. This proves the forward set inclusion.

Conversely, if $x\in (A\setminus B)\cap (A\setminus C)$, then $x\in A$, $x\notin B$, and $x\notin C$. Hence $x\notin B\cup C$, giving $x\in A\setminus (B\cup C)$. Therefore

For the first set inclusion, take $x\in (A\cap B)\setminus C$. Membership in the intersection gives $x\in A$ and $x\in B$, while the set difference gives $x\notin C$. Consequently $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, an element of $(A\setminus C)\cap (B\setminus C)$ belongs to both $A$ and $B$ and does not belong to $C$. It therefore belongs to $(A\cap B)\setminus C$. By double inclusion proof,

Complements are relative to the same universal set $\mathcal{U}$. Suppose $A\subseteq B$ and $x\in \overline{B}$. Then $x\in \mathcal{U}$ and $x\notin B$. If $x$ belonged to $A$, the assumed set inclusion would imply $x\in B$, a contradiction. Thus $x\notin A$ and $x\in \overline{A}$, provingThere is only one set inclusion in this conclusion; a reverse inclusion is neither needed nor generally true. The request for double inclusion applies to the equalities in (i) and (ii).

Use the definition $A\oplus B=(A\setminus B)\cup (B\setminus A)$ of symmetric difference. The algebraic laws for set difference and the empty set giveand

Because $A\subseteq \mathcal{U}$, the set difference $A\setminus \mathcal{U}$ is empty and $\mathcal{U}\setminus A=\overline{A}$. Therefore the symmetric difference satisfiesThe disjoint sets $A$ and $\overline{A}$ have union $\mathcal{U}$, so

Apply symmetric difference with $C$ to both sides, then use its associativity and the identities in (b)(i):The final identity gives $A=B$. This is cancellation by applying the same operation twice.

Fix one distinguished element $a$ of the $n$-element set. Every partition of a set into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block partition of a set of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrenceUse $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.

Starting from $n$ singleton blocks, a partition of a set into $n-1$ nonempty blocks has exactly one block of size two and all other blocks of size one: the sum of the block sizes exceeds the number of blocks by exactly one. Choosing that pair determines the partition uniquely. HenceThis fixed value of $k$ works for every $n\ge 2$. It is forced already by $n=2$: $S(2,1)=1$, whereas for positive $k$ the only $\left(\genfrac{}{}{0ex}{}{2}{k}\right)$ equal to one is $\left(\genfrac{}{}{0ex}{}{2}{2}\right)$.

Each of the $m$ elements of $A$ independently receives one of $n$ images in $B$. The multiplication principle therefore gives $n^m$ functions. In particular an empty set domain has exactly one function to any $B$, so here $0^0$ is interpreted as $1$; a nonempty domain has no function to an empty set codomain.

A bijection between finite sets requires equal cardinality. When $m=n$, list the elements of $A$ and choose their distinct images in $n,n-1,\dots ,1$ ways. ThusThe factorial convention $0!=1$ includes the unique bijection from the empty set to itself.

For a surjection, the nonempty fibres $f^{-1}(b)$ form a partition of a set $A$ into exactly $n$ blocks. Choose these unlabelled blocks in $S(m,n)$ ways, then assign the $n$ distinct elements of $B$ to them in $n!$ ways. ConsequentlyIt is zero when $m<n$. With $S(0,0)=1$ and $S(m,0)=0$ for $m>0$, the same formula also handles an empty set codomain.

Choose the image of a function as a $j$-element subset of $B$, then choose a surjection onto that selected image as in (iii). ThereforeThe answer is zero when $j>n$. If $j=0$, it is one for $m=0$ and zero for $m>0$, as the Stirling numbers of the second kind conventions require.