Extending a partial order

122 Views Asked by At

Consider a partially ordered set $(X,\leq)$. For finite subsets $A,B\subseteq X$, write $A\preceq B$ whenever there is an injection $f:A\to B$ such that $a\leq f(a)$ for every $a\in A$.

It is easily seen that the finite subsets of $X$ are now quasi-ordered by $\preceq$, that is, $\preceq$ is a reflexive and transitive relation.

I am wondering if the antisymmetry of $\leq$ now also extends to $\preceq$?

3

There are 3 best solutions below

9
On BEST ANSWER

Yes, it does. It may be easiest to reason by induction. Note that if $A \leq B$ and $B \leq A$ then $|A| = |B|$. Trivially it is true for $A, B$ empty. Now suppose that our statement is true for all subsets smaller than $A, B$.

Suppose that $A, B$ are such that $A \leq B$ and $B \leq A$ by your definition, witnessed by $f: A \to B$ and $g: B \to A$. Now take $a \in A$ and consider $a \leq f(a) \leq g(f(a)) \leq f(g(f(a))) \leq \cdots$. This is an infinite increasing sequence in the set $A \cup B$, and thus must eventually repeat, let's say starting at element $b$. Because $\leq$ is anti-symmetric, it follows that we find $b = f(b) = g(f(b))$. Then we can consider $A \setminus \{b\}$ and $B \setminus \{b\}$, and restricting $f, g$ to those sets still gives us that $A \setminus \{b\} \leq B \setminus \{b\}$ and vice versa. But by the induction hypothesis, it follows that these sets are equal. Thus they are also equal when $b$ is added back in, completing the proof by induction.

1
On

I think it does. Let $f:A\to B$ and $g:B\to A$ be injections such that $\forall a\in A\quad a\le f(a)$ and $\forall b\in B\quad b\le g(b).$ Let us prove that $A\subset B$ (by symmetry, $B\subset A$ will also hold).

Take some $a\in A$ and consider $$a\le f(a)\le g(f(a))\le f(g(f(a)))\le\dots.$$ Since $A$ is finite, there must exist two integers $0\le p<q=p+n$ such that $(g\circ f)^p(a)=(g\circ f)^q(a).$ Going backwards by injectivity of $f$ and $g$, this entails $a=(g\circ f)^n(a)$ hence $$a=f(a)=g(f(a))=f(g(f(a)))=\dots=(g\circ f)^n(a),$$ in particular $a=f(a)\in B,$ q.e.d.

0
On

The answer to your question is affirmative and can be established in a logically clear fashion along the following line of reasoning. Recall that an ordered set $(A, R)$ (where $R$ is an order relation on $A$) is called Artinian provided that any nonempty subset $\varnothing \neq X \subseteq A$ admits a minimal element (with respect to $R$, of course). Note that in particular finite ordered sets are always Artinian.

One first establishes the following fundamental

Lemma: Let $(A, R)$ be Artinian and $f \colon A \to A$ a surjection such that $x \leqslant_R f(x)$ for any $x \in A$ (let us agree to call such a map inflationary). Then necessarily $f=\mathbf{1}_A$ (the identity map of $A$).

Proof: we will use a method of reasoning preeminently featured in the theory of Artinian sets, namely the general form of induction, which in our case is to be formulated as follows: if for arbitrary $y \in A$ we have that $f(x)=x$ for any $x<_R y$, it follows that also $f(y)=y$. To show this is indeed the case for arbitrary $y \in A$, by the surjectivity of $f$ we gather the existence of $t \in A$ such $f(t)=y$; it follows immediately from the inflationary character of $f$ that $t \leqslant_R y$. Should it be the case that $t \neq y$ we would have automatically that $t <_R y$ and hence $f(t)=t \neq y$, by virtue of the (generalised) induction hypothesis. This leaves us with the only option $t=y$, entailing $f(y)=y$ and concluding the proof. $\Box$

