How was it established that there are more real numbers than rational numbers?

Factual Questions
21

I think you are at least asking the right question here, which implies that you actually understand the matter better than you think you do.

When you try to make a one-to-one pairing between two sets, there are any number of ways you could choose to match them up. Comparing two finite sets, you will get the same result no matter how you pair up the elements: One of the sets in particular will be smaller and the other bigger, or else they will be the same size.

When you try this with infinite sets, funny things happen. Consider pairing up the set of all positive integers with the set of all positive even integers. There are several ways you could do this, with several different results. You can easily find a pairing scheme that shows the sets to be equal in size. You can also easily find a pairing that shows the set of all integers to have many left-overs (infinitely many in fact), showing that this set is the larger. What to make of this?

Cantor made this definition (perhaps arbitrarily): If you can find ANY WAY to pair up the sets to make them come out equal in size, then the sets are equal in size.

But if you find a way to show one set is larger (that is, has left-overs) and you CAN’T find a way to pair them up one-to-one, then the set with the left-overs is the larger set. Now we run into a problem – the very problem that you are hinting at:

If you CAN’T find a one-to-one pairing scheme, does that mean it can’t be done? OR does it simply mean you aren’t clever enough to find the scheme, or that you haven’t tried hard enough?

Thus, to show that one set is larger, you actually have to PROVE that there CAN’T be any one-to-one pairing scheme, no matter how clever you are.

Cantor’s diagonal argument does this. Notice that he doesn’t actually show any particular alleged one-to-one scheme and then disprove it. Rather, he shows a generalized idea of a one-to-one scheme, that could actually be any scheme, and then proves that it can’t work. Thus, what the diagonal argument proves is that ANY scheme you could possibly come up with is susceptible to that change-the-digits trick, and thus that ANY scheme would leave you with left-over numbers in the real-number column.

Thus, the diagonal proof shows that the reals will out-number (or should I say, “out-infinite”) the rationals no matter how you try to pair them up. This is the sort of thing you must do to show that one infinite set is larger than some other infinite set.

22

I’m inclined to agree with Senegoid on this. An obvious fourth possibility is that the term “quantity”, as normally understood, doesn’t apply to this relationship.

23

It’s not as obvious as it is in the finite case, but it’s still true. Two sets have the same cardinality iff there’s a bijection between them. Given two sets A and B, there’s either a bijection between them, or between one of them and a proper subset of the other.

24

This is true in that you have to go ahead and prove for two sets that the relation “there exists a bijection between A and B” is an equivalence relation, and the relation “there exists a bijection between a subset of B and A” is a total order (using the former equivalence relation in defining “=” for the antisymmetry axiom for the total order), to establish some of these proofs.

And… ninja’d.

25

Simplest is to define, for cardinal numbers, A = B, A ≤ B (and therefore A ≥ B); and to then prove that if both A ≤ B and A ≥ B then A = B. It is the need to prove this that has been overlooked upthread. Here’s one of several proofs of that “Cantor-Bernstein Theorem,” which, despite the name, was first proved by Richard Dedekind.

As a matter of history, both Archimedes and Galileo understood that one infinity could be “equal to” an apparently much larger infinity. That some infinities were absolutely larger than others may not have been realized until the work of Deedekind And Cantor.

(Or both.)

26

For what it’s worth, the axiom of choice is needed to show that, of any two sets, at least one is in bijection with a subset of the other (i.e., of any two cardinalities, one is “less than or equal to” the other; the “trichotomy rule” mentioned by Senegoid, et al). In fact, this claim is equivalent to the axiom of choice.

Also, for what it’s worth, in intuitionistic mathematics, it’s not necessarily the case that if A is in bijection with a subset of B, and B is also in bijection with a subset of A, then A and B can be put in bijection (i.e., if two cardinalities are both “less than or equal to” the other, they are in fact equal; the Cantor-Schroeder-Bernstein theorem mentioned by septimus). For example, it is intuitionistically consistent to suppose that all functions from reals to reals are continuous, so taking A to be a single interval and B to be a pair of disjoint intervals serves as a counterexample. Or, for another example, it is intuitionistically consistent to suppose that all functions form naturals to naturals are computable, so taking A to be the set of all naturals and B to be the set of naturals coding halting programs serves as a counterexample.

27

Just to provide more intuition for why the axiom of choice is needed, let’s use the usual metaphor of indistinguishable socks. Imagine a sequence of boxes, Box #0, Box #1, Box #2, etc., each containing two socks, in a Choice-less world where the only sets and functions describable/existent are those which do not treat the two socks in a box differently for more than finitely many boxes. Injecting the naturals into the set of socks or vice versa would give us a way to pick, for infinitely many boxes, which is the “first” sock and which is the “second” sock, which can’t be done, and thus the set of naturals and the set of socks will be incomparable. (The jargon name for this sort of argument is “Fraenkel-Mostowski permutation models”)

The way to actually derive the axiom of choice from trichotomy is as follows: let A be a set, and let wf(A) be the set of order types of well-orderings of subsets of A. As the collection of ordinals forms a proper class (the Burali-Forti result), there must be some ordinal not in wf(A) [in fact, this ordinal will essentially be wf(A) itself]. This ordinal cannot inject into A and thus, by trichotomy, instead admits an injection from A. It follows that A can be well-ordered, which is to say, arbitrary sets can be well-ordered, from which the axiom of choice easily follows (whenever you need to make a bunch of choices, well-order all the options, and take the first option for each decision).

28

Ok, I just finished counting all of them. I can tell you with absolute certainty that there are more … wait … crap! I missed a bunch of them. Hold on, I’ll have to get back to you.

29

