Past exam of the mathematics course of the University of Cambridge / 2022 / ia / Paper 4 / 7F (Numbers and Sets)

Because $P(\mathbf{x})\subseteq P(\mathbf{x})$, the relation is reflexive. If $\mathbf{x}⪯\mathbf{y}$ and $\mathbf{y}⪯\mathbf{z}$, thenso it is transitive. It is not symmetric: forone has $\mathbf{x}⪯\mathbf{y}$ but not $\mathbf{y}⪯\mathbf{x}$.

Suppose $\mathbf{x}⪯\mathbf{y}$. Define the nonnegative tuple $\mathbf{z}$ coordinatewise byWhen $y_i=0$, support inclusion forces $x_i=0$, so $x_i=y_i{z}_i$ in every coordinate.

Conversely, if $x_i=y_i{z}_i$ with $y_i,z_i\ge 0$, then $x_i>0$ implies $y_i>0$. Hence $P(\mathbf{x})\subseteq P(\mathbf{y})$ and $\mathbf{x}⪯\mathbf{y}$. This proves the equivalence.

The definition saysEquality of sets is reflexive, symmetric, and transitive, so $\sim$ is an equivalence relation. Its classes are indexed by all subsets of $\{1,\dots ,n\}$, and every subset occurs as the support of its zero-one indicator vector. The number of classes is therefore

DefineThen $\mathbf{x}=\mathbf{y}+\mathbf{z}$, the support of $\mathbf{y}$ lies in $P(\mathbf{s})$, and the support of $\mathbf{z}$ is disjoint from $P(\mathbf{s})$. Thus $\mathbf{y}⪯\mathbf{s}$ and $\mathbf{z}\perp \mathbf{s}$.

For uniqueness, if $s_i>0$, orthogonality forces $z_i=0$, hence $y_i=x_i$. If $s_i=0$, the condition $\mathbf{y}⪯\mathbf{s}$ forces $y_i=0$, hence $z_i=x_i$. Every coordinate is therefore forced, proving uniqueness.