### Russell's Paradox

Sep. 17th, 2007 05:59 pm**lederhosen**

Following on from yesterday's post, I thought I might explain a bit about the problem Russell discovered with set theory.

Most of you probably ran into set theory at some stage during school - Venn diagrams, that sort of thing. If you're rusty on that or never learned it, just think of a 'set' as a sort of magical octopus with lot of tentacles that can reach out and touch things - and not just tangible things, but some pretty intangible things like "the number five" or "midday".

All these octopuses are pretty much alike, so the only way to tell them apart is by looking at what they're touching with their tentacles - and to make life simpler, I'll tell you that if two octopuses are touching exactly the same things, they are in fact the

For octopuses that are only touching a few things, mathematicians might use curly brackets to show what they're touching - for instance, {1, 2, 3} is the octopus that has tentacles on the numbers 1, 2, and 3, and nothing else. (By the way, you can usually take that "and nothing else" as read when somebody identifies an octopus.)

For more enthusiastic octopuses, that gets unwieldy, and we might identify them by a rule - for instance, "the octopus touching all the even numbers". I'll get back to that idea in a moment.

It's possible for two octopuses to touch the same things - for instance, {1, 2, 3} and {2, 3, 4, 5, 6} are both touching the numbers 2 and 3. And sometimes, they even end up touching other octopuses.

For instance, to visualise {{1, 2}, {2, 3}}: think of a red octopus {1,2}touching the numbers 1 and 2, and a blue octopus {2,3} touching 2 and 3. Now think of a green octopus touching both the red and blue ones - that octopus is {{1,2},{2,3}}.

There's also a purple octopus, {{1,2},{2,3},2}, which touches the red and blue octopuses - and also touches the number 2 directly. This is

By the way, I should mention here that for reasons of etiquette, octopuses never touch tentacles - the only acceptable contact is tentacle-to-head - and each octopus only counts what it's touching with its own tentacles. For instance, in the example above, the green octopus touches the red and blue ones, but the red and blue ones don't count as touching the green one.

Mathematicians worked out all sorts of useful rules about octopuses. For instance, if everything that Tartan Octopus touches is also touched by Paisley Octopus, and everything that Paisley Octopus touches is also touched by Polkadot Octopus... then Polkadot Octopus has its tentacles on everything Tartan Octopus touches. That might seem pretty trivial, but mathematicians are a cautious lot; they like to start with things that are very, very obvious, and work up from there.

In 1889, Giuseppe Peano - building on the work of Richard Dedekind - figured out a way to represent the counting numbers as octopuses*. He started with one who might be considered the ancestor of all octopuses - {}, who is simply a round blob with a beak and no tentacles at all. This fellow, he equated to the number 1.

Next, Peano added {{}}, an octopus who touches only the Great Ancestral Octopus, who equates to the number 2. And then, as you might have guessed, he went to {{{}}}, and {{{{}}}}, and so on - a conga line of one-tentacled octopuses stretching off to infinity. For each octopus, he defined "plus one" to mean "the octopus in the conga line who is touching you".

He also taught the octopuses in that chain how to play a game: he'd ask all of them to mimic the one they were touching, and then ask {} to blush a colour. As long as the others could be trusted to follow that rule, it followed that they'd all end up the same colour as their progenitor {} - which is another way of looking at the process of 'induction' that I mentioned previously.

With a few more rules like this, he managed to turn these octopuses into a sort of representation of the counting numbers - for instance, he taught them an 'addition game', where you pick two octopuses (or one octopus twice) and get them all changing colour according to certain rules, until one octopus is red and all the others are blue. For instance, if you pick {{}} twice, the game ends up with {{{{}}}} blushing red and all the others blue - which is to say, "two plus two equals four".

So far, so good. But as I mentioned before, mathematicians weren't always satisfied with octopuses that just had a few tentacles. They wanted to muck around with octopuses that had

You can think of these rules as a sort of 'membership test' - each octopus has a name-tag with its own rules ("I only touch even numbers", "I only touch octopuses who only touch even numbers") and obeys those rules in choosing what it touches.

Mathematicians worked for a long time on the assumption that for any meaningful rule you could come up with - even if it was something silly like "anything with a pulse" - there was an octopus following that rule.

Then along came Bertrand Russell with a name-tag he'd found lying on the floor:

"If it doesn't touch itself, I touch it. Otherwise, I don't."

This is a pretty easily tested rule - for any octopus, you can look at it and see whether it's touching itself on the head. But where is the octopus who would wear that name-tag?

