Programming and Order Theory

Covariance, Contravariance and Order Theory

In this post I make the observation that covariance and contravariance in programming are what are known as Order Duals.  I am not the first person to make this observation, however, these ideas often tend to be buried in academic research papers like "Adding Axioms to Cardelli-Wegner Subtyping" by Anthony J H Simons, don’t get me wrong I love these types of papers, they give me hope and inspiration that software engineering will someday become a first class engineering citizen.  Unfortunately, these types of papers tend to be too theoretical and thus not very accessible for the average developer.  This is unfortunate as the idea of covariance and contravariance as order duals both puts these concepts into the mathematical context of order theory and possibly gives programmers some native context for order theory.  So hopefully this post will make these ideas more programmer friendly.

I previously wrote a post about lattice theory, which is part of the more general order theory, where I talked about some basic order theory ideas such as duality.   Order theory occurs quite a lot in software and programming and this is part of a series of posts to talk about those occurrences.

Covariance and contravariance receive a fair amount of attention, as they should, in software blogs and some of these posts include some interesting observations. One, perhaps slightly off topic observation, is "Liskov Substitution Principle is Contravariance" which is an interesting observation and interesting post if you overlook the disdainful tone towards OO.  Another more relevant post which is a nice post about "Covariance and Contravaiance in Scala" relates these ideas to category theory which is relevant especially since apparently you can think of "Category Theory as Coherently Constructive Lattice Theory", warning heavy going in that paper.

Defining Covariance and Contravariance

To me one of the most striking and perhaps apropos examples of order theory in software is that of covariance and contravariance which Eric Lippert defines on his blog as:

The first thing to understand is that for any two types T and U, exactly one of the following statements is true:

• T is bigger than U.
• T is smaller than U.
• T is equal to U.
• T is not related to U.

For example, consider a type hierarchy consisting of Animal, Mammal, Reptile, Giraffe, Tiger, Snake and Turtle, with the obvious relationships. (Mammal is a subclass of Animal, etc.) Mammal is a bigger type than Giraffe and smaller than Animal, and obviously equal to Mammal. But Mammal is neither bigger than, smaller than, nor equal to Reptile, it’s just different.

He has an eleven part series on covariance and contravariance, his posts cover some C# implantation details but the ideas are generally applicable and looking at one language’s details can help with comparing and contrasting to other languages.

Wikipedia includes the following definition, the animal example is pretty popular:

• Covariant: converting from wider (Animals) to narrower (Cats).
• Contravariant: converting from narrower (Triangles) to wider (Shapes).
• Invariant: Not able to convert.

Including this is slightly redundant but this definition captures the conversion aspect and defines the relationships explicitly. 

Covariance and Contravariance as Order Duals

The above are definitions that have order theory written all over them.  In fact that is pretty much a text book definition of an order Relation in that it is reflexive, transitive, and antisymmetric. It is reflexive since Animal = Animal, transitive since Animal ≤ Mammal ≤ Cat implies Animal ≤ Cat, and antisymmetric since Animal ≤ Mammal implies not Animal ≥ Mammal and in the animal example there are cases of both comparability and incomparability as you would find in a partial order.

As you can see from the above definitions both sets of terms, wider/narrower or bigger/smaller, which are the same, define an order dual for comparison.  To write it more formally we will call the set C classes of various types in an OO hierarchy. So covariant would be represented by less than or equals ≤ and contravariant would be represented by greater than or equals ≥ and a set of classes with these order relations can be written with mathematical notation as (C, ≤) = (C, ≥)^d .

Types as Sets of Fields

It was in researching this post that I came across the paper "Adding Axioms to Cardelli-Wegner Subtyping". These kinds of discoveries are one of the reasons I write these posts.  In that paper they quote another paper "On understanding types, data abstraction and polymorphism" by Luca Cardelli and Peter Wegner:

a type A is included in, or is a subtype of another type B when all the values of type A are also values of B, that is, exactly when A, considered as a set of values, is a subset of B

The ideas about types and subtypes covered in these papers extend beyond which fields a class or object has, however, I thought it would be interesting and beneficial to limit the discussion to that case.  One reason is that if you take the fields of an object or class then all subtype collections of fields will be found in the powerset and all subtypes will be a subset relation and these can be drawn as my favorite lattice, yes I have favorite lattice, the powerset lattice.  Also in this case covariance and contravariance are now defined as the subset and superset operations on the powerset lattice.

Types as Sets of Fields in the Real World

