katzenfabrik

Posted by David R. MacIver

https://notebook.drmaciver.com/posts/2019-02-21-18:58.html

Do numbers exist?

Published

2019-02-21

In What even is a number? I finished with:

There is a more foundational question, which is whether numbers "exist" in any meaningful sense. My answer is "Almost certainly not, but if so why would we care?"

I'm going to backtrack on that a bit. Obviously numbers exist.

The problem is that this is a bad question because there are no non-misleading answers to it. Both the statements "numbers exist" and "numbers do not exist" are more likely to cause you to believe false things than true ones, and which answer you prefer says more about what you mean by "exist" than it does about numbers.

Numbers don't exist, in that there is no platonic realm where you will find the authentic number 3. At least, there is no evidence that there is such a realm, there isn't even a suggestion of what such evidence would look like, and it doesn't seem to be especially useful to postulate that one exists, so there might as well not be. Insert your own atheism analogy here. Michelangelo's Stone: an Argument against Platonism in Mathematics is a good argument against the idea that one exists, basically by pointing out that if such a thing existed it would be too large to serve the role that its proponents want it to - it is basically the infinite library of Borges, with every random string written down in a book. All published works exist there, but finding them is a harder task than creating them would be.

Additionally, they don't exist because as I argued, numbers aren't really any one thing. There is not "the number 3", there is only "the value that corresponds to the number 3 in our current implementation of natural numbers." In What Numbers Could not Be Paul Benacerraf argues quite convincingly that it is a category error to equate the number 3 with any particular instantiation of it.

So numbers really don't exist in any literal physical sense. I promise.

And yet numbers obviously exist.

Why?

Well because all of the same arguments apply to Chess, and if you try telling someone that Chess doesn't exist they'll look at you like you've sprouted an extra head.

Imagine the conversation:

You: Chess does not exist.

Them: Um, yes it does. Look, here's a Chess board.

You: Sure, that's a Chess board, but that's not Chess, that's just the symbolic representation you use to play the game of Chess.

Them: Which doesn't exist.

You: That's correct, yes.

Them: We have literally played a game of Chess on this board. How can we play Chess if it doesn't exist?

You: It's easy, you just follow the rules of Chess.

Them: Which don't exist.

You: Oh, well, there are rules of Chess of course, but those are mere matters of human convention. They don't imply any sort of abstract platonic ideal of Chess that exists somewhere.

Them: Look, here is a printed out copy of the rules of Chess.

You: I see. And?

Them: That seems to suggest the rules of chess exist.

You: Why? Those aren't the rules of chess, they're just words on a page that describe how to play chess. The rules are a purely abstract concept that exist purely as a matter of human convention.

Them: This seems like a fairly spurious distinction.

You: I suppose it does rather.

Them: Shall we settle it over a game of Chess?

You: Sure, why not.

And yet these are exactly parallel to the arguments that say numbers don't exist. People are very attached to the idea that you can apply the word "exist" to abstract objects and, while I don't want to entirely defer to common usage of a word for its more specific meaning, I think it would require an extremely convincing argument to persuade me that they are wrong to do so. Countries are also purely abstract objects designed purely as a matter of human rules and convention, but if you told me that France did not exist I could only answer "It does, though".

So, any reasonable definition of the word "exist" should incorporate abstract concepts with rules and names defined purely by human convention. Numbers are such a thing, and as purely abstract concepts it is perfectly reasonable to say that they exist. They exist in the same way and for the same reasons that France and Chess exist: Because we say so.

https://notebook.drmaciver.com/posts/2019-02-21-18:58.html

Posted by David R. MacIver

https://notebook.drmaciver.com/posts/2019-02-18-08:58.html

What even is a number?

Published

2019-02-18

Context: A philosopher friend asked me this question. This is my attempt to answer.

Attention Conservation Notice: It may not be a very good attempt to answer.

Epistemic status: My philosophy of mathematics is slightly idiosyncratic, in the sense that most people appear to believe ridiculously wrong things so it is unusual to be correct about this. I'm aware that feeling this is a bad sign for one's reliability.

