h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

yeah: it's the Cantor's Diagonalisation thing again.

Take a set S which claims to be P(N), and has size |N|.
That means there is a function S(x), which takes a natural number x, and returns a set of natural numbers

Construct a set C, which is a subset of the natural numbers, as follows: first let C(0) be the smallest number in C, C(1) be the next, etc, etc - in other words, sort them.

C(0) is the smallest number NOT in S(0)
C(1) is the smallest number NOT in S(1) AND greater than C(0)
C(2) is the smallest number NOT in S(2) AND greater than C(1)
etc

Now, C cannot be a member of S, since it isn't equal to S(n) for any n. Therefore, we have a contradiction, so the set S cannot exist.

Hence, |P(N)| > |N|

Version for managing directors: Henry's right.

yes, of course... how silly of me...

I see how you showed that |P(N)| > |N|, but have you also shown that |P(N)| = |R|?

GTB
(God, I love set theory proofs....)

To show that |A|=|B| the easiest way is to show that there is a one to one mapping between A and a subset of B, and between B and a subset of A. This proves that there is a 1-1 mapping between A and B.

{there is a fancy law for the reasoning behind this, but I can't remember it off the top of my head, so you'll have to take my word for it. Or we can play "name that theorem"... }

let A = P(N), and B = R.

For each element x of B, do a conversion something like the following:

0.123456789012345 => A(1,23,456,7890,12345})
-987654321 => {0} disjoint union with B(23,456,7890})
12345.6789 => B({5,43,210}) disjoint union with A({6,78,900})

The A() function multiplies all elements of the set by two, and the B() function multiplies all elements of the set by two and adds one. {hence, A gives evens, and B gives odds}. Negative numbers get a zero, positive numbers don't. This gives you one of the mappings {if you like, proving that |A| >= |B|}. Halfway there.

