Of particular importance for our study are partial orders and other relations associated with partial orders. The importance stems from the fact that the corresponding graphs are in some ways analogous to the standard reliability setting.
Suppose that \(S\) is a nonempty set.
A strict partial order graph \((S, \prec)\) is also asymmetric: if \(x \prec y\) and \(y \prec x\) for some \(x, \, y \in S\) then by the transitive property, \(x \prec x\). But this contradicts the irreflexive property. More generallly, \((S, \prec)\) is acyclic. If \(x \prec x_1 \prec \cdots \prec x_n \prec x\) for some \(x \in S\), \(n \in \N_+\) and \((x_1, \ldots, x_n) \in S^n\) (a cycle of length \(n + 1\)), then again by transitivity, we have the contradiction \(x \prec x\).
The term partially ordered set (poset) is commonly used in the literature, but we want to continue with graph terminology for consistency. The following results are clearly suggested by the notation (recall the definitions of reflexive reduction and reflexive closure from Section 1).
Suppose again that \(S\) is a nonempty set.
Here is a summary of some of the graphs associated with a given partial order graph.
Suppose that \((S, \preceq)\) is a partial order graph. Associated graphs include
Of course, \(\succeq\) is the inverse (or reverse) of \(\preceq\) and is also a partial order. Similarly \(\prec\) and \(\succ\) are inverses of each other and are strict partial orders. The equality relation \(=\) is the intersection of \(\preceq\) and \(\succeq\) and is also a partial order. The relation \(\perp\) is the union of \(\preceq\) and \(\succeq\) so that \(x \perp y\) if and only if \(x\) and \(y\) are comparable. Finally, \(\parallel\) is the complement of \(\perp\) so that \(x \parallel y\) if and only if \(x\) and \(y\) are non-comparable. The following result is natural given the details in definition .
Suppose that \((S, \rta)\) is an acyclic graph. Define the relation \(\prec\) on \(S\) by \(x \prec y\) if and only if there exists a finite path in \((S, \rta)\) from \(x\) to \(y\). Then \(\prec\) is a strict partial order on \(S\).
Since \((S, \rta)\) is acyclic, \(\prec\) is irreflexive: there are no finite paths in \((S, \rta)\) from \(x\) to \(x\) for \(x \in S\). Also \(\prec\) is transitive. If \(x, \, y, \, z \in S\) and there exist finite paths in \((S, \rta)\) from \(x\) to \(y\) and from \(y\) to \(z\). Then combining the two paths we have a path in \((S, \rta)\) from \(x\) to \(z\).
Suppose that \((S, \preceq)\) is a partial order graph. If either \(x \preceq y\) or \(y \preceq x\) for every \(x, \, y \in S\) then \((S, \preceq)\) is totally ordered.
The term linearly ordered is sometimes used instead of totally ordered. In the discrete case, a totally ordered graph is also called a chain.
The dimension of a partial order graph \((S, \preceq)\) is the smallest number of total orders on \(S\) whose intersection (as subsets of \(S^2\)) is \(\preceq\). The dimension is denoted by \(\dim(S, \preceq)\).
Interval notation is natural for a partial order graph.
FSuppose that \((S, \preceq)\) is a partial order graph. For \(a, \, b \in S\) define
The concepts of increasing, decreasing, and convex sets and functions are also natrual.
Suppose again that \((S, \preceq)\) is a partial order graph and that \(A \subseteq S\).
If \(A \subseteq S\) is convex and \(x, \, y \in A\) then \([x, y] \subseteq A\). In particular, if \(a, \, b \in S\) then each of the intervals \([a, b]\), \((a, b)\), \([a, b)\) and \((a, b]\) is itself convex. Intersection preserves these special properties.
Suppose again that \((S, \preceq)\) is a partial order graph and that \(A_i \subseteq S\) for each \(i\) in a nonempty index set \(I\).
In turn, this leads in the usual way to the increasing, decreasing, and convex sets generated by a given set.
Suppose again that \((S, \preceq)\) is a partial order graph and that \(A \subseteq S\).
If \(A\) is increasing or if \(A\) is decreasing then trivially \(A\) is convex. The following result is only slightly more complicated.
Suppose again that \((S, \preceq)\) is a partial order graph. If \(A \subseteq S\) is increasing and \(B \subseteq S\) is decreasing then \(A \cap B\) is convex.
Suppose that \(x, \, z \in A \cap B\), \(y \in S\) and \(x \preceq y \preceq z\). Then \(y \in A\) since \(x \in A\) and \(x \preceq y\). Similarly \(y \in B\) since \(z \in B\) and \(y \preceq z\). Hence \(y \in A \cap B\).
The notions of increasing and decreasing can be extended to functions:
Suppose that \((S_1, \preceq_1)\) and \((S_2, \preceq_2)\) are partial order graphs, and that \(f: S_1 \to S_2\).
If \((S, \preceq)\) is a partial order graph and \(A \subseteq S\), then \(A\) is increasing (decreasing) if and only if \(\bs 1_A\) is increasing (decreasing), where as usual \(\bs 1_A\) is the indicator function of \(A\), mapping \((S, \preceq)\) into \((\{0, 1\}, \le)\).
Various extremal elements make sense in a partial order graph.
Suppose that \((S, \preceq)\) is a partial order graph and that \(A \in \ms S\).
As the terminology suggests, the minimum and maximum elements of \(A\) are unique if they exist, and are denoted \(\min(A)\) and \(\max(A)\) respectively. On the other hand, \(A\) can have multiple minimal or maximal elements (or none).
Suppose again that \((S, \preceq)\) is a partial order graph and that \(A \subseteq S\).
The infimum of \(A\) is unique if it exists, and is denoted \(\inf(A)\). Similarly, the supremum of \(A\) is unique if it exists, and is denoted \(\sup(A)\). Note that every element of \(S\) is a lower bound and an upper bound of \(\emptyset\) since the conditions in the definition hold vacuously. For \(x, \, y \in S\), an operator notation is commonly used for the infimum and supremum: \(x \wedge y = \inf\{x, y\}\) and \(x \vee y = \sup\{x, y\}\). When these exist, the partial order graph has a special name.
Suppose that \((S, \preceq)\) is a partial order graph.
A partial order graph \((S, \preceq)\) is well founded if every nonepmty subset of \(S\) has a minimal element. The graph is well ordered if it is totally ordered and well founded.
In particular, if \((S, \preceq)\) is well founded then \(S\) itself has a miniimal element. If \((S, \preceq)\) is well ordered then every nonempty subset of \(S\), including \(S\) itself, has a minimum element.
A partial order graph \((S, \preceq)\) is well founded if and only if the graph does not have an infinite descending chain, that is, a sequence \((x_1, x_2, \ldots)\) with \(x_1 \succ x_2 \succ \cdots\).
Suppose that \((S, \preceq)\) is not well founded. Then there exists a nonempty \(A \subseteq S\) with no minimal element. Let \(x_1 \in A\). Since \(x_1\) is not a minimial element of \(A\), there exists \(x_2 \in A\) with \(x_2 \prec x_1\). Since \(x_2\) is not a minimal element of \(A\), there exists \(x_3 \in A\) with \(x_3 \prec x_2\). Continuing in this way produces an infinite descending chain. Conversely, suppose that \((S, \prec)\) has a sequence \((x_1, x_2, \ldots)\) with \(x_1 \succ x_2 \succ \cdots\). Then clearly \(\{x_1, x_2, \ldots\}\) has no minimal element so \((S, \preceq)\) is not well founded.
Well-founded partial order graphs are important because they support a type of induction and a type of recursion known, appropriately enough, as well-founded induction.
Suppose that \((S, \preceq)\) is a well-founded partial order graph and that \(P(x)\) is a predicate in \(x \in S\). If for every \(x \in S\), \(P(y)\) for \(y \prec x\) implies \(P(x)\), then \(P(x)\) for all \(x \in S\).
Suppose that the induction hypothesis in the theorem holds, that is, \(P(y)\) for \(y \prec x\) implies \(P(x)\) for every \(x \in S\). Let \(A = \{x \in S: \lnot P(x)\}\). If \(A \ne \emptyset\) then \(A\) has a minimal element \(a \in A\). But then by definition of minimality, if \(y \in S\) and \(y \prec a\) then \(P(y)\). By the induction hypothesis, \(P(a)\) which is a contradiction. Hence \(A = \emptyset\).
There is another graph that we can associate with a given partial order graph, but this one is primarily of value in the discrete case.
Suppose that \((S, \preceq)\) is a partial order graph. For \(x, \, y \in S\), element \(y\) covers \(x\) if \(y\) is a minimal element of \(\{ u \in S: x \prec u\}\). Equivalently, \(y\) covers \(x\) if and only if \(x \prec y\) but no \(z \in S\) satisfies \(x \prec z \prec y\). If \(\upa\) denotes the covering relation then the graph \((S, \upa)\) is the covering graph or Hasse graph of \((S, \preceq)\).
The term Hasse graph is named for the German mathematician Helmut Hasse. For \(x \in S\) note that \(\{ y \in S: x \upa y \}\) is the set of elements immediately after \(x\) in the partial order while \(\{u \in S: u \upa x\}\) is the set of elements immediately before \(x\) in the partial order. The convering graph is characterized by two properties.
Suppose again that \((S, \preceq)\) is a partial order graph, and let \((S, \upa)\) denote the covering graph. Then
As a consequence of , the covering graph of \((S, \preceq)\) defines a strict partial order. But in general this may not be the strict partial order \(\prec\) that we started with.
Suppose that \((S, \preceq)\) is a well founded partial order graph. If \(x, \, y \in S\) with \(x \prec y\) then there exists \(z \in S\) with \(x \upa z\) and \(z \le y\).
The set \(\{u \in S: x \prec u\}\) is nonempty and hence, since the graph is well founded, has a minimal element \(z\).
Suppose now that \((S, \ms S)\) is a measurable space. Recall that \(S^n\) is given the product \(\sigma\)-algebra \(\ms S^n\) for \(n \in \N_+\). From our general definitions in Section 1, a graph \((S, \rta)\) is measruable if the relation \(\rta\) (as a subset of \(S^2\)) is measurable, that is, \(\{(x, y) \in S^2: x \rta y\} \in \ms S^2\). On the other hand, the right \(\sigma\)-algebra assocated with \((S, \rta)\) is the \(\sigma\)-algebras \(\ms A\) generated by the collection of right neighbor sets: \(\ms A = \sigma\{A_x: x \in S\}\) where \(A_x = \{y \in S: x \rta y\}\) for \(x \in S\). These definitions apply of course to the graphs studied in this section.
Suppose \((S, \preceq)\) is a measurable partial order graph. Then each of the associated graphs is also measurable.
The results follow from general results in the Section 1.
From part (b), a measurable partial order graph has a measurable diagonal, an important property discussed in the Preface. On the other hand, the measurability of \((S, \prec)\) does not in general imply the measurability of \((S, =)\) or \((S, \preceq)\).
If \((S, \preceq)\) is a measurable partial order graph then each of the intervals defined in is in \(\ms S\).
The following result was given in Section 1, but we repeat it here for emphasis.
Suppose that \(S\) is a nonempty set. The \(\sigma\)-algebra associated with \((S, =)\) is the collection of countable and co-countable sets: \[ \ms C = \{A \subseteq S: A \text{ is countable or } A^c \text{ is countable}\}\]
The countable, co-countable \(\sigma\) algebra is the \(\sigma\) algebra generated by the singleton sets.
In particular, if \(S\) itself is countable then the \(\sigma\)-algebra assocated with \((S, =)\) is \(\ms P(S)\), the collection of all subsets of \(S\).
For the remainder of this subsection, suppose that \(\lambda\) is a fixed \(\sigma\)-finite reference measure on \((S, \ms S)\). In the discrete case, the reference measure is always counting measure \(\#\). From the general definition in Section 1, a partial order graph \((S, \preceq)\) is left finite if \(u(x) = \lambda\{t \in S: t \preceq x\} \lt \infty\) for \(x \in S\). In general, left finiteness is the appropriate assumption for the abstract reliablity theory that we will study, starting in Section 3.
Suppose that \((S, \preceq)\) is a discrete, left finite partial order graph. Then \((S, \preceq)\) is well founded.
If \((x_1, x_2, \ldots)\) is an infinite descending chain, so that \(x_1 \succ x_2 \succ \cdots\), then \(\{t \in S: t \preceq x_1\}\) has infinitely many elements, a contradiction.
Suppose that \((S, \preceq)\) is a discrete, left finite partial order graph. If \(x, \, y \in S\) with \(x \prec y\) then there exists a finte path from \(x\) to \(y\) in the covering graph \((S, \upa)\).
There exists \(z_1 \in S\) with \(x \upa z_1 \le y\) because otherwise there would exists an infinite sequence \((u_1, u_2, \ldots)\) with \(x \prec u_n \le y\) for each \(n \in \N_+\), contradicting the fact that \(\{t \in S: t \preceq y\}\) is finite. If \(z_1 \prec y\) we can repeat the argument to obtain \(z_2 \in S\) with \(x \upa z_1 \upa z_2 \preceq y\). The proecess must terminate, again since \(\{t \in S: t \preceq y\}\) is finite.
Suppose again that \((S, \preceq)\) is a discrete, left finite partial order graph. For \(n \in \N\), let \(\upa^n\) denote the \(n\)-fold composition power of the covering relation \(\upa\) of \(\preceq\), where by convention, \(\upa^0\) is the equality relation \(=\). As subsets of \(S^2\), the partial order \(\preceq\) is the union of \(\upa^n\) over \(n \in \N\). That is, \(x \preceq y\) if and only if \(x \upa^n y\) for some \(n \in \N\). Similarly, the strict order \(\prec\) is the union of \(\upa^n\) over \(n \in \N_+\). That is, \(x \prec y\) if and only if \(x \upa^n y\) for some \(n \in \N_+\).
Suppose again that \((S, \preceq)\) is a discrete, left-finite partial order graph. Then the right \(\sigma\)-algebra associated with the graph is the reference \(\sigma\)-algebra \(\ms P(S)\), the collection of all subsets of \(S\).
Let \(\ms A = \sigma\{A_x: x \in S\}\) denote the right \(\sigma\)-algebra associated with \((S, \preceq)\) where \(A_x = \{ y \in S: x \preceq y\}\) is the right neigbor set at \(x \in S\). As usual, let \(\upa\) denote the covering relation. Then by , \(\{y \in S: x \prec y\} = \bigcup_{x \upa z} A_z\) for \(x \in S\). The union is finite, so \(\{y \in S: x \prec y\} \in \ms A\). Taking the set difference we have \(\{x\} \in \ms A\) for \(x \in S\).
Suppose again that \((S, \preceq)\) is a discrete, left-finite partial order graph. Then the right \(\sigma\)-algebra associated with \((S, \upa)\) is the same as the right\(\sigma\)-algebra associated with \((S, \prec)\).
Let \(A_x = \{y \in S: x \upa y\}\) denote the right neighbor set of \(x \in S\) for \((S, \upa)\), so that \(\ms A = \sigma\{A_x: x \in S\}\) is the right \(\sigma\)-algebra associated with \((S, \upa)\). Similarly, let \(B_x = \{y \in S: x \prec y\}\) denote the right neighbor set of \(x \in S\) for \((S, \prec)\), so that \(\ms B = \sigma\{B_x: x \in S\}\) is the right \(\sigma\)-algebra associated with \((S, \prec)\). We need to show that \(A_x \in \ms B\) for \(x \in S\) so that \(\ms A \subseteq \ms B\), amd that \(B_x \in \ms A\) for \(x \in S\) so that \(\ms B \subseteq \ms A\). First, \[A_x = B_x \setminus \left(\bigcup_{x \upa z} B_z\right) \in \ms B, \quad x \in S\] Next \[B_x = \bigcup_{n = 1}^\infty \{y \in S: x \upa^n y\}, \quad x \in S\] By a general result in Section 1, \(\{y \in S: x \upa^n y\} \in \ms A\) for \(x \in S\) amd \(n \in \N_+\). Hence \(B_x \in \ms A\) for \(x \in S\).
The common \(\sigma\)-algebra associated with \((S, \upa)\) and \((S, \prec)\) may be a strict subset of the reference \(\sigma\)-algebra \(\ms P(S)\). Examples are given in Section 5.1 on rooted trees and Section 8.1 on the subset partial order.
A discrete, left finite partial order graph \((S, \preceq)\) is uniform if for \(x, \, y \in S\) with \(x \prec y\), all pahts from \(x\) to \(y\) in the covering graph \((S, \upa)\) have the same length. Let \(d(x, y)\) denote the common length. In this case, \(\preceq\) is the disjoint untion of \(\upa^n\) over \(n \in \N\).
Suppose that \((S, \preceq)\) is a discrete, left finite partial order graph with minimum element \(e\). Then \((S, \preceq)\) is uniform if and only if for every \(x \in S\), all paths from \(e\) to \(x\) in the covering graph \((S, \uparrow)\) have have the same length.
If \((S, \preceq)\) is uniform, then trivially the condition in the theorem holds Conversely, suppose that the condition in the theorem holds. Suppose that \(x \preceq y\) and there are paths from \(x\) to \(y\) in \((S, \uparrow)\) with lengths \(m\) and \(n\). There must exist a path in \((S, \uparrow)\) from \(e\) to \(x\), since \((S, \preceq)\) is left finite; let \(k\) denote the length of this path. Then we have two paths from \(e\) to \(y\) in \((S, \uparrow)\) of lengths \(k + m\) and \(k + n\), so \(k + m = k + n\) and hence \(m = n\).
Suppose that \((S, \preceq)\) is a discrete, left finite, partial order graph. In this setting, the theory of Möbius inversion is important. Let \(\ms K\) denote the collection of kernels \(K\) on \((S, \preceq)\) with \(K(x, x) \ne 0\). So \(K \in \ms K\) means that \(K: S^2 \to \R\) and that \(K(x, x) \ne 0\) for \(x \in S\) while \(K(x, y) = 0\) if \(x \nprec y\). Note that the \(I \in \ms K\), where \(I\) is the adjacency kernel of \((S, =)\), so that \(I(x, y) = \bs 1(x = y)\) for \((x, y) \in S^2\). Similarly, \(L \in \ms K\) where \(L\) is the adjacency kernel of \((S, \preceq)\), so that \(L(x, y) = \bs 1(x \preceq y)\) for \((x, y) \in S^2\).
The space \((\ms K, \cdot)\) is a group with identity \(I\). The inverse of \(K \in \ms K\) is the function \(K^{-1} \in \ms K\) defined inductively as follows: \begin{align*} K^{-1}(x, x) &= \frac{1}{K(x, x)}, \quad x \in S \\ K^{-1}(x, y) &= -\frac{1}{K(y, y)} \sum_{t \in [x, y)} K^{-1}(x, t)K(t, y), \quad x \prec y \end{align*}
Suppose that \(J, \, K \in \ms K\). Since \((S, \preceq)\) is transitive, we know that \(J K\) is also a kernel for \((S, \preceq)\). In addition, \((J K)(x, x) = J(x, x) K(x, x) \ne 0\). Hence \(J K \in \ms K\). Trivially \(I\) is the identity for \((\ms K, \cdot)\). Let \(K \in \ms K\) and let \(J\) be defined by the inverse formula above, which makes sense by the left finiteness assumption. Then \[(J K)(x, x) = J(x, x) K(x, x) = \frac{K(x, x)}{K(x, x)} = 1, \quad x \in S\] Next, if \(x \prec y\) then \begin{align*} (J K)(x, y) &= \sum_{t \in [x, y]} J(x, t) K(t, y) = \sum_{t \in [x, y)} J(x, t) K(t, y) + J(x, y) K(y, y) \\ &= \sum_{t \in [x, y)} J(x, t) K(t, y) - \left[\frac{1}{K(y, y)} \sum_{t \in [x, y)} J(x, t) K(t, y) \right] K(y, y)\\ &= \sum_{t \in [x, y)} J(x, t) K(t, y) - \sum_{t \in [x, y)} J(x, t) K(t, y) = 0 \end{align*} So \(J\) is a left inverse of \(K\). Finally we show that it's also a right inverse. First note that \[(K J)^2 = (K J)(K J) = K (J K) J = K I J = K J \] so that \(K J\) is idempotent. Next, since \(K J \in \ms K\), \(K J\) itself has a left inverse, say \(N \in \ms K\). Then using the idempotent property, \[K J = I (K J) = [N (K J)] (K J) = N (K J)^2 = N (K J) = I\] and hence \(J\) is a right inverse of \(K\). Groups will be discussed in more detail in Section 2.1.
Möbius inversion was first developed in the context of number theory and then extended to discrete partial orders. In this context, the collection of kernels for \((S, \preceq)\) is known as the incidence algebra. The identity \(I\) is known as the Kronecker delta function (and traditionally denoted \(\delta\)). The adjacency kernel \(L\) of \((S, \preceq)\) is known as the Riemann function or the zeta function of the partial order graph. Like all kernels in \(\ms K\), it has an inverse:
The Möbius kernel \(M \in \ms K\) of \((S, \preceq)\) is the inverse of the adjacency kernel \(L\). It is defined inductively as follows: \begin{align*} M(x, x) &= 1, \quad x \in S \\ M(x, y) &= -\sum_{t \in [x, y)} M(x,t), \quad x \prec y \end{align*}
Proposition and definition lead to the following fundamental result, known as the Möbius inversion formula.
Suppose again that \(L\) and \(M\) are the adjacency kernel and Möbius kernel of \((S, \preceq)\). If \(f: S \to \R\) and \(g = f L\) then \(f = g M\).
The results follow immediately since \(M\) is the inverse of \(L\). Since \(g(y) = (f L)(y) = \sum_{x \preceq y} f(x)\) for \(y \in S\) then \(f(y) = \sum_{x \preceq y} g(x) M(x, y)\) for \(y \in S\). Note that the sums are finite.
When \(L\) operates on the right, we need an additional assumption, since the sum may have infinitely many terms:
Suppose again that \(L\) and \(M\) are the adjacency kernel and Möbius kernel of \((S, \preceq)\). If \(f \in \ms L_1\) and \(g = L f\) then \(f = M g\).
Again, the result follows since \(M\) is the inverse of \(L\). Since \(g(x) = (L f)(x) = \sum_{x \preceq y} f(y)\) for \(x \in S\) and the sum is absolutely convertent, it follows that \(f(x) = \sum_{x \preceq y} M(x, y) g(y)\) for \(x \in S\).
In this subsection we give a few definitions and results from the book by Leopold Nachbin, a classic that explores the interplay between topolgy and partial order. Suppose that \((S, \ms U)\) is a topological space, and as usual, we give \(S^2\) the product topology \(\ms U^2\). Recall that if \((S, \ms U)\) is separable and metrizable then \(\sigma(\ms U^2) = [\sigma(\ms U)]^2\), so the Borel \(\sigma\)-algebras are consistent with the results in the last subsection.
Suppose that \((S, \preceq)\) is a partial order graph.
The first result is a separation property.
\((S, \preceq)\) is closed if and only if for every \(x, \, y \in S\) with \(x \not \preceq y\), there exists an increasing neighborhood \(U\) of \(x\) and a decreasing neighborhood \(V\) of \(y\) that are disjoint.
In the case of a total order, this leads to the ordinary Hausdorff separation property:
If \((S, \preceq)\) is a closed and \(\preceq\) is a total order then \((S, \ms U)\) is Hausdorff.
Suppose that \(x, \, y \in S\) are distinct. Since \(\preceq\) is a total order, either \(x \not \preceq y\) or \(y \not \preceq x\). In either case, there exist disjoint neighborhoods \(U\) of \(x\) and \(V\) of \(y\).
Next is a condition for the graph to be locally convex.
If the collection \(\ms M\) of increasing open sets and decreasing open sets is a sub-base for \(\ms U\) then \((S, \preceq)\) is locally convex.
Recall that the term sub-base means that the collection \(\ms B\) of finite intersections of sets in \(\ms M\) is a base for \(\ms U\). In turn, this means that every set in \(\ms U\) is the union of a subcollection of \(\ms B\). The intersection of a finite collection of increasing open sets is still increasing and open, and similarly the intersection of a finite collection of decreasing open sets is still decreasing and open. On the other hand, the intersection of an increasing open set with a decreasing open set is a convex open set. Hence the hypothesis can be rephrased to say that the collection of convex open sets is a sub-base for \(\ms U\).
Recall that the interval \([0, \infty)\) is given the usual collection of Borel measurable subsets as the reference \(\sigma\)-algebra, and Lebesgue measure \(\lambda\) as the reference measure. With this structure, the measurable graph \(([0, \infty), \le) \) is the standard continuous graph.
Some properties of the standard continuous graph:
The properties also hold for the graph \(((0, \infty), \lt)\). The standard continuous graph is studied in detail in Chapter 3.
As with all countable sets, \(\N\) is given the \(\sigma\)-algebra \(\ms P(N)\) of all subsets, with counting measure \(\#\) as the reference measure. With this structure, \((\N, \le)\) is the standard discrete graph.
Some properties of the standard discrete graph:
The properties also hold for the graphs \((\N, \lt)\) and \((\N, =)\). Parts (b) and (c) hold for the covering graph \((\N, \upa)\). The standard discrete graph is studied in detail in Chapter 4.
Let \(\preceq\) denote the division relation on \(\N_+\) so that \(x \preceq y\) if and only if \(y / x \in \N_+\) for \(x, \, y \in \N_+\). That is, \(x\) divides \(y\). Then \((\N_+, \preceq)\) is a partial order graph.
Consider the division partial order graph \((\N_+, \preceq)\) and let \(A\) be a nonempty subset of \(\N_+\).
Properties of \((\N_+, \preceq)\).
The division partial order graph is studied in more detail in Chapter 6 on arithmetic semigroups.
A rooted, directed tree with root \(e \in S\) is a discrete, irreflexive graph \((S, \upa)\) with the property that there is a unique finite path from \(e\) to \(x\) for each \(x \in S\).
A rooted directed tree \((S, \upa)\) is the covering graph for a partial order graph \((S, \preceq)\), so that \(x \preceq y\) if and only if \(x = y\) or there is a (unique) finite path from \(x\) to \(y\) in \((S, \upa)\).
Properties of the rooted tree \((S, \preceq)\)
Rooted trees are studied in detail in Chapter 5.
Let \(S\) be a set and let \(\ms P(S)\) denote the power set of \(S\) (the collection of all subsets of \(S\)). Then \((\ms P(S), \subseteq)\) is a partial order graph.
For the subset partial order, the inf and sup operators correspond to intersection and union, respectively:
Let \(S\) be a set and consider again the partial order graph \((\ms P(S), \subseteq)\). If \(\ms A\) be a nonempty subset of \(\ms P(S)\) then
In particular, \( A \wedge B = A \cap B \) and \( A \vee B = A \cup B \), so \( (\ms P(S), \subseteq) \) is a lattice. In Chapter 8 we study a subgraph of \((\ms P(\N), \subseteq)\) where the base set consists of finite subsets of \(\N\).