This applies to the particular context of your problem in the following manner. Consider arbitrary ordered set $(A, R)$ and on the power-set $\mathscr{P}(A)$ define the binary relation $\mathscr{R}$ by: $$X\mathscr{R}Y \Leftrightarrow (\exists f)(f \in \mathrm{Hom}^{\mathrm{i}}_{\mathbf{Ens}}(X, Y)\ \wedge (\forall x)(x \in X \Rightarrow x\leqslant_R f(x))),$$

precisely as you have specified above. I have taken the liberty to use the notation $\mathrm{Hom}^{\mathrm{i}}_{\mathbf{Ens}}(M, N)$ to refer to the set of all injections from $M$ to $N$.

As you remark, $\mathscr{R}$ will in general only be a preorder on the powerset $\mathscr{P}(A)$, however its restriction to the collection of all subsets of $A$ which are Artinian with respect to $R$ becomes an order, satisfying the more stringent axiom of antisymmetry. Let us formalise this by introducing the notations:

  • $R_{|M} \stackrel{\small\text{def}}{=} R \cap \left(M \times M\right)$, to denote the restriction to subset $M \subseteq A$ of any binary relation $R$ on a given set $A$; if $M \subseteq N \subseteq A$, it is obvious that $R_{|M}=\left({R_{|N}}\right)_{|M}$ (transitivity of restrictions); if $R$ is an order on $A$ it is obvious that $\left(M, R_{|M}\right)$ will correspondingly be an ordered set (hereditary character of orders).
  • $\mathscr{Art}_R(A) \stackrel{\small\text{def}}{=} \left\{X \subseteq A \mid \left(X, R_{|X}\right)\ \text{Artinian}\right\}$, denoting the collection of all $R$-Artinian subsets of $A$.

With these preparations in place, we can claim that:

Proposition: $\left(\mathscr{Art}_R(A), \mathscr{R}_{|\mathscr{Art}_R(A)}\right)$ is an ordered set.

Proof: the claim amounts to saying that whenever $X \leqslant_{\mathscr{R}}Y$ and $Y \leqslant_{\mathscr{R}}X$ simultaneously hold it follows with necessity that $X=Y$, for arbitrary artinian subsets $X, Y \subseteq A$. We prove this directly, by first inferring the existence of injections $f \colon X \to Y$ respectively $g \colon Y \to X$ such that $x \leqslant_R f(x)$ for all $x \in X$ respectively $y \leqslant_R g(y)$ for all $y \in Y$, on the grounds of the sheer definition of $\mathscr{R}$.

It is clear that $g \circ f \colon X \to X$ is a bijection inflationary with respect to $R_{|X}$ and - since $(X, R_{|X})$ is Artinian by hypothesis - the above lemma applies with the conclusion that $g \circ f=\mathbf{1}_X$ (obviously, the analogous reasoning applies to the reverse composition $f \circ g=\mathbf{1}_Y$).

Considering the inflationary character of $f$ and $g$ - in this order of application, so to speak - we infer the relation $x \leqslant_R f(x) \leqslant_R g(f(x))=x$ for any $x \in X$, which by virtue of the antisymmetry of $R$ entails $f(x)=x$ for any $x \in X$ and hence $X \subseteq Y$; the reciprocal inclusion is of course established by considering the corresponding reasoning, where applies $g$ first and then $f$. Thus, we can conclude that $X=Y$. $\Box$

As mentioned in a previous paragraph, finite ordered sets are Artinian. If we agree to denote the collection of finite subsets of $A$ by $\mathscr{F}(A)$, we can thus formulate the succinct relation $\mathscr{F}(A) \subseteq \mathscr{Art}_R(A)$. As such, by transitivity of restrictions it is clear that $\mathscr{R_{|\mathscr{F}(A)}}$ is a restriction of $\mathscr{R}_{|\mathscr{Art}_R(A)}$ and as the latter is an order we conclude on grounds of heredity that so is the former.