Who needs numbers if you have structures

This is an article about how different representations can make it easier or harder to understand certain concepts. It is also about numbers and functions and relations and about interesting properties that some of them have. I'm not sure that it's a very useful article, but I felt like writing it and so I hope that it will find its audience.

It starts, completely free of context, with a selection of line graphs.

When I first learned about functions at school, I remember that they all looked like that. At the time I never thought much about what information those graphs convey, what they were designed for communicating. The fact that there are lines and not dots or crosses or something else tells us that we are looking at something continuous, meaning that between two positions, there are always more positions. Sometimes you see graphs that have dots and also lines between them, which usually means that the real information is in the dots, and the lines are just there to make them look more like the continuous graphs above. Here are the three kinds of graphs beside each other, so we can compare their visual qualities:

If you ask me, the first graph looks much better than the third, and the second graph just seems like a compromise. It seems that this kind of graph really wants to be continuous, which works best if the data is also continuous. But many domains are discrete, not continuous, which means that between any two values, there is nothing—not even empty space. Just nothing. They are separate values. Presenting them as having empty space between them is kind of a lie. All it is good for is suggesting that those discrete values are somewhat related to another domain that actually is continuous. Integers and real numbers are an example of that. Integers are often presented as if they were a very selective window into the continuous world of real numbers.

Most information processed by computers is discrete. There is a lot of information out there that we work with every day that is discrete, and it is not always so useful to think of it as an inferior version of something continous.

Another flaw of those graphs is that you can’t see very well that functions are one-way streets: they have an input and an output. As an example, think of the function succ(x) = x + 1. The way it works is: if you have an x, you can get the successor of x by adding 1 to it. It doesn’t say anything about how you would go from the result back to the original x, because you can't. That's not what this function does. It can only take you in one direction, step by step, by applying the function multiple times:

succ(x) = x + 1

succ(1) = 1 + 1
        = 2

succ(succ(1)) = (succ 1) + 1
              = (1 + 1) + 1
              = 3
...

That's a pretty interesting thing you can do with this function, and I don't see how the line graphs communicate that.

Yet another flaw: if the two axes are both numbers, then why are they so far apart from each other? It’s not like the numbers on the horizontal axis are somehow different numbers than those on the vertical axis. But there really only is one number called “1”, and only one number called “2”. The numbers on the two axes refer to the exact same numbers, and yet, they don’t appear as the same things.

Numbers as objects

What I want is a visualization that doesn't have the above flaws, and I kind of also want that visualization to give each one the objects its own identity. Like this one:

In my ideal world anyway, numbers would be depicted like that. But that kind of representation has the problem that it is relatively time-consuming to draw, and it is much easier to just draw objects as circles.

Functions, or: objects pointing at other objects

Now let’s visualize the succ function. All we need to do is give every object the ability to point at one other object, and then we have to make them point to the right objects.

There you have it: a representation of the function succ(x) = x + 1. You can see how it takes you from 0 to 1 and from 1 to 2 and from 5 to 6, and so on. It doesn’t have the same flaws as more traditional graphs: every number is its own object, and you can see the direction from input to output in the form of arrows.

One thing that's nice about this visualization is that the chain of numbers can be arranged in any way without changing its meaning. It doesn't matter if all the numbers line up left to right or right to left or not at all. (You can drag the objects around and watch the structure move with them if you want!)

What happens if we remove the number labels? Does that change the meaning?

It clearly still is a chain of objects, but can we say that it is the same function as before, or does removing the numbers make it ambiguous? The answer is that it is ambiguous, because there is more than one function with that exact same structure. Consider the function that, given a number, returns the number before it, pred(x) = x - 1. the only difference between it and the succ function is the direction of the arrows.

What that picture shows is that one function is the inverse of the other, meaning that if you follow the succ arrow from one number to another, and then you follow the pred arrow from there, you end up at the same number as before, and vice versa. Let’s compare the traditional way of drawing functions in a coordinate system:

Can you tell from that picture that the two functions are inverses? You actually can, if you know how to recognize inverses in line graphs, but our object graphs makes it very clear what that relationship means from the perspective of walking from one object to another.

Relations, or: objects pointing at any number of other objects

How would you visualize the notion that one number can be smaller or bigger than another number? You could take one number as the starting point, say 1 or 3 or any other number, and draw arrows to all the other numbers that it is less than:

The fact that there are multiple arrows going out from one object to others is what makes less than not a function. Less than is a binary relation, which means that between any two objects, there may or may not be an arrow that relates the two, so you can have any number of arrows going from one object to others.

The graphs above are focussed on two particular starting points (1 and 3), which keeps the pictures simple. If we wanted to connect all the objects in the picture, it soon becomes very noisy and hard to read. You can look at the progression of going from only two connected objects to five in the pictures below:

Even though the circles in these graphs have no labels, we can still tell what the numbers are by looking at the number of incoming arrows.

zero is the object that has no incoming arrows, because no other object is less than zero.
one is the object that has one incoming arrow, because zero is less than it.
two is the object that has two incoming arrows, because zero and one are less than it.
and so on.

One thing that’s interesting is that the succ function is hidden in these pictures. You can see it highlighted in green when you hover over them. Less than and succ are related to each other in a special way. For one thing, if object B is the successor of A, then A is also less than B. But also, if you start with the arrows defined by succ and, whenever it is possible to reach another object via a path of existing arrows, you add an arrow to that object directly, you end up with a less than graph as a result.