Starting from there, it's painfully obvious that there are a lot of other nametags that can't possibly be attached to an octopus. A lot of mathematicians' assumptions about octopuses were dangerously wrong. So what Russell had to do was go out and establish some new rules about what sorts of octopuses could exist, and what sorts couldn't, so we could go on relying on things like Peano's conga-line of octopuses in the knowledge that they weren't about to vanish in a puff of logic.

*Well, he just called them 'sets', but I'm having fun with this analogy. And I've taken some liberties with Peano's original formulation, not least because I'm too lazy to look it up right now.

Most of you probably ran into set theory at some stage during school - Venn diagrams, that sort of thing. If you're rusty on that or never learned it, just think of a 'set' as a sort of magical octopus with lot of tentacles that can reach out and touch things - and not just tangible things, but some pretty intangible things like "the number five" or "midday".

All these octopuses are pretty much alike, so the only way to tell them apart is by looking at what they're touching with their tentacles - and to make life simpler, I'll tell you that if two octopuses are touching exactly the same things, they are in fact the

*same octopus*.For octopuses that are only touching a few things, mathematicians might use curly brackets to show what they're touching - for instance, {1, 2, 3} is the octopus that has tentacles on the numbers 1, 2, and 3, and nothing else. (By the way, you can usually take that "and nothing else" as read when somebody identifies an octopus.)

For more enthusiastic octopuses, that gets unwieldy, and we might identify them by a rule - for instance, "the octopus touching all the even numbers". I'll get back to that idea in a moment.

It's possible for two octopuses to touch the same things - for instance, {1, 2, 3} and {2, 3, 4, 5, 6} are both touching the numbers 2 and 3. And sometimes, they even end up touching other octopuses.

For instance, to visualise {{1, 2}, {2, 3}}: think of a red octopus {1,2}touching the numbers 1 and 2, and a blue octopus {2,3} touching 2 and 3. Now think of a green octopus touching both the red and blue ones - that octopus is {{1,2},{2,3}}.

There's also a purple octopus, {{1,2},{2,3},2}, which touches the red and blue octopuses - and also touches the number 2 directly. This is

*not*the same octopus as {{1,2},{2,3}}.By the way, I should mention here that for reasons of etiquette, octopuses never touch tentacles - the only acceptable contact is tentacle-to-head - and each octopus only counts what it's touching with its own tentacles. For instance, in the example above, the green octopus touches the red and blue ones, but the red and blue ones don't count as touching the green one.

Mathematicians worked out all sorts of useful rules about octopuses. For instance, if everything that Tartan Octopus touches is also touched by Paisley Octopus, and everything that Paisley Octopus touches is also touched by Polkadot Octopus... then Polkadot Octopus has its tentacles on everything Tartan Octopus touches. That might seem pretty trivial, but mathematicians are a cautious lot; they like to start with things that are very, very obvious, and work up from there.

In 1889, Giuseppe Peano - building on the work of Richard Dedekind - figured out a way to represent the counting numbers as octopuses*. He started with one who might be considered the ancestor of all octopuses - {}, who is simply a round blob with a beak and no tentacles at all. This fellow, he equated to the number 1.

Next, Peano added {{}}, an octopus who touches only the Great Ancestral Octopus, who equates to the number 2. And then, as you might have guessed, he went to {{{}}}, and {{{{}}}}, and so on - a conga line of one-tentacled octopuses stretching off to infinity. For each octopus, he defined "plus one" to mean "the octopus in the conga line who is touching you".

He also taught the octopuses in that chain how to play a game: he'd ask all of them to mimic the one they were touching, and then ask {} to blush a colour. As long as the others could be trusted to follow that rule, it followed that they'd all end up the same colour as their progenitor {} - which is another way of looking at the process of 'induction' that I mentioned previously.

With a few more rules like this, he managed to turn these octopuses into a sort of representation of the counting numbers - for instance, he taught them an 'addition game', where you pick two octopuses (or one octopus twice) and get them all changing colour according to certain rules, until one octopus is red and all the others are blue. For instance, if you pick {{}} twice, the game ends up with {{{{}}}} blushing red and all the others blue - which is to say, "two plus two equals four".

So far, so good. But as I mentioned before, mathematicians weren't always satisfied with octopuses that just had a few tentacles. They wanted to muck around with octopuses that had

*infinitely many*tentacles, and when you're doing that you don't have time to write out a list of what each octopus is touching. Instead, they worked on a rules-based approach - "octopus touching all even numbers", "octopus touching all octopuses who only touch even numbers", that sort of thing.You can think of these rules as a sort of 'membership test' - each octopus has a name-tag with its own rules ("I only touch even numbers", "I only touch octopuses who only touch even numbers") and obeys those rules in choosing what it touches.

