computing with infinite objects
25 August 2015

It seems common sense to say that computers can only deal with finite objects such as bytes, integers, or strings, and will therefore never be able to work with mathematical objects such as a real number or infinite subsets of natural numbers. However, one shouldn't forget that even the integers that a computer deals with are not the actual mathematical integers but a representation. As we will see, a computer can actually easily handle quite a large class of mathematical objects when one chooses the right representation. Let us consider subsets of natural numbers $ \mathbb{N} $ as an example. Naively it seems like computers aren't adequate to compute with them: if we were to represent a subset $ A \subset \mathbb{N} $ by a list of its elements, we would restrict ourselves to finite subsets only (leaving aside memory and time constraints, which in reality restrict us even more). We could easily form the union and intersection of two such sets and check whether two such sets are equal. However we would never be able to consider the set of all even numbers, at best we could compute with approximations of the form $ \{2,4,6,..., 2n \} $. There is however a way that we can implement a much larger class than all finite subsets of $ \mathbb{N}$, including the set of all even numbers. The basic idea is to represent a subset $A$ of $\mathbb{N}$ not by a list of its members but by its characteristic function $\chi_A$. We are missing one important puzzle piece however. To implement, say, the union of two such sets we need to implement a function (program) that accepts not lists, but (characteristic) functions as an input. Luckily there is a large class of programming languages that are able to do just that! A functional programming language is one that treats its functions as "first class citizens" and lets us not only apply functions to simple data types, but also pass them to other functions as input. There are purely functional programming languages (Haskell, Scheme, etc), but many modern programming languages allow functional constructs too some degree. In the following we are going to show how to use Python (using Skulpt) to compute with our sets. We first define an object dec_set, with certain properties and functions. We then create two instances of this object $A$ and $B$. Now $B$ represents the set $\{ 1, ..., 20000 \}$ and $A$ the set of even numbers. Finally we form $C=A \cup B$ and answer the simple question whether $3 \in C$ and $20003 \in C$. Even though this is a fairly simple example it is rather exciting to manipulate infinite sets on a computer as if we would numbers!
class dec_set:
  def __init__(self, chi):
    if type(chi) is set:
      self.chi=lambda n: n in chi
    else:
      self.chi=chi
  def __contains__(self,n):
    return self.chi(n)
  def union(self,other):
    return dec_set(lambda n: n in self or n in other)
  def intersection(self,other):
    return dec_set(lambda n: n in self and n in other)
  def setminus(self,other):
    return dec_set(lambda n: n in self and not n in other)
B=dec_set(lambda n : n <= 20000)
A=dec_set(lambda n : n%2 == 0)
C=B.union(A)
print(3 in C)
print(20003 in C)

It is clear that we could extend this to a larger part of set theory potentially ending up with something useful. Here we would only like to clean up some more mathematical aspects. Readers familiar with computability theory will know that what we actually have implemented are the decidable sets, i.e. exactly those subsets of the natural number that have a computable characteristic function. As there are only countably many such sets, there is a large class of sets we will not be able to represent. There's also some more problems we now have. Notice that we can check whether two finite sets represented as a list are equal. Here this is not possible anymore: If there was a function checking whether two sets represented by their characteristic function were equal we could solve the Halting problem (simple exercise). In particular we cannot check whether a set is empty or not. This might seem like a large prize to pay, however constructive mathematicians have long shown that, at least for the reals, not being able to check whether two objects are equal or not is actually not as big an issue as one might expect.