Hacker News Reader

Comment by hansbo | Hacker News Reader

It is unintuitive to me why the rational numbers are dense in the reals, since rational numbers are countably infinite, as opposed to the reals. I think infinity is hard to grasp.

View on HN

It’s because for every pair of irrational numbers, there is a first place in their decimal representation where their digits differ, which means you can construct a number with finite decimal representation that fits between the two, which thus is rational.

In other words, it’s because while there are uncountably many irrational numbers, their representation is still only countably infinite each.

Or in yet other words, uncountable infinity is only a teensy bit larger than countable infinity, not that much larger. Consider that every prefix of an irrational number is a rational number. ;)

In decimal form, almost every real number between 0 and 1 is zero-point followed by an infinite sequence of random digits. No computer in the universe has enough hard drive space to store an arbitrary fixed real number between 0 and 1. This is of course not true for rationals: any rational number can be saved on a big enough hard drive. In particular, given unbounded resources, we can build a computer that approximates (0,1) by storing a finite set of rational numbers, and reaches a given real number x with arbitrary nonzero error. But we will never get zero error on a physical computer.

The tough part with analogies like this is there are obviously rationals too large for any computer in the universe as well and anything which fixes that portion goes back to needing to reckon about the different types of infinities involved in the original problem.

I don't think that's the case here unless you are referring to a busy beaver thing I don't understand :)

If you are referring to the observable universe being finite, then that's not relevant for the discussion: I am just putting a few more grounded terms on the theorem that computable reals (including rationals) are a countable set. The point is that "for every integer n you can get n+1" is unphysical, yet "grokkable" symbolically, so it works well within a conceptual mathematical universe (regardless of what the physical universe has to say about it). Within this math universe we build an abstract computer that can hold an arbitrary rational/computable number, but only a countable subset of the real numbers, since almost all real numbers cannot be described by any "physical" program, even if that program is larger than the entire universe.

I wish I understood the busy beaver problem / connections to Ramsey theory / etc. However for this intuitive discussion it seems like a serious digression.

This is what I mean in that it only appears more grounded if you already understand why a countable set has a different type of infinity than an uncountable set in the first place and what type of universe that implies. Otherwise you're left wondering what type of universe is needed and why it is that type of universe can account for some infinities but not others. The latter part is just the answer to the original question of what the difference between a countable and uncountable set is again so if you can answer that you didn't have the question to start with!

I think you are getting away from the actual original question, which is why (intuitively) the rationals are dense in the reals despite being a different form of infinity. The confusion wasn't about different forms of infinity, it was really about the topology of R with respect to Q - why is Q "big enough" yet Z "too small" despite the sets having the same cardinality? And that is intimately related to any fixed real number having a computable/rational approximation up to any accuracy, yet most real numbers not actually being computable.

> why the rational numbers are dense in the reals

the reals are defined as limits of the sequences of rationals, and thus the rationals are dense in reals by that definition.

>since rational numbers are countably infinite

while the set of all the infinite convergent series of rationals happens to be strongly larger than countably infinite.

Dense means arbitrarily close together, which is what rationals i/n and (i+1)/n are.

I think precisely the rationals being dense in the reals means that for any two real numbers x and y where x < y there exists a rational number m/n (m and n being integers) such that x < m/n < y.

Yes, that's the more formal equivalent formulation. For n > 1/(y-x), the sequence of rationals ... ,i/n, (i+1)/n, ... must land in (x,y).

Rationals are also dense in the p-adic numbers, which you can think of as the other way to form their completion, if I understand correctly (with a different notion of absolute value.)

I always thought using countable and uncountable was a little confusing and that introducing aleph/beth numbers would have made things clearer when those ideas were introduced.

Reply on news.ycombinator.com