5
$\begingroup$

Let $S=(S,\prec)$ be a set together with an acyclic binary relation, generally nontransitive. $S$ is locally finite if, for every element $x\in S$, the sets $\{w|w\prec x\}$ ("direct past of $x$") and $\{y|x\prec y\}$ ("direct future of $x$") are finite.

A linearly ordered set $(L,\le)$ is locally isomorphic to $\mathbb{Z}$ if every element of $L$ has a maximal predecessor and a minimal successor. The simplest example "larger than $\mathbb{Z}$" is $\mathbb{Z}\cup\mathbb{Z}$, in which each element of the first copy of $\mathbb{Z}$ precedes each element of the second.

An embedding of $(S,\prec)$ into $(L,\le)$, if it exists, is a set map $f:S\rightarrow L$, such that $f(x)<f(y)$ in $L$ whenever $x\prec y$ in $S$; i.e., it preserves $\prec$ strictly.

The question is then "does every locally finite acyclic directed set $S$ embed into a linearly ordered set $L$ locally isomorphic to $\mathbb{Z}$?"

Example: Let $(S,\prec)$ be the set (I will call it "Jacob's Ladder") with elements $\{x_i\}_{i\in\mathbb{N}}\cup \{y_{-j}\}_{j\in\mathbb{N}}$ and relations $x_i\prec x_{i+1}$, $y_{-j}\prec y_{-j+1}$, and $x_i\prec y_{-i}$ for all $i,j$. $S$ is locally finite; its transitive closure is $\mathbb{N}\cup-\mathbb{N}$, and it embeds into $\mathbb{Z}\cup\mathbb{Z}$ in the obvious way.

I have a messy ad hoc "proof" in the affirmative, but I have little confidence in it. The question seems simple enough that I'd expect it to be already known one way or the other. Can anybody help? I'd be satisfied with the countable case. EDIT: this particular "proof" doesn't work, but I still don't know the answer to the question.

EDIT: As Joel points out, the question is trivial as I first stated it. What I really want is an extension of a locally finite acyclic binary relation to a linear order isomorphic to the integers except possibly for a unique maximal and/or minimal element. The example of extending Jacob's Ladder to $\mathbb{N}\cup-\mathbb{N}$ illustrates this. Is it possible in general?

$\endgroup$
4
  • $\begingroup$ By the way, these kinds of orders are called discrete orders, a linear order where every non-least point has an immediate predecessor and every non-greatest point has an immediate successor. $\endgroup$ Sep 25, 2013 at 19:58
  • $\begingroup$ Your edit makes this an extremely interesting question! $\endgroup$ Sep 25, 2013 at 23:51
  • $\begingroup$ Incidentally, you can reduce to the countable case, since the connected components of $S$ are each countable, and you can treat each connected component separately, afterwards merging these discrete orders into one giant discrete order. (There is a complication when most of the discrete orders arising have a minimal but no maximal element, or conversely, but this can be handled by allowing those bottom parts to overlap.) $\endgroup$ Sep 26, 2013 at 3:00
  • $\begingroup$ Joel, that's a helpful observation, since it allows you to begin with an arbitrary enumeration and try to use some sort of inductive procedure. $\endgroup$
    – Ben
    Sep 26, 2013 at 7:25

1 Answer 1

1
$\begingroup$

$\newcommand{\P}{\mathbb{P}} \newcommand{\L}{\mathbb{L}} \newcommand{\Z}{\mathbb{Z}}$

The answer is yes, and you don't need the locally finite hypothesis. Also, you may assume that the embedding is injective.

Theorem. Every acyclic relation $\langle S,\prec\rangle$ admits an order-preserving injective map from $S$ to a linear order locally isomorphic to $\Z$.

Proof. Suppose $\langle S,\prec\rangle$ is an acylic relation. Let $\leq$ be the reachability relation on this digraph, that is, the transitive closure of $\prec$. This is a partial order on $S$, because $\prec$ is acyclic. Since every partial order extends to a linear order, we may inject $\prec$ order-preservingly into a linear order $L$. Further, every linear order $L$ sits inside a linear order locally isomorphic to $\Z$, simply by taking $L$ copies of $\Z$, that is, by embedding $L$ into $\Z\times L$ with the usual order (reverse lexical order). This new order looks locally just like $\Z$, since what we have done is replace each point in the linear order with a copy of $\Z$. QED

$\endgroup$
3
  • $\begingroup$ thanks, this clarifies things... the way I described the problem turns out to be trivial. What I was actually trying to do was extend the locally finite acyclic relation to a linear relation locally isomorphic to the integers except for possibly having a unique minimal and/or maximal element. Do you know if this is possible? $\endgroup$
    – Ben
    Sep 25, 2013 at 18:10
  • $\begingroup$ That is a more reasonable question, to extend it to such a relation without adding any new points. I'll give it some thought... $\endgroup$ Sep 25, 2013 at 18:48
  • $\begingroup$ Joel, I added an edit at the bottom adjusting the question... but left the rest alone for comprehensibility. $\endgroup$
    – Ben
    Sep 25, 2013 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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