1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple pictorial proof of the uncountability of irrationals?

  1. Oct 16, 2014 #1
    I think I might have found a proof that the irrational positive real numbers (including transcendentals) are uncountable that involves the use of a very simple picture: the identity function graph.

    As you know, the identity function involves taking two axes perpendicular to each other and then depicting a straight line at a 45o to either axis and meeting at the crossing point of said axes. Now, according to the Pythagorean Theorem, for every range unit of length "u" on either axis, there is a corresponding length 2.5u on the actual graph. Now that length "u" can be viewed as a domain on either the x- or y-axis. Only the identity function has this feature such that the domain is necessarily the same as the range, since the two are completely interchangeable. Thus, we take a domain from the y- axis which transforms into a range on the graph line itself, and from there it re-transforms into a domain on the x-axis (or vice versa), getting identity. The one problem is that any domain "u" will undergo a distortion as it translates into a 2.5 range on the graph line itself.

    Now if all positive real numbers were countable, then some numbers on the graph line itself could not possibly appear on either x-axis or y-axis since the range is different from the domain (by a factor of 2.5), which would reveal that some numbers are not identical with their own selves. But since this is clearly a contradiction, then the set of all positive real numbers is not countable.
  2. jcsd
  3. Oct 16, 2014 #2


    Staff: Mentor

    I'm confused. The graph of y = x for nonnegative x does not have numbers on it - it is made up of pairs of numbers. Are you looking at the graph of y = x as its own real number line?

    Your use of domain and range differ from their normal usages. The domain usually means the set of all numbers that can be used as inputs to some function. The range (or codomain) is the set of all numbers that are paired with numbers in the domain of the function.

    When you say, "we take a domain from the y- axis which transforms into a range on the graph line itself", I take this to mean that an interval on the y-axis maps to an interval on the line y = x. Is that what you meant?

    If I'm on the right track, a simpler way to describe things is with two sets that are intevals on the real line: A = [0, 1] and B = [0, √2]. The function f such that f(x) = √2x turns out to be a one-to-one function. Every point in the first interval maps to a point in the second interval, and vice versa.

    One implication of this is that even though the lengths of the two intervals are different, they both have the same cardinality, which is sort of a measure of how many points are in them.
  4. Oct 16, 2014 #3
    Yes, I am looking at the graph y = x as its own real number line. I justify this because since the two numbers in the pair are exactly the same, we can for the purposes consider it as one number.

    I think the identity function creates a unique situation with range and domain. Since it wouldn't matter whether we used either the x-axis or the y-axis as the domain, we can consider the range and the domain interchangeable. Therefore, it wouldn't be impermissible to use the x-axis and the y-axis both as domains. But since every domain has a range, there is no where else to place a range but on the graph line itself (this where my "proof" would break down if it did anywhere, I believe.) So yes, an interval on either the y- or x-axis would map onto an interval on the line y = x.

    The last two sentences in your post would probably be a description of what I'm trying to indicate, except that the implication would be that interval length couldn't be equated with cardinality because if it could, the domain and the "range" would have different cardinalities. This would prove that the set of all real numbers has no cardinality (i.e. are uncountable.).
  5. Oct 16, 2014 #4


    Staff: Mentor

    Still not clear. You started out by saying that you wanted to prove that the positive irrationals were uncountable. In the last sentence of the previous post, you say, "This would prove that the set of all real numbers has no cardinality (i.e. are uncountable.)."

    For one thing, I'm not sure you understand the term "cardinality," which is a measure of the number of elements in a set (cribbed from Wikipedia - see http://en.wikipedia.org/wiki/Cardinality).

    For another, it's well known that the reals are uncountably infinite (as opposed to the rationals, which are countably infinite). I don't see that you have established that the irrationals are uncountably infinite.

    Are you familiar with Cantor's diagonal argument for the uncountability of the irrationals? (See http://en.wikipedia.org/wiki/Cantor's_diagonal_argument.)
  6. Oct 16, 2014 #5
    That sort of argument is doomed to be circular because what you are doing is applying a stretch factor. A stretch factor is going to just give you a one to one onto map, so it has no effect on the cardinality. In set theory terms, applying a stretch factor is equivalent to doing nothing, so there is no way to achieve anything by it, unless you are just trying to establish that something has the same cardinality as something else (what you are actually proving is that the diagonal line has the same cardinality as the real numbers). The only way it's going to work is if you assume what you are trying to prove.

    The way I like to think of it is that the real numbers are similar to the power set of the natural numbers and taking a power set always strictly raises the cardinality. The power set of a set is the set of all subsets of that set. Seems pretty plausible that that should be bigger than the original set, but you can actually prove it by contradiction. Think of a town full of barbers. If you have a mapping from the set of barbers to the power set of the barbers, you can think of each barber being mapped to the set of people whose hair they cut (they could cut their own hair). Then, consider the set of barbers that don't cut their own hair. There can't be a barber who cuts the hair of the people in that set because the way the mapping is defined, that barber maps to the set of people whose hair he cuts. If he's in the set, he cuts his own hair, contradicting the definition of the set. If he is not in the set, then he doesn't cut his own hair, so he should be in the set, which is also a contraction. So, that's why taking the power set raises cardinality. There are never enough barbers to cut all the subsets of barbers, no matter how you assign them.

    When you do a binary decimal expansion, all you need is a decision of whether to go right or left, infinitely many times because what you are doing is picking subintervals. Start with [0,1]. Divide that in half. Then pick either the left half or the right half. Repeat infinitely many times with the halves. You can get to any real number this way. Another way to put it is that you can just pick a subset of the natural numbers to get a real number by counting from one up to infinity and going left whenever you get to a number that's in the set. For example, let's take the set {2, 3, 5}. 1 right, 2 left, 3, left, 4 right, 5 left, 6 right, 7 right, 8 right, and so on. I'm lying a little bit here because you have to worry about stuff like 0.111111111....in base 2 being the same as 1.0, but with a little tweak, you can get the idea to work. What I'm giving you is an onto map, but not one-to-one, which is bad because onto just implies the cardinality of the power set of the natural numbers is bigger than that of the reals. Even though it's not one to one, you can show that's it's close enough to one-to-one that you're okay, so the intuition that they should have the same cardinality turns out to be correct, even if it's not quite as simple as you'd like. It's not super hard to prove, but this is long-winded enough already, and I just wanted to convey the general idea.

    If you notice, my arguments were sort of visual and concrete, except perhaps the logical barber confusion, but none the less not really geometric, aside from the binary expansion bit.
  7. Oct 16, 2014 #6
    Wouldn't the pattern of picking left or right have to have no discernible pattern to ensure that it wouldn't be a rational number? If I always pick the left half, the final result would approach zero. If I always pick the right half, the result would approach one. If I go "right, left" and repeat this pattern of "right, left" to infinity, the final result would approach 2/3 (I think). If "left, right" infinitely, then 1/3 (I think). I'm sure other rational number would show up if the repeating pattern were "right, right, left" or "left, right, left" or "left, left, left, right, left, right, right, left, right" or any finite pattern that repeats infinitely. Or am I mistaken?

    Sorry. You're dealing with a relative nitwit here. :oops: No formal education in math.
  8. Oct 16, 2014 #7
    You are right, but I was just arguing that the real numbers have the same cardinality as the power set of the natural numbers. You're thinking of the irrationals, still. To get to the irrationals, you just note that the rationals are countable. When you go from irrationals to reals, you just throw in a countable set, so that's not going to make it uncountable. So, the irrationals have to be uncountable to begin with.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook