Orchid XP v8 wrote:
> ...OK, and this is the kind of thing that I sit down and read and end up 
> feeling utterly perplexed.
> 
> Logic, set theory, category theory, number theory, complexity theory, 
> topology... they all seem to abound with utterly counter-intuitive laws 
> and theorums. It's really quite mind-bending.

Don't be intimidated, I think that the diagonalization arguments are 
actually rather easy to understand for someone who doesn't have a lot of 
background in this sort of thing.  It's a bit mind blowing at first, but 
at some point it'll click and everything will make sense, something 
which I haven't found to be the case with eg. set theory.

I suggest you start by proving that there's the same number of rationals 
as natural numbers.  Once you've done that study Cantor's diagonal 
argument until you understand why there's more reals than natural 
numbers, and thus more reals than rationals.  Ask for help if you're 
confused and I'll provide it when I read the newsgroup (or more likely, 
someone else will beat me to it).

 From there I'd take a look at the definition of the busy beaver 
function as an example of the same sort of technique on computable 
functions, and then look at the halting theorem in the same light. 
Sooner or later it should all start to seem intuitive and 
straightforward, even if it's a bit mind-bending at the moment.

Post a reply to this message