Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation (CCOM 4214)

Original examination: Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation examination paper by the University of Oxford (2005).

The image of a linear map and kernel of a linear map areA linear map sends zero to zero, since $T(0)=T(0+0)=T(0)+T(0)$. Thus both displayed sets contain zero. If $w_1=T(v_1)$ and $w_2=T(v_2)$ belong to the image of a linear map, then for any real scalars $a,b$,If $v_1,v_2$ belong to the kernel of a linear map, thenso $a{v}_1+b{v}_2\in \ker T$. Containing zero and being closed under linear combinations is the vector subspace criterion. Hence the image of a linear map is a vector subspace of $W$, and the kernel of a linear map is a vector subspace of $V$.

The rank-nullity theorem says that for a linear map $T:V\to W$ with finite-dimensional domain of a function $V$,Take a basis $k_1,\dots ,k_r$ of the kernel of a linear map and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We show that $T(u_1),\dots ,T(u_s)$ is a basis of the image of a linear map.

Every $v\in V$ is a linear combination of the extended basis, and its $k_i$ terms vanish under $T$. Therefore $T(v)$ is a linear combination of the $T(u_j)$, proving the required linear span property. For linear independence, suppose ${\sum }_j{b}_{j}T(u_j)=0$. Then ${\sum }_j{b}_j{u}_j\in \ker T$, so ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some real scalars $a_i$. The extended basis is linearly independent, forcing every $a_i$ and $b_j$ to be zero. Thus the image of a linear map has dimension $s$, the kernel of a linear map has dimension $r$, and $\dim V=r+s$ proves the result.

A basis provides unique coordinates. DefineThe uniqueness of the coordinates makes this a well-defined function. Adding coordinates and multiplying them by a real scalar shows directly that $\alpha (au+bw)=a\alpha (u)+b\alpha (w)$, so it is a linear map. Substituting $e_i$ gives $\alpha (e_i)=v_i$.

Conversely, every linear map with those three values must send ${\sum }_i{a}_i{e}_i$ to ${\sum }_i{a}_i{v}_i$, by preservation of linear combinations. This determines its value on every element of $V$, proving uniqueness. No linear independence of $v_1,v_2,v_3$ is needed.

Here $v_3=2v_1-v_2$, so the image of a linear map is the linear span of $v_1,v_2$. These two vectors are linearly independent: if $a{v}_1+b{v}_2=0$, the $e_1$ and $e_2$ coordinates give $a+b=0$ and $a-b=0$, hence $a=b=0$. Consequently the rank of a linear map is two. By the rank-nullity theorem, the nullity is $3-2=1$:More explicitly, the relation $-2v_1+v_2+v_3=0$ gives the kernel of a linear map

The printed word “eigenvalues” must read “eigenvectors”: eigenvalues are real numbers, whereas a basis of ${\mathbb{R}}^n$ consists of vectors. The intended assertion isThis wording error is present in the original scan.^[ref]

If $X^{-1}AX=D=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$ for an invertible matrix $X$, write $x_i$ for its columns. The matrix identity $AX=XD$ says $A{x}_i={\lambda }_i{x}_i$. The columns of an invertible matrix are a basis, hence they give the required basis of eigenvectors.

Conversely, put a basis of real eigenvectors $x_1,\dots ,x_n$ into the columns of $X$, with corresponding eigenvalues ${\lambda }_i$. The basis property makes $X$ an invertible matrix. The equations $A{x}_i={\lambda }_i{x}_i$ give $AX=XD$, so $X^{-1}AX=D$. This is precisely diagonalizability over the real numbers.

For the first matrix, the characteristic polynomial isThus the real eigenvalues are $4,-1,3$. Corresponding eigenvectors are $(3,1,0{)}^{\mathsf{T}}$, $(-2,1,0{)}^{\mathsf{T}}$ and $(0,0,1{)}^{\mathsf{T}}$. They are linearly independent; the determinant of the matrix with these columns is $5$. ThereforeFor example, multiplying the first column by $A$ gives $(12,4,0{)}^{\mathsf{T}}$, four times that column; multiplying the second gives $(2,-1,0{)}^{\mathsf{T}}$, its negative. These also check the chosen eigenvectors directly.

