Sets
Sets are rigorously defined generalization of mental concepts. It is more abstract and general than any particular collection, or a sequence or a list (which is a particular kind of a sequence).
This is canonical example of how mathematics does not consider any representation of its abstract concepts, so it could abstract out any representation-related notions whatsoever (and add non-existent, imaginary ones, such as \(\emptyset\) and to consider properties of something that does not exist).
When we say “there is an empty set \(\emptyset\)” we imply “in the context of this particular axiomatic system”. It does not “exist” outside of it (or outside your head).
The lack of a type-discipline messes everything up very quickly.
No ordering
There is no notion of a particular ordering of elements, as in a heap inside a bag, and no notion of duplicate - each mentioning refers to the same unique element.
The only valid notion for elements membership \(x \in X\).
Partitioning
There is the universal notion of partitioning of a Set based on some common property defined by a predicate on elements. \[ X' = \{x \in X\ \mid P(x)\}\]
Such partition is a subset \(X'\) of a Set \(X\).
The explicit quantifier \(x \in X\) corresponds to the notion x : X (x
has the type of X) and implies \(P(x)\) is defined \(\forall x \in X\) (or that P(x)
is well-typed).
This very notion of “such that” is the basis of sub-typing, selection, filtering and specialization.
The set comprehension notation is well-established in Haskell.
Typing
In Mathematics a Set and its Subset are the same kind of an object (of the same type), and therefore every set is a subset of itself \(A \subset A\). This leads to nonsensical paradoxes, like the notion that the set of all sets is a subset of itself.
In CS a Set and its Subsets are of the same type (of a container), but the notion of inclusion in itself is rejected - they are distinct objects with unique identities. This solves the Russell paradox.
The relation \(\in\) is of an Element and a Set.
The relation \(\subset\) is of an Subset and a Set.