Now I always feel that a real example helps quite a bit so I have created a set of example classes, Scala traits actually, which illustrate the above ideas using a quasi-real-world example.  Please note that these code examples are designed for the purposes of illustrating these ideas and may contain design issues that one would not implement in the real world, but they should be close enough to bridge the conceptual gap, if you will.  Also this first example is should be applicable to dynamically typed languages that might use duck typing or structural typing.

The following Scala traits define a possible domain object hierarchy that could be used to persist data to a database and render it back to a web page among other possible uses:

trait BaseDomain {

override def equals(that: Any) : Boolean

override def hashCode : Int

}

 

trait PersonInfo extends BaseDomain {

var firstName : String

var lastName : String

}

 

trait Address extends BaseDomain {

var street : String

var street2 : String

var city : String

var state : String

var country : String

var zipCode : String

}

 

trait PhoneNumber extends BaseDomain {

var phoneNumber : String

var extension : String

}

 

trait Person extends BaseDomain {

var personInfo : PersonInfo

var address : Address

var phoneNumber : PhoneNumber

}

These traits yield the following field powerset lattice:

Now suppose we would want to define a type for each of the above lattice points, which we probably would not do but there may be cases to do similar types of things in the real world.  Let’s define the following Scala traits that wrap the above domain object hierarchy elements:

trait PersonInfoTrait extends BaseDomain {

var personInfo : PersonInfo

}

 

trait AddressTrait {

var address : Address

}

 

trait PhoneNumberTrait extends BaseDomain {

var phoneNumber : PhoneNumber

}

 

trait PersonInfoAddressTrait extends AddressTrait with PersonInfoTrait {

}

 

trait AddressPhoneNumberTrait extends AddressTrait with PhoneNumberTrait {

}

 

trait PersonInfoPhoneNumberTrait extends PhoneNumberTrait with PersonInfoTrait {

}

 

trait PersonTrait extends PersonInfoAddressTrait with AddressPhoneNumberTrait with PersonInfoPhoneNumberTrait {

}

Since Scala traits support multiple inheritance we can define the above type hierarchy which can be drawn as the powerset lattice that it is:

Again we can see covariant and contravariant types defined on this lattice and each relation is actually the subset superset relation on fields.

I feel the basic observations and the above examples on order duals and covariance and contravariance make the ideas pretty strait forward for field set context.  In writing this I delved into a number of papers, adding some of them to my "to read list", on Types in programming and Type Theory and I feel there are probably some deeper insights and implications of all this. 

Lattice Theory for Programmers and Non Computer Scientists

Part One: Mathematical Foundations

Matt Might has a blog post "Order Theory for Computer Scientists" in which he concisely outlines some basics of order theory.  It is a nice post but it is targeted towards computer scientists and is possibly only of interest to that audience, especially since all of his examples are in Haskell, not that there is anything wrong with that, but I think this is unfortunate as these ideas are potentially interesting to programmers as well.

In this post I am mostly talking about lattice theory as opposed to the more general order theory. While general order theory is both interesting and relevant to programming and CS, lattice theory is too and there are many interesting ideas that relate to lattice theory. Lattices impose more structure on orders and that is probably why there are a lot of books on lattice theory such as George Gratzer’s comprehensive and recently updated Lattice Theory : Foundation.  Lattice theory has been described by Gian-Carlo Rota, an accomplished twentieth century mathematician and lecturer, as having "been the object of such vociferous vituperation".  The book Combinitorics the Rota Way, which he coauthored, gives deep insights into this subject and its relationship to other areas of math including, of course, combinatorics, but also topology, set theory, Boolean algebras, probability theory, and more.  I think Rota will be vindicated with a vengeance as it seems to me that lattices show up almost everywhere in math.  Additionally I feel that lattice theory will be become quintessential in computer science and software engineering and should be a mandatory math for those curricula.  I will expand on these ideas in follow up posts.

One anecdote tells of a senior mathematician who stopped Rota in the halls of MIT and stared at him demanding: "Admit it! All lattice theory is trivial."  I confess I have some difficulty with lattice theory as it does seem to be both trivial and deep, at first the ideas don’t seem to really have that much substance, but deeper you dig the more things you find, and it seems that it is always showing up in other areas of math, and even if it is not obvious it often seems to be right under the surface.  I think that’s the duality here, the ideas, per se, are not that impressive, much of the importance comes from the application of the ideas and their relation to other areas of math.