For the second matrix,The quadratic factor has negative discriminant $-3$, so $1$ is the only real eigenvalue. Solving $Av=v$ gives $v=(a,a,a{)}^{\mathsf{T}}$, a one-dimensional eigenspace. It cannot provide a basis of ${\mathbb{R}}^3$, so

Let $\lambda$ be the single eigenvalue. By diagonalizability, there is a basis $v_1,\dots ,v_n$ of eigenvectors, and every corresponding eigenvalue is $\lambda$. For any $v={\sum }_i{a}_i{v}_i$, linearity givesThus $\boxed{T=\lambda I}$, a scalar multiple of the identity map.

A counterexample to the conclusion without diagonalizability isIts characteristic polynomial is $(t-2{)}^2$, but $(J-2I)(a,b{)}^{\mathsf{T}}=(b,0{)}^{\mathsf{T}}$. The eigenspace for $2$ is therefore $\mathrm{span}\{(1,0{)}^{\mathsf{T}}\}$, of dimension one. There is no basis of eigenvectors in dimension two, so $J$ is not diagonalizable.

The homogeneous linear differential equation has solutions $\cos x$ and $\sin x$. Since the forcing is already a homogeneous solution, seek a particular solution proportional to $x\cos x$. Direct differentiation givesThus the general solution of the linear ordinary differential equation isThe first initial condition gives $A=0$. Alsoso the second initial condition gives $B-\frac{1}{2}=-\frac{1}{2}$, hence $B=0$. Therefore

For $y_1=e^x/x$, on an interval avoiding zero,Substitution into the ordinary differential equation givesTo find an independent solution, put $v=xy$. The product rule gives $v^{\prime \prime }=x{y}^{\prime \prime }+2y^{\prime }$, so the ordinary differential equation becomes $v^{\prime \prime }-v=0$. Its independent solutions are $e^x$ and $e^{-x}$. HenceThe two displayed solutions are linearly independent, since their ratio $e^{2x}$ is nonconstant on any open interval. Constants can be chosen separately on the two sides of the singular point $x=0$.

The logarithm requires $y>0$, and $x>0$ is given. Set $z=\log (y/x)$, so $y=x{e}^z$ and the chain rule yields $x{y}^{\prime }/y=1+x{z}^{\prime }$. Dividing the ordinary differential equation by $y$ therefore givesSince $(z/x{)}^{\prime }=(x{z}^{\prime }-z)/x^2=0$, we obtain $z=Cx$, including the case $z=0$. Thus the general positive solution is $y=x{e}^{Cx}$. The initial condition $y(1)=e$ gives $C=1$:For the separate decay requirement, $x{e}^{Cx}\to 0$ precisely when $C<0$: if $C=0$, the result is $x$, and if $C>0$, it grows. Consequently the full family with the stated limit isThis latter family does not also satisfy $y(1)=e$; the solution selected by that initial condition grows. The identically zero function is excluded by the original logarithm.

For $r>0$, the chain rule gives $r_x=x/r$ and $r_y=y/r$. Applying it twice to the radial function $u=f(r)$ givesUsing $x^2+y^2=r^2$, Laplace's equation becomesTwo integrations now giveThese are the general solutions of the specified radial function form on an annulus or a punctured plane. If the solution must extend continuously to the origin, the logarithm term forces $A=0$, leaving only a constant function.

