In FP we talk a lot about algebras functions and types. But types are sets and functions are also sets. Algebras are types with operations, that fulfill some conditions, which means also sets. So how low should we get if we want to start from the beginning? I would say we should start with finitary relations.
Relation
So, let us begin with the question: what is a relation? We usually assume that it is a bound between 2 things, e.g. brothersister, fatherson, motherdaughter. If we take a look at fatherson relation, we can say, that this relation has an information of some kind of direction or difference between both sides of relation (if A is a son of B, B is not a son of A). In more general sense relation might connect more than 2 things, e.g. if Alice is the youngest sibling of Bob, and they both have also the oldest sibling Charlie, we could say that Bob is in amiddlechild relation with his siblings.
So, our definition of relation must allow sides of a relation to not be interchangeable and potentially any number of sides involved. There is already a construction, that allows that: tuple.
But can we just take a Cartesian product and it will be our relationship? Not necessarily. In parenthood relationship is a valid definition ( is a parent to the ), it belongs to set, but Cartesian product also allows (which here means that the is a parent of the ). Therefore, we cannot demand our relationship to be a Cartesian product, but a subset will do. As a matter of the fact, that is how mathematicians define it:
A (finitary) relation is a subset of a Cartesian product.
Now, that we know how we define them, let us learn some properties a relation can have and how we could name them.
nary relations
The first thing we can notice is a number of sets that were used to create a Cartesian product we cherrypicked to define our relation (arity). Later on, we’ll see a nice correspondence between relations and functions (and their arities).
Unary relation
Unary always implies single input. Here it is a subset of a Cartesian product of one set… which is basically a normal subset. There are no benefits to calling it a unary relation if we can call it just a subset, but it’s worth knowing just in case.
Binary relation
Most commonly used one a relation between 2 things. It’s worth mentioning that there is a special notation for saying that something belongs to our relation set.
Ternary relation
Relation of 3 things.
An example we used earlier was a middlechildrelation. Other could be joins (as in an edge x, joins points y and z).
Hardly ever I saw anyone using a distinct name for a relationship (or a function) with more than 3 arguments. For anything bigger expect a name like 4ary relation, 5ary relation, etc.
Relation’s properties
Next thing we can examine when we take a closer look at our relation is what properties it has. I described here some more commonly used.
Reflexive relation
Let’s say we have a group of narcissists () and we are doing a research on them: who likes who. Alice might like Bob, Bob might like Charlie, etc. But since they are all narcissists each of them like him/herself. We could describe it mathematically as:
Such relation where we can always say, that any x is in relation with itself, we call a reflexive relation.
Just to be sure: in reflexive relation each element is always in relation with itself, but it can also be in relation with something else. Just think of a relation between cars has the same color to imagine it.
Symmetric relation
We want our relation definition to allow both sides to be on unequal positions e.g. the father is a parent of the son. But sometimes we want some particular relation to have the ability to switch sides and still be true. E.g. if Alice is a sibling to Bob, Bob is a sibling to Alice.
If we tried to draw it as a table, where we would put elements as labels for rows and columns (and if we put them in rows and columns in the same order), and if we marked x for cells that show which pairs are in a relation, then we could see that xes would create a symmetrical figure.
That is why a relation where implies for each , we call a symmetric relation.
Antisymmetric relation
Sometimes we have a relation which has a sense of is the same as or something. For instance, we could compare sound frequencies and we want to say that one frequency is the same as or higher than the other. Such a relation would not be symmetric. It would be reflexive thought. Additionally, if we found 2 elements that are interchangeable, we could assume that they are one and the same element.
Such relation we call a antisymmetric relation.
Transitive relation
Sometimes relation can be kind of inherited. For example, if we say that the father is an ancestor of the son, and the grandfather is an ancestor of the father, we know that the grandfather is also an ancestor of a son.
We call such relation a transitive relation. Be careful: we can only combine relations we know about, we cannot split one relation into two, by adding an intermediate point without any additional assumption, which allows us to do it.
Now, that we know some terminology, we can take a look at some more common relations.
Preorder
Preorder (not to confuse with preorder) is a binary relation that is both reflexive and transitive.
Quite a lot of relations can be considered preorders: isthesameas (), isgreaterorequal (), islesserorequal (), isdivisibleby (), issuperset (), issubset ()…
As a matter of the fact, just by adding symmetry or antisymmetry condition we could turn it into one of the next two relations.
Equivalence
Equivalence relation is a binary relation that is reflexive, transitive and symmetric  in other words, a symmetric preorder.
Most commonly known equivalence relation is equality.
Reflexivity:
( is equal to means, that belongs to relation).
Transitivity:
Symmetry:
Intuitively, all equivalence relations will take a look at objects and look for some properties to check if they are equal. This is what we need to keep in mind, when implementing contracts like .equals
in Java or ==
in C++ (or to understand why ==
is broken in JavaScript).
Equivalence class and quotient set
If we have some set with an equivalence relation , this relation can partition the whole set into smaller disjoint sets of equivalent elements. Each of such sets is called an equivalence class and a set made of such classes is called quotient set. We denote it with .
Additive group
For instance: let us take a set of integers. Now, let us take some positive natural number e.g. . Then, let us multiply all integers by that number:
We created a set of all numbers divisible by . What would happen if we took all possible integers and calculated sets ?
We would end up with:
Sets are equal if they have the same elements. If we add (or remove) exactly 7 from each element of one of the sets above, we don’t have a choice, we end up with one of the existing sets: , , , , ,, every other set we’ll create will be identical to one of these 7!
Someone who ever did division with a remainder can notice, that we basically created sets of numbers with the same remainder in the division by 7.
Calculating such remainder is often called operation modulo, and an equivalence relation is called equality modulo :
Can we do something interesting about these classes? Well, we could e.g. define operator for them:
Basically: take every element from one set and add to by every element from another set. Interestingly, the way remainders work will guarantee us, that each number in a set we’ll create that way, will have the same remainder.
We cannot overflow, results of addition becomes an addition modulo and becomes a neutral element of the addition. Actually, that how addition modulo is defined:
This way we defined an additive group (more about groups soon):
Multiplicative group
Multiplication of our equivalence classes would be defined as:
Basically: take every element from one set and multiply by every element from another set.
Our set multiplication becomes a multiplication modulo with as a neutral element.
If we limit our set to only numbers coprime with we’ll get a multiplicative group modulo .
Partial order
Partial order (partially ordered set, poset) is a binary relation that is reflexive, transitive and antisymmetric  or an antisymmetric preorder if you prefer.
We usually use as a partial order relation symbol. Numbers are partially ordered. But with (real) numbers we can always say, that some number is lesser than the other. On the other hands with sets and issubset relation we might say that one set is lesser than the other in some situations:
but some sets are completely unrelated!
This is where the partial part came from.
Partial orders describe hierarchies. Because sets are a hierarchy (via subsets) and types are basically sets, types hierarchy in types programming languages are also partial orders (issubtype). Another example of such hierarchy would be natural numbers and divides () relation:
Minimal, maximal, least and greatest elements
Interestingly, if we draw a graph of this relation for natural numbers greater than 1, we could easily spot prime numbers: they would be at the bottom of the graph.
Such elements that have no elements lesser than them are called minimal elements. Similarly in relations where there are elements that have nothing greater than them they are called maximal elements.
Sometimes we have an element that is lesser than any other element. We would call it the least element of the partial order. Element greater than any other would be the greatest element.
If a set has the least element it is automatically (the only) minimal element of the set. The greatest element is always (the only) maximal element of the set.
On the other hand, a set with one minimal/maximal element doesn’t necessarily have the least/greatest element. Take a set of all even numbers and odd numbers from 1 to 9. Now lets define relation islesserthanandbothareevenorbothareodd. All even elements would be related to each other, but unrelated to odd elements. Odd elements would be related to each other but unrelated to even elements. Even parts would have no minimal nor maximal element. But the odd part would: 1 and 9. However, because neither would be greater/lesser than every other considered number (we consider all even numbers), set would not have a minimal nor maximal element.
Infimum and supremum
If for some subset of our partially ordered we can find find one greatest that is , we can say that is infimum of .
E.g. if our poset are integers and we take a look at subset , then all will be greater than . It is the greatest number with such property ( and are also smaller than anything in , but they are smaller than ), which makes it infimum of set .
If for a subset of our partially ordered we can find find one least that is , we can say that is supremum of .
E.g. For integers and and such p would be .
If we think about it, the Least Upper Bound which Scala compiler used for type inference is basically a supremum of types to which value belongs.
Linear order
Such issues as the one described above disappear if we add another condition. Partial order where each 2 elements , have either or relation, is called a linear order (or total order). The names are obvious once we’ll understand that this property lets us take each element and align them in a line: a lesser before a greater. A number line is a great example showing why natural numbers, integers, rational and real numbers are linear order.
Some numbers are not linear (e.g. complex), but all subset of real numbers is. Question is it a linear order? can often be replaced by can I index the elements with real numbers?
Wellorder
A linear order which each subset contains the least element is called wellordered or wellorder.
Well ordered sets have one nice property: we can apply proof by induction on them. E.g. if we wanted to prove, that each (natural) power of 2 corresponds to some power set cardinality we could do the following:

for we take a singleton of an empty set . It is a power set of . Obviously, its cardinality is
so it works so far,

for we take a set and make a copy of it, where we are putting into each sets contained by it an element that is not yet there, e.g. and then combine both sets of sets. So,
 for we take and put into , and then combine resulting with obtaining ,
 for we take and put into and , and then we combine with obtaining
 etc.
For each the cardinality is by definition
Since we were able to build a power set for and then we shown how to build a power set of cardinality basing on power set for cardinality we provided a way to build a power set for each power of 2, which was what we wanted.
This and many other proves based on injections basically require that we can start from any point, and then we’ll have a way to get closer and closer to the point, where we can stop and where we know that we reached our goal.
In typelevel programming we can think of such wellorders, e.g. when we think about the hierarchy of types and type class derivation. Notice that each induction  both on a product as well as coproduct  is basically an inductive proof where are using the property that HList
and Coproduct
are wellordered!
Lattice
Though the name looks similar to lettuce, a lattice is actually a partial order which has supremum and infimum for every two elements. In other words: for every two elements, there will be something greater or equal to both of them and something lesser or equal to both of them.
One of the best use cases for lattices I know are access management systems.
Imagine we have a certain file system. If we grant someone access to a directory (be it read, write or execute), it propagates down to all files, subdirectories, subsubdirectories etc. You can specify that script A has read access to /company/accounting
and /company/invoices/2018
. Requirements for script B is that it has to have read access to /company/invoices
and /company/accounting/integrationspayments
. These 2 sets of accesses has a infimum  read access to /company/invoices/2018
and /company/accounting/integrationpayments
. They also have supremum  read access to /company/accounting
and /company/invoices
. With that, we can see a subset of files that can be used by both scripts, and a set of files that could be accessed by either of files.
If instead of scripts, these were accessed policies in a company (or AWS, because they also use LBAC) we could easily model which combination of policies gives access to which resources.
Such system is named latticebased access control (LBAC). It’s the best and most powerful way of modeling access management in hierarchical resource structures. However, as you might feel it do comes with some complexity (you need to be able to efficiently decide whether or not something is a part of a lattice and derive relations from the way your store your data). That is why in most cases you’ll meet rolebased access control. With RBAC your entitlements are usually 11 mapping of roles you have  e.g. OAuth2 entitlements. Roles are easier to implement and test, but they don’t deal well with structures where some entitlements should be somehow inherited.
Function
A function is basically a relation between arguments and returned value. The only requirement is that the same arguments should always return the same value.
Functions have also a nice correspondence to relations. A unary function is a binary relation. A binary function is a ternary relation. A ternary function is a 4ary relation… A nullary function would be a unary relation. A function’s arity is basically smaller by 1 than relations arity.
Of course, we are assuming, that the result is always a value, not a tuple itself. What if we don’t assume that? Well, IMHO then we are explaining currying as a function which is a relation between one tuple and another tuple  if we’d say that nested tuples are the same as flattened ones then:
function  cartesian  tuple  application 

