(I didn't see any question like this on the CSTheory exchange -- apologies if it has already been answered.)

In a nested hierarchy, a higher level includes all levels below it.

The classic example of a "non-nested" hierarchy is military rank. A general is not a lieutenant, so military rank is a non-nested hierarchy.

But here's my objection -- doesn't a general have all the skills a lieutenant has, plus more skills? So in that sense, isn't every general a lieutenant? He may not be called "lieutenant", but in reality he is a lieutenant-plus.

Thus, I am wondering... can we really say that any hierarchy is non-nested?

  • 5
    $\begingroup$ This seems off-topic unless you add a connection to research-level theoretical computer science. $\endgroup$
    – Laakeri
    Dec 22 '20 at 18:56
  • 1
    $\begingroup$ I thought from the title it was going to ask about hierarchies like PH or the W-hierarchy, and whether there are analogous hierarchies that aren't linearly ordered... $\endgroup$ Dec 22 '20 at 21:51
  • $\begingroup$ Sorry guys - I’ll try to move this question to the StackExchange for the English language (or for Math). I’m a data wrangler rather than a true CS person. $\endgroup$
    – Steve_P
    Jan 6 at 19:27

I think this question is more about the semantics of the english language than about cs theory. Unless this has a connection to some problem. I think generally speaking, hierarchy of things just means there is a well ordered relation of these things. And nested just means that the things are nested within each other. The relation is defined based on nesting. So the military ranks are a hierarchy, but not a nested one because the groups aren't nested within each other.

  • $\begingroup$ Thanks @styopa ! Can I ask a quick follow-up… A, B, C, and D are sets. A includes B. B includes C and D. Thus, for nesting-level: A = 0. B = 1. C = 2. D = 2. Nesting-level is a total order on A, but it is not a well-order because not every subset of A has a least element. A is nested, but can we call it a hierarchy? $\endgroup$
    – Steve_P
    Jan 6 at 19:28
  • $\begingroup$ From the definition of hierarchy I've seen most, I wouldn't call it a hierarchy. However, I don't think this matters for any practical purposes. You could just make a small note before calling it a hierarchy. $\endgroup$
    – styopa
    Jan 8 at 0:08
  • $\begingroup$ Thank you so much! @styopa $\endgroup$
    – Steve_P
    Jan 9 at 6:50

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.