Use the product rule for the Laplace operator:Thus Laplace's equation, away from the origin, reduces to $g^{\prime \prime }+3g^{\prime }/r=0$. On the line $x=0$ the displayed expression vanishes automatically; requiring the equation on an open region gives the same radial equation by continuity from $x\ne 0$. Multiplying by $r^3$ gives $(r^3{g}^{\prime }{)}^{\prime }=0$, so $g^{\prime }=C{r}^{-3}$ and $g=A+B{r}^{-2}$. ThereforeIf extension through the origin is required, $B=0$: along the horizontal axis the second term is $B/x$. The remaining harmonic function is $Ax$.

For the wave equation with wave speed one, D'Alembert's formula with arbitrary twice continuously differentiable initial displacement $h(x)=u(x,0)$ isThe arbitrary function $h$ is essential: only the initial velocity is prescribed. For $g=0$, this givesBoth travelling terms solve the wave equation, and their time derivatives cancel at $t=0$. Conversely every classical solution has this form for its initial displacement $h$.

The velocity contribution in D'Alembert's formula is $\frac{1}{2}{\int }_{x-t}^{x+t}1ds=t$. Hence, with arbitrary twice continuously differentiable $h$,The added term has both second partial derivatives zero and has time derivative one, so it supplies precisely the required initial condition while preserving the wave equation.

Here the velocity contribution in D'Alembert's formula isThus, with arbitrary twice continuously differentiable $h$,For the added term, $u_{tt}=e^x\sinh t=u_{xx}$ and $u_t(x,0)=e^x\cosh 0=e^x$. Its displacement at $t=0$ is zero, leaving $h$ free as required.

The domain of a function is fixed by its declared type, soAlthough the rational expression also has values at some negative arguments, they are not in the specified domain of a function. Part (a) of the printed question only supplies the definition used in these four subparts.^[ref]

For $r>0$, solve $f(s)=r$ with $s>0$. Multiplying by the positive denominator gives $s^2+s=1/r$, so the quadratic formula givesThe minus sign gives a negative number and is inadmissible. The plus sign gives a positive number for every $r>0$, and it is the unique positive solution. Hence the inverse function isIndeed $g(r)(g(r)+1)=1/r$, so $f(g(r))=r$. Conversely, for $s>0$, $\sqrt{1+4/f(s)}=\sqrt{(2s+1{)}^2}=2s+1$, giving $g(f(s))=s$. These verify both inverse function identities.

For $s>0$, the denominator $s(s+1)$ is positive, so every value of $f$ is positive. Conversely, for every $r>0$, the positive number $s=(\sqrt{1+4/r}-1)/2$ satisfies $f(s)=r$. Thus its image of a function, or range, isOne can also see the full range from continuity and monotonicity: $f$ is a continuous function with $f^{\prime }(s)=-(2s+1)/(s^2+s{)}^2<0$, and its endpoint limits are $+\infty$ as $s\to 0^{+}$ and $0$ as $s\to \infty$. The endpoints themselves are not attained.

The partial fraction decompositionmakes the sum a telescoping sum. All interior terms cancel:

Use the two-chain noncontinuous complete partial orderwhere $\perp <a_1<a_2<\cdots <\top$ and $\perp <b_1<b_2<\cdots <\top$, with no comparisons between the two interiors. In this solution $\sup D$ denotes the least upper bound printed as $\sqcap D$ in the question.^[ref]

Every nonempty directed set containing $\top$ has least upper bound $\top$. A directed set omitting $\top$ cannot contain both an $a_i$ and a $b_j$, because their only common upper bound in $P$ is $\top$, which would have to belong to that directed set. It therefore lies in one chain, possibly with $\perp$. If its indices are bounded it has a greatest element, which is its least upper bound; if they are unbounded its least upper bound is $\top$. Thus $P$ is a directed-complete partial order.

No element other than $\perp$ is way-below $\top$. For $a_i$, the directed set $\{b_n:n\ge 1\}$ has least upper bound $\top$, but none of its members is above $a_i$. Interchanging the two chains excludes every $b_i$. Either chain excludes $\top$ itself. On the other hand, $\perp \ll \top$: every directed set whose least upper bound is above $\top$ is nonempty, and any member is above $\perp$. HenceSo $P$ is not a continuous directed-complete partial order.

