Collections

Classifying collections according to the properties:

  • ordering of elements:

    • ordered collection respect and preserves the order

    • unordered collection has no notion of order

  • uniqueness (multiplicity) of elements

    • elements may be repeated

    • elemets must be unique

    • elements that are equal collapse into one

    • an element is considered singular even if it has multiple copies (ignored)

The notion of order is seemingly straigtforward - as a constrained on a collection, it regulates the order in which the elements appear. Ordered collections (sequence, list, array, tree) recognize and enforce the ordering of their elements, which comes with computational benefits such as indexed access to elements, efficient search, better caching. An ordered collection can use an element's index (absolute position) to identify it. Distinguishing multiple copies of the same element, in an unordered collection that allows duplicates (bag), seems impossible. Unordered collections (set, bag) have no notion of order, so their element must be identified relying solely on the element equality. Therefore, elements of unorder collection must support some kind of equality testing; in Haskell, it would be said that they must be in Eq class, which defines EQ (==) methods (and its opposite, NEQ). In programming, you must use EQ method to test whether the element you want to add already exists (in the set or bag). In math, such check is not required, which causes some controversy regarding duplicated elements in a set: Does a duplicated element vanishes (collapses) as soon as the extra copy of existing element is added to the set? Seems it isn't so, since most authors just give an example of how the two sets are equal, e.g . {a,b,a} = {a,b}. Does that mean that an element can freely spawn copies of itself? Most of the time, this is irrelevant, justifying those vague definitions that cannot seem to decide if the extra copies are ignored or prohibited, but there may be times when this turns out important. Although the people are discouraged to consider the low-level implementation details once natural number are constructed ou of sets, it would still be nice if multiplicity would be consstent in all cases:

  • natural numbers:

    • 0 := ∅

    • successor, S(n) := n ∪ {n}

    • 1 = 0 ∪ {0} = { } ∪ = = {∅ } = {0}

    • 2 = 1 ∪ {1} = {∅} ∪ = {∅ , {∅} } = {0,1}

    • 3 = 2 ∪ {2} = {∅,{∅}} ∪ } = {∅ , {∅} , {∅,{∅}} } = {0,1,2}

    • N = {0, 1, 2, ..., N-1}

  • ordered pair:

    • (a,b) := { {a}, {a,b} }

    • (a,a) = { {a}, {a,a} } = { {a}, {a} } =

    • (0,0) = { {∅}, {∅,∅} } = { {∅}, {∅} } = = }

    • (1,2) = { {1}, {1,2} } = { , {{∅},{∅,{∅}}} }

    • (a,b,c) = { }, , c} }

    • (0,1,0) = ,}}} , ,}},{}}}

((a,b), c) = ( , c) = { {m}, {m , c} } = ( , c) = { }, , c} }

(0,1,0) = ((0,1),0) = { }, , c} } = { }, , 0} } = { { { {0} , {0,1} } } : { { {0} , {0,1} }, 0 } } = { { { , } } } : { { , } }, {} } } = ,}}} : ,}},{}}}

(0,1,0) = {{{{{}},{{},{{}}}}} , {{{{}},{{},{{}}}},{}}}

With respect to uniqueness, whether the repeated elements are taken as distinct or as separate entities.

Multiset

https://en.wikipedia.org/wiki/Multiset

