poetix (old content)

oh build your ship of death

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 [tex]{H}[/tex] of elements of a group [tex]{G}[/tex] is a subgroup if and only if [tex]{x} . {y}^{-1} \epsilon {H}[/tex] for all [tex]{x}[/tex] and [tex]{y}[/tex] in [tex]{H}[/tex].”. 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 [tex]{H}[/tex] is a group, in other words that:

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

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

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

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

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

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