all of the above are interchangeable.
This should show us why maps (or dictionaries) in many programming languages are actually functions. While expressed in a different way they represent the same mathematical idea.
But we can say a bit more about a function’s properties.
Injective function
All functions have one value for each tuple of arguments. But sometimes we want to make sure for each different argument(s) function will return a different result. This way we’ll have a function, that has both unique arguments and returned values  this way we are able to revert it and obtain arguments by the resulted value!
We call such function oneonone function or an injective function. Sometimes it is a required property (basically each 11 mapping). Sometimes we explicitly don’t want a function to be injective  e.g. each hash function in cryptography (there 11 property would be a vulnerability).
We denote injective functions with above the arrow:
or using an arrow with another head at its tail:
A composition of injections is also an injection.
Surjective function
Sometimes we want to explicitly tell that function makes use of all values of a set that is declared as a codomain. Because, you know, it is not obvious:
This function declares the whole set of natural numbers as its codomain. However, actual codomain will only be made of and . On the other hand, the signature:
would be precise. Such function which set of returned values exactly match the declared codomain is called a function onto or a surjective function. We can denote it with an arrow with the double head:
though I saw also:
A composition of surjections is also a surjection.
Bijective function
Interesting things happen if a function is both onto and 11. A bijective function or onetoone correspondence function is always reversible. You could take a domain of to calculate its image, then create and use it to recreate domain from its image.
To denote bijection we can use an arrow with 2 heads at head and 1 at tail:
or
A composition of bijections is also a bijection.
If our and are somehow similar and the transformation preserves that similarity (homomorphism), then our bijection is called isomorphism.
When we say that 2 things are isomorphic we can understand that they are one and the same things just in 2 different representations.
Partial and total functions
So far we always assumed, that a function returns values for each value in its domain. Without that property, it would be hard to reason about function composition. However, at some point, people found that definition restricting.
That is why a function which has a defined value for each argument of its domain is now called a total function.
On the other hand, a function which defines values only for a strict subset of some is called a partial function.
Partial functions are useful for computer scientists working with e.g. functions in computability theory where an exact domain is not always known. In programming languages are quite often a result of either a messy design or are used to perform filtering and transformation in one step.
For instance Scala’s PartialFunction
is used in collect
to do filtering and mapping at once:
List(1,2,3,4,5,6,7,8,9,10) collect {
case i if i % 2 == 0 => i.toString
}
// List("2", "4", "6", "8")
or for handling only certain kinds of errors:
Future(performAction()) recover {
case e: SpecialKindOfException => // ...
}
In general, though partial functions cause more trouble than they are worth.
Summary
In this post, we talked a bit about relations, what they are, and what are their most common use cases. Knowing what are relations, equivalence, partial orders and functions we can move on and talk a bit about another foundation of modern mathematics  algebras. At the same time, we can see that all in all whole mathematics (and indirectly computing) is build on top of sets in various combinations.