There is a small convention issue in the printed definitions. Our usual directed set is nonempty, but the question's pairwise condition also allows the empty set. Taken literally, the empty set has least upper bound $\perp$, and the preceding example and failure of continuity still work. Under this literal convention $\perp /\ll \perp$, because the empty set supplies no witness. We retain this qualification in the next parts.

The continuous nonalgebraic unit interval isEvery nonempty directed set has a least upper bound by completeness of the real numbers, and that least upper bound lies in $[0,1]$. Thus this is a directed-complete partial order.

For $0\le a<b\le 1$, we have $a\ll b$. Indeed, if $b\le \sup D$ and no $d\in D$ were at least $a$, then $a$ would be an upper bound for $D$, implying $\sup D\le a<b$, a contradiction. If $a>b$, the singleton directed set $\{b\}$ excludes $a\ll b$. If $a=b>0$, the increasing sequence $d_n=b(1-1/n)$, $n\ge 1$, has least upper bound $b$ and has no member at least $b$, so $b/\ll b$.

Under the usual nonempty convention, $0\ll 0$. Therefore the elements way-below $b>0$ form $[0,b)$, and those way-below $0$ form $\{0\}$. These are directed sets with least upper bounds $b$ and $0$, respectively, proving that $[0,1]$ is a continuous directed-complete partial order. Its only compact element is $0$. For any $b>0$, the compact elements below $b$ have least upper bound $0$, rather than $b$, so it is not an algebraic partially ordered set.

Under the literal empty-set convention of the paper, $0/\ll 0$ as well. The elements way-below zero then form the empty set, which is directed in that convention and has least upper bound zero. There are no compact elements, and their empty set still fails to approximate any positive $b$. Thus both conventions give the same requested classification:

We prove the result algebraic partially ordered sets are continuous directly from the definitions. First, $a\ll b$ implies $a\le b$, by applying the way-below relation to the singleton directed set $\{b\}$. Also,if $c\le \sup D$, then $b\le \sup D$, so the witness required for $a\ll b$ also works for $a\ll c$.

Fix $x$ and putBy algebraicity, $K_x$ is a directed set with least upper bound $x$. Every $k\in K_x$ satisfies $k\ll k\le x$, hence $k\ll x$. Thus $K_x\subseteq A_x\subseteq \{a:a\le x\}$.

To prove that $A_x$ is a directed set, take $a,b\in A_x$. Applying $a\ll x$ and $b\ll x$ to $x=\sup K_x$ gives $k_a,k_b\in K_x$ such that $a\le k_a$ and $b\le k_b$. Directedness of $K_x$ gives $k\in K_x$ above both. Since $k\in A_x$, it is the required common upper bound inside $A_x$. With the usual nonempty convention, $A_x$ is nonempty since it contains $K_x$.

By directed completeness $A_x$ has a least upper bound. The inclusions above givesoThe same proof handles the paper's literal empty-set convention. If $K_x=\varnothing$, then $x=\sup \varnothing =\perp$, and the defining implication for $a\ll x$, applied to $D=K_x$, shows that $A_x$ must also be empty. Its least upper bound is again $x$. If $K_x$ is nonempty, the argument already given applies without change.

In first-order logic with equality, the three first-order sentences areA reflexive relation relates each element to itself. An antisymmetric relation forbids distinct elements from relating in both directions. A transitive relation contains every composite of two successive related pairs. Together these axioms define a partially ordered set.

The requested examples are binary relations on sets, rather than partially ordered sets: a partially ordered set necessarily has all three properties. This corrects the wording of the source.^[ref]

For an antisymmetric relation and transitive relation that is not a reflexive relation, take $S=\{0,1\}$ and $R=\{(0,1)\}$. No distinct pair relates both ways, so the antisymmetric relation condition holds. There are no composable pairs, so the transitive relation condition holds vacuously. Neither $(0,0)$ nor $(1,1)$ belongs to $R$, so the reflexive relation condition fails.

