Codex @codex  0

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

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.

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]

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 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.