Content warning: Highly informal mathematics.

My glib answer to this question which is completely 100% true and is actually quite deep when unpacked is "Depends. What do you want it to be?".

This is an answer that took a few hundred years of very heated arguing and people defending their own aesthetic preferences about numbers to arrive at. You can see some of that history of what we call some of the different sorts of numbers: e.g. Negative, irrational, and imaginary numbers.

Each of these represents a bitter argument about whether a new type of number should be allowed, all of which were eventually won by the people on the side of the new numbers, but with a legacy of our distaste for them left in the name.

You can view this as a process of discovery, with people finding out new things that are also numbers. You would be factually incorrect in doing so, and misunderstanding the basic nature of mathematics, but you could.

The main problems with this viewpoint are that there isn't really a single thing that we mean by "number", and each of these types of number is better viewed as having been invented than discovered.

Anyway, before we talk about the fundamental nature of mathematics, lets talk about sheep.

Suppose you are a farmer and you want to keep track of your sheep. In particular you want to make sure that all of your sheep who left the enclosure in the morning return to it in the evening. Unfortunately, numbers haven't been invented yet. What do you do?

(This is not a true history and is only a parable. Also it is definitely not my own invention but I can't figure out who the original source for this story is. Plausibly it's based on a misremembering of Yan Tan Tethera. People keep telling me it's from Yudkowsky but that's definitely not where I got it from and Lucy Keer points out prior art that is also not where I got it from. At this point I think we might as well just label it folklore)

Well, there's a very easy trick! You keep a small bag. Every time a sheep leaves the enclosure in the morning, you put a pebble in the bag. Every time a sheep returns to the enclosure, you take a stone out of the bag.

There are a couple of scenarios here:

1. If all the sheep are in the enclosure and the bag is empty then the same number of sheep have left as returned, yay.
2. If all the sheep you see are in the enclosure and there are still stones in the bag, you're missing some sheep. For each stone remaining, there is a missing sheep out there somewhere.
3. If the bag is empty and there are still sheep outside of the enclosure, something has gone a bit wrong. You seem to have picked up some extra sheep from somewhere.

To take a simple system and make it complicated, what we have done is create a correspondence between the set of stones in the bag and the set of sheep outside the enclosure, such that we can perform equivalent operations on each of these things. In this correspondence we have the following:

• There is a ground state of emptiness.
• We can add an item to the set (a sheep leaves the enclosure, a stone enters the bag), at which point it becomes non-empty.
• If the set is non-empty, we can remove an item from it (a sheep enters the enclosure, a stone leaves the bag).

The thing that makes this correspondence work is that the set of stones and the set of sheep behave in the same way, and so we can set up parallel arguments based on the behaviour of these two different systems matching at every step of the way.

Our claim is that the sheep are all in the enclosure if and only if the bag is empty. How can we know that this is the case?

Lets represent a series of operations on one of these things (the bag or the sheep) by writing them down as follows: We write down a \(+\) every time something is added to the collection (the rocks in the bag, the sheep in the enclosure), and a \(-\) every time something is removed. So for example if three sheep leave the enclosure and then two enter it (three rocks enter the bag, two are taken out of it), we would write that as \(+++--\).

These sequences obey the following rules:

1. If the sequence starts with \(-\) then something has gone wrong - we've tried to take a rock out of an empty bag, or a sheep out of a world with no sheep in it.
2. If the sequence ends with a \(+\) then the collection is not empty (we've just added something to it - we put a rock in the bag, a sheep left the enclosure).
3. If there is a \(+-\) somewhere in the sequence (we put a rock in the bag then immediately took one out, a sheep left the enclosure and then a sheep returned) then the sequence of operations is equivalent to the same sequence with that \(+-\) removed (any two sheep and any two rocks are interchangeable for our purposes).

We can now determine whether the end state of any sequence of operations is empty solely from its representation in this notation by running the following procedure:

1. If there are no operations, we are in the starting state of emptiness so the set is empty.
2. If the last element is a \(+\) then by the above rules the set is not empty.
3. If the first element is a \(-\) then we're in an error state. Thus the first element must be a \(+\) and we contain at least one \(-\). Scan forward until we find the first \(-\). This must follow a \(+\) (because it's the first). Remove that \(+-\) pair from the sequence to get a shorter sequence, and determine if the new sequence is empty.

