Proceedings of the Ninth Prague Topological Symposium Contributed papers from the symposium held in Prague, Czech Republic, August 19–25, 2001

SUB-REPRESENTATION OF POSETS

M. K. GORMLEY AND T. B. M. MCMASTER

Abstract. We define a property sub-representability and we give a complete characterisation of sub-representability of posets.

1. Introduction

Definition 1.1. Given an ordered set E and a topological space X, we say that E can be realised within X [see [1]] if there is an injection j from E into the class of (homeomorphism classes of) subspaces of X such that, for x, y in E, x ≤ y if and only if j(x) is homeomorphically embeddable into j(y).

The question of which spaces have the ‘converse’ of this property of realisability appears difficult in general, but we are able to handle the principal T_{0} case. What we shall now do therefore is to try to represent the family of subposets of a partially ordered set P, ordered by embeddability, within that family ordered by inclusion. However, we additionally want the representation to be such that each sub-poset is represented by an embeddability-wise equivalent poset. That is, we wish to sub-represent the poset.

Definition 1.2. Whenever P_{1} and P_{2} are posets, we shall say that P_{1} ↪ P_{2} if and only if P_{1} is isomorphic to a subset of P_{2}.

Definition 1.3. We shall say that P is sub-representable if and only if there exists a map g from ℙ(P) to ℙ(P) such that for all P_{1}, P_{2} ∈ ℙ(P):

(i) P_{1} ↪ P_{2} if and only if g(P_{1}) ⊆ g(P_{2}), and

(ii) P_{1} ↪ g(P_{1}) ↪ P_{1}.

Example 1.4. Figure 1 details a sub-representation of a four-point poset.

2000 Mathematics Subject Classification. 06A06, 54B99.

Key words and phrases. Poset, sub-representable, flower, pinboard.

The research of the first author was supported by a distinction award scholarship from the Department of Education for Northern Ireland.

M. K. Gormley and T. B. M. McMaster, Sub-representation of posets, Proceedings of the Ninth Prague Topological Symposium, (Prague, 2001), pp. 135–146, Topology Atlas, Toronto, 2002: arXiv:math.GN/0204128.

[figure: 3; 2; 3; 1; 2; 3; 4; 3; 2; 3; 4; 1; 2; 3; 4; Sub-posets ordered; by embeddability.; Representative sub-posets; ordered by inclusion.]

Figure 1

Theorem 1.5. Suppose that P_{1} ⊆ P. If P_{1} is not sub-representable, then P is not sub-representable.

Proof. Suppose that P was sub-representable and g is as in Definition 1.3. Now g(P_{1}) embeds into P_{1} by a map h. Then it is clear that if g^{∗} = g_{|P_{1}}, then h ∘ g^{∗} will sub-represent P_{1}. □

Definition 1.6. The posets whose Hasse diagrams are given in Figure 2 shall be known as a vee, a wedge, and a diamond, respectively.

[figure]

Figure 2

Example 1.7.

• All two-point posets are (trivially) sub-representable.

• All three-point posets are (trivially) sub-representable.

• Not all four-point posets are sub-representable: see Example 1.8.

Example 1.8. The poset P in Figure 3 is not sub-representable for the following reasons. Suppose that P were sub-representable. Since P contains a wedge, the wedge must be sub-represented by either {1, 3, 4} or {2, 3, 4}. A two-point chain must then be mapped to {1, 3}, {3, 4} or {2, 3}; not to {1, 2}. However, in all three cases we see that there is no other point incomparable with the chain, and hence the disjoint union {1, 2, 4} of a two-point chain and a single point cannot be sub-represented: a contradiction.

[figure: 1; 2; 3; 4]

Figure 3

Figure 4 gives all four-point posets that cannot be sub-represented, as may be verified by simple arguments like that of above.

[figure]

Figure 4

Figure 5 gives all four-point posets (likewise identified) that can be subrepresented.

[figure]

Figure 5

Example 1.8 shows that we do not have universal sub-representability, even among finite posets. We seek to identify which posets are sub-represent-able.

Note 1.9. Let x ∈ P. We shall use the following notation (note the strictness of the inequalities):

• U(x) = {y ∈ P : y > x}
• D(x) = {y ∈ P : y < x}.

Definition 1.10. A linear ordering A is called a • well-ordering if every non-empty subset B of A has a least element,

• well-ordering* if every non-empty subset B of A has a greatest element.

Definition 1.11. We shall call P a

• flower if and only if there exists x ∈ P such that D(x) is a wellordered* chain, U(x) is an antichain (with |U(x)| > 1) and D(x) ∪ U(x) ∪ {x} = P

• co-flower if and only if there exists x ∈ P such that U(x) is a well-ordered chain, D(x) is an antichain (with |D(x)| > 1) and D(x) ∪ U(x) ∪ {x} = P.

Note 1.12. Note that the dual of a flower is a co-flower and vice versa. Also every flower contains a vee and every co-flower contains a wedge.

Theorem 1.13. Suppose that P contains both a vee and a wedge. Then P is not sub-representable.

Proof. Suppose that P is sub-representable but contains both a vee and a wedge. Suppose that a vee, {1, 2, 3 : 1 < 2, 1 < 3}, is represented by {a, b, c : b < a, b < c}. Then we must have the two-point antichain embedded as {a, c}. The wedge {4, 5, 6 : 4 < 6, 5 < 6} would then partially embed as follows: {4, 5} → {a, c}, and hence we would have a diamond {a, b, c, d : b < a, b < c, a < d, c < d} contained in P. By Example 1.8, any space containing a diamond is not sub-representable: a contradiction. □

Theorem 1.14. Suppose that P contains one of the posets in Figure 6. Then P is not sub-representable.

[figure: x; y; .; .; .; .; .; No maximum; element.; A; .; .; .; .; .; .; B; No minimum; element.]

Figure 6

Proof. Suppose that P contains poset A but that P is sub-representable. Notice that A contains a copy of ℕ. Then a two-point antichain must be represented by {x, y} and hence a singleton must be represented by either {x} or {y}. In either case we have that the representative of ℕ would have a maximal element: a contradiction, and hence P is not sub-representable. A similar contradiction arises if P contains B. □

Theorem 1.15. If P is sub-representable then P is a flower or a co-flower or a disjoint union of chains.

Proof. Suppose that P is neither a flower nor a co-flower nor a disjoint union of chains. Since it is not a disjoint union of chains it contains a vee or a wedge. By Theorem 1.13 if it contains both then it is not sub-representable. Suppose then that P contains a vee but not a wedge. Since it is not a flower it must contain one of the following:

[figure: A; B; .; .; .; .; .; C]

Figure 7

However, A and B are not sub-representable by Example 1.8 and C is not sub-representable by Theorem 1.14. Hence P is not sub-representable either. Dually, suppose that P contains a wedge but not a vee. Since it is not a co-flower it must contain one of the following:

[figure: D; E; .; .; .; .; .; .; .; F]

Figure 8

However, D and E are not sub-representable by Example 1.8 and F is not sub-representable by Theorem 1.14. Hence neither is P. □

Example 1.16. Let P = ⋃_{k∈ℕ}{P_{k}} where P_{k} is the k-point chain. Then P is not sub-representable.

Proof. Suppose that this poset is sub-representable. Then there exist values of k and m such that P_{k} is represented by being mapped into P_{m}(m ≥ k). We then have that P_{m+1} must map into more than one P_{k}, since it must contain the image of P_{k} whereas P_{m} contains only m points: this yields the desired contradiction. □

Note 1.17. Let P be a finite poset. Recall that the height of P, denoted by ht(P), is the largest cardinality of a chain in P, and that the width of P, denoted by wd(P), is the largest cardinality of an antichain in P.

Theorem 1.18. Suppose that P is finite. If P is either a flower or a coflower or a disjoint union of chains then P is sub-representable.

Proof. Suppose that P is a flower with ht(P) = n and wd(P) = k. The family of subsets of P consists of flowers of height m and width r for all 1 < m ≤ n, 1 < r ≤ k, together with chains of size ≤ n and antichains of size ≤ k. Label the points of P in the maximal antichain as x_{1}, x_{2}, ..., x_{k}. There exists a point x such that P = D(x) ∪ U(x) ∪ {x}. Label x as x_{k+1} and the points of D(x) as x_{k+2}, x_{k+3}, ..., x_{k+n−1} where x_{k+2} > x_{k+3} > ... > x_{k+n−1} as in Figure 9. Our isomorphism is defined as follows: map a singleton to x_{1}; map each chain of size m > 1 to {x_{1}, x_{k+1}, ..., x_{k+m−1}}; map each antichain of size r > 1 to {x_{1}, ..., x_{r}}; map each flower of height m and width r to {x_{j} : k < j ≤ k + m − 1} ∪ {x_{j} : 1 ≤ j ≤ r}. It is clear that P has been sub-represented.

[figure: x_{1}; x_{2}; x_{k}; .; .; .; .; .; .; .; .; x_{k+n−1}; x_{k+2}; x_{k+1}; .; .; .; .; .; .; .]

Figure 9

The case where P is a co-flower is precisely dual to the preceding discussion. Now suppose that P is a disjoint union of chains. Arrange the chains in descending order of cardinality. That is, denote P as ⋃{P_{k} : k ≤ n} where ht(P_{k}) ≥ ht(P_{k+1}). Label the points of each P_{k} as {x_{m}^{k} : 1 ≤ m ≤ ht(P_{k})} as in Figure 10.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; P_{k}; x_{1}^{k}; x_{2}^{k}; x_{3}^{k}; x_{m−1}^{k}; x_{m}^{k}; .; .; .]

Figure 10 Let S be a subset of P, and suppose that S intersects each of the posets {P_{k_{1}}, P_{k_{2}}, ..., P_{k_{t}}} where |S ∩ P_{k_{q}}| ≥ |S ∩ P_{k_{q+1}}| for all 1 ≤ q ≤ t − 1. For each r ≤ t map S ∩ P_{k_{r}} to {x_{m}^{r} : m ≤ |S ∩ P_{k_{r}}|}. The poset P has now been sub-represented. □

Corollary 1.19. Let P be a finite poset. Then P is sub-representable if and only if P is either a flower or a co-flower or a disjoint union of chains.

Example 1.20. Consider ℤ = {..., −3, −2, −1, 0, 1, 2, 3, ...}, the set of integers with their usual ordering. Then ℤ is not sub-representable.

Proof. Suppose that ℤ is sub-representable. Let the image of the equivalence class of the natural numbers, i.e. θ([ℕ]), be the set {0′, 1′, 2′, 3′, ...}. Let θ([−ℕ]) be the set {(−0)′, (−1)′, (−2)′, (−3)′, ...}. Since a singleton must be mapped into both θ([ℕ]) and θ([−ℕ]), we know that |θ([ℕ]) ∩ θ([−ℕ])| > 0. Suppose that p′ is the least point of θ([ℕ])∩θ([−ℕ]), that is, p′ = (−q)′, which implies that |θ([ℕ]) ∩ θ([−ℕ])| ≤ q + 1. Then θ([{0, 1, 2, 3..., q, q + 1}]) must be a subset of θ([ℕ]) and also a subset of θ([−ℕ]). This is a contradiction, since |θ([ℕ]) ∩ θ([−ℕ])| ≤ q + 1. □

Corollary 1.21. By Corollary 1.5 we then have that ℚ, ℝ and ℝ \ ℚ (as ordered sets) cannot be sub-represented.

Corollary 1.22. If P contains a copy of ℕ and a copy of −ℕ then it cannot be sub-represented.

Note 1.23. If P is a chain which is not well-ordered then it contains a copy of −ℕ, and if P is a chain which is not well-ordered* then it contains a copy of ℕ.

Corollary 1.24. If P is a chain which is not well-ordered and not wellordered* then it cannot be sub-represented.

Theorem 1.25. Every well-ordered set can be sub-represented.

Proof. Let P be a well-ordered chain of order-type α. It suffices to show that α itself is sub-representable. Let S ⊆ α and suppose that S is orderisomorphic to β < α. We map [S] to β where β is a proper initial segment of α. On the other hand, if S is order-isomorphic to α, map [S] to α itself. □

Theorem 1.26. Every well-ordered* set can be sub-represented.

Proof. Let P be a well-ordered* chain. Let P^{∗} denote the dual of P. Then P^{∗} is, without loss of generality, an ordinal α. If S ⊆ P then S^{∗} is orderisomorphic to some β ≤ α, and so map [S] to the final segment of α^{∗} of order-type β^{∗}. □

