Is the Hasse diagram of $(X,\mid)$ a tree?

155 Views Asked by At

Let $X=\{1,2,3,...,n\}$ and let $(X,\mid)$ be a poset with the the partial order of divisibility on $X$. Is the directed Hasse diagram of $(X,\mid)$ a directed rooted tree? (Where the arrows points from $a$ to $b$ off $b$ covers $a$) Proving that it's a directed rooted tree will also prove the well known fact that every common divisor of two numbers divides their gcd. But, I couldn't give any proof to this problem other than using the above fact and reversing the arguments. I am searching for another proof which doesn't use the above fact.

1

There are 1 best solutions below

2
On BEST ANSWER

It's not a tree as soon as $X$ contains a number of the form $pq$ with $p\neq q$: $$1\to p\to pq\to q\to 1$$ will be a loop.

After edit: note that for a directed graph, being a tree and not having oriented loops are two different things. A directed graph is a tree if and only if the underlying undirected graph is a tree. In fact, a tree is most of the time defined as an undirected graph with no loops.