A multiset (bag, mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements.

D.Knuth lists other names that were proposed or used for this concept, including: list, bunch, bag, heap, sample, weighted set, collection, suite.

The positive integer number of instances, given for each element is called the multiplicity of this element in the multiset.

As a consequence, an infinite number of multisets exist, which contain only elements a and b, but vary by the multiplicity of their elements:

  • The set {a, b} contains only elements a and b, each having multiplicity 1, when {a, b} is seen as a multiset.

  • In multiset {a, a, b}, the element a has multiplicity 2, and b has multiplicity 1.

  • In multiset {a, a, a, b, b, b}, a and b both have multiplicity 3.

These objects are all different, when viewed as multisets, although they are the same set, since they all consist of the same elements.

As with sets, and in contrast to tuples, order does not matter in discriminating multisets, so {a, a, b} and {a, b, a} denote the same multiset.

To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset {a, a, b} is denoted as [a, a, b].

The cardinality of a multiset is constructed by summing up the multiplicities of all its elements. For example, in the multiset {a, a, b, b, b, c} the multiplicities of the members a, b, and c are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.

One of the simplest and most natural examples is the multiset of prime factors of a number n. Here the underlying set of elements is the set of prime divisors of n. For example, the number 120 has the prime factorization 120=233151120=2^{3}3^{1}5^{1} which gives the multiset {2, 2, 2, 3, 5}.

Sequence

A sequence is an enumerated collection of objects in which repetitions are allowed. Like a set, it contains members (elements, terms).

The number of elements (possibly infinite) is called the length of the sequence.

Unlike a set, the same elements can appear multiple times at different positions in a sequence, and order matters.

Formally, a sequence can be defined as a function whose domain is either the set of the natural numbers (for infinite sequences) or the set of the first n natural numbers (for a sequence of finite length n).

The position of an element in a sequence is its index (rank); it is the natural number from which the element is the image. It depends on the context or a specific convention, if the first element has index 0 or 1. When a symbol has been chosen for denoting a sequence, the nth element of the sequence is denoted by this symbol with n as subscript; for example, the nth element of the Fibonacci sequence is generally denoted Fn.

The length of a sequence is defined as the number of terms in the sequence.

A sequence of a finite length n is also called an n-tuple. Finite sequences include the empty sequence ( ) that has no elements.

Finite and infinite

Normally, the term infinite sequence refers to a sequence that is infinite in one direction, and finite in the other - the sequence has a first element, but no final element. Such a sequence is called a singly infinite sequence or a one-sided infinite sequence when disambiguation is necessary.

In contrast, a sequence that is infinite in both directions, i.e. that has neither a first nor a final element is called a bi-infinite sequence, two-way infinite sequence, or doubly infinite sequence. A function from the set Z of all integers into a set, such as for instance the sequence of all even integers ( …, −4, −2, 0, 2, 4, 6, 8… ), is bi-infinite. This sequence could be denoted (2n)n=−∞∞(2n)_{n=-\infty}^{\infty}

Increasing and decreasing

A sequence is said to be monotonically increasing, if each term is greater than or equal to the one before it.

For example, the sequence (an)n=1∞(a_n)_{n=1}^{\infty} is monotonically increasing iff an+1≥ana_{n+1} \geq a_n for all n∈Nn \in N.

If each consecutive term is strictly greater thanthe previous term then the sequence is called strictly monotonically increasing.

A sequence is monotonically decreasing if each consecutive term is less than or equal to the previous one.

A sequence is strictly monotonically decreasing if each consecutive term is strictly less than the previous.

If a sequence is either increasing or decreasing it is called a monotone sequence. This is a special case of the more general notion of a monotonic function.

The terms nondecreasing and nonincreasing are often used in place of increasing and decreasing in order to avoid any possible confusion with strictly increasing and strictly decreasing, respectively.

Bounded

If the sequence of real numbers (an)(a_n) is such that all the terms are less than some real number M, then the sequence is said to be bounded from above.

In other words, this means that there exists MM such that for all nn, an≤Man \le M.

Any such MM is called an upper bound.

Likewise, if, for some real m, an≥man \ge m for all n greater than some N, then the sequence is bounded from below and any such m is called a lower bound.

If a sequence is both bounded from above and bounded from below, then the sequence is said to be bounded.

Subsequences

A subsequence of a given sequence is a sequence formed from the given sequence by deleting some of the elements without disturbing the relative positions of the remaining elements.

For instance, the sequence of positive even integers (2, 4, 6, ...) is a subsequence of the positive integers (1, 2, 3, ...). The positions of some elements change when other elements are deleted. However, the relative positions are preserved.

Formally, a subsequence of the sequence (an)n∈N(a_{n})_{n\in \mathbb{N}} is any sequence of the form (ank)k∈N(a_{n_k})_{k \in \mathbb {N}}, where (nk)k∈N(n_k)_{k \in \mathbb {N}} is a strictly increasing sequence of positive integers.

Generically, an alternative set theory (AST) is an alternative mathematical approach to the concept of set. It is a proposed alternative to the standard (axiomatic) set theory.

Some of the alternative set theories are:

  • the theory of semisets

  • the set theory New Foundations

  • Positive set theory

  • Internal set theory

A semiset is a proper class that is contained in a set.

https://en.wikipedia.org/wiki/Multiset https://en.wikipedia.org/wiki/Sequence https://en.wikipedia.org/wiki/Exact_sequence https://en.wikipedia.org/wiki/N-tuple

PreviousBasic concepts in mathNextElementary concepts in objects

Last updated