Theorem 1.27. Let P be a flower or a co-flower. Then P is sub-represent-able.

Proof. Suppose that P is a flower. Then P = D(x) ∪ U(x) ∪ {x}. Suppose that |U(x)| = δ. Label the points of U(x) as {x_{β} : β < δ}. By definition, D(x) ∪ {x} ∪ {x_{0}} is a well-ordered* chain. Label the points of U(x) \ {x_{0}} as {x′_{β} : β < δ′}. Let S ⊆ P. If S is a copy of α^{∗} for some ordinal α, map S to the final segment α^{∗} of D(x) ∪ {x} ∪ {x_{0}}. Otherwise S contains a copy of α^{∗} for some ordinal α (such that it does not contain a copy of γ^{∗} for some γ > α) together with an antichain of cardinality ζ. Map S to {x′_{β} : β < ζ} together with the final segment α^{∗} of D(x) ∪ {x} ∪ {x_{0}}. We have now sub-represented P. The case where P is a co-flower is similar. □

Theorem 1.28. Let P be the disjoint union of finitely many well-ordered sets. Then P is sub-representable.

Proof. Suppose that P = ⋃_{k≤n} ⋃_{s≤m_{k}}{^{s}ω^{k}} where ^{s}ω^{k} is a copy of an ordinal ω^{k}. Then (up to order-isomorphism) P is a copy of n^{∗} = ∑_{k} m_{k} many ordinals. So let us consider P as ⋃_{n≤n^{∗}}{ω^{n}} where ω^{n} ≥ ω^{n+1} for all n ≤ n^{∗}. Let Y ⊆ P meet each of ω^{n_{1}}, ω^{n_{2}}, ..., ω^{n_{t}} where |Y ∩ ω^{n_{p}}| ≥ |Y ∩ ω^{n_{p+1}}| for all 1 ≤ p ≤ t − 1. Now Y ∩ ω^{n_{p}} is a copy of an ordinal α_{p}. So map Y ∩ ω^{n_{p}} to α_{p} ∈ ω^{p} and hence P has been sub-represented. □

Corollary 1.29. A similar proof gives the result that a disjoint union of finitely many well-ordered* sets is sub-representable.

Let us examine further the question of which disjoint unions of ordinals can be sub-represented. Let P be a disjoint union of ordinals. If P contains a copy of the disjoint union of the family of ordinals {1, 2, 3, 4, ...} then by Example 1.16 and Corollary 1.5, P cannot be sub-represented. Hence P must contain copies of only finitely many distinct ordinals and only finitely many copies of each relevant infinite ordinal. If we have only finitely many copies of each ordinal then by Theorem 1.28, P is sub-representable. So all that remains to consider is the case where there are infinitely many copies of one or more finite ordinals. It will be seen — although the demonstration requires considerably more effort than earlier proofs in this paper — that this case also is sub-representable.

2. Sub-representation of pinboards

Definition 2.1. A pinboard is a finite set of ordered pairs

{(h_{i}, f_{i}) : 1 ≤ i ≤ k}

in which, for each value of i, h_{i} (the height) is an ordinal, f_{i} (the frequency) is a cardinal, and not both h_{i}, f_{i} can be infinite. We recall that a cardinal is merely an initial ordinal (or equivalently, the least one of a given cardinality).

Definition 2.2. A simple pinboard is a pinboard of the form

{(β, n), (m, γ)}

where β and γ are infinite cardinals, and m and n are finite cardinals.

Definition 2.3. The poset of a pinboard {(h_{i}, f_{i}) : 1 ≤ i ≤ k} is the disjoint union of f_{i}-many copies of h_{i} for 1 ≤ i ≤ k. For example, if the pinboard was {(ω_{2}, 5), (ω_{1}, 2), (6, ω), (3, 1)}, then the poset is as suggested by Figure 11.

ω_{2} ω_{1} 6 30 1 2 3 4 5 6 7 8  ω_{0} . . . . . . .

Figure 11

Our aim is to sub-represent the poset of an arbitrary pinboard. However, it is easy to see that the poset of any pinboard is a subset of the poset of a simple pinboard. Hence, by Theorem 1.5, if every simple pinboard’s poset is sub-representable, then every pinboard’s poset is sub-representable.

Let P be the poset of a simple pinboard {(β, n), (m, γ)}. We shall represent P by the set

