Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

[NB: Throughout this post, let the subscript $i$ range over the set $\unicode{x1D7DA} \equiv \{0, 1\}$.]

Let $(Y, \leqslant)$ be a poset, and $X\subseteq Y$. Let $\iota_i$ be the canonical inclusions $Y \hookrightarrow (Y \amalg Y)$. Define $Z = (Y \amalg Y)/\sim$, where $\sim$ is the smallest equivalence relation on $Y\amalg Y$ that identifies $\iota_0(x)$ and $\iota_1(x)$, for all $x \in X \subseteq Y$. Finally, define functions $f_i = \pi\;{\scriptstyle \circ}\;\iota_i$, where $\pi$ is the canonical projection $(Y \amalg Y) \to Z = (Y \amalg Y)/\sim$.

I'm looking for a construction of a partial order $\leqslant_Z$ on $Z = (Y \amalg Y)/\sim$ such that both $f_0$ and $f_1$ are order-preserving wrt $\leqslant_Z$.

This is what I have so far:

Since the $f_i$ are injections, the $\leqslant_i$ given by

$$ \leqslant_i \;\;=\;\; \{(f_i(y), f_i(y\,')) \;\;|\;\; (y, y\,' \in Y) \wedge (y \leqslant y\,')\} \;\;\cup\;\; I_Z. $$

...(where $I_Z$ is the identity on $Z$) are well-defined partial orders on $Z$.

Now, let $T$ be the transitive closure of the relation on $Z$ given by $\leqslant_0 \cup \leqslant_1$. I.e. $T = \bigcap_{V \in \mathscr{T}} V$, where $\mathscr{T} \neq \varnothing$ is the family of transitive relations containing $\leqslant_0 \cup \leqslant_1 $. $T$ is obviously transitive, and it is also reflexive, since $I_Z \subseteq V, \forall \; V \in \mathscr{T}$.

The question therefore reduces to whether $T$ is antisymmetric (i.e. $T\cap T^{-1} = I_Z$).

I'm having a hard time finding a halfway reasonable-looking approach to this last point.

share|cite|improve this question

Suppose that $z\leq w$ and $w\leq z$, this means that there are finite sequences so that $z=z_0\leq z_1\leq ...\leq z_n=w$ and $w=w_0\leq w_1\leq ...\leq w_m=z$ where for all $i< n$ $(z_i,z_{i+1})\in (\leq_0\cup \leq_1\cup I_Z)$ and for all $j<m$ $(w_j,w_{j+1})\in (\leq_0\cup \leq_1\cup I_Z)$. This implies $z$ equivalent to $w$.

share|cite|improve this answer
up vote 0 down vote accepted

In the following, the subscript index $i$ ranges over $\mathbb{Z}/2$.

Let $<_Y \;=\; \leqslant_Y - I_Y$. Likewise, let $<_i \;=\; \leqslant_i - I_Z = \{(f_i(x), f_i(y))|(x, y) \in <_Y\}$, $<^* \;=\; <_0 \;\cup\; <_1$, and $<_* \;=\; <_0 \;\cap\; <_1$. Also, define $\tilde{X} = f_0[Y] \cap f_1[Y] = f_0[X] = f_1[X]$, and $\tilde{E}_i = f_i[Y - X]$. Hence $Z = \tilde{X} \cup \tilde{E}_0 \cup \tilde{E}_1$ and $\tilde{X} \cap \tilde{E}_i = \tilde{E}_0 \cap \tilde{E}_1 = \varnothing$.

First, note that $\text{dom}(<_*) \subseteq \text{dom}(<_0) \cap \text{dom}(<_1) \subseteq f_0[Y] \cap f_1[Y] = \tilde{X}$, and similarly, $\text{ran}(<_*) \subseteq \tilde{X}$. Therefore $<_* \;\subseteq\;\tilde{X}\times\tilde{X}$, and thus, $\forall x, x' \in \tilde{X}$, we have that $x <_i x' \Leftrightarrow x <_* x'$.

Now, denote by $\mathscr{C}_p$ the class of all cycles in $<^*$ with basepoint $p\in Z$. Suppose that $\mathscr{C}_p \neq \varnothing$, for some $p \in Z$. Let $C = (p = p_0, p_1, \cdots, p_n = p) \in \mathscr{C}_p$ be of minimal length. From this last property, and the transitivity of the $<_i$, it follows that the pairs $(p_j, p_{j+1}), \forall j \in \mathbb{Z}/n$ that make up $C$ must belong alternately to $<_i$ and $<_{i+1}$. Abusing notation slightly, this situation can be summarized like this: $$ p_0 <_i p_1 <_{i+1} p_2 <_i \cdots <_i p_{n-1} <_{i+1} p_n = p = p_0 $$

...for some $i\in \mathbb{Z}/2$. Now, for every $j\in \mathbb{Z}/n$, it follows from $p_{j-1} <_{i_j} p_j$ and $p_j <_{{i_j}+1} p_{j+1}$ that $p_j \in \tilde{X}$, and from this, and the fact (shown above) that the restrictions of the $<_i$ to $\tilde{X}$ are equal to $<_*$, we conclude that

$$ p_0 <_* p_1 <_* p_2 <_* \cdots <_* p_{n-1} <_* p_n = p = p_0. $$

Since this contradicts the asymmetry of $<_*$, we conclude that $\mathscr{C}_p = \varnothing, \forall p\in Z$. From this it follows that $<^*$ is acyclic, and so its transitive closure $\overline{<^*}$ must be irreflexive. So we have that $\overline{<^*} \;\cup\; I_Z$ is a partial order on $Z$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.