We are studying a partial order P with the following specific properties:

  1. P is countably infinite.
  2. There are infinitely many isolated elements (not comparable to any other element).
  3. Every chain is finite.
  4. There is a grading g: P -> N_0 (natural numbers), such that
    • x < y implies g(x) < g(y)
    • if y covers x (y > x, and nothing between), then g(y) = g(x) + 1.
  5. If x <= y, then the interval [x,y] is isomorphic to the powerset of g(y) - g(x) elements (and the subset-relation).

We can't find such partial orders in the literature, and so we wonder whether something is known here? Especially Property 5 seems relevant.

P comes from a logical-combinatorial situation. The motivation for this question is, whether the above properties can relate our investigations to the theory of partial orders (or whether there seem to be no deeper relations)?

  • $\begingroup$ I was able to answer the first part of your question but - unfortunately - I have no idea what the last part is supposed to mean. Could you try to clarify what you mean by an 'investigation to the theory of partial orders'? $\endgroup$ – Stefan Mesken Feb 26 '17 at 19:12
  • $\begingroup$ Any countably infinite set with the discrete ordering would work. $\endgroup$ – Max Feb 26 '17 at 19:19
  • $\begingroup$ By Answer 1, and also by the comment of Max we obtain models of the five properties. Which is interesting. My question in general is about a theory for such posets, that is, what is known for such posets. My remark on "investigations" means, whether there is an interesting theory possible at the general poset-level (given these five properties), or whether the structure is still too general to have interesting theorems. Our investigations currently use much more specific information about these objects (not just these order-theoretic properties). $\endgroup$ – Oliver Kullmann Feb 26 '17 at 23:19
  • $\begingroup$ I take it now that at the level of general order theory there is apparently not so much to say about posets fulfilling the five conditions. That's an answer. Furthermore it seems useful to decompose P into its "components" in the sense of representing P as a disjoint union of partial orders, which themselves can not be further decomposed. Then the structure from Answer 1 decomposes into the points (1,{k}) plus the partial orders given by the (n,x) with fixed n >= 2. In our case the components are all finite, and these finite partial order likely should be studied on their own. $\endgroup$ – Oliver Kullmann Feb 27 '17 at 8:55

Let $(P; \preceq)$ be the poset $\bigcup_{n \in \mathbb N} \{n\} \times X_n$, where $X_n = \{ x \subseteq \mathbb N \mid x \neq \emptyset \wedge \operatorname{card}(x) \le n \}$, such that for $(m,x), (n,y) \in P$ $$ (m,x) \preceq (n,y) : \iff m = n \wedge x \subseteq y. $$ Furthermore, let $$ g \colon P \to \mathbb N_{0}, (n,x) \mapsto \operatorname{card}(x). $$

  1. $P$ is the union of countably many countable sets and hence countable. (In fact, $P$ is easily seen to be countable without any choice.)
  2. For every $k \in \mathbb N$ the set $(1,\{k\})$ is an isolated point of $P$.
  3. Clearly every chain in $P$ is finite.
  4. holds trivially.
  5. Identify, for any $(n,x) \preceq (n,y)$ the interval $[(n,x), (n,y)]_{\preceq}$ with $[x,y]_{\subseteq}$ and note that the latter is canonically isomorphic to $(\mathcal{P}(\operatorname{card}(y \setminus x)), \subseteq)$.
  • $\begingroup$ You must have meant $card(x) \leq n$ $\endgroup$ – Max Feb 26 '17 at 19:17
  • $\begingroup$ @Max Yep, that's a typo. Thanks. $\endgroup$ – Stefan Mesken Feb 26 '17 at 19:19
  • $\begingroup$ It seems Point 2 is not true, since for all n >= 1 the pair (n,{}) is a smallest element of the subset of all (n,x) of P. So there aren't any isolated points in P. If X_n is redefined to exclude the empty set, then the pairs (1,{k}) for all k >= 1 are isolated points. But e.g. (2,{k}) < (2,{k,k+1}), and in general no (n,x) for n >= 2 is isolated. With these corrections we obtain a model of the given five properties. @Stefan $\endgroup$ – Oliver Kullmann Feb 26 '17 at 23:13
  • $\begingroup$ @Oliver I follow your first correction and indeed, that was just a careless mistake. (Note however, that in my previous definition $(n, \emptyset)$ was an isolated point for all $n \in \mathbb N$ - so the poset still worked, but my argument didn't. However, I'm not sure what the last part is supposed to mean? $\endgroup$ – Stefan Mesken Feb 27 '17 at 7:40
  • $\begingroup$ Still, e.g. (2,{1}) is not an isolated point, since (2,{1}) < (2,{1,2}), and thus (2,{1}) is comparable to some other element. All (n,{k}) are minimal elements of P, but only for n=1 there is nothing above them. Just a minor point. $\endgroup$ – Oliver Kullmann Feb 27 '17 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.