In George Gratzer’s updated Lattice Theory : Foundation he states that a difference between the new addition and the previous edition is the addition of more diagrams, and recommends the reader drawing their own as well, in my opinion he does not go far enough, one of the goals of this post to have some pictures for the basic ideas.  I admit I will do my best here to help the motivated learner, but this post should probably be viewed as supplemental to other resources.  Also you will need to have some knowledge of set theory and concepts like Cartesian products and some knowledge of abstract algebra such as group theory may also be helpful.  Also knowledge of basic graph theory is needed.  You will also need some comfort level with basic mathematical notation.  If you don’t have this knowledge, hopefully you are willing to get up to speed on it, trust me, it’s worth it.  Another point to note is that everything covered here will be finite, all sets, orderings, and lattices are finite, I believe that much of this extends to the countable infinite, etc.  I leave that for you to pursue.

Lattices Drawn as Graphs

Lattices have some connections to graph theory and to really fully understand the nuances of these ideas you need to have an understanding of basic graph theory, specifically the differences between directed graphs and undirected graphs and an understanding of cycles and acyclic graphs.

Lattices can be drawn as graphs the main diagram used to visually represent lattices is the Hasse diagram which depict lattices as a undirected graph, more on this below.  Also it should be noted that issues of graph planarity are ignored and two crossing edges, that is with no vertex, have no significance in terms of order, also sometimes for aesthetic reasons intersecting lines are shown as crossing behind other lines, again this has no impact on the order structure.

Binary Relations

Lattices are built on the concept of a binary relation on a non empty set. This is usually expressed in terms of the Cartesian product of a set with itself, where R is the relation and S is the set:

R : S x S → S

In this case the binary relation emits a member of the same set, which means it is closed on the set.

For example for the set S = {a,b,c} a possible relation is the ordered pairs: R = {(a, c), (a, a), (b, c), (c, a)}.  In general a Binary Relation can be written as a set of ordered pairs.  When talking about orders there is a distinction as to whether the relationship between two elements in the set exists, meaning does the ordered pair (x,y) exist in R.  In the example above (b,c) exists, (b,c) ∈ R. Also note that opposite relation of (b,c), (c,b) is not in R, (c,b) ∉ R.

This binary relation can be seen in the diagram below, each of the ordered pairs map to a directed edge:

Properties of Binary Relations

Binary Relations can have certain properties.  I feel this is the crux of understanding ordering relationships.  The first two properties are:

Reflexive ∀x ∈ S (x,x) ∈ R

Transitive∀ x,y,z ∈ S if (x,y) ∈ R  and (y,z) ∈ R then (x,z) ∈ R

If a binary relation has these two properties, that is it is Reflexive and Transitive then it is known as a preorder or quasi-order.  This is a more general type of binary relation which we are not really interested in initially except in how it relates to two more specific types of binary relations.

The symmetric property is defined as:

Symetric ∀ x,y ∈ S if (x,y) ∈ R  then (y,x) ∈ R

A preorder with the symmetric property is known as an equivalence relation.  In terms of Lattice Theory this is another binary relation that we are not immediately interested in.  Equivalence relations are well worth learning more about in their own right, as they play an important role in partitioning sets which have interesting applications in abstract algebra in relation to quotients of groups and rings and homomorphisms of groups and rings.

The next property, which we are very interested in, is the antisymmetric property which is defined as:

Antisymmetric ∀ x,y ∈ S if (x,y) ∈ R and (y,x) ∈ R then x = y

A preorder with the antisymmetric property is known as an order relation sometimes referred to as a partial order. A set with a partial order on it is called a partially ordered set, poset, or just an ordered set.  So now we have a definition of an order:

If S is a non-empty set then by an order on S we mean a binary relation on S that is reflexive, anti-symmetric, and transitive.

We will now use the less than equals symbol ≤ to denote our order relation which follows as:

(∀x∈ S) x ≤ x;	(reflexive)
(∀x, y ∈ S) if x ≤ y and y ≤ x then x = y;	(antisymmetric)
(∀x, y, z ∈ S) if x ≤ y and y ≤ z then x ≤ z.	(transitive)

In general an order is defined using the notational convention: (S, ≤) where S is the Set on which  the order is defined and ≤ denotes ordering relation.  Note:  ≤ is not necessarily the same as less than or equals, it might be, but it could also be a number of other order relations.

Comparability: Partial Orders, Total Orders and Antichains

One thing that I found confusing when learning about ordering relations is the difference between a total order and a partial order.  The idea of a partial order is that not all elements in a set have a relation.  Some pairs of elements are incomparable, meaning no relation exists between them.  This is denoted using the parallel lines symbol: ∥, for example x ∥ y means (x,y) ∉ R and (y,x) ∉ R. 

An example of a partial order is the set of partitions below:

