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

A preorder is a binary relation that is both reflexive and transitive: $a⪯a$ for every $a\in A$, and $a⪯b⪯c$ implies $a⪯c$.

A partial order is a preorder satisfying the antisymmetric relation axiom. In addition to reflexivity and transitivity, it satisfies $a⪯b$ and $b⪯a$ only when $a=b$.

A total order is a partial order in which every pair is comparable: for every $a,b\in A$, at least one of $a⪯b$ and $b⪯a$ holds. Both hold exactly when $a=b$.

For the product order, reflexivity follows from $a_i\le a_i$ in every coordinate. If $\mathbf{a}⪯\mathbf{b}$ and $\mathbf{b}⪯\mathbf{a}$, the antisymmetric relation axiom for the usual real order gives $a_i=b_i$ for every $i$, hence $\mathbf{a}=\mathbf{b}$. If $\mathbf{a}⪯\mathbf{b}⪯\mathbf{c}$, transitivity in each coordinate gives $a_i\le c_i$, hence $\mathbf{a}⪯\mathbf{c}$. Thus this is a partial order.

For $n\ge 2$, the vectors $(1,0,0,\dots )$ and $(0,1,0,\dots )$ are incomparable: each has a coordinate larger than the corresponding coordinate of the other. It is not a total order for $n\ge 2$. The dimension qualification matters: for $n=1$ this is the usual total order on $\mathbb{R}$, so the printed non-totality claim needs the implicit assumption $n\ge 2$.

For the pointwise order on real polynomials, $p(x)\le p(x)$ proves reflexivity. Two opposite inequalities imply $p(x)=q(x)$ for every real $x$; the polynomials are therefore equal, proving the antisymmetric relation axiom. Chaining the inequalities at every $x$ proves transitivity.

To disprove total order, take $p(x)=x$ and $q(x)=0$. The inequality $p⪯q$ fails at $x=1$, whereas $q⪯p$ fails at $x=-1$. The order is partial but non-total.

The greatest element of $S$, also called its maximum, is an element $m\in S$ such that $s⪯m$ for every $s\in S$. Membership in $S$ is essential; an upper bound need not belong to $S$.

A least upper bound of $S$ is an element $u\in A$ such that $s⪯u$ for every $s\in S$, and such that $u⪯v$ for every other upper bound $v\in A$ of $S$. It need not belong to $S$. The antisymmetric relation axiom makes it unique whenever it exists.

Write each member as $3-2/(n+1)$. Every member is strictly below $3$, so $3$ is an upper bound. If $u<3$, the Archimedean property supplies $n\in \mathbb{N}$ with $n+1>2/(3-u)$; then $3-2/(n+1)>u$. Thus no smaller number is an upper bound, proving $\sup S=3$. Since $3\notin S$, there is no greatest element. Equivalently, each member is followed by a larger member because $2/(n+2)<2/(n+1)$.

For every $a$, both $aRa$ and $aSa$ hold, so the intersection of equivalence relations is reflexive. If $a(R\cap S)b$, symmetry of both component binary relations gives $bRa$ and $bSa$, hence $b(R\cap S)a$. Finally, if $a(R\cap S)b$ and $b(R\cap S)c$, transitivity in each component gives $aRc$ and $aSc$, hence $a(R\cap S)c$. These are precisely the three conditions for an equivalence relation.

For every $x\in A$, membership in the relevant equivalence class satisfiesEquality follows by axiom of extensionality. Thus $[a{]}_{R\cap S}=[a{]}_R\cap [a{]}_S$.

The floor function is constant at $j$ on the four consecutive integers $4j,4j+1,4j+2,4j+3$. Consequently the partition of a set is $\{\{4j,4j+1,4j+2,4j+3\}:j\in \mathbb{N}\}$. Different blocks are disjoint and every nonnegative integer has exactly one quotient and remainder upon division by $4$.

Take the nonempty intersections of the length-three and length-four blocks. Within the first twelve nonnegative integers the common cut points are $0,3,4,6,8,9,12$, givingThe complete partition of a set consists of these six blocks translated by $12j$ for every $j\in \mathbb{N}$. Indeed, adding $12$ increases the two floor quotients by $4$ and $3$ respectively, preserving equality of both quotients within each translated block. No adjacent displayed blocks can merge because at least one quotient changes at their boundary. This is the periodic common refinement of floor-quotient partitions, with period $\mathrm{lcm}(3,4)=12$.