Thread: Different kinds of infinity?

Originally Posted by Xei

Note that it is not, as you said (I imagine you said it offhandedly), actually necessary to show that each disc has a unique n (in other words to show injectivity); in fact, with my mapping, it's pretty much as uninjective as can be; each disc has infinite elements in N which map to it.

That confuses me a little. I've been taught that a set is countably infinite iff there is a bijection between N and that set. Why don't we require injectivity here. Is it that we're only talking about "countable" and not "countably infinite"?

Originally Posted by Xei

I wouldn't say that an infinite set is not well-defined.

That's not really what I said. I said that a set with an infinite definition is not well-defined. Not that it matters now. The whole idea of an infinite definition was out of place here, anyway.

Yes, I understand that's what you meant. You seemed to be okay with something like an infinite number of circles radius 1/4 centred at every point in N^2 (for example) where there was an obvious rule, but not with the idea of an infinite collection of discs with no pattern, but rather specified by an infinite list.

That confuses me a little. I've been taught that a set is countably infinite iff there is a bijection between N and that set. Why don't we require injectivity here. Is it that we're only talking about "countable" and not "countably infinite"?

Whilst I believe it is true that it's countably infinite if and only if there exists a bijection, it is not actually necessary to create a bijection to prove that something is countably infinite; that is too strong.

For example, the set of even numbers. We can count this with the identity function mapping to the set N,

i(n) = n

which is an injection but not a surjection.

This shows us however that the even numbers are countable, because there exists a element in N to count each element in the evens, without leaving any out.

The evens are also patently infinite. Hence we've shown the evens are countably infinite.

A bijection does exist of course ( f(n) = n/2 ), and you can also create an injection from N onto the evens (e.g. f(n) = 4n ).

I think it's fairly intuitive: you don't need to map to every element in N to show that your set 'fits into N'; you can do it in a lazy manner if you wish.

It's slightly weird, but I guess this works because of the nature of infinity: if you insisted on a bijection it'd be trivial to create one. You have an injection onto N; you find the smallest element in N which is mapped to and map it to 1, then the next smallest and map it to 2, etcetera, shifting everything along and removing all the gaps. The analogy of the infinite hotel comes to mind.

I looked through the thread and it doesn't seem that anybody has tackled the figure eights. It's not really that hard and I'm curious to see what other people come up with.