This is a partial order of set partitions of a set of three items.  For example suppose that the set {a,b,c} is a plate containing an apple, a banana and a cherry.  As you move down the lattice you get more partitions, in the second row you can partition two pieces of fruit onto one plate and one on another, in three different ways {a}, {b,c}  or  {b}, {a,c}  or  {c}, {a,b} .  In the bottom row you can only partition three pieces of fruit one way on three different plates {a},{b},{c}.  If you move up the lattice you can reverse the operation and consolidate the set partitions (plates) in the same manner. 

You should note that above the elements:  a|bc,  b|a,c, and c|a,b have no ordering relation to each other, that is there is no way to further partition the current plates, rearranging them isn’t allowed. So these items are incomparable: a|bc  ∥  b|a,c,   b|a,c  ∥  c|a,b , ...

A total order is also known as a linear order or a chain. In a total order all elements are comparable meaning that the relationship has the following total property:

Total ∀ x,y ∈ S  (x,y) ∈ R  or  (y,x) ∈ R

A fairly simple example of a chain is the integers 1-5 with the ordering relation less than or equals, which would be written as ({1,2,3,4,5}, ≤) which would have the following diagram:

An antichain is a set where no two elements are comparable:

Antichain ∀ x,y ∈ S  (x,y) ∉ R  and (y,x) ∉ R

An example is the suits of a card deck, there are probably some exceptions, but in general a spade, a heart, a club and a diamond have no order relation to each other, this antichain can be depicted as:

Also you should note that above the elements:  a|bc,  b|a,c, and c|a,b in our set partition lattice above form an antichain within that lattice.

Order Duality

Order duality is actually a fairly intuitive idea, for example if you had a list of words in alphabetical order, you can reverse the order. This holds true for every ordering relation and is called the Duality principle.  More formally if you have an order P = (S, ≤), its dual denoted P^d would be defined as P^d =(S, ≥).  If you take any of the lattice examples above or below and reverse them, flip them upside-down, you get the dual of the order relation.  This is one of the most seminal ideas in order theory. It also shows up in other parts of math.

The Powerset Lattice

The powerset of set is a set of all of the subsets of the set.  For a set of three items, S = {a,b,c} The power set of S, which is a set of sets, is: { {a,b,c}, {a,b }, {a,c}, {b,c}, {a}, {b}, {c}, ∅ }.  A common notation for denoting the powerset is 2^S.  This notation draws from the fact that the cardinality of the powerset is the cardinality, the size of the set, of the set raised to the power of 2, this can be expressed more concisely using the notation |S| to describe cardinality, so the above set has the cardinality |S| = 3. The powerset of S 2^S has the cardinality |2^S | = 2³ = 8.

The lattice below shows the ordering relation "is a subset of", this can be denoted by ⊆ and the order would be given in notational form as (2^S, ⊆).

Its order dual which is "is a superset of" given by (2^S, ⊇):

Binary Relations Drawn as Graphs

Now that we have some definitions and diagrams in place I wanted to revisit the drawing of lattice diagrams.  Our first relation diagram above has a loop for (a,a) and (b,c) (c,a) makes it transitive, but it is not reflexive because it is missing loops for b and c.  So that relation is not a preorder which means it is also neither an equivalence relation nor an ordering relation.

For every preorder, there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices.  Graphs of preorders can contain cycles.  Also all nodes in a preorder group will have a loop for the reflexive relation that must exists on each node.  Graphs representing equivalence relations will be undirected graphs since these relations are symmetric and will of course have loops on each vertex for reflexivity.   As mentioned above graphs for partial orders will be a directed acyclic graph graph due to antisymmetry also they should have reflexivity loops.

The total order for 1-6 mentioned above would look as follows for the relation ≤ it is a simple directed graph:

If we were to add all of the transitive and reflexive relations it would look like this:

As we have seen in our diagrams the reflexivity loops are omitted as they are not needed and would be increase the complexity of the diagrams.  Also in the diagrams the transitivity can be inferred by following the two paths connecting three nodes.

Hasse diagrams are drawn as undirected graphs which implies the order duality, we can decompose that graph into two directed graphs as in our example above for the two dual realtions (subset ⊆ and superset ⊇) on the powerset lattice, the lattice is conventionally drawn as the following Hasse diagram: 

Another interesting point here is the difference between equivalence relations and order relations is that no cycles will occur in an ordering relation.

Subsets of Posets

Since we are dealing with sets, a set with an order relation, a poset (short for partially ordered set), can have subsets.  The interesting thing is that the subsets as a whole can be different types of orders than the original poset.  For example the power set above has as a sub-poset, {a,b,c}-{a,b}-{a}-∅, which is a total order.  Additionally the antichain {{a,b}  {a,c}  {b,c}} is also a subset of the powerset poset.  These elements still have the same relations as they did in the original set, but the subsets themselves are different structures.

