Order ideal

A subset $I$ of a partially ordered set such that $x\in I$ and $y\le x$ imply $y\in I$. Thus membership forces all smaller elements to belong as well. This definition concerns an order, rather than an ideal of a ring.

For an order ideal in a finite rectangular grid with coordinatewise partial order, occupied cells in each row form a left prefix. Their lengths form a nonincreasing sequence $r_y$. Conversely, any nonincreasing sequence of valid row lengths specifies exactly one such order ideal, giving an abstraction function with no redundant per-cell information.

Removing all occupied cells with $x\ge a$ and $y\ge b$ replaces $r_y$ by $\min (r_y,a)$ for $y\ge b$ and leaves earlier rows unchanged. The new lengths remain nonincreasing: affected rows preserve their mutual order, and the first affected row only decreases. For a legal removal, the boundary immediately below it was already at least $a$. A cached sum of row lengths can be updated by subtracting the decreases. This yields constant-time membership and count queries, linear storage, and an update linear in the number of affected rows.

A downward-closed subset of a finite product grid can be represented by nonincreasing column heights. Occupancy is $0\le y<h(x)$; the condition $h(0)\ge \cdots \ge h(N-1)$ is exactly closure toward smaller coordinates. Removing the northeast rectangle anchored at a legal $(x,y)$ truncates each height to its right to $\min (h(i),y)$, preserving closure. This represents a potentially quadratic number of occupied cells using a linear number of boundary values.