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

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