14
$\begingroup$

I am not a mathematician, so please point out any mistakes I am making here - I am trying to grasp the concept of countable vs. uncountable infinity in a somewhat informal way and would like to know whether that conception makes sense.

We can imagine the set of natural numbers as an axis that goes from some fixed point ($0$, or $1$ if you want) to infinity:

Clearly, the points on this axis are countable, because we know exactly how the axis goes on and can therefore make a precise calculation about how many points the rest of the axis will contain.

For the integers, we no longer have a fixed starting point, but the axis grows infinitely in two directions:
enter image description here

However, we still have only one axis of fixed points and can make a precise calculation of how many points the axis as a whole will contain.
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}$?

For the rational numbers, things get a little more difficult, but we can still handle it: Any rational number can be displayed as the fraction between two integers - if I understood it correctly, this is what the Cantor pairing function does? - so we can just add a second axis to account for the combinatoric possibilities yielding $\mathbb{Q}$:
enter image description here

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". Is this correct?
But we still have finitely many axes with countably many points, so the whole amount of points is countable too.

Now for the case of real numbers, things look a bit differently.
Clearly, a one-dimensional system doesn't suffice because we need to account for the digits behind the comma, so we need at least two axes, in order to create $0.0, 0.1, 0.2, ..., 1.0, 1.1, ...$: enter image description here
Now that doesn't suffice either, because from $1.1$, we can decide to either stay at $1.1$, which would be $1.10$ (Is it true that $1.1$ is in fact $1.10$ which is in fact $1.1000000...$, so that rational numbers are actually never really finite, or is this idea false and $1.1$ is really just $1.1$?) or go further to $1.11$, so we need another axis:
enter image description here
We are now three-dimensional and can thus account for all the numbers with two digits behind the comma, but that still doesn't suffice, because between $1.10$ and $1.11$, we also have the numbers $1.101, 1.102, 1.103, ... $, and from any point we are, we are recursively stepping one dimension deeper, because for any digit we add, we again have all the possibilities to go on from that point, so we never reach a point where we can stop adding axes:
enter image description here
(At this point I'm running out of imagination on how to draw a 7D diagram, sorry)

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.

My question is:
Is it adequate to say that countably infinite corresponds to finitely many dimensions, while uncountably infinite corresponds to infinitely many dimensions, or did I go anywhere wrong in my conception?

$\endgroup$
3
  • 6
    $\begingroup$ When considering infinite quantities, many of the familiar properties of finite numbers must go out the window. For example, one might think that a circle of radius 2 contains more points than a concentric circle of radius 1 since the arc length of the former is twice that of the latter, but radial segments between such circles demonstrate that the points on the circles are in bijective correspondence (equinumerous). $\endgroup$
    – MPW
    Jan 1, 2017 at 1:43
  • 3
    $\begingroup$ I don't think there is any connection whatsoever between countably and uncountable infinity and finitely many and infinitely many dimensions. $\endgroup$ Jan 1, 2017 at 5:19
  • 1
    $\begingroup$ "make a precise calculation about how many points the rest of the $\mathbb N$ axis will contain." That's infinitely many, the same is true for $\mathbb R$. $\endgroup$
    – Jasper
    Jan 1, 2017 at 13:08

5 Answers 5

10
$\begingroup$

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. :)

$\endgroup$
7
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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.


[ EDIT ]  To try and address @Yakk's point raised in a comment...

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.

$\endgroup$
11
  • $\begingroup$ I think that OP meant to write $\mathbb{R}$ instead of $\mathbb{Q}$. $\endgroup$
    – J. C.
    Jan 1, 2017 at 0:58
  • $\begingroup$ @JoãoC. Yes, that's what I assumed as well in the rest of the answer. But, since it's a direct quote, I'll leave it to the OP to fix it in the question first. $\endgroup$
    – dxiv
    Jan 1, 2017 at 1:04
  • $\begingroup$ Oh, sorry, I had not understood your answer I thought you were talking about Q, because you refered it in the answer. I should have more attention! $\endgroup$
    – J. C.
    Jan 1, 2017 at 1:07
  • $\begingroup$ Yes, I seem to have mixed up $\mathbb{R}$ and $\mathbb{Q}$, thanks for pointing it out. I edited the question. $\endgroup$
    – lemontree
    Jan 1, 2017 at 1:09
  • $\begingroup$ @lemontree Thanks, updated the quote as well. $\endgroup$
    – dxiv
    Jan 1, 2017 at 1:10
2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ The idea of "what is the next number?" is very misleading; what is the next rational number after 1? There isn't any, and yet there are only countably infinite rational numbers. $\endgroup$
    – Wildcard
    Jan 1, 2017 at 4:44
  • $\begingroup$ math.stackexchange.com/questions/500849/… -- It seems the problem with the "infinite dimensions" idea is more subtle than this answer implies. $\endgroup$
    – David K
    Jan 1, 2017 at 15:55
  • $\begingroup$ I must agree with Wildcard. The nature of infinite sets is not so cut and dry. Your logic fails short on the rational numbers. Instead, by countable sets, you should mean nowhere dense sets, and by uncountable sets, you should mean dense sets. Then your logic makes sense. $\endgroup$ Jan 10, 2017 at 23:47
-4
$\begingroup$

Your understanding of the whole thing is a little off the road of regular Mathematical sense. I am not a mathematician or even a math major, but I know some math and let me tell you some of my understanding. The major difference btw set R and N is that N is listable but R is not, and listable is just another saying of countable. N is somewhat discrete while R is "continous". Btw every 2 reals, there will always be a real, no matter rational or irrational while between 2 consecutive integer, no integer exists. There is no "next" for a real. As to the dimension thing, you have to know linear combination and dimension is defined as the minimal number of elements such that each element of the space can be represented as a linear combination of those elements. Those elements must also be linear independent. In finite dimensional space, the situation is always simpler than infinite dim space. In finite dim, people tend to find element whose span is dense instead of being the whole space. For R, it is one dimensional because a single real can represent all others by linear combination.

$\endgroup$
1
  • 1
    $\begingroup$ $\mathbb{Q}$ is also dense, but countable ... $\endgroup$ Mar 12, 2018 at 3:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.