Names of different kinds of sets based on uniqueness, ordering, and length

Question

I have some descriptions of some things like sets, based on some properties, and I'm trying to find out what they're called.

In the course of investigating the concepts behind Ruby arrays, I noticed that the things it next most resembles (mathematical vectors and sets) and it either have or do not have a set of three properties:

• Order matters
• Values are unique
• Length is fixed

So I made a little chart, to look at each combination:

  1. unordered nonunique nonfixed - ?
  2. unordered nonunique fixed    - ?
  3. unordered unique    nonfixed - set
  4. unordered unique    fixed    - ?
  5. ordered   nonunique nonfixed - array
  6. ordered   nonunique fixed    - vector
  7. ordered   unique    nonfixed - ?
  8. ordered   unique    fixed    - ?

  ordered - Order of the elements matters
  unique  - No elements are repeated
  fixed   - Length of the set does not change

I made a guess as to where "set", "array" and "vector" fit in, based on my understanding, but there's certainly the possibility I've named them wrong.

Can you fill in the missing names, so I can look them up and read about them?

PS - If it's not abundantly clear, I am no mathematician and really have no idea how to ask this question "properly". Correct my terminology, suggest tags, etc, and I'll happily update.

Thank you!

Answer 1

In my opinion, nothing ever 'changes' in mathematics, so the fixed/nonfixed distinction probably doesn't make a whole lot of sense. Unless you're trying to model things changing in time, of course, but the point is, the distinction is less fundamental than the other other two. Good question, by the way.

So without the fixed/nonfixed distinction, we have:

1. unordered unique - set
2. unordered non-unique - heap (or 'multiset' if you prefer)
3. ordered unique - chain (or 'linearly ordered set' if you prefer)
4. ordered non-unique - function whose source (or 'domain' if you prefer) is a chain.

Hope this is what you were after.

Edit. Here's a different idea. Under this point of view, 'ordered non-unique' is the most general, and the other concepts specialize this concept.

1. ordered non-unique - quasi-ordered set.
2. ordered unique - partially ordered set
3. unordered non-unique - equivalence relation
4. unordered unique - an ordered set whose order relation coincides with equality.

Answer 2

A related taxonomy is the Boom hierarchy, where datastructures are classified according to whether they are 'unital', associative, commutative and/or idempotent with respect to the 'joining together' operation.

In your terminology, a set has all four of these properties, vectors and arrays are unital and associative (but not commutative or idempotent). The fixed/non-fixed distinction doesn't come into the picture, but there's a lot of other structures like trees, or mobiles (trees where the order of the children doesn't matter) to look at.