X = {(β, i, α) : α < β, i < n} ∪ {(m, α, j) : j < m, α < γ},

that is, an isomorphic copy of β over each (β, i) and an isomorphic copy of m over each (m, α). We note that the ordinal ⊕_{m}γ has the same cardinality as the set

F = {(β, i) : i < n} ∪ {(m, α) : α < γ}

which underlies X. We can therefore choose an injection λ : ⊕_{m}γ → F such that the first n terms of its domain map onto {(β, i) : i < n}. We now have labelled the columns of X in a ⊕_{m}γ-sequence such that the first n columns are those of the infinite ordinals.

Let Y be a subset of the simple pinboard above. Then Y consists of at most n ordinals that exceed m and at most γ-many copies of each of the ordinals m, m−1, ..., 2, 1. We can assume that for each term (h, f) in Y there does not exist a term (h′, f′) in Y, where f′ is infinite, such that h′ < h and f′ < f: for, if there was such a term (h′, f′), the elimination of (h′, f′) would not affect the embeddability class of Y. Therefore we can consider Y to be of the following form:

Y = {(β_{1}, n_{1}), (β_{2}, n_{2}), ..., (β_{k}, n_{k}), (m, γ_{m}), (m − 1, γ_{m−1}), ..., (1, γ_{1})},

where β_{1} > β_{2} > ... > m.

We note that the ordinal sum

n_{1} ⊕ n_{2} ⊕ ⋯ ⊕ n_{k} ⊕ γ_{m} ⊕ ⋯ ⊕ γ_{1} ≤ n ⊕ (⊕_{m}γ) = ⊕_{m}γ

and hence we can find a ‘remainder’ ordinal γ_{0} such that

n_{1} ⊕ n_{2} ⊕ ⋯ ⊕ n_{k} ⊕ γ_{m} ⊕ ⋯ ⊕ γ_{1} ⊕ γ_{0} = ⊕_{m}γ.

We now apply our injection λ and hence associate a copy of β_{1} with the first n_{1}-many columns of X, a copy of β_{2} with the next n_{2}-many columns and so on. Our subset θ(Y) of X associated with Y is now formed by taking the desired initial segments of the associated columns, and it is clear that θ(Y) is an isomorphic copy of Y.

Theorem 2.4. Let Y, Y′ be subsets of X. Then Y ↪ Y′ if and only if θ(Y) ⊆ θ(Y′).

Proof. Suppose that Y ↪ Y′. Let us denote Y′ as

{β′_{1}, n′_{1}), (β′_{2}, n′_{2}), …, (β′_{l}, n′_{l}), (m, γ′_{m}), (m − 1, γ′_{m−1}), …, (1, γ′_{1})},

where β′_{1} > β′_{2} > ⋯ > β′_{l} > m. Let θ(Y′) be generated as above. We proceed to show that θ(Y) ⊆ θ(Y′). Consider the ordinals (without repetitions) comprising Y and Y′, and denote this set arranged in decreasing order as

{ζ_{1}, ζ_{2}, …, ζ_{q}, m, m − 1, …, 1}.

It is clear that a single column of Y must embed into a single column of Y′ and hence the ordinal ζ_{1} is in fact β′_{1}. We can now assume that Y and Y′ are of the following form where some of the frequencies may be zero:

Y = {ζ_{1}, r_{1}), (ζ_{2}, r_{2}), …, (ζ_{q}, r_{q}), (m, γ_{m}), (m − 1, γ_{m−1}), …, (1, γ_{1})},

Y′ = {ζ_{1}, r′_{1}), (ζ_{2}, r′_{2}), …, (ζ_{q}, r′_{q}), (m, γ′_{m}), (m − 1, γ′_{m−1}), …, (1, γ′_{1})}.

The proof now proceeds as follows: Stage 1: Any column of Y of height ζ_{1} must embed into a column of Y′ of that height, and so it follows that r_{1} ≤ r′_{1}. That is to say, the columns of θ(Y) of height ζ_{1} are contained in θ(Y′). Stage 2: Any column of height ζ_{1} or ζ_{2} must embed into a column of Y′ of height ζ_{1} or ζ_{2}, and hence r_{1} + r_{2} ≤ r′_{1} + r′_{2}. It follows that the columns of Y of height ζ_{2} are contained in θ(Y′). The obvious iteration process will now yield, in a finite number of stages, θ(Y) ⊆ θ(Y′). □