Upper and Lower Bounds

A finite set, remember we are only considering finite sets, with an order relation implies that if you move up and down the ordering relation eventually you will hit a maximum or minimum element.  The above examples, the total order has an upper bound of 5 and lower bound of 1, the powerset lattice has an upper bound of the set itself and the empty set as a lower bound.  The antichain does not have a single upper or lower bound the four elements are each both their upper and their lower bounds.  The idea of bounds, specifically the idea of greatest lower bound (GLB)  which is also known as an infimum and the dual the least upper bound (LUB) which also known as the supremum are important in order theory but show up in other areas of math such as topology.

A poset may not have one upper or lower bound, this is a distinction from a lattice which is still a poset but it has a single upper and lower bound.   A lattice will have both a distinct upper and distinct lower bound, that is one element that is the upper bound and one element that is the lower bound. These are sometimes denoted as ⊤ for upper bound and ⊥ for lower bound.  This bounding feature of lattices is very important as we will see.

The Samuel L Jackson Lattice (Total Order)

Since Samuel L. Jackson has a habit of showing up everywhere, he is the new Kevin Bacon, and it is only fitting that he would show up in Lattice Theory.  Another example of a total order or chain is what is known as the "Samuel L. Jackson Scale of Black Emotion" which was developed by Larry Willmore of the Daily Show.  It forms a Total Order also known as the Samuel L Jackson Lattice, which includes the following elements:

• Furious Anger Guy
• Shaft
• Changing Lanes Guy
• Snakes on a Plane Guy
• Jurrasic Park Jackson
• Frozone
• Mace Windu

As you can see the sup(Samuel L. Jackson Lattice) = ⊤ = "Furious Anger Guy" and the inf(Samuel L. Jackson Lattice) = ⊥ = "Mace Windu". Now it’s pretty obvious in an intuitive human sense that the Master of the Order and Jedi Master Mace Windu is the lattice dual of Furious Anger Guy of Pulp Fiction, well up to his epiphany in the diner robbery scene anyway.

As with all lattices, this lattice has an order dual denoted (Samuel L Jackson Lattice)^d known as the Inverse Samuel L Jackson Lattice, which just a reverse of the above list.

Ok, I’m having a little fun here, trying to lighten the mood a little.  However, this is a legitimate example of a lattice.

Lattices vs Posets

By definition a lattice is a poset, however, a poset is not necessarily a lattice.  A lattice is defined as, with sup being supremum and inf being infimum:

An order (S,≤) is a lattice if sup{a,b} and inf{a,b} exist ∀ a, b ∈ S.

Actually there are some distinctions between different classes of lattices:

A lattice is a poset in which all nonempty finite subsets have both a least upper bound and a greatest lower bound.

A complete lattice is a poset in which all subsets have both a least upper bound and a greatest lower bound.

A bounded lattice has a unique top element and a unique bottom element, actually there are algebraic implications that we will discuss below.

Finite sets form complete lattices and since we are limiting ourselves to finite sets we will only be dealing with complete lattices. Also every complete lattice is a bounded lattice so when we talk about lattices here we will mean complete lattices aka bounded lattices.

Up and Down Sets

If you take an element of a poset or a Lattice and take the subset of all elements that are greater than the element you get a new poset or lattice that is a subset, these types of subsets are referred to as up-sets or down-sets. An up-set of an element x denoted as ↑ x includes the element and everything above it is defined as:

↑ x = {y∈ P : y ≥ x}

The up-set of the element {a} in the powerset lattice above would look like (shown in blue):

Similarly, or perhaps "dually" the down set, denoted as ↓ x, is defined as:

↓ x = {y∈ P : y ≤ x}

With the down-set of the element {a,b} in the powerset lattice (in red):

Meet and Join

Meet and Join are two binary operators defined on elements of posets and and lattices which yield a unique value and they are dual operations of each other.  In the case of a poset meet and join may or may not exist on any two elements, in the case of a bounded lattice they will exist.  Join is usually denoted with the or symbol: ∨ and meet is denoted with the and symbol: ∧.  Join is equivalent to supremum and meet is equivalent to infumum. They are defined as: 

x ∨ y = sup{x,y}

x ∧ y = inf{x, y}

The following describes their relation with ordering:

x ≤ y  ⇔ x ∨  y = y

x ≤ y  ⇔ x ∧  y = x

As you can see above when two elements are comparable meet and join will reduce to the appropriate minimum or maximum element, when two elements are incomparable as in the picture of the join below between {a} ∨ {c} the lattice lines show how the join moves up to the element {a,c} that is above each element, not coincidently the join on this lattice is the set union operation ∪ actually this join can be expressed as {a,c} = {a} ∪ {c} which is right out of set theory.

