Proof by contradiction

Here I explain proof by contradiction so that anyone who has ever done a sudoku and seen algebra may understand it.

Sequence on Awodey's Category Theory

In the summer of 2015, I worked through Awodey’s Category Theory, and I produced a large collection of posts as I tried to understand its contents. These posts are probably not of much interest to anyone who is just looking for something to read, so they’re siloed off.

Motivational learning

In which I am a wizard.

Sometimes as a student, the work piles up and I start to think “I’ll never finish this”. It becomes easy to think that there’s no point in working because the work will never be over. When that happens to me, I imagine that my course is magic/alchemy/something with flashy special effects. I’m going through the Wizardry Academy, and I’ll graduate able to manipulate the four elements. Even if I’m not the best in the year at it, I’m still able to manipulate the elements, and if I work at it, I’ll be able to manipulate them better and in flashier ways - that’s not something most people can do!

Latin translation tips

I’m clearing out my computer, and found a file which may as well be here.

Chunking:

  1. The first thing to do is to run through the sentence, identifying the verbs and anything that looks like it might be a verb (even in a strange form, like “passus” or “ascendere”).
  2. Run through a second time, looking for structures like “ut + subjunctive” and “non solum… sed etiam…” - if a verb you spotted is in an odd form, this is when you look quickly for why it’s in that form.
  3. Look for any subordinate clauses (like “dixit Caecilius, qui in horto laborabat…”)
  4. If you see an adjective-looking thing, it probably has to go with a noun.
  5. With that in mind, chunk the text, remembering that two verbs in the same chunk is unlikely unless one is something like “dixit” or “poterat”, which can modify another verb. Remember that chunks shouldn’t be too long, but lots of really short words together might not count against the length limit. Try reading out each chunk - rhythm takes time to learn to grasp, but it might help you.

Once the text is chunked:

  1. Remember that your chunking is probably wrong somewhere, but also is probably broadly right.
  2. In each chunk, if there’s a nominative and a verb then try and translate those first. Then think about what the verb “expects”; if the verb is looking for an accusative, find an accusative, while if it’s looking for a dative, find a dative. For example, “docet” = “he teaches” is looking for an accusative, while “trahet” = “he drags” is looking both for an accusative (“he drags something”) and possibly a dative (“he drags something somewhere”).
  3. If it looks like a jumble of words, identify the case of everything (in poetry, it can help if you scan the text) - this should tell you what goes with what. Don’t be too fussy about getting the right case, though - I’d be happy with “dative or ablative”, most of the time, because that’s usually clear from context - as long as you have the right case among your options!

Guessing vocab:

Try and work out what the principal parts of a verb are. The English word from a given Latin one almost always comes from the past passive participle (the fourth principal part), by adding “tion” instead of “us”: “passus” -> “passion” [a bit misleading if you don’t know about the Passion of the Christ, because it means “suffering”], “traho” -> “tractus” -> “traction”; it actually means “drag”. How to guess the principal parts is the kind of thing you learn with time, but as a general rule, “t” -> “s” (as in “patior passus”) and almost everything else goes to “ct”: “pingere pictus” from which “depiction” so “painting”, “facere factus” from which “manufaction” which isn’t really English but tells you it means “making”, etc.

Matrix puzzle

I recently saw a problem from an Indian maths olympiad:

There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f is defined as the sum of the products of the elements of each row, over all rows and g is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

Film recommendation, Interstellar

I’ve just come back from seeing Interstellar, a film of peril and physics. This post will be spoiler-free except for sections which are in rot13.

I thought the film was excellent. My previous favourite film in its genre was Sunshine, but this beats it in many ways, chiefly that the physics portrayed in Interstellar - relativity, primarily - is not so wrong that it’s immediately implausible. Indeed, some physics-driven plot twists (such as gvqny sbeprf arne n oynpx ubyr) I called in advance, which is a testament to how closely the film matched my physical expectations. My stomach nearly dropped out when the characters realised what relativity meant for them.

Christmas carols

In which I provide my favourite carols and my favourite renditions of them.

In no particular order, except that 1) must be at the start and 9) at the end.

  1. Once in Royal David’s City. Always opens the Festival of Nine Lessons and Carols. Has the same problem as 9) in that the only nice recordings seem to have congregations in, but I suppose that’s all part of it.

  2. The Three Kings. My favourite. This performance (King’s College) has a soloist who is a bit strident, I think, but all the other ones I’ve listened to are even stridenter.

Sum-of-two-squares theorem

*Wherein I detail the most beautiful proof of a theorem I’ve ever seen, in a bite-size form suitable for an Anki deck.

Statement

There’s no particularly nice way to motivate this in this context, I’m afraid, so we’ll just dive in. I have found this method extremely hard to motivate - a few of the steps are a glorious magic.

  • \(n\) is a sum of two squares iff in the prime factorisation of \(n\), primes 3 mod 4 appear only to even powers.

Proof

We’re going to need a few background results.

Python, script shadowing

A very brief post about the solution to a problem I came across in Python.

In the course of my work on Sextant (specifically the project to add support for accessing a Neo4j instance by SSH), I ran into a problem whose nature is explained here as the Name Shadowing Trap. Essentially, in a project whose root directory contains a bin/executable.py script, which is intended as a thin wrapper to the module executable, you can’t import executable, because the bin/executable.py shadows the module executable.

Parables, chapter 1, verses 1-10

One day, a group of investors came to Bezos in the Temple and begged of him, “You are known throughout the land for your wisdom. Please tell us: what lessons did you learn early in life, which we have not yet learnt?”

