Posts
Feb 23
Feb 9
Feb 8
Feb 4

We look at strategies for disproving mathematical statements, focusing on universal statements and existential statements.

Feb 3

A mathematician thinks of the cards in a pack, not in terms of their face value and suit, but in terms of their position in the original pack. So if you have a pack of 52 cards, label each card 0 to 51 by its position (the top card is labelled 0, rather than 1, as this makes the maths simpler). “I might want to know where each of these cards might lie after different combinations of the shuffles,” says Praeger. “So each outcome is like a reordering, a permutation, of the cards in the pack. I want to know how many different permutations there are. And perhaps what sort of structure this whole set of reorderings, this permutation group, has.”

The first things we can do is count all the possible permutations you can create by shuffling the cards. If we start with a pack of k cards, then we know there are k different positions in the shuffled pack to place the top card. Then there’s only k-1 slots left for the second card, k-2 slots for the third card, and so on. The total number of possible reorderings is k x (k-1) x (k-2) x … x 2 x 1, otherwise known as the factorial of k, written k!. The collection of all possible permutations of a pack of k cards is called the symmetric group – and the size of the symmetric group for a pack of k cards is k!. For example, for a pack consisting of 6 cards, there are 6! = 6x5x4x3x2x1 = 720 possible permutations in the symmetric group….

Feb 3

The Curry-Howard correspondence can be pithily described as saying “proofs = programs”. The statement is short, alliterative, and rather beautiful. As a professional mathematician I know exactly what a proof is; as an amateur programmer I have a pretty clear idea about what a program is, and the concept that they might be in some sense the same thing is both enigmatic and appealing. A proof is a logical sequence of statements deducing a theorem from the the rules of maths; a program is a logical sequence of commands producing valid code from the rules of the programming language being used. When learning Lean I saw the correspondence in action many times, and so it actually took quite some time for the penny to drop: the Curry-Howard correspondence is not actually true.

Of course something is true, but what is not true is any statement of this form where “proof” is interpreted as “what the pure mathematicians in my department do”. What is true is that if you stick to constructive maths or intuitionistic logic or one of the flavours of maths where you’re not allowed to use the axiom of choice or the law of the excluded middle — in other words a version of maths which is unrecognisable to over 95% of pure mathematicians working in mathematics departments — then you might be in good shape. But that is not what I see happening in my mathematics department or the other mathematics departments which I’ve had experience of. Some proofs are not programs.