This mathematical property of the less than relation is called transitivity. The word literally means something like "going-through-ness". The idea is that if there is a way to go from one object to another object via some relation, then the objects at the start and the end of the path are also related in the same way.

Written in a shorter format, that is:

for any numbers A, B, C:  if A < B and B < C then also A < C

That notation is pretty succinct, but we can make it even shorter if we leave out the "for any…" part and introduce an arrow that means "then we also know that" or "implies":

A < B and B < C  =>  A < C

The purpose of this exercise is to show some appreciation for textual notation, because it is also just another tool that can be used to represent and think about abstract concepts. So let's go one step further and write down a generalized rule for transitive binary relations, which less than is merely one example of:

any binary relation R is transitive if:  R(a, b) and R(b, c)  =>  R(a, c)

Discovering that a relation is transitive is a great thing! What it means is that there is a more compact representation that uses way fewer arrows between objects with no loss of information, as long as you know that transitivity applies.

The numbers are kind of in the way

You may wonder why I keep removing number labels from pictures. Aren’t they helpful for understanding better what's going on? Well, they can be, but at the same time, they can make it possible to cheat and use knowledge that is not actually in the picture, just because it is something you already knew about the numbers involved. For example, if you wanted to use the following picture to answer the question “is 4 equal to 4?”, what would you say?

Given only the information in the picture, you can't answer the question, because there are no is equal to arrows, which would look like this:

We can also make a combined picture of equal and greater than, which gives us greater than or equal, and we can use the trick of mentioning the fact that it is a transitive relation in order to reduce the number of arrows. Also, let's not add any number labels so we can focus on just the structure.

Even though the objects are not labeled, the graph can be used to answer any questions about whether one object is greater than or equal than another object, as long as we can somehow point at the objects we are talking about.

The structure of inequality

If you compare the pictures of equality and inequality, you can see that one is very tidy and the other one also quite pretty, but at the same time very noisy.

Is there a way to simplify the picture for inequality? If it is a transitive relation, we might be able to reduce the number of arrows by quite a bit. How do we know if it is transitive? What we need to look out for are arrows that are not really essential, because they are just shortcuts from one object to another, and if you removed them, there would still be a connection left.

Let's start by focussing on just one number and see what it is pointing at: from 4, you can go to 3 and 2, among others. But you can also go from 4 to 2 by going through 3, and you can go from 4 to 3 through 2. It seems like not all of those arrows are essential and it should be safe to remove most of them. Maybe we could just guess what a transitive version of inequality might look like and then check if we got it right afterwards.

Any object that is greater than or less than another object is also not equal to it. As we have seen earlier, greater than and less than are transitive relations and can be reduced to transitive versions of the succ and pred function. If we put those two together, we get a very clean picture that may or may not be a transitive version of a graph of inequality:

Unfortunately, there is a problem with it: even though all we did is remove arrows, we also accidentally introduced new, invisible arrows, by saying that it is transitive, because transitivity means that for every path that you can walk between objects, there also exists a shortcut arrow that we just don't draw because it is not essential. In this graph, one thing you can do is walk from 5 to 6 and back to 5, which means that there is an invisible arrow from 5 to 5, which means that 5 is not equal to 5, which is clearly wrong.

So, sadly, this attempt at finding a more compact form of not equal has failed, but it has taught us a lesson: using a tool to simplify the representation of a concept not only has the risk of removing information, it also has the risk of accidentally adding information that was not there before and is probably wrong.

It also teaches us something about inequality: even though less than and greater than (as examples of relations about objects not being equal to each other) are transitive, when you combine them into one relation, you lose that precious property.

One thing we could do, though, is use the concept of not: one object is not equal to another object if, in the graph that shows whether two objects are equal, there is no arrow between them.

Some structures are orderings

In addition to colloqial meanings of order, there is also a mathematical notion of order. For example, the less than relation is an example of a strict ordering. "Strict" means two things here:

1. Asymmetry: if there is a path from one object to another, there is definitely not a path back
2. Irreflexivity: objects never point at themselves

This is a point where textual notation might be convenient again:

any binary relation R is  symmetric if:  R(a, b) => R(b, a)
                         asymmetric if:  R(a, b) => not R(b, a)

                          reflexive if:  for all a:  R(a, a)
                        irreflexive if:  for all a:  not R(a, a)

The following picture contrasts strict ordering with non-strict ordering and with something that is not an ordering at all:

You can tell that the third picture above is definitely not an ordering because it is symmetric: it is possible to go from one object to another and also back the other way. And the second picture is not strict, because it is reflexive: objects do point at themselves.

Who needs numbers if you have structures

Seeing relations as a bunch of arrows between objects is quite useful. It makes it easy to think about mathematical properties those relations might have, and to see how to simplify your view of something by exploiting those properties.

Numbers are only one example of objects in a discrete domain. In computer programs, there tend to be a lot of things that are very similar to numbers, but they are not numbers themselves. Being familiar with the structures around numbers allows you to see those same structures in other domains. Sometimes you may not even know the shape of your data because all you have is some mathematical model of how objects should be related, for example in some kind of lattice structure, or maybe a non-strict ordering or whatever else is required, and then you can use that knowledge to design your data types and algorithms to represent and work with the data efficiently.

But even if you don't usually write programs, I hope you enjoyed the ride and I hope it made you curious to learn more about functions and relations and orderings. There is a lot of information out there on Wikipedia, but sometimes it can be hard to decode, especially if you lack tools to visualize concepts in an understandable way.