Case Study III: Computer Science: The bestiary of potential infinities December 15, 2007Posted by Alexandre Borovik in Uncategorized.
We quote a professional computer scientist who left the following comment on the blog of one of us:
I would caution everyone … not to confuse “mathematical thinking” with “The thinking done by computer scientists and programmers”.
Unfortunately, most people who are not computer scientists believe these two modes of thinking to be the same.
The purposes, nature, frequency and levels of abstraction commonly used in programming are very different from those in mathematics.
We would like to illustrate the validity of these words on a very simple example.
Let us look at a simple calculation with MATLAB, an industry standard software package for mathematical computations.
>> t= 2
t = 2
ans = 0.5000
What is shown in this screen dump is a basic calculation which uses floating point arithmetic for computations with rounding.
Next, let us make the same calculation with a different kind of integers:
s = 2
ans = 1/2
Here we use “symbolic integers”, designed for use as coefficients in symbolic expressions.
Next, let us try to combine the two kinds of integers in a single calculation:
ans = 1/4
We observe that the sum of a floating point number $t$ and a symbolic integer is a symbolic integer.
Examples involving analytic functions are even more striking:
ans = 1.4142
ans = 2^(1/2)
ans = 2
We see that MATLAB can handle two absolutely different representations of integers, remembering, however, the intimate relation between them.
The example above is written in C++}. When represented in C++, even the simplest mathematical objects and structures appear in the form of (a potentially infinite variety of) classes linked by mechanisms of inheritance and polymorphism. This is a manifestation of one of the paradigms of the computer science: if mathematicians instinctively seek to build their discipline around a small number of “canonical” (actually) infinite structures, computer scientists frequently prefer to work with a host of potential infinities controlled and handled with the help of a special technique which is category-theoretic by its nature. In the context of Computer Science, a category-theoretic approach frequently has an advantage over the set-theoretic: in the example above, the set of “symbolic” integers appears as a process for building its elements; it is not closed, its boundaries are not defined. We find ourselves in the situation summarised in the famous words by Henri Poincare:
“There is no actual infinity; and when we speak of an infinite collection, we understand a collection to which we can add new elements unceasingly.”
When we move from integers to other algebraic structures ofinterest for practical applications, for example, (finite)abelian groups and finite fields, we see a real explosion in variety and diversity of their computer realisations. Ofcourse, any two Galois fields of the same order are isomorphic, but they can be constructed in different ways. What is important, the variation of computational complexity of different realisations of the same structure is the key issue of algebraic cryptography, with tremendous implications for information security. In the traditional discussion of “identity” or “sameness” of mathematical objects, the complexity-theoretical aspect of the problem has been mostly ignored.
The link between computer science and category theory is especially interesting because we shall look, in the next case study, at the real time emergence of yet another form of actual infinity in a developing mathematics discipline: the higher-dimensional category theory.