Algebra of Sets

The concept of a class or a set of objects (a collection) is defined by any property or attribute which each object considered must either possess or not posses; those objects which posses the property form a corresponding set (belong to a corresponding class).

The fundamental property of Sets is that they have an order relation which defines a set - subset relationship. Which means Sets may (or may not) be nested.

Formally, the set A is said to be the subset of the set B if there is no object in A that is not also in B. Which means A is nested (contained) in B. Each set therefore is self-contained (or, like a Number, equal to itself).

Equality for Sets is defined as every element of A must be also an element of B and conversely, which implies the same size. This is per-element equality (not a structural equality, since Sets have no notion of structure, only of membership).

This is similar to less-or-equal relation, which is defined as the difference is 0 (there is no difference) for equality and a positive difference (the result of subtraction) for less-than relation.

However, Sets does not have complete ordering, like Numbers, since any two sets A and B could be completely unrelated (having nothing in common - () as their logical product) or partially related (having non-empty intersection (a set of common elements).

  • A + A = A - logical sum or union
  • A * A = A - logical product or intersection

If A is a subset of B then (A + B) = B

Sets are fundamental abstract containers (a generalized and abstracted out pattern of What Is) or abstract classes so, they have laws similar to Natural Numbers (another generalized and abstracted out pattern - another fundamental abstraction).

This equation

A(B+C) = AB + AC

which reads The set consisting of objects which are in A and also in either B or C is the same as the set consisting of those objects which are either in both A and B or in both A and C, is example of an algebraic law. There are more that 20 of these laws.

  • Sum is union of either A or B (that is why the whole it is called a sum)
  • Product is intersection of both A and B (so it is called a product of the two)

() is 0 or nothing or False I is 1 or the whole or True

A' is a complement (inverse) - logical NOT) so ()' = I I' = ()

  • AA' = () - nothing can be both A and NOT A - the law of contradiction
  • A + A' = I - either in this or in that - the law of excluded middle


A ⊃ B and B ⊃ C then A ⊃ C. If all Bs are As and all Cs are Bs then Cs are As.

Which is the basis of classification (class-subclass relationships (is-a relationship).

Types are sets

Algebraic Data Types

Algebraic Data Types are a straightforward specialization of sets into so called Sum Types (True | False) and Product Types (Data.Tuple).


Collections, such as Lists, which are ADTs are specialized sets defined by name and interface to implement. Good collections, like Lists must have a closure property ("the empty list" is a List).

Type Classes

In Haskell Type-Classes are specialized sets coupled with protocols to implement, which are defined as a templates, to be instantiated with "concrete" types (like [Char]).


Classes are templates for a structured values (usually called objects) which combine data slots and code slots - closures (usually called methods).

Classes might have a straightforward set - subset hierarchy, which is basis for inheritance (the way to structure the code for reuse).

Traits or Behaviors

The set - subset relationship could not be established for sets like {1,2,3} and {2,3,4}. Neither is a subset of either. This is what Traits are all about - partial relations.

Traits (or Mixins) are composable implementations of protocols or interfaces (behaviors) which could be substituted in the equivalent-for-equivalent basis.

No wonder, languages with Traits are more flexible (more suitable for modeling aspects of reality) than languages with only class - subclass relationships (your fucking Java).

Last modified 2 years ago Last modified on Nov 20, 2018, 12:04:37 PM
Note: See TracWiki for help on using the wiki.