And the dual relation is {a} ∩ {c} = ∅:

Semilattices

A semilattice will define either a meet or a join operation over an order resulting in either a meet  semilattice or join semilattice, technically a lattice is both of these combined. A good example is a tree which as a single root node, let’s call it a lower bound aka an infimum, a common example is the prefix tree for strings, in this case we are using binary strings 0 or 1 up to length three:

In this example the order relation is: "Is a prefix of".  As you can see you can define a meet on any two elements with the empty string λ serving as the semi-lattice bottom ⊥. Also as you can see there are no joins on this order.  Pretty much any tree can be viewed as semi lattice with descendency from the root node through all of the other nodes serving as the ordering relation.

Lattices are Algebraic

One of the interesting and sometimes confusing things about lattices is that, while they are structural they are also algebraic.  Meet and join follow a number of algebraic rules.  In general lattices can be defined as an algebra L=(S, ∧, ∨) which satisfy the following algebraic rules for all x, y, z ∈ S:

Idempotent

x ∧ x = x

x ∨ x = x,

Commutative

x ∧ y = y ∧ x

x ∨ y = y ∨ x,

Associative

x ∧ (y ∧ z) = (x ∧ y) ∧ z

x ∨ (y ∨ z) = (x ∨ y) ∨ z,

Absorption

x ∧ (x ∨ y) = x

x ∨ (x ∧ y) = x.

The first three pairs of axioms say that L is both a meet and join semilattice. The fourth pair (the absorption laws) say that both operations induce the same order on L.

Since we are dealing with bounded lattices we extend the above laws to include the following for the top and bottom elements, here we will represent the bottom element ⊥ as 0 and the top element ⊤ as 1.  For a bounded lattice the algebra is defined as L=(S, ∧, ∨, 0, 1) with the following identity laws:

x ∨ 0 = x

x ∧ 1 = x

x ∧ 0 = 0

x ∨ 1 = 1

For our powerset lattice above the algebra is (S, ∩, ∪, ∅, S) with the empty set as the identity for the union operation and the set itself as the identity for the intersection.

Other Lattice Properties and Operations

If you take our powerset example above, you might have noticed that there are some more algebraic properties of this lattice that are not listed above.  The first is the distributive property.  While the powerset lattice does have the distributive property you should note that not all lattices do.  The distributive property is defined as:

Distributive Law

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Another property which can be found in certain lattices and also applies to our powerset lattice is the property of complementation which means that for every element x the lattice has a complement y under both the meet and join operations:

x ∧ y = 0

x ∨ y = 1

Some Lattice which are Complemented can have additional properties which is known as orthocomplementation and has the following laws:

Complement Law

x ∧ x^c = 0

x ∨ x^c = 1

Involution Law

(x^c)^c = x

Order Reversing

x ≤ y then y^c ≤ x^c

Our power set lattice which is also a Boolean Algrebra also follows Demorgans laws:

Demorgans laws

(x ∨ y)^c = x^c ∧ y^c

(x ∧ y)^c = x^c ∨ y^c

Some lattices can have a property known as Modularity which follows the following law, which is similar to the distributive law:

Modular law

x ≤ z implies x ∨ (y ∧ z) = (x ∨ y) ∧ z

I am including Modularity for completeness as I am not discussing it or including examples.  Distributivity, Modularity and Complementation have many intricacies and there is much theory and complexity surrounding how these work and where they show up, this becomes quickly obvious if you dig into more resources on lattices.

The Algebraic Structure of the Powerset Lattice

With the above algebraic laws of complemented (orthocomplemented) bounded lattices defined, I figured it might be nice to list out these laws as they apply to our powerset lattice, if we take the powerset 2^S of any set S, the empty set ∅ is the lower bound and the set S is the upper bound. The powerset lattice has the following laws:

Idempotent

x ∩ x = x

x ∪ x = x

Commutative

x ∩ y = y ∩ x

x ∪ y = y ∪ x

Associative

x ∩ (y ∩ z) = (x ∩ y) ∩ z

x ∪ (y ∪ z) = (x ∪ y) ∪ z

Absorption

x ∩ (x ∪ y) = x

x ∪ (x ∩ y) = x

Distributive

x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z)

x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z)

Identity

x ∪ ∅ = x

x ∩ S = x

x ∩ ∅ = ∅

x ∪ S = S

Complement Law

x ∩ x^c = ∅

x ∪ x^c = S

Involution Law

(x^c)^c = x