It’s not hard to put all the rationals in order.

We know that all rational numbers can be expressed as the ratio of two whole numbers, say p/q. Start with 1/1 (p+q = 2). Then include 2/1, 1/2 (p+q = 3). Then, 3/1, 2/2, 1/3 (p+q = 4). And so on. Of course we should drop alternate forms of the same number. And alternate between positive and negatives. And not forget 0.

So the sequence of all rationals is: 0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, 3, -3, 1/4, -1/4, 2/3, -2/3, 3/2, -3/2, 4, -4, 1/5, -1/5, 5, -5, 1/6, -1/6, 2/5, -2/5, 3/4, -3/4, 4/3, -4/3, 5/2, -5/2, 6, -6, …

Of course, there’s nothing special about this sequence.

30

i have tried to understand this but when someone says that one infinity is larger than another one, my brain hurts a lot.

31

Why should your brain hurt?

Look at it this way: An inch and a mile both contain infinitely many points, yet there is a sense in which a mile is much larger, right? For some purposes, you might want to say “They’re both have infinitely many bits, and that’s that”, and for some purposes you might want to say “They both have infinitely many bits, but there’s a sense in which one is much larger”.

In the same way, someone came up with yet another sense of the word “larger” which they found interesting, and they managed to demonstrate that sometimes, two things could be infinite with one being “larger” (in this particular sense) than the other. Your brain no more needs to recoil at that than at the inch/mile thing.

32

Heck, ordinary counting-numbers infinity makes my brain hurt!

One of my favorite silly math jokes is where you go through all kinds of contrivances and manipulations to create the largest number you can think of – like Googol to the Googol power, factorial – and then admit, off-handedly, “But, of course, that’s actually a very small number.”

Blimey, something as dull as 10^35 makes my brain hurt!

33

I think what I need to understand is that everything is made up of infinite number of parts, but also a finite number, noo my brain still hurts.:smack:

Seems nonsensical to me, although you can keep dividing something forever it is not infinite.

34

Ok. Here’s my proof (just came up with it. haven’t done any research or read upthread).

Any rational number can be expressed as the ratio of two integers, eg 1123/5445, or for easier work 49/100 or 50/100.

Between any two sequential integers exist an infinite number of rational numbers, capable of being expressed as the ratio of two integers. An integer numerator can always be found. I.E. (49.5/100) x (2/2) = 99/200, or alternately (49.5/100)x(20000/20000)=9900/20000

An irrational number, whose value is between two fractions with a common divisor, multiplied by the given divisor in the ratio, will always give an irrational number between them. A irrational number that starts .49812122… can be multiplied by the divisor to give a fraction that’ll be irrational itself and between the integers. .49812122… = (49.812122…/100).

Since an irrational number multiplied by any possible integer expression of unity will not give an integer numerator, and a rational number multiplied by the right expression of unity will give an integer numerator, and the next rational number in the series in either direction is one integer in the numerator away, then no series can be found, no matter how large the integers in the expression of unity, where a finite number of irrational numbers can be contained between any two integer values of the fraction. (4981.2122…/20000) will be between (4981/20000) and (4982/20000).

Q.E.D. unless I’ve made an error.

35

(Emphasis mine.) So far as I can tell you are trying to prove that between any two rationals there will be an infinite number of irrationals. But that isn’t sufficient to show the cardinality of the two sets differ; c.f. the fact that there are the same number (qua cardinality) of rationals and integers, despite, as you note, there being an infinite number of rationals between any two integers. I might just be misunderstanding what you are trying to do.

36

Remember that this discussion is theoretical math. In real life, if you draw a line and inch long and start dividing by two, you eventually (I have no idea, maybe 200 divisions?) get down to less than the size of electrons and are in a realm where “distance” doesn’t have any real meaning. We think of the real numbers as “points” on a “line” but the point has no measurement (no width, length, or height) and the line has no width or height. No mathematical “point” exists in the real world. So, take a couple of headache remedies and remember that math-theoretic is not the same as real-life.

37

Let’s see, using Planck length of about 1 x 10^-35meters as the realm where ‘distance’ doesn’t have any meaning (this is much smaller than an electron), going from an inch, or about 2 x 10^-2 meters to Planck length is a ratio of about 2e33. Which, I believe is about 2^111. So something like 111 divisions.

38

Not only are there an infinite number of irrational numbers between any pair of rational numbers, but there are also an infinite number of rational numbers between any pair of irrational numbers.

39

And an infinite number of rationals between rationals and an infinite number of irrationals between irrationals and an infinite number of rationals between a rational and an irrational and every other such thing…

There is a proof of the uncountability of the reals along these “I can always find something inbetween” lines, though. Imagine a countable sequence of reals. Start off with no constraints in mind, and go through the sequence in order; each time you come to a value which satisfies all the constraints you’ve made so far, add a new constraint of either the form “I want a value bigger than the one I just saw” or “I want a value smaller than the one I just saw”, alternating between these. By design, no value in the sequence will satisfy all the constraints you impose; thus, if we can show that there does exist a real satisfying all the imposed constraints, we have established that there is a real not contained in the provided sequence.

Also by design, the constraints you impose consist of an increasing sequence of lower bound constraints and a decreasing sequence of upper bound constraints, each of the former below each of the latter. Because of the alternation, either there are only finitely many constraints of each type (in which case, the combination of all the constraints amounts to an inhabited open interval) or there are infinitely many constraints of each type (in which case, the combination of all the constraints amounts to an inhabited closed interval). Either way, there is some real which satisfies all the constraints; Q.E.D.

(This was, in fact, Cantor’s first uncountability proof)

40

Why doesn’t that apply to the rationals as well?