Proof that a finite poset is uniquely determined by its cover relation

Question

My proof:

It is enough to show that if two partial orders on a finite set satisfy the same cover relation, then they must be the same order.

Let, $X$ is a finite set, and $\le_1$ and $\le_2$ be two partial orders on $X$ satisfying the same cover relation $\lt_c$. If possible, let $\le_2$ be distinct from $\le_1$, that is, $\exists a,b \in X, a\lt_2b, a\nless_1b$.

$a\lt_cb \implies a\lt_1b$, a contradiction, and so, $a\nless_cb$. Hence, $\exists x_1\in X, a\lt_2x_1\lt_2b$. By the same argument, $a\nless_cx_1$, and hence, $\exists x_2\in X, a\lt_2x_2\lt_2x_1$.

Hence, there are infinitely many elements $x_i \in X, a \lt_2 \dots \lt_2 x_2 \lt_2 x_1 \lt_2 b$. But this contradicts the assumption that $X$ is a finite set, and hence, $\le_1$ and $\le_2$ must be the same order.

Is the above proof correct?

PS: I am trying to learn combinatorics from Brualdi's "Introductory Combinatorics", and in chapter 4 this theorem is given as an exercise, with the hint to use transitivity. I don't see where transitivity can be used to prove this, so I'll appreciate it if somebody can give an hint regarding that.

Answer 1

Using OP's notation.

Claim 1: $a \leq_2 b \land a \neq b \Rightarrow a \leq_1 b$.

Suppose $a <_c b$, then $a \leq_1 b$ and we are done. If not $\exists x_0$ s.t. $a <_2 x_0 <_2 b$ s.t. $x_0 <_c b$.

(If $x_0 \not<_c b$, then we can find $x_1$ s.t. $x_0 <_2 x_1 <_2 b$. If $x_1 \not<_c b$, then we can find $x_2$, and so on. As the set is finite, this process must terminate, and hence such an $x_0$ exists)

If $a \not<_c x_0$, then we similar to previous case we can find $x_1$ s.t. $a <_2 x_1 <_2 x_0$ s.t. $x_1 <_c x_0$. We can iterate this process. Again as the set is finite, this process must terminate, which implies $\exists \{x_i \; | 0 \leq i \leq N \}$ s.t. $a <_2 x_0 \land (\forall i) x_i <_2 x_{i+1} \land x_N <_2 b \land a <_c x_0 \land (\forall i) x_i <_c x_{i+1} \land x_N <_c b$. Thus $a <_1 x_0 \land (\forall i) x_i <_1 x_{i+1} \land x_N <_1 b$, and by the transitivity of a partial order, we have $a \leq_1 b$.

Claim 2: $a \leq_2 a \Rightarrow a \leq_1 a$ (holds by reflexivity)

These claims show that $\leq_2 \; \subseteq \; \leq_1$. By symmetry, $\leq_1 \; \subseteq \; \leq_2$ which implies that $\leq_2 \; = \; \leq_1$.

Generalization: From the above proof, we see that the above property holds true for even preorders, as we only require reflexivity and transitivity.

Answer 2

The phenomenon you are mentioning is quite remarkable and can be described in a more general fashion. Given arbitrary set $A$ let us write $\mathscr{Ord}(A)$ for the set of all order relations on $A$. For fixed order $R \in \mathscr{Ord}(A)$ we use the following notations:

• $x \leqslant_R y$ as an equivalent rendering of $xRy$ (or $(x, y) \in R$).
• $x<_R y$ as an equivalent rendering of $x \leqslant_R y \wedge x \neq y$ or $(x, y) \in R \setminus \Delta_A$.
• $(x, y)_R \colon=\{t \mid x <_R t <_R y\}$ for the open interval with respect to $R$ determined by $x$ and $y$, together with the analogous suggestive syntax for the other types of intervals: $[x, y]_R$, $[x, y)_R$, $(x, y]_R$, $(\leftarrow, y)_R$, $(\leftarrow, y]_R$, $(x, \rightarrow)_R$, $[x, \rightarrow)_R$.
• $\mathrm{Min}_R(X)$ for the set of all $R$-minimal elements of arbitrary subset $X \subseteq A$.
• $R_{\bullet}\colon=\{u \mid (\exists x, y)\left(u=(x, y) \wedge x<_Ry \wedge (x, y)_R=\varnothing\right)\}$ to denote the collection of all ordered pairs $(x, y)$ such that $y$ is a successor of $x$ with respect to $R$, in other words the so-called covering relation associated to $R$.
• $\{x\}^+_R \colon=\{y \mid x<_R y \wedge (x, y)_R=\varnothing\}$ ($\{x\}^-_R \colon=\{y \mid y<_R x \wedge (y, x)_R=\varnothing\}$) for the set of all successors (predecessors) of $x$ with respect to $R$. We note that $\{x\}^+_R=R_{\bullet}\langle x \rangle$ (respectively $\{x\}^-_R=\left(R_{\bullet}\right)^{-1}\langle x \rangle$).
• $\mathscr{Rel}(A)\colon=\mathscr{P}(A \times A)$ for the set of all binary relations on $A$.
• $[X]_{\mathrm{RefTr}}=\displaystyle\bigcup_{n \in \mathbb{N}}X^{[n]}$ for the reflexive-transitive closure of arbitrary binary relation $X \subseteq A \times A$ (closure which is defined as the intersection of all the reflexive & transitive relations on $A$ which include $X$ or equivalently the smallest such (including $X$) reflexive & transitive relation on $A$ with respect to the order given by inclusion). $X^{[m]}$ denotes the composition of $X$ $m$ times with itself, or more rigorously speaking the power of exponent $m$ of $X$ with respect to the monoid $\left(\mathscr{Rel}(A), \circ\right)$ (the operation being the composition of binary relations).

Recall that given $R \in \mathscr{Ord}(A)$ we say the ordered set $(A, R)$ is artinian (noetherian) if any nonempty subset $X \subseteq A$ admits a minimal (maximal) element. The following are then equivalent statements regarding the ordered set $(A, R)$:

• $(A, R)$ is artinian (noetherian)

• any sequence $x \in A^{\mathbb{N}}$ decreasing (increasing) with respect to $R$ is necessarily eventually stationary

• there exists no sequence $x \in A^{\mathbb{N}}$ strictly decreasing (increasing) with respect to $R$.

Recall also the fundamental theorem of recursion in its following formulation: given arbitrary set $A$, fixed element $a \in A$ and self-map $f \colon A \to A$, there exists a unique sequence $u \in A^{\mathbb{N}}$ such that $u_0=a$ and $u_{n+1}=f(u_n)$ for every $n \in \mathbb{N}$.

We shall now establish the following:

Proposition. Consider set $A$ and two orders $R, R' \in \mathscr{Ord}(A)$ such that $R_{\bullet} \subseteq R'_{\bullet}$. If the ordered set $(A, R)$ is simultaneously artinian and noetherian it holds that $R \subseteq R'$.

Proof. We first remark the relation: $$\{x\}^+_R=R_{\bullet}\langle x \rangle \subseteq R'_{\bullet}\langle x \rangle=\{x\}^+_{R'},$$ in other words any $R$-successor of $x$ is automatically an $R'$-successor for any $x \in A$.

Let us proceed by Reductio ad absurdum and assume the contrary of what we must prove, namely that $R \setminus R' \neq \varnothing$. This means there exist $a, b \in A$ such that $a \leqslant_R b$ and nevertheless $(a, b) \notin R'$. Since $\Delta_A \subseteq R'$ by definition, it follows that $(a, b) \notin \Delta_A$ and hence that $a<_R b$. Furthermore, since $R_{\bullet} \subseteq R'_{\bullet} \subseteq R'$, it also must be that $(a, b) \notin R_{\bullet}$ whence in conjunction with $a<_R b$ we infer that necessarily $(a, b)_R \neq \varnothing$.