In each step of this process one of two things happen:

1. We determine the answer and stop.
2. We replace the sequence with a strictly shorter sequence and try again.

This process of replacing the sequence with a strictly shorter one must eventually stop, because we can run it for no longer than it took us to build the sequence in the first place. This means we eventually end up either with an empty sequence (the set is empty) or with a sequence with only \(+\) operations in it (the set is not empty). Importantly, because these operations represent either sheep or stones, and because both sheep and stones obey the rules we laid out above, we know that the set of sheep in the outside world is empty if and only if the bag is empty: We can represent the current state of each by the same sequence of \(+\) and \(-\) operations, and we can determine solely from those operations whether the set is empty.

We can abstract this further.

Say something is a counter if you can do the following three things and obey the following rules:

1. Ask if it is currently empty.
2. Increment it.
3. If it is not currently empty, decrement it.

Say two counters are observationally equivalent if, after doing the same sequence of increment/decrement operations to each side, they are either both empty or both not-empty.

Now, counters must obey the following rules:

1. After incrementing it, the counter is not empty.
2. Incrementing it then decrementing it results in a counter that is observationally equivalent to the original counter (and in particular is empty if and only if it started empty).

The above argument provides the stronger conclusion: Any two empty counters are observationally equivalent. We can represent the sequences of operations with our \(+/-\) notation, and at the end we will have concluded that either both counters are empty or both counters are non-empty.

OK, what does this have to do with the original question about numbers?

A counter can be anything that implements those increment and decrement operations. You can ask "What is a counter?" and the answer isn't any one thing. It could be a flock of sheep, it could be a bag of stones. Both of those things are counters, because they allow you to implement the counter operations in a way that obeys the rules. The notion of a counter is not that of a single concrete class of object, it is an abstract description of the behaviour of a system providing certain operations satisfying certain rules.

The nice thing about the counter rules is that to a certain degree we don't need to care what a counter is - the power of the behaviour is that we can know that whichever counter implementation we have, they will behave the same way. Because any two empty counters are observationally equivalent you can talk about the empty counter, but this is a polite fiction: There are an infinite variety of empty counters, we just don't care because they all behave the same way as far as counting is concerned.

This is also what a number is. A number is not any one thing, it is any one of any number of things that implement some operations (and there are different types of number depending on what operations you want to implement).

The numbers closest to the counters we've discussed are what are called the natural numbers: \(0, 1, 2, \ldots\). They don't include negative numbers like \(-3\) or fractional numbers like \(\frac{1}{2}\). We could also call them counting numbers, as these are the numbers which can be used to represent operations that correspond to counting things

The operations you can perform on natural numbers are that you can take their successor (the next element), and you can test if two numbers are equal. Additionally, there is a special element called zero (or \(0\)). The rules they have to satisfy are the following:

1. \(0\) is not the successor of any element.
2. Every element has a successor element.
3. If two elements are equal then their successor is equal (this is important to state because there may e.g. be irrelevant information in the representation. Think of how we represented counts with stones - two bags of stones represent the same if they have the same number of stones, regardless of whether they're literally the same stones).
4. If the successor of two elements are equal then those elements are also equal.
5. Every number can be formed by writing down a series of successor operations from zero.

For example, one implementation of the natural numbers is our sequences of \(+\) operations for a counter. The empty sequence is our \(0\) element, taking the successor is adding a \(+\) to the end, two elements are equal if they are the same word.

In the same way that we reasoned about the behaviour of counters without having to know exactly what counter implementation we were using, we can reason about the behaviour of numbers without knowing how they work, and conclude properties that must hold for any implementations.

In particular, we can conclude from \(4\) that every element other than \(0\) is the successor of some other element: Suppose for an arbitrary number that we'll call \(n\), we write the successor of \(n\) as \(S(n)\). Then any number other than \(0\) can be written as \(S(S(\ldots S(0)\ldots))\) by rule \(4\), so is the successor of the bit inside the brackets. By rule \(3\), every non-zero number has a unique element that it is the successor of. Call this its predecessor. Similarly if \(n\) is some arbitrary non-zero number then we write its predecessor as \(P(n)\).

This means that we can use any implementation of natural numbers to implement a counter as follows:

1. A counter wraps a single number.
2. It is empty if that number is \(0\)
3. When incrementing the counter we replace the number with its successor.
4. When decrementing the counter we replace the number with its predecessor (which is valid because the counter is non-empty if and only if it contains a non-zero number).

Two of these counters are observationally equivalent if and only if they wrap equal numbers, because for any such counter you can produce a unique sequence of decrements that makes it empty (this isn't totally obvious, but the details are fiddly and unenlightening without getting much more formal than I want to).

This means that we can use any implementation of numbers to define the notion of the size of any given counter: It is the unique (up to equality) number that is observationally equivalent to the current counter.

The careful reader will notice a sleight of hand there: I haven't proven that there is always such a number, only that if there is one then it is unique. This is because there is not always such a number!

The following is a perfectly valid implementation of a counter:

1. The counter is never empty.
2. Incrementing the counter does nothing.
3. Decrementing the counter does nothing.

Such a counter cannot be represented by a number, because for any number based counter implemented as above you can eventually run a sequence of decrement operations to make it empty. You could think of such a thing as representing an infinite collection, but note that this doesn't require any foundational assumptions about whether infinity is in some sense real or realisable, it's just a straightforward implementation of a set of rules.

In fact, every counter as defined is equivalent to either this infinite counter or some number, but I'll leave proving that as an exercise for the interested reader.

OK, after all of that, what actually is a number?

Depends. What do you want it to be?

The problem with asking this question about abstract mathematical entities like numbers is that they are not any one thing. A number is not its representation, any more than a counter is a bag of rocks or a flock of sheep. A number is an entity that comes from some implementation of the operations that we have decided to consider distinctively numeric.

An interesting feature of something like the natural numbers is that we can choose the rules to uniquely constrain the behaviour of the implementation (with some caveats about formal systems that I won't go into here), but there are many other classes of mathematical objects that are also interesting where this is not the case.

There is a more foundational question, which is whether numbers "exist" in any meaningful sense. My answer is "Almost certainly not, but if so why would we care?". It may be that there is some pure platonic realm of numbers where the true numbers exist, but we don't need it to exist to do mathematics, and it's unclear what its existence would imply about how we do mathematics anyway - it's not like this view of mathematical objects as reasoning about abstract systems obeying rules stops working in that event, the platonic realm just becomes another system that we can model this way.

https://notebook.drmaciver.com/posts/2019-02-18-08:58.html

Posted by David R. MacIver

https://notebook.drmaciver.com/posts/2019-02-15-14:37.html

Caching interactions with an arbitrary interface

Published

2019-02-15

This is a trick I've figured out recently for Hypothesis. I've yet to decide whether it's something I want to use, but it's a neat trick. It's much more easily implemented in a dynamically typed language, though I expect you could make something like it work in a statically typed language relatively easily with macros and metaprogramming and suchlike.

Suppose you have some interface that has the following two properties:

1. All of the arguments to its methods are immutable.
2. All of the return values of its methods are both immutable and hashable (for the sake of simplicity I will assume that none of its methods throw exceptions, but this can easily be made to work if they do).

Now suppose you have a deterministic function that takes any implementation of this interface and returns an immutable value. You can cache that function, which may be a big win if it is very slow (as it may be if it's a complicated test function as in Hypothesis).

You do not need to know anything about the implementation of the interface in order to do this. The cache will work by returning the value of any prior implementation of the interface that it is called with that is observationally equivalent to the current implementation.

How could this be?

Because the function is deterministic, what it does next is determined entirely by what has happened so far, which is in turn determined entirely by the sequence of return values from the object it is called with. Thus every result of calling the function corresponds to a unique sequence of return values. Additionally, none of these sequences can be a prefix of another, because that would be non-deterministic behaviour - once the function ran and called another method after this point, another time it didn't.

This structure makes it very easy to store the results in a tree. Each node either records which method was called and its arguments, or that no more methods were called and is a leaf storing the return value, or stores a sentinel value to record that we don't know what happens here and need to ask the underlying test function (this is helpful for the representation):

import attr
from collections import defaultdict


@attr.s()
class TreeNode(object):
    """Node wrapping a previous observation. Having a mutable
    wrapper class around the value makes the implementation a lot
    tidier."""
    observation = attr.ib(default=None)

@attr.s()
class Result(object):
    """A previously observed return value."""
    value = attr.ib()

@attr.s()
class Decision(object):
    """A previously observed call to the underlying implementation."""
    method = attr.ib()
    args = attr.ib()
    children = attr.ib(default=attr.Factory(lambda: defaultdict(TreeNode)))

To populate the tree you use the following wrapper around the implementation which proxies method calls to the underlying implementation and puts the observations in the tree:

class WrapperImplementation(object):
    def __init__(self, tree, underlying):
        self.__tree = tree
        self.__underlying = underlying

    def __getattr__(self, name):
        base = getattr(self.__underlying, 'name')
        if not callable(base):
            return base

        def accept(*args):
            if self.__tree.observation is None:
                self.__tree.observation = Decision(name, args)
            rv = base(*args)
            self.__tree = self.__tree.observation.children[rv]


def call_recorded(fn, tree, implementation):
    """Call fn(implementation) and update the tree to reflect the
    interaction."""
    return fn(WrapperImplementation(tree, implementaiton))

We can then define a cached version of the test function as follows:

class UnknownResult(Exception):
    pass

def simulated_function(tree, implementation)
    """Either returns a previous result we've saved in the tree from
    calling this implementation, or raise UnknownResult."""

    previous = tree.observation

    if previous is None:
        raise UnknownResult()

    if isinstance(previous, Result):
        return previous.value
    else:
        rv = getattr(implementation, previous.method)(*args)
        tree = previous.children[rv]

In order get a cached outcome of an arbitrary implementation it's a little complicated and I can't be bothered to sketch out the code: If you can reset the implementation to empty it's easy, you just call it with the simulated function, reset it, and then call it recorded with the real function. If you can't reset it then you can define a new wrapper implementation that replays the prefix that was observed in simulated_function without calling the underlying implementation, then starts calling the real implementation once you're in unknown territory. You can implement this in terms of a resettable wrapper around the implementation.

How useful is this technique? Unsure. It's pretty niche. I think it might help a lot in Hypothesis though, where we're currently having some significant scalability issues for large and hard to reduce examples, and having something like this will allow us to avoid keeping them around because of how easy it is to recreate the data without reinvoking the test function.

https://notebook.drmaciver.com/posts/2019-02-15-14:37.html

Posted by David R. MacIver

https://notebook.drmaciver.com/posts/2019-02-11-12:07.html

Talking to your imaginary friends as a writing prompt

Published

2019-02-11

This is an idea that has been bumping around in my head for a while and I've never quite got around to trying, but I still think it's a good idea.

A common problem is this: I want to write, but I don't know what to write about.

A possible solution to this is as follows: Make up a fictional character, and have a conversation with them about something.

Even if you don't do anything with this, it's still useful writing practice, but I suspect it will also result in things that might be usefully edited into a long form piece.

Possible prompts within that:

1. Explain some problem you're having to the fictional person.
2. The fictional person doesn't understand something and wants your advice on it.

https://notebook.drmaciver.com/posts/2019-02-11-12:07.html