Order Reversing

x ⊆ y  then  y^c ⊆ x^c

Demorgans laws

(x ∪ y)^c = x^c ∩ y^c

(x ∩ y)^c = x^c ∪ y^c

The D4 Dihedral Subgroup Lattice

This topic might be filed under an advanced example, so feel free to skip if you’ve had enough for the moment.  In doing my research I came across the following lattice diagram, it is the lattice of the subgroups of the D₄ Dihedral Group, I looked at cyclic groups and subgroups including the cyclic subgroups of D₄ in a previous post on abstract algebra.  I have modified it to better show the identity element marked in blue. It also includes the names of well known isomorphic groups that correspond to each subgroup.

This lattice shows some really interesting things about the dihedral group. The top element is the D₄ group itself and the bottom element is the trivial Z₁ group consisting of only the identity. As you can see the center forms a chain consisting of three cyclic groups, Z₁, Z₂, Z₄, and D₄ (not cyclical). The anti-chain of five Z₂ isomorphic groups, all of which are involutions, like negation it is an operation which if applied twice results in the original value, on the left are the horizontal (H) and vertical (V) reflection involutions, the middle one is a 180 degree rotation (R₂) involution and on the right are two diagonal (D₁, D₂) reflection involutions. As you can see on the vertical and horizontal involutions on the left along with the rotation involution form the group (R₀, V, H, R₂) and on similarly on the right the subgroup (R₀, D₁, D₂, R₂) is formed. Also both of these groups are isomorphic to what is known as the V group, aka the four group, aka Klein group, aka the Vierergruppe. I am not sure what all of this means but I find it fascinating. Also please note that there is a minor nomenclature conflict as V refers to both the Klein group and the vertical reflection D₄ group element, but the context of each is mutually exclusive. The same goes for D_n where D₁ and D₂ are elements and D₄ is a group. Additionally this lattice give a nice visual depiction of Lagrange's Theorem which states that the order of each subgroup will evenly divide the order of the group. Therefore, as in the lattice, a group of order 8 only has subgroups of orders 4,2,1.

Some Notes on Notation

In math notation can vary and order theory has several variants on notation that it helps to be aware of.  Firstly the following sets of symbols can often be used in relations to orders:

Sometimes these choices are made at a particular authors preference other times combinations of these are used, such as in discussing things like Galois Connections which are mappings between two different orders, in such a case multiple sets of the above symbols might be needed to differentiate between specific instances of different orders.  Usually the set notation symbols are not used for lattices but they sometimes are, and in our examples above both meanings apply.  Also the following symbols get used to describe comparison as well:

Another set of symbols that show up, which are often used to describe covers, or immediately precedes or immediately succeeds, in that there are no elements between the two items compared are:  

Additional Topics

The topics of lattice theory and order theory are extensive and this post really just scratches the surface.  When you feel comfortable or even if you don’t depending on your learning style, there are many things that I did not cover.  There are order specific concepts like strict and asymmetric. Complete partial orders show up a lot in CS as well.  For lattices there are things that I only mentioned like modularity and Galois connections, there functions on lattices which include ideas like monotone, antitone, and isotone.  New lattice can be created by number of techniques like the Cartesian product of two lattices.  And of course there are many interesting results relating to fixed points, and the list goes on.

In my next post I will look at some specific examples of some the ideas discussed here in everyday programming and some more theoretical examples as well.

References and Resources

There are a number of books on the subject, including the previously mentioned  the recently updated Lattice Theory: Foundation  by George Grätzer and Combinatorics: The Rota Way by Joseph P. S. Kung, Gian-Carlo Rota and Catherine H. Yan, there are a number of books on the subject including:

• Lattices and Ordered Algebraic Structures by T.S. Blyth
• Introduction to Lattices and Order by B. A. Davey and H. A. Priestley
• General Lattice Theory (Second Edition) by George Grätzer, B.A. Davey, R. Freese and B. Ganter

If you are just getting into the subject, and even if you are not, I would recommend taking advantage of some good free resources, listed in no particular order:

Lattice Theory with Applications  by Vijay K. Garg

Notes on Lattice Theory[complete pdf here] by J. B. Nation of the University of Hawaii

Chapter 1 - Lattice theory in Vaughan Pratt’s CS 353: Algebraic Logic course handouts

Dave Abrams "Order I Say" blog post, some of the above images are from his post, with his permission, thanks.

Lattice Tutorial by Nenad Jovanovic of Secure Systems Lab

Lecture 7 and lecture 8 of Lionel Levine’s course on Algebraic Combinatorics