To go the other way, take your subset of N (element of P(N), and sort it. Start with the interval from 0 to 1. If it contains the element 0, go to the top half of the interval (0.5 to 1.0), otherwise go to the bottom half. Divide again based on whether it contains the element 1, and again on 2, and again, and again.

The interval will get smaller and smaller, tending to some limit. This limit is the real number you set up a 1-1 mapping with. Hence, |A| <= |B|.

Hence, using {fancy theorem name here}, |A| = |B|.

Hey! Wake up!

Just to say I love the article

James

Apologies for being a lowly A-level student - that verged on being 'reductio ad nauseam' for me... what's a disjoint union?

Hey, we finally got a scout on the thread!

A disjoint union is when you take a number of sets (say, X and Y) that are disjoint (ie share no elements) and produce a new set containing all elements in aforementioned sets (eg X and Y). Just like a normal union of sets, but the sets are disjoint.

nice proof!

MyRedDice/Lucinda: Schroeder Bernstein Theorem. Incidentally, the way that |A| = |B| is defined (which may not be clear) is that there is a one to one, onto function from A to B. I.e. you can pair up the elements of A with corresponding elements of B. Schroeder Bernstein just tells you that if youve got a one to one function going from A to a subset of B and another one to one function going from B to a subset of A then you can find a single function that is one to one and onto from A to B.

Maybe we should do an entry about cardinalities, seems people are interested in it. Would be handy if I could find the old conversation in which we did it before though. (and you didn't *have* to use 'A' and 'B' for both the sets and the functions...)

Hey, I'm a scout too!

Back on topic: I'll try and knock up a chunk of text for self-reference in programming - gimme a couple days...

Here goes nothing...
{note, there are a bunch of h2g2 links which go with this - I'll post 'em in later}

Self-Reference in computers

It is said that when programming computers you are creating things from 'pure mindstuff' - building temples out of the air. It is, perhaps, no surprise that programs can contain self-reference.

Recursive functions

A recursive function is a function that calls itself in order to return an answer - the classic example is factorials: in order to calculate 5!, simply deduce 4! and multiply it by 5. In general, we can write fact(x) = x times fact(x-1). This is self-reference because a function is defined *in terms of itself*.

Because recursion is self-reference it is very powerful from a theoretical point of view: having recursion in a language automatically makes it 'turing complete' - which makes it capable of as many things as any other language, but also makes it suffer from the halting problem and similar things.

Reflection

If recursion is the practice of calling your own code, then reflection is the practice of looking at your own code. This is most often used in Object Orientated Languages, such as java. In such a language we can instruct a computer to "know thyself".

For example, suppose we want to create some code which will create new instances of any object we pass it - so if we pass it a Mercedes it will spit out another Mercedes. This process of 'cloning' requires reflection so we can find out *everything* there is to know about the passed object, without initially knowing what it is.

Normally reflection is only permitted at a fairly high level: we have access to what *chunks* of code there are, but not what each individual line is. This is largely because it does not seem to be useful - artificial intelligence has a long way to go before computers can make sense of human-written code in a useful way.

Self-modifying Code

Finally, self-modifying code is code which can *modify* its own code - which is the most powerful (and also by far the most complicated) ability yet. Self-modifying code can effectively redefine itself and what it does on the fly - here's an example:

Suppose you have a function which will return the number of times it has been called. Normally such a function would look something like this:

int count = 0;
int counter() {
count = count + 1;
return count;
}

Using self-modifying code, it would look something like the following:

line 1 - int counter() {
line 2 - *SELF-MODIFY*: add one to the integer in line 3
line 3 - return 0;
line 4 - }

In the past, self-modifying code has been the preserve of those who wrote directly in machine code - and even those hardy fellows treated it with the respect that it deserved. Why use it if it's so dangerous? Simple: it's *fast* - and there are some cases when it's worth spending twice the normal time coding to get that speed.

Nowadays, very few people program in machine code, so it is much, much, less of an issue. However, there are cases where it still occurs. The first is in games like "Core War" - where you create pieces of code which do battle against each other - typically winning by causing the opposing program to execute an illegal instruction. The best programs in these games are invariably self-modifying. The second is simply by mistake: if a program has a bug and starts randomly corrupting memory, some of the corrupted memory may turn out to be its own code - when this happens, all bets are off.

The third is in evolution research. Typically, a bunch of programs are let loose in some virtual playground, where Death and Radiation randomly cull and mutate, respectively, the inhabitants. Just as in natural selection, the programs which are alive at the end are the "fittest" - being able to reproduce faster and more accurately than their forefathers.

Finally, some programming languages allow programs to create new pieces of code, compile them, and then create objects according to the newly compiled blueprint. Misused, this is almost as unstable as the original machine code self-modification, but it does have its uses, for example in writing sophisticated programming tools, and in certain brands of AI.

Whoops, sorry. I really should get into the habit of looking at people's personal spaces.

Now won't one of you make a recommendation here?

Ok, added in the computers section. Also added a bit after the first paragraph of recursion, linking it to endless loops and explaining bottoming out.

Did someone metion habits???
Anyway a good entry if a little confusing I think i'll need to be a little bit older than 13 to understand this kind of stuff

Unfortunately it's not my day to recommend at the moment

How about a reference to that scene in "Being John Malkovitch" where JM goes inside his own head?

I've not seen the film, so I couldn't do that bit. If you think it fits (presumably in the self-reference in art section) then write it up and I'll include it. If it makes a proper point out of JM going inside his own head in a self-referential manner then it should be included...

Ok, having read a couple of reviews on the net, sounds interesting

Can I do that bit then? Do you think it'd be a bit of a spoiler to include it? (The relevant scenes are by far the funniest in the film.)

If you let me, it could be my first credit on an Edited entry...

Yeah go for it. Good point about the spoiler though. Is there any way you can give the gist without giving all of it away? Maybe do the 'theory' bit without the actual lines said or something?

Er... I'll see what I can do... I'll probably have to rent/buy it again, since I've only seen it once, but... I'll try for this Saturday.

(Note to self: join the Royal Procrastinators' Society.)