Bezos replied thus.

“When I was but a child, when I had not yet seen seven summers, I discovered that my teacher had a bountiful store of chocolates hidden in the stationery cupboard. Being of an enterprising frame of mind, I proceeded to eat one of them every day for a week.” For he was mindful of the need to preserve the source of good things.

Perfect pitch

I have a limited form of perfect (absolute) pitch, which I am sometimes asked about. Often it’s the same questions, so here they are. No doubt people with better perfect pitch than mine will be annoyed at this impudent upstart claiming the ability, but perfect pitch comes on a spectrum anyway. Apparently some people can identify notes to within the nearest fifth of a semitone, while some can only identify the semitone closest to the note. I am a bit further towards the “tone-deaf” end of that spectrum.

Music practice

A couple of weeks ago, someone opined to me that there was a type of person who was just able to sit down and play at the piano, without sheet music.

I, myself, am capable of playing precisely one piece inexpertly, from memory, at the piano. (My rendering of that piece is nowhere near the arranger’s standard.) I can play nothing else without sheet music. I very much think that this is the natural state for essentially every musician who has not spent thousands upon thousands of hours practising in a general way. That is, almost no-one can naturally sit down and play a piece from memory without a lot of work beforehand, and almost no-one can improvise well without a great deal of effort directed either at learning how to improvise, or at learning generally the mechanics of playing.

What maths does to the brain

In my activities on The Student Room, a student forum, someone (let’s call em Entity, because I like that word) recently asked me about the following question.

Isaac places some counters onto the squares of an 8 by 8 chessboard so that there is at most one counter in each of the 64 squares. Determine, with justification, the maximum number that he can place without having five or more counters in the same row, or in the same column, or on either of the two long diagonals.

Solvability of nonograms

Recently, a friend re-introduced me to the joys of the nonogram (variously known as “hanjie” or “griddler”). I was first shown these about ten years ago, I think, because they appeared in The Times. When The Times stopped printing them, I forgot about them for a long time, until two years ago, or thereabouts, I tried these on a website. I find the process much more satisfying on paper with a pencil than on computer, so I gave them up again and forgot about them again.

Possible cons of Soylent

I have seen many glowing reviews of Soylent, and many vitriolic naturalistic arguments against it. What I have not really seen is a proper collection of credible reasons why you might not want to try Soylent (that is, reasons which do not boil down to “it’s not natural, therefore Soylent is bad” or “food is great, therefore Soylent is bad”).

This page used to contain citations in the form of links to the Soylent Discourse forum at discourse.soylent.com. However, that site is now defunct.

Proof that symmetric matrices are diagonalisable

This comes up quite frequently, but I’ve been stuck for an easy memory-friendly way to do this. I trawled through the 1A Vectors and Matrices course notes, and found the following mechanical proof. (It’s not a discovery-proof - I looked it up.)

Lemma

Let \(A\) be a symmetric matrix. Then any eigenvectors corresponding to different eigenvalues are orthonormal. (This is a very standard fact that is probably hammered very hard into your head if you have ever studied maths post-secondary-school.) The proof of this is of the “write it down, and you can’t help proving it” variety:

Discovering a proof of Sylvester's Law of Inertia

This is part of what has become a series on discovering some fairly basic mathematical results, and/or discovering their proofs. It’s mostly intended so that I start finding the results intuitive - having once found a proof myself, I hope to be able to reproduce it without too much effort in the exam.

Statement of the theorem

Sylvester’s Law of Inertia states that given a quadratic form \(A\) on a real finite-dimensional vector space \(V\), there is a diagonal matrix \(D\), with entries \(( 1_1,1_2,\dots,1_p, -1_1, -1_2, \dots, -1_q, 0,0,\dots,0 )\), to which \(A\) is congruent; moreover, \(p\) and \(q\) are the same however we transform \(A\) into this diagonal form.

Sequentially compact iff compact

Prof Körner told us during the IB Metric and Topological Spaces course that the real meat of the course (indeed, its hardest theorem) was “a metric space is sequentially compact iff it is compact”. At the moment, all I remember of this result is that one direction requires Lebesgue’s lemma (whose statement I don’t remember) and that the other direction is quite easy. I’m going to try and discover a proof - I’ll be honest when I have to look things up.

Cayley-Hamilton theorem

This is to detail a much easier proof (at least, I find it so) of Cayley-Hamilton than the ones which appear on the Wikipedia page. It only applies in the case of complex vector spaces; most of the post is taken up with a proof of a lemma about complex matrices that is very useful in many contexts.

The idea is as follows: given an arbitrary square matrix, upper-triangularise it (looking at it in basis \(B\)). Then consider how \(A-\lambda I\) acts on the vectors of \(B\); in particular, how it deals with the subspace spanned by \(b_1, \dots, b_i\).

Sample topology question

As part of the recent series on how I approach maths problems, I give another one here (question 14 on the Maths Tripos IB 2007 paper 4). The question is:

Show that a compact metric space has a countable dense subset.

This is intuitively clear if we go by our favourite examples of metric spaces (namely \(\mathbb{R}^n\), the discrete metric and the indiscrete metric). Indeed, in \(\mathbb{R}^n\), which isn’t even compact, we have the rationals (so the theorem doesn’t give a necessary condition, only a sufficient one); in the indiscrete metric, any singleton \({x }\) is dense (since the only closed non-empty set is the whole space); in the discrete metric, where every set is open, we can’t possibly be compact unless the space is finite, so that’s why the theorem doesn’t hold for a topology with so many sets.