Elementary concepts in objects
Mathematical structures with regard to the order and uniqueness properties.
Order (ordering) property
If a math structure is said to be ordered, then its elements appear in some defined order; it can also be said that the place an element obtains when it was first inserted remains throughout the life of a particular structure. The property of order is enforced on the structure and elements within.
If a structure doesn't have an ordering, i.e. if it lacks specifications about the treatment of ordering wrt its elements, then such a structure is free to do whatever it wants in that respect, even to enforce the certain way of ordering its elements. This is of no concern in math, but it is big issue in CS, so an implementation of unordered structures (such as sets) will almost always use some specific "internal" order, so that the operations that work on that structure (crucially, the search for a specific element) are performed more efficiently. However, this ordering is internal, it is an implementation detail, it cannot be exposed to the outside world. The API must not let this feature leak outside the module for that would break the specification; e.g. sets are by specification unordered, but as previously mentioned, that fortunatelly doesn't enforce disorder, so sets are expected to be unoredered even if they are always presented in a very specific order. However, the lack of ordering, is not about the visual presentation of set's elements, but it is nevertheless reflected in the supported operations. For example, it is common across PLs that sets support the assition of new elements
Uniqueness (multiplicity) property
The most elementary object in mathematics is perhaps a set but an even more unrestricted collection is called a bag (bunch).
A bag is just a bunch of objects without further constraints. It is unordered like a set, but unlike a set it doesn't restrict the multiplicity of objects.That is, a bag allows for multiple instances of the same object, while a set has a somewhat "magic" property that makes multiple instances of an object "collapse" into one.
However, there are many unknowns around this property. Almost every author will state that sets consists of unique elements by giving an example such as:
{a, b, c} = {a, b, a, c}
Which seems to allow for a set to contain multiple object until an operation on a set is performed. For example, querying two sets for equality seems to collapse elements in each. Querying a finite set's cardinality will also collapse elements producing a count that corresponds to the number of unique objects it contains. My issue with this is, if a set allows multiplicity (until an operation is performed), is it also allowed to make duplicates of its elements if needed?
In any case, a common opinion is that sets are the most elementary mathematical objects since they have no additional structure, representing just a collection of unique (collapsed) mathematical objects as elements. It seems that the property of uniqueness of elements works well since bags, despite being different from sets in exactly that one property, are relatively unknown and unused in math.
Even though a set seems to recognize uniqueness restriction and that only when forced by an operation, it remains an issue how are two sets exactly compared? Taking an arbitrary element from the first set and comparing it against every element of the second set requires the notion of equality after all. That is, the elements have to support equality comparisions. Even if two simple elements can be compared by shape only, more complicated ones will not allow for such comparisons. And than a question really becomes: how to detrmine the equality between two objects? And that question doesn't have a simple answer; it has spawned a multitude of possible approaches to equality based on the exact circumstances and granularity of compared parts and properties of objects.
However, if elements of a set have a solution for equality comparison, such a set is usually called a setoid. It has a different name since a set is a collection devoid of any addition feature or structure. So a setoid can already be considered a mathematical structure i.e. a set endowed with an additional feature, viz. equivalence relation.
More collections
Both bags and sets are unordered collections differing regarding their multiplicity i.e. uniqueness restriction. What are then their counterparts? A collection that is ordered and allows multiplicity of elements is a list or sequence. However, it seems there's no use for an ordered collection with uniqueness constraint since no name for such collection comes to mind.
Collections:
bag : unordered, multiplicity
set : unordered, uniqueness
list : ordered, multiplicity
unknown: ordered, uniqueness
Last updated