[sadie]

I'm looking for a word to describe the relationship between items. It's vaguely tree-like, in that one element is a member of another, but it's not exclusive in the way that a tree is. One element can has many members, but also one element can be a member of any other.

It's not a lattice because there's no fixed regularity in it. And it's not just a loose network because it does keep some items 'above' others - there shouldn't be any loops in it.

As an example: Egypt is a member of Africa, and it's also a member of the Middle East. Both are members of the World. Each element is on its own tier, so you can't have loops, but it's not a strict tree.

Any ideas? Programming language is irrelevant, human languages less so but if it's a good word i'll consider it.

[Mactoid]

In graph theory, an acyclic graph is called a forest. A tree is a special case of forest that is connected (or think of it the other way, a forest is a graph that contains multiple trees).

[tie]

Partial order is the name of the relationship. Lattice is the correct name for the induced graph (despite the possible lack of regular structure).

[sadie]

tie chimed in with:
<STRONG>Lattice is the correct name for the induced graph (despite the possible lack of regular structure).</STRONG>

Are you sure? I thought that a lattice was...

dictionary.com
<STRONG>an arrangement of points or particles or objects in a regular periodic pattern in 2 or 3 dimensions</STRONG>

ne? Buf if you are sure I'll gladly use it.

[sadie]

Hang on:

Merriam-Webster, www.m-w.com
<STRONG>Lattice: a mathematical set that has some elements ordered and that is such that for any two elements there exists a greatest element in the subset of all elements less than or equal to both and a least element in the subset of all elements greater than or equal to both.</STRONG>

If you apply that to the tree-like structure I'm thinking of, then i'm not sure it does fit. For example, using the words 'child/parent' for simplicity (!):

• Imagine two elements A and B that are siblings (ie, neither of them is an ancestor or descendent of the other).
• Element A has two children, C and D. Element B has two children, E and F. You may need to start drawing this.
• Element G is a child of both C and E. Element H is a child of both D and F. Now imagine that no other nodes exist.
• Therefore, elements G and H are both descended from both A and B. But they are siblings - neither of them is descended from the other.
• In more math-like terms, G and H are elements of the subset of A and B. But neither G nor H can be defined as being 'greater than' the other - there is no specified ordering on them.
• Hence, there is no <STRONG>"greatest element in the subset of all elements less than or equal to both"</STRONG> A and B.

So, while it could be a partially ordered set, it can't be a lattice. Comprende? Or have i misunderstood?

[ 12-13-2001: Message edited by: sadie ]

[tie]

Originally posted by sadie:
<STRONG>Merriam-Webster, www.m-w.com
Lattice: a mathematical set that has some elements ordered and that is such that for any two elements there exists a greatest element in the subset of all elements less than or equal to both and a least element in the subset of all elements greater than or equal to both.</STRONG>

The dictionary.com definition is completely wrong. I think "complete lattice" is the correct term for what MW describes. Mathematicians still use lattice to describe the graph of any partially ordered set; see, e.g., http://mathworld.wolfram.com/Lattice.html .

[parallax]

Well, we all know better than to look at m-w or dict.com for exact math definitions!
http://mathworld.wolfram.com/

[sadie]

Well, sorry. If i knew all this in advance, I wouldn't have to ask!