Skip to main content
deleted 67 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

$\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. For everyEvery acyclic relation $\langle S,\prec\rangle$, there is 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$, and so itsince what we have done is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.

$\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.

Theorem. For every acyclic relation $\langle S,\prec\rangle$, there is 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$, and so it is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.

$\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

added 23 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

$\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.

Theorem. For every acyclic relation $\langle S,\prec\rangle$, there is an order-preserving injective map from $S$ to a locally finite 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-preservingpreservingly into a linear order $L$. Further, every linear order $L$ sits inside a locally finite 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$, and so it is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.

$\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.

Theorem. For every acyclic relation $\langle S,\prec\rangle$, there is an order-preserving injective map from $S$ to a locally finite linear order.

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-preserving into a linear order $L$. Further, every linear order $L$ sits inside a locally finite linear order, 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$, and so it is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.

$\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.

Theorem. For every acyclic relation $\langle S,\prec\rangle$, there is 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$, and so it is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

$\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.

Theorem. For every acyclic relation $\langle S,\prec\rangle$, there is an order-preserving injective map from $S$ to a locally finite linear order.

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-preserving into a linear order $L$. Further, every linear order $L$ sits inside a locally finite linear order, 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$, and so it is locally finite. Basically, you replace each point in the linear order with a copy of $\Z$. QED

So one doesn't need the locally finite hypothesis, and also the embedding can be injective.