Example 2.5. Suppose that P is the poset of the simple pinboard {(ℵ_{2}, 12), (7, ℵ_{3})} and we have a labelling map λ : ⊕_{7}ℵ_{3} → F where F = {(ℵ_{2}, i) : i < 12} ∪ {(7, α) : α < ℵ_{3}}, such that {λ(0), .., λ(11)} are the base points of the infinite columns. Let Y be a subset of P whose columns have the following ordinalities: {ω_{1} ⊕ 1, ω_{1}, ω_{0} ⊕ 5, ω_{0} ⊕ 5, ω_{0}, 30, 30, 20} together with ℵ_{0} copies of 5 and ℵ_{0} copies of 3. As before, we can disregard the ℵ_{0} copies of 3 since these do not affect the embeddability class of Y. The remaining frequencies (in decreasing order of corresponding height) are as follows: {1, 1, 2, 1, 2, 1, ℵ_{0}}. We then have that θ(Y) consists of the following initial segments:

θ(Y) = \begin{cases}ω_{1} ⊕ 1 & of column λ(0), \\ ω_{1} & of column λ(1), \\ ω_{0} ⊕ 5 & of columns λ(2) and λ(3), \\ ω_{0} & of column λ(4), \\ 30 & of columns λ(5) and λ(6), \\ 20 & of column λ(7), \\ 5 & of columns λ(8 ⊕ t) for all t < ℵ_{0}, \\ 0 & otherwise. \end{cases}

Let Y′ be another subset of P whose columns have the following ordinalities: {ω_{2}, ω_{2}, ω_{1} ⊕ 10, ω_{1}, ω_{0}, 60, 40, 30, 20} together with ℵ_{1} copies of 6. We note that Y ↪ Y′. The frequencies (in decreasing order of corresponding height) are as follows: {2, 1, 1, 1, 1, 1, 1, 1, ℵ_{1}}. We then have that θ(Y′) consists of the following initial segments:

θ(Y′) = \begin{cases}ω_{2} & of columns λ(0) and λ(1), \\ ω_{1} ⊕ 10 & of column λ(2), \\ ω_{1} & of column λ(3), \\ ω_{0} & of column λ(4), \\ 60 & of column λ(5), \\ 40 & of column λ(6), \\ 30 & of column λ(7), \\ 20 & of column λ(8), \\ 6 & of columns λ(9 ⊕ t) for all t < ℵ_{1}, \\ 0 & otherwise, \end{cases}

and we observe that θ(Y) ⊆ θ(Y′).

Definition 2.6. A co-pinboard is a finite set of ordered pairs {(h_{i}, f_{i}) : 1 ≤ i ≤ k} such that {(h_{i}^{∗}, f_{i}) : 1 ≤ i ≤ k} is a pinboard.

Result 2.7. Let P be a poset. Then P is sub-representable if and only if P is either:

(i) a flower, or (ii) a co-flower, or (iii) the poset of a pinboard, or (iv) the poset of a co-pinboard.

Note 2.8. We could similarly define sub-representation of an arbitrary topological space as follows: Let (X, T ) be a topological space. We shall say that (X, T ) is sub-representable if and only if there exists a map g from ℙ(X) to ℙ(X) such that for all Y, Z ∈ ℙ(X):

(i) (Y, T_{|Y}) ↪ (Z, T_{|Z}) if and only if g(Y) ⊆ g(Z), and (ii) (Y, T_{|Y}) ↪ (g(Y), T_{|g(Y)}) ↪ (Y, T_{|Y}).

It then follows that we have already characterised all principal T_{0} spaces which are sub-representable. The question of which other topological spaces are sub-representable remains open.

References

[1] A. E. McCluskey and T. B. M. McMaster, Realizing quasiordered sets by subspaces of “continuum-like” spaces, Order 15 (1998/99), no. 2, 143–149. MR 2001i:54042

Department of Pure Mathematics, Queen’s University, Belfast, University Road, Belfast, BT7 1NN, United Kingdom

E-mail address: m.k.gormley@qub.ac.uk
E-mail address: t.b.m.mcmaster@qub.ac.uk