Mathematicians worked for a long time on the assumption that for any meaningful rule you could come up with - even if it was something silly like "anything with a pulse" - there was an octopus following that rule.

Then along came Bertrand Russell with a name-tag he'd found lying on the floor:

"If it doesn't touch itself, I touch it. Otherwise, I don't."

This is a pretty easily tested rule - for any octopus, you can look at it and see whether it's touching itself on the head. But where is the octopus who would wear that name-tag?

Starting from there, it's painfully obvious that there are a lot of other nametags that can't possibly be attached to an octopus. A lot of mathematicians' assumptions about octopuses were dangerously wrong. So what Russell had to do was go out and establish some new rules about what sorts of octopuses could exist, and what sorts couldn't, so we could go on relying on things like Peano's conga-line of octopuses in the knowledge that they weren't about to vanish in a puff of logic.

*Well, he just called them 'sets', but I'm having fun with this analogy. And I've taken some liberties with Peano's original formulation, not least because I'm too lazy to look it up right now.

## no subject

Date: 2007-09-17 10:36 am (UTC)cheshire-bitten.livejournal.comIt's now up at work.

## no subject

Date: 2007-09-17 12:15 pm (UTC)chaos-crafter.livejournal.com## no subject

Date: 2007-09-17 12:23 pm (UTC)tyggerjai.livejournal.comSo, if the octopus wearing the nametag starts out touching itself, then it falls into the set of octopii it shouldn't touch, so it stops touching itself, thus becoming an octopus it should touch, so it touches itself, thus becoming an octopus it shouldn't touch ... etc.

jai.

.

## no subject

Date: 2007-09-17 05:44 pm (UTC)panacea1.livejournal.comWON'T. GO. AWAY.Thank you, Lederhosen.

## no subject

Date: 2007-09-17 08:51 pm (UTC)tyggerjai.livejournal.comjai.

.

## no subject

Date: 2007-09-18 07:47 am (UTC)lederhosen.livejournal.comMy work here is done!

## no subject

Date: 2007-09-21 10:46 am (UTC)thorfinn## no subject

Date: 2007-09-21 01:52 pm (UTC)lederhosen.livejournal.com## no subject

Date: 2007-09-17 12:28 pm (UTC)tyggerjai.livejournal.comjai.

.

## no subject

Date: 2007-09-18 07:58 am (UTC)lederhosen.livejournal.comIf you start with "let X be the set containing all sets that do not contain themselves", and accept that such a set exists, you can prove

anything, and while that particular phrasing might make the pitfall obvious, it's not as obvious whatotherrules might lead to paradox.## no subject

Date: 2007-09-17 03:23 pm (UTC)publius1.livejournal.com## no subject

Date: 2007-09-17 08:19 pm (UTC)mr-figgy.livejournal.com## no subject

Date: 2007-09-17 08:33 pm (UTC)terrycloth.livejournal.comThat was near the end of the semester, though, so I don't know where he was going with it. We didn't get to where they'd even define what addition meant.

## no subject

Date: 2007-09-17 11:18 pm (UTC)michiexileAddition might work - with "having size" replaced by "having size at least" - like follows:

1 + 1 = {x union y : x in 1, y in 1}

Then you would get some member sets in 1+1 having cardinality 1, but you would most certainly get a lot of member sets having cardinality 2. And so on.

## no subject

Date: 2007-09-17 11:16 pm (UTC)michiexileAnd by dividing the interesting things in octopi and Great Ones, you can outrule various nametags as not applicable, since they couldn't possibly belong to octopi, but also couldn't possibly belong to Great Ones.

## no subject

Date: 2007-09-29 03:36 am (UTC)winterkoninkje.livejournal.com~~set~~octopus was defined as zero rather than one, but all the same. Not that I would question ye O Great Loremaster. Tell us another story Great Loremaster, tell the one about the hotel with infinitely many rooms!## no subject

Date: 2007-09-29 03:38 am (UTC)winterkoninkje.livejournal.com## no subject

Date: 2007-09-29 06:50 am (UTC)lederhosen.livejournal.comActually, I believe the empty~~set~~octopus was defined as zero rather than one, but all the same.That's the usual formulation these days, and it's what I encountered in university, but if Wikipedia is to be believed Peano's original version started at 1.

## no subject

Date: 2007-09-30 11:10 pm (UTC)winterkoninkje.livejournal.com