# Proof Positive

First of all, if you’ve never encountered Tupper’s Self-Referential Formula, you’ve missed a true wonder of nature/mathematics. That has next to nothing to do with what follows, but I found it whilst googling the Latex plugin (less exciting than it sounds) needed to render this post properly, and it is the most astounding thing I’ve seen in a long while. I am having serious trouble believing it really works. How the hell…? And are there any more of those things? (I suspect an infinite number, but how do you find them?)

So, I bought a book on Algebraic Topology, started reading it on the train, just the opening section on “prerequisites” (a bit of naïve set theory - no problem - a bit of algebra, slightly less familiar). There’s a discussion of groups, in which it’s mentioned that “it can be shown that a set $${H}$$ of elements of a group $${G}$$ is a subgroup if and only if $${x} . {y}^{-1} \epsilon {H}$$ for all $${x}$$ and $${y}$$ in $${H}$$.”. I was taking reading notes, and wrote “How???”…

Well, here’s how. I worked most of it out on the train, and the rest on the bike ride home.

We have to prove that $${H}$$ is a group, in other words that:

• It is closed over the “multiplication” operation, e.g. if $${x}$$ and $${y}$$ are in the group, then so is $${x} . {y}$$.
• It contains an element $${e}$$, such that $${x} . {e}={e} . {x}={x}$$.
• For every element $${x}$$ in the group, there is a unique corresponding “inverse” element, $${x}^{-1}$$ in the group such that $${x}.{x}^{-1}={e}$$.

Let’s start with proving that $${e} \epsilon {H}$$. This is actually quite easy. We know that $${x} . {y}^{-1} \epsilon {H}$$ for all $${x}$$ and $${y}$$ in $${H}$$. What happens if $${x}$$ and $${y}$$ are the same? In that case, $${x} . {x}^{-1} \epsilon {H}$$, and since $${x} . {x}^{-1}={e}$$, that means that $${e} \epsilon {H}$$. Hooray.

Now we must prove that for all $${x} \epsilon {H}$$, $${x}^{-1} \epsilon {H}$$. This is also quite easy. Since we know that $${e} \epsilon {H}$$, let $${x}={e}$$. That means that for all $${y} \epsilon {H}$$, $${e}.{y}^{-1} \epsilon {H}$$. And $${e}.{y}^{-1}={y}^{-1}$$, so for all $${y} \epsilon {H}$$, $${y}^{-1} \epsilon {H}$$. Hooray again.

Now we can prove that $${x}.{y} \epsilon {H}$$. First we must show that $$({x}^{-1})^{-1}={x}$$. Let $${z}={x}^{-1}$$. $${z}.{z}^{-1}={e}={x}^{-1}.{x}$$, therefore $${x}^{-1}.{z}^{-1}={x}^{-1}.{x}$$. It follows that $${z}^{-1}={x}$$, in other words that $$({x}^{-1})^{-1}={x}$$.

Now, since $${x}.{y}^{-1} \epsilon {H}$$ for all $${x} \epsilon {H}$$ and $${y} \epsilon {H}$$, and for all $${y} \epsilon {H}$$, $${y}^{-1} \epsilon {H}$$, it follows that $${x}.({y}^{-1})^{-1} \epsilon {H}$$, therefore $${x}.{y} \epsilon {H}$$, Q.E.D.

It’s a bit like the proof that you can derive all of the boolean logical operators from NAND…