For a reflexive relation and transitive relation that is not an antisymmetric relation, take $S=\{0,1\}$ and $R=S\times S$. All diagonal pairs and all composite pairs belong to $R$, but $R(0,1)$ and $R(1,0)$ both hold with $0\ne 1$.

For a reflexive relation and antisymmetric relation that is not a transitive relation, takeAll diagonal pairs are present, and no off-diagonal pair has its reverse present. However $R(0,1)$ and $R(1,2)$ hold while $R(0,2)$ fails. Thus each pair of axioms can hold without the third.

Totality of the binary relation is expressed byWhen $R$ is already an order, this adds comparability and makes it a total order. In fact this first-order sentence alone entails $\rho =\forall xR(x,x)$.

By the definition of semantic entailment, $\tau \models \rho$ means that every first-order structure satisfying $\tau$ also satisfies $\rho$. Let $\mathcal{M}$ be any such first-order structure, and let $a$ be any element of its domain of a first-order structure. The instance of $\tau$ with $x=y=a$ gives $R(a,a)\vee R(a,a)$, which is true only if $R(a,a)$ is true. Since $a$ was arbitrary, $\mathcal{M}\models \forall xR(x,x)$. ThereforeThere is no exception for $x=y$ in the displayed totality axiom; that case is exactly what forces the reflexive relation property.

In this first-order structure, $R(x,z)\wedge R(y,z)$ says $x\le z$ and $y\le z$. Thus $z$ is an upper bound of $x,y$. The universally quantified clause says that if $w$ is any other upper bound, then $z\le w$. Therefore $z$ is their least upper bound. In the usual total order on the natural numbers, this is their maximum:This describes a condition on the values assigned to the free variables $x,y,z$; $\varphi$ itself is not a closed first-order sentence.

Every pair of natural numbers has a maximum, itself a natural number. Given arbitrary $x,y$, choose $z=\max \{x,y\}$. Then $x,y\le z$, and any $w$ satisfying $x,y\le w$ also satisfies $z\le w$. All three clauses of $\varphi$ hold. ThusThis explicitly supplies the witness required by the existential quantifier for every pair chosen by the two universal quantifiers.

Here the direction of the divisibility relation matters: $R(x,z)$ means $z\mid x$. The first two clauses say that $z$ is a common divisor of $x,y$. The last clause says that every common divisor $w$ divides $z$. These are precisely the defining properties of the greatest common divisor. Choose $z=\gcd (x,y)$; thenHenceThis also holds if the natural numbers include zero: use $\gcd (x,0)=x$ and $\gcd (0,0)=0$. Every natural number divides zero, so for $x=y=z=0$ the last clause remains true. In the order obtained by reversing divisibility, the greatest common divisor is the least upper bound.

The first two clauses now require $x=2z$ and $y=2z$. Thus they already imply $x=y$. Choose, for example, $x=1,y=2$; no natural number $z$ can satisfy both equations. Consequently the existential quantifier fails for this pair, irrespective of the universally quantified final clause, andIn fact even $x=y=1$ fails, since $1=2z$ has no solution among the natural numbers.

A regular language over a finite alphabet is a formal language recognized by a deterministic finite automaton; equivalently it is described by a regular expression. A nondeterministic finite automaton accepts an input string if at least one permitted computation consumes that string and reaches an accepting state. The connection is the equivalenceEvery deterministic finite automaton is a special case of a nondeterministic finite automaton. Conversely, the subset construction makes a deterministic finite automaton whose states record the set of all possible current states of a nondeterministic finite automaton. After each input symbol, update that set by taking all permitted transitions, also including any epsilon closure. A new state is accepting exactly when it contains an old accepting state. A finite state set has finitely many subsets, so this really is a deterministic finite automaton recognizing the same formal language.

