OddThinking

As further evidence that I am a sad, sad nerd, I proffer a story from a long, long, long time ago, that I really should have let go by now.

In my third year of university, I studied a subject called Theory Of Computation.

The assessment was in two parts.

The first was a “Take Home Exam” (I would have merely called it an assignment.) After it had been submitted and marked, they gave our exams back to look at. A few of us compared our answers, and I was surprised to see that one close friend of mine had solved one of the more mathematical problems in a third of the space it had taken me.

From memory, the problem had boiled down to this:

A set B is said to have the property R if for all elements e in B, e has the property mumble, mumble, mumble.
The set S has the property R.
The set SS is a subset of S, such that blah blah blah
Prove or disprove that SS has the property R.

From memory, her answer used the following argument:

S has the property R.
Therefore, for all e in S, e has the property mumble, mumble, mumble.
Therefore, for all e in any subset of S, e has that property.
Therefore, for all e in SS, e has that property.
Therefore, SS has the property R.

The marker ticked this logic, and she got full marks for the question.

I don’t remember the exact conversation when I looked at this, but remembering my skills of tact and nuance, I suspect I said something supportive like “No! That’s all wrong!”

That started a… err… spirited discussion amongst the group.

I was told that SS did so have the property R and so the logic was right. I should have gently explained that an invalid syllogism doesn’t imply a false conclusion. Instead I got tongue-tied trying to explain that I knew SS had the property R; I had written up a full page proving it myself.

I was accused of trying to get a friend’s assignment marked down. Nothing was further from the truth. I didn’t care about her extra mark; good luck to her. This wasn’t a personal attack; this was a bit of nerdy pedantry, about some interesting logical fallacies. I was unable to communicate this motive.

Mainly, I was told that the logic was perfect. I argued that it actually depended on the mumbled bit.

I actually went off and came up with some new, much simpler, definitions of the sets and the mumbled bits, and re-applied the logic line-by-line, side-by-side with the original proof – and showed it lead to a contradiction. I thought this would clearly demonstrate the logic itself was flawed. Another friend inspected it and declared my example to be invalid, but the original valid! It was the same damned logic!

I was getting frustrated at how badly I was communicating this simple idea. At this point, something pierced my skull. My principled drive for logical purity was pissing off everyone involved. I bit my tongue, and let the matter drop.

As I lay awake this morning, thinking about this story, I have realised I never did really let the matter drop! And that I finally have a chance to right this wrong without anyone involved getting hurt.

Here we go.

The key issue here is in the definition of the property “mumble, mumble, mumble“. If the property had been something simple like “e is positive” or “e is not an elephant”, it would have been fine. That is, if it could be represented as a a boolean function, f(e), then the logic would have held.

But the actual definition was more complex. Let me restate it again, without any mumbling this time.

A set B is said to have the property R if for all elements e in B, -e is also an element of B.

Now this can’t be expressed as a simple function f(e). It must be expressed as f(e,B).

So what?

Well if we follow the original logic through, spelling out the definitions, we get a different result.

S has the property R.
Therefore, for all e in S, -e is in S.
Therefore, for all e in any subset of S, -e is in S.
Therefore, for all e in SS, -e is in S.
BUT! We still don’t know if -e is in SS, so we are stuck!

To prove the SS has the property R, required a page of working exploring the definition of “blah blah blah” in the original problem. You can’t take a shortcut, because the variable B leaked into the definition of the property of the element.

See! I was right! Ahh that’s better. Now that the world finally realises this, perhaps I can finally let it rest.