Fixing an arbitrary element $u \in A$, let us remark that for given $x \in (\leftarrow, u)_R$ we either have that $(x, u)_R=\varnothing$ - in which case $u$ itself is an $R$-successor of $x$ - or $(x, u)_R \neq \varnothing$, in which case any of the elements of the set $\mathrm{Min}_R\left((x, u)_R\right) \neq \varnothing$ - set nonempty by virtue of artinianity and the fact that $(x, u)_R \neq \varnothing$ - is once again an $R$-successor of $x$ at most equal to $u$ (actually in this case strictly less than $u$). By a so-called application of the axiom of choice we thus infer the existence of a map $\sigma \colon (\leftarrow, b)_R \to (\leftarrow, b]_R$ such that $\sigma(x) \in \{x\}^+_R$ for each $x<_R b$.

Let us move on to introducing the subset: $$B \colon=\{x \in [a, b)_R \mid a \leqslant_{R'} x \wedge (x, b)_R \neq \varnothing\}=[a, \rightarrow)_{R'} \cap [a, b)_R \setminus \{b\}^-_R$$ and let us make the crucial observation that $\sigma[B] \subseteq B$ (this is the part where the hint regarding transitivity comes into play). Indeed, if $x \in B$ then by definition $a \leqslant_R x<_R b$ and $(x, b)_R \neq \varnothing$, which means that $\sigma(x) \neq b$. Hence we have $a \leqslant_R x <_R \sigma(x) <_R b$, which means that $\sigma(x) \in [a, b)_R$. Since by construction $\sigma(x) \in \{x\}^+_R$ we infer from our opening remark that $\sigma(x) \in \{x\}^+_{R'}$ and hence that $x \leqslant_{R'} \sigma(x)$. Bearing in mind that by definition of $B$ we also have $a \leqslant_{R'} x$, we infer from transitivity that $a \leqslant_{R'} \sigma(x)$ and hence $\sigma(x) \in [a, \rightarrow)_{R'}$.

We now only need to ascertain that $(\sigma(x), b)_R \neq \varnothing$ in order to conclude that $\sigma(x) \in B$. Assuming the contrary - that $(\sigma(x), b)=\varnothing$ - would mean in conjunction with the relation $\sigma(x)<_R b$ that $(\sigma(x), b) \in R_{\bullet} \subseteq R'_{\bullet} \subseteq R'$ and would eventually entail $a \leqslant_{R'} \sigma(x) \leqslant_{R'} b$, which once again by transitivity would amount to the absurd conclusion that $a \leqslant_{R'} b$.

Thus we can introduce the two-sided restriction $\varphi=_{B|}\sigma_{|B}$ which of course is a self-map $\varphi \colon B \to B$. Furthermore, it is clear that $a \in B$ and hence we can apply the fundamental theorem of recursion to the triplet $(B, a, \varphi)$ in order to infer the existence of sequence $c \in B^{\mathbb{N}}$ described by $c_0=a$ and $c_{n+1}=\varphi(c_n)$ for each $n \in \mathbb{N}$. Since however $x <_R \sigma(x)$ for any $x<_R b$ from the preceding recursive definition we gather that $c_{n+1}=\sigma(c_n) >_R c_n$ for every $n \in \mathbb{N}$. This means that the sequence $c$ is strictly increasing with respect to $R$ which contradicts the fact that $(A, R)$ is noetherian, bringing our proof to an end. $\Box$

From this proposition it is easy to derive the following:

Corollary. Let $\mathscr{Ord}_{\mathrm{AN}}(A)$ denote the set of all orders $R$ on $A$ such that $(A, R)$ is at the same time artinian and noetherian. Then the map given by: \begin{align} \mathscr{Ord}_{\mathrm{AN}}(A) &\to \mathscr{Rel}(A) \\ R &\mapsto R_{\bullet} \end{align} is injective.

Another consequence which perhaps requires a bit more effort to prove but nevertheless essentially relies on the proposition above is:

Corollary. Let $A$ be a set and $R \in \mathscr{Ord}_{\mathrm{AN}}(A)$. Then the relation $R=\left[R_{\bullet}\right]_{\mathrm{RefTr}}$ holds (in other words, any artinian & noetherian order relation can be recovered as the reflexive-transitive closure of its covering relation).