Every finite formal language is a regular language. A single string $a_1\cdots a_k$ is described by the regular expression formed by concatenating its symbols; the empty string is described by $\epsilon$. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by $\varnothing$. ThusEquivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

These strings are the even-length palindromes $u{u}^R$. Suppose this were a regular language, and let $p$ be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with $u=0^{p}1$. In any allowed decomposition $w=abc$, where $|ab|\le p$ and $|b|>0$, the pumped block is $b=0^k$ with $1\le k\le p$. Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form $u{u}^R$, contradicting the pumping lemma for regular languages. Therefore

This is a regular language. A deterministic finite automaton needs only to remember the number of consecutive trailing ones, up to three, and whether a forbidden run of four has already occurred. Use states $q_0,q_1,q_2,q_3,q_{\times }$, start at $q_0$, and accept in $q_0,q_1,q_2,q_3$. Its transition function of a finite automaton is:

Reading a zero resets the trailing count unless rejection has already occurred. A fourth successive one enters the permanent rejecting state $q_{\times }$. Thus the accepted strings are exactly those with no substring $1111$, and

Let $L=\{0^m{1}^n:m,n\ge 0,m\ne n\}$, and suppose it were a regular language. The formal language $B=0^{\ast }{1}^{\ast }$ is a regular language. By closure of regular languages under set difference,would be a regular language. But the pumping lemma for regular languages rules this out: for pumping length $p$, every permitted pumped block in $0^p{1}^p$ consists of $k>0$ zeros, and deleting it produces $0^{p-k}{1}^p$, with unequal counts. This contradiction provesThe closure step can also be realized by a product automaton accepting when the automaton for $B$ accepts and the automaton for $L$ rejects. If the exponents are instead required to be positive, use $B=0^{+}{1}^{+}$; the same argument applies.

A context-free grammar is a quadruple $(N,\Sigma ,P,S)$: $N$ is a finite set of nonterminal symbols, $\Sigma$ is a disjoint finite alphabet of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite set of productions $A\to \alpha$, with $A\in N$ and $\alpha \in (N\cup \Sigma {)}^{\ast }$. Its formal language consists of the terminal strings derivable from $S$.

For the even-length palindromes in (b)(ii), take terminal alphabet $\{0,1\}$ and the context-free grammarEvery production adds identical symbols at the two ends, so every generated string is an even-length palindrome. Conversely, remove the matching outer pair of any nonempty even-length palindrome and repeat; this constructs its derivation, ending with $\epsilon$.

For the unequal-block formal language in (b)(iv), useAfter $k$ uses of $A\to 0A1$, and $j\ge 1$ zeros from $Z$, the resulting string is $0^{k+j}{1}^k$, so its zero count is larger. Every such unequal pair with $m>n$ occurs by choosing $k=n,j=m-n$. Similarly $B$ generates exactly $0^k{1}^{k+j}$ with $j\ge 1$, covering precisely $m<n$. The start alternatives cover both possibilities and never equal counts. If positive exponents are required, replace the start productions by $S\to 0A1\mid 0B1$, which adds one matched pair and ensures both counts are positive.

A Turing machine has a finite control, an unbounded tape divided into cells over a finite tape alphabet including a blank symbol, and a head that reads one cell at a time. For a deterministic Turing machine, the current state and scanned symbol determine the replacement symbol, a head move one cell left or right, and the next state. The input occupies finitely many cells initially; all other cells are blank. Distinguished halting states report acceptance or rejection.

A formal language is a decidable language if some Turing machine halts on every input string, accepting exactly the members and rejecting all nonmembers:Halting on the nonmembers is part of the requirement; a machine that merely runs forever on some nonmembers need not decide the formal language.

Cancel one unary symbol from each block at each round. Mark the first, middle and last delimiters by $L,C,E$, respectively; use $X$ for a cancelled symbol in the left block and $Y$ for one in the right block. These are extra tape symbols of the Turing machine, all distinct from $0,1$ and blank. No numerical counter is needed in the finite control.