Chapter 2 - Ordered Sets and Complete Lattices, A Primer for Computer Science by Hilary A. Priestley of  the Mathematical Institute, University of Oxford

The Many Lives of Lattice Theory by Gian-Carlo Rota

Wolfram’s Mathworld on lattices

The Combinatorial and Other Math of the Java Collections API

The Java Collections API both involves some explicit Math and presents some nice artifacts which parallel other Math concepts.

Combinatorics is probably one of the more fundamental Maths for Computer Science and is also prevalent throughout other Maths. In one example of Combinatorial counting problems, there is a collection of items, say a deck of cards, from which we want to determine the number of selections, say hands. The formula to compute the possible Combinations is written as:

This can also be stated as “n choose k.” My mnemonic for remembering this, and it is worth remembering, is to look at the left side above note that the n is on top and the k is on the bottom, which visually maps the n! to the numerator and k! to the denominator, and then rotate the left part by 90 degrees counter clockwise so that it forms (n - k)! and put it in the denominator. Also every number calculated by this equation is a Binomial Coefficient found in Pascal’s Triangle, which in my opinion is one of the most amazing mathematical structures.

Our example for possible five card hands from a deck of cards computes as follows:

Combinations give you the number of elements with no repetitions and where order does not matter. The possible cases and Mathematical structures for the criteria of order and repetition are as follows:

	Order Does not Matter	Order Matters
No Repetitions	Combination/Set	Permutation
Repetitions	Multiset/Bag	Enumeration/List/String

The Combinatorial equations are as follows:

	Order Does not Matter	Order Matters
No Repetitions
Repetitions

 

The interesting thing about lists is that if you make lists of varying lengths of the following characters [0,1,2,3,4,5,6,7,8,9] , you have the natural numbers in base ten, so a list of length 3 gives you 10³ or 1000 possibilities, which are: 000-999. Also lists have the highest cardinality of the four:

|List| > |Multiset| > |Permutation| > |Combinitation|

Where |object| means the cardinality or size of the collection, which is the number of elements in the set, list, etc.

The corresponding Java classes/interfaces are:

	Order Does not Matter	Order Matters
No Repetitions	java.util.Set	java.util.SortedSet
Repetitions	org.apache.commons.collections.Bag	java.util.List/java.lang.String

Sadly the Java Collections API is incomplete in this regard. Also this example is somewhat abstract but it does demonstrate how to view these objects from a Combinatorial perspective, which in turn can help with choosing the appropriate data structure, also it gives insight into possible ways that they may be populated and perhaps even tested.

This is an introductory example to Combinatorics, for more perspective there is an expansion on this known as the Twelvefold way.

The next example is more concrete, in fact it comes directly from the java docs for Comparator and Comparable:

For the mathematically inclined, the relation that defines the imposed ordering that a given comparator c imposes on a given set of objects S is:

{(x, y) such that c.compare(x, y) <= 0}.
 

The quotient for this total order is:

{(x, y) such that c.compare(x, y) == 0}.
 

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the imposed ordering is a total order on S. When we say that the ordering imposed by c on S is consistent with equals, we mean that the quotient for the ordering is the equivalence relation defined by the objects' equals(Object) method(s):

{(x, y) such that x.equals(y)}. 

I have to admit when I first read that a few years back, I was like, WTF does that mean! Obviously whoever wrote that was thinking deeply and mathematically about the underlying principals here which is clearly needed if you are designing fundamental low level framework aspects of base classes and collections.

Comparators and Comparable are about ordering, so what is being defined above is a Total Order which means that all elements can be compared to every other element, compare this to a Partial Order where elements may or may not be comparable to each other, both of these fall under the more general Order Theory. The Quotient aka Equivalence Class concept is a bit more complicated and beyond what I am trying to talk about here.

I believe the above Comparator Javadoc quote was written by Joshua Bloch, the following is from his book Effective Java:

The equals method implements an equivalence relation. It is:

• Reflexive: For any non-null reference value x, x.equals(x) must return true.
• Symmetric: For any non-null reference values x and y, x.equals(y) must return true if and only if y.equals(x) returns true.
• Transitive: For any non-null reference values x, y, z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) must return true.
• Consistent: For any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
• For any non-null reference value x, x.equals(null) must return false.

The first three are the Mathematical definition of an Equivalence Relation (which relates back to the Equivalence Class) can be found in “Abstract Mathematics” or “Transition to Advanced Mathematics” type books which describe Functions and Relations. CS Majors usually are exposed to these concepts as part of the intro into discrete math.

What I find interesting about these concepts is how the comparator/comparable and equals relation and their interrelationship for the individual object map back to control the collections behavior of ordering and repetitions.