When does a weakly connected directed acyclic graph have a unique transitive reduction?

Question

Given a relation $R$ whose digraph representation forms a weakly connected directed acyclic graph, when does there exists a unique minimal (ordered by inclusion) relation $L\subseteq R$ with $L^{+}=R^{+}$? Where the superscript $+$ is being used to express the transitive closure. Can we assume if $R$ does have a transitive reduction, then it is at-least countable? I can't seem to think of any uncountable weakly connected DAGs with a transitive reduction. Are they all countable?

I already know the result, that there is a unique reduction if $R$ is finite but I'm interested in cases when its not finite. At the very least it seems no subset of $R$ can be dense, is there anything else?

Answer 1

Never mind my hypothetical objection in the comments; it does not matter much for the solution.

Note that $R^+$ is a strict partial order; let us denote this by $<$. Furthermore, let $\leq$ denote its corresponding (non-strict/reflexive) partial order, and let $\lessdot$ denote its corresponding covering relation (in other words, we have $x \lessdot z$ if and only if $x < z$ and there is no $y$ such that $x < y < z$).

Proposition 1. Let $L \subseteq R^+$ be a relation such that $L^+ = R^+$ holds. Then $L$ contains the covering relation.

Proof. Suppose that $x \lessdot y$ holds but $(x,y) \notin L$. No directed path from $x$ to $y$ remains in the digraph representation of $L$, so we have $(x,y) \notin L^+ = R^+$. This is a contradiction, for $x \lessdot y$ in particular implies $x < y$, or equivalently: $(x,y) \in R^+$.

In particular, the above result shows that $R$ contains the covering relation.

The above proposition is complemented by the following result:

Proposition 2. Let $L \subseteq R^+$ be a relation such that $L^+ = R^+$ holds. If $L$ contains a non-covering pair (in other words, we have $(x,z) \in L$ but $x \not\lessdot z$), then $L$ is not minimal.

Proof. Set $K := L \setminus \{(x,z)\}$. Note that $xLz$ implies $x < z$, so the fact that $z$ does not cover $x$ (that is, we have $x \not\lessdot z$) implies that there is some $y$ with $x < y < z$. The digraph representation of $L$ therefore contains some path $x \leadsto y \leadsto z$. This path doesn't use the edge $(x,z)$ that we removed, so the path also exists in $K$. Therefore we have $K^+ = L^+$, showing that $L$ is not minimal.

Combining these two results, we get:

Theorem 3. A minimal $L \subseteq R$ with $L^+ = R^+$ exists if and only if $\lessdot^+ = R^+$ holds. In that case, we have $L = \: \lessdot$, which is not only a minimal but in fact a least subset of $R$ such that $L^+ = R^+$ holds.

Proof. On the one hand, suppose that $L$ is a minimal subset of $R$ satisfying $L^+ = R^+$. By proposition 2, $L$ does not contain non-covering pairs, so we have $L \subseteq \: \lessdot$. Furthermore, by proposition 1 we have $\lessdot \: \subseteq L$, so equality holds. In particular, we have $\lessdot^+ = R^+$.

On the other hand, suppose that $\lessdot^+ = R^+$ holds. Now we know from proposition 1 that $\lessdot \: \subseteq R$ holds, and it is clear from that same proposition that $L := \: \lessdot$ is the least subset of $R$ satisfying $L^+ = R^+$.

Ordered sets such as $\mathbb{Q}$ and $\mathbb{R}$ have no covering pairs at all, so here a transitive reduction doesn't exist. Hagen von Eitzen gave an example where every inequality is covering, so that the partial order is equal to its own transitive reduction. In general, you'll want to avoid infinite bounded chains; they tend to have insufficient covering pairs. (An unbounded chain is not necessarily problematic; for instance $\mathbb{N}$ and $\mathbb{Z}$ have ample covering pairs.)