Is this conception of countable vs. uncountable infinity adequate?

Solution 1:

The notion of "countably infinite" is well named. Another word you can use is "enumerable," which is even more descriptive in my opinion.

I understand your intuition on the subject and I see where you're coming from. Let me try to give you some insight into the agreements about infinity that have been reached over the years by the mathematicians who've worked on this problem. (This is what I wish someone had explained to me.)

"Countably infinite" just means that you can define a sequence (an order) in which the elements can be listed. (Such that every element is listed exactly once.)

The natural numbers are the most naturally "countable"—they're even called "counting numbers"—because they are the most basic, natural sequence. The word "sequence" itself is wrapped up in what we mean by natural numbers, which is just one thing following another, and the next one coming after that, and the next one after that, and so on in sequence.

But the integers are countable as well. In other words, they are enumerable. You can specify an order which lists every integer exactly once and doesn't miss any of them. (Actually it doesn't matter, for the meaning of "countable," if a particular element gets listed more than once, because you could always just skip it any time it appears after the first time.)

Here is an example of how you can enumerate (count, list out) every single integer without missing any:

$0, 1, -1, 2, -2, 3, -3...$

The rational numbers are also countable, again because you can define a sequence which lists every rational number. The fact that they are listed means (at the same time) that they are listed in a sequence, which means that you can assign a counting number to each one.

The real numbers are not countable. This is because it is impossible to define a list or method or sequence that will list every single real number. It's not just difficult; it's actually impossible. See "Cantor's diagonal argument."

This will hopefully give you a solid starting point to understanding anything else about infinite sets which you care to examine. :)

Solution 2:

You are somewhat right, in the sense that it is true that $\mathbb N^n$ is countable for positive $n$, and $\mathbb N^\mathbb N$ is uncountable (which is the set of functions from $\mathbb N$ to $\mathbb N$). Even $\{1,2\ldots n\}^\mathbb N$ is uncountable for $n>1$ (think about writing the numbers in the interval $(0,1]$ in an arbitrary base).

So a reliable way to prove that a set $A$ is countable is to build an injective function $f:A\rightarrow \mathbb N^n$, and a reliable way to prove that a set $B$ is uncountable, is to build an injective function $g:\{1,2\ldots n\}^\mathbb N\rightarrow B$

Solution 3:

You are using non-standard imagery but, as I read it, the point where the "intuition" you describe fails is this:

Now we are at the point where we run into an infinite number of axes - and this corresponds to the set of real numbers $\mathbb{R}$ no longer being countably infinite.

Consider for example the set of algebraic numbers which contains all numbers that are roots of some polynomial with rational coefficients. This set obviously includes $\mathbb{Q}\,$, and it is a strict superset of $\mathbb{Q}$ since e.g. $\sqrt{2}$ is an algebraic number (as being a root of $x^2-2=0$) but $\sqrt{2} \not \in \mathbb{Q}\,$.

If you tried a construction similar to those "axes" you'd likely end up with an infinite number of them to cover all algebraic numbers. However, the set of algebraic numbers is provably countable.

You should be more concrete about your construction of a counter example to the intuitive understanding of the OP. As an example, talk about the ring of polynomials directly instead of the algebraic numbers in your answer, then illustrate how it has the infinite axis property, and point out it remains countable.

I chose algebraic numbers as an example since it seemed to better fit the pattern of "towering" extensions of number sets in the original post. That said, OP's construction of "axes" is not clear enough to me to even attempt to duplicate it for algebraic numbers. I got the idea from this (quoting) "uncountably infinite corresponds to infinitely many dimensions" that the "axes" may be related to "dimensions" or loosely speaking some other measure of "degrees of freedom". My "counterexample" about algebraic numbers was meant to give an example of such a case where an "infinitely dimensional" super-set (again, loosely speaking) happened to still be countable.

The relation between algebraic numbers and polynomials in $\mathbb{Q}[X]$ is obvious by definition, so I did not elaborate much on that. One problem with open-ended questions like this one is that it's hard to second-guess the right language that "connects" best.

Solution 4:

While certainly the "intuition" you have does help, if you want to begin to tackle cardinality questions, it will not suffice. It is a bit like saying that:

A countably infinite set is one where you can count the next number, while uncountably infinite is you can't even begin to go to the next number. For example, the next natural number after 1 is 2. What's the next real number after 1?

(In actuality, I think the above is actually more useful). To begin tackling a few of your comments:

The first thing that bugs me: Since the axis is calculably exactly twice as long, this should be a "larger infinity" than the for the natural numbers, right? But still, we would say that $\mathbb{Z}$ has the same cardinality as $\mathbb{N}$?

Yes, it should rightfully bother you. It is true since there is a bijection from $\mathbb{Z} \rightarrow \mathbb{N}$. If you want to use your "axes" argument, you can view it as the $x-y$ axis of just the natural numbers, consisting of only the positive $x$ axis and negative $y$ axis.

The amount of points now doesn't simply add up, i.e. the axis doesn't just get longer (as in the step from $\mathbb{N}$ to $\mathbb{Z}$), but it multiplies, i.e. there are more axes now, so that's even a "larger increase of infinity"

Ok..you can possibly extend your argument to the entire $x-y$ plane of just the natural numbers. The main point you are actually using is the fact that whenever you have trouble counting the set you have, you just add another axis of the integers/natural numbers. This is of course...true, if you can explicilty count out a set using this method, then for sure it is countable since it is proven that the cross product of countably infinite sets is countable. However, it is quite nonsensical to say that "uncountably infinite corresponds to infinitely many dimensions" because a countably infinite cross product of countably infinite sets is also countably infinite...and your argument denies this.

Not to mention, it is far from useful to prove more complicated cardinalities and ones of actual mathematical interest. If you want to actually understand "cardinality" and countable vs. uncountable, you can only start by using the actual definition that is that a set is of the same cardinality if you can form a bijection between them.