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

The relative complement consists of the elements of the first set absent from the second, while the symmetric difference consists of elements in exactly one set:The two parts of the symmetric difference are disjoint sets.

For the first set inclusion, take $x\in A\setminus (A\setminus B)$. Then $x\in A$ but $x\notin A\setminus B$. Since membership in $A$ is already known, failure to lie in that relative complement forces $x\in B$. Hence $x\in A\cap B$.

Conversely, if $x\in A\cap B$, then $x\in A$ and its membership in $B$ excludes it from $A\setminus B$. Therefore $x\in A\setminus (A\setminus B)$. The two inclusions prove the stated equality with the set intersection.

If $x\in A\oplus B$, the definition of symmetric difference puts it in exactly one of $A,B$. It is therefore in their set union and outside their set intersection, giving $x\in (A\cup B)\setminus (A\cap B)$.

Conversely, an element of $(A\cup B)\setminus (A\cap B)$ lies in at least one of the two sets but not both. It consequently belongs to $A\setminus B$ or to $B\setminus A$, and hence to $A\oplus B$. Both set inclusions hold.

The outermost braces form a singleton set, regardless of how its one element is nested. Its cardinality is therefore $1$. A set containing the empty set is different from the empty set itself.

A Cartesian product with the empty set is empty: there is no possible second coordinate. Thus the requested cardinality is $0$, independently of the first factor's power set.

The singleton set $\{\varnothing \}$ has cardinality one, so its power set has cardinality two. Taking the Cartesian product with the singleton $\{\varnothing \}$ leaves that cardinality equal to two. The outer power set therefore has $2^2=4$ elements.

One example is the identity function, $f(n)=n$. A second is the permutationBoth are bijections of $\mathbb{N}$, whichever convention includes or excludes zero. For the second, applying $f$ three times returns every input to itself. Thus $f^3=\mathrm{id}$, and composing with the inverse function gives $f^2=f^{-1}$. This permutation cube identity criterion also shows why three-cycles work whereas a nontrivial two-cycle would not.

Use the convention that $R\circ S$ applies $S$ first. Reflexivity inserts an identity step: if $aRb$, use $aSa$ to obtain $(a,b)\in R\circ S$; if $aSb$, use $bRb$ for the same conclusion. Thus $R\cup S\subseteq R\circ S$. By monotonicity of relation composition,For strictness, take $A=\{0,1,2,3\}$ and let $R=S$ consist of the identity pairs together with $(0,1),(1,2),(2,3)$. Both are reflexive relations. The left side permits at most two forward chain steps, so does not contain $(0,3)$. The right side permits four steps, including $0\to 1\to 2\to 3\to 3$, so does contain it. Equality therefore need not hold.