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 ∣ 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.