Why can't I do this? (Infinite sets and cardinality)
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 336
 Joined: Mon Jul 28, 2008 4:16 am UTC
Why can't I do this? (Infinite sets and cardinality)
This has been bugging me since yesterday, ever since another math class decided to revisit Cantor's argument.
So, I have the set of integers and the set of real numbers. I understand Cantor's diagonalization argument, although I seem to be missing some details about why it necessarily has to apply. So I'm getting the impression that he's saying I couldn't possibly possess a particular bijection between the two sets. Because, whatever particular bijection I could try, he has a procedure which proves I'm wrong. So a bijection can't exist. I dunno, because that last bit seems like a bit of a leap of faith.
Suppose instead, I want to do this. I have the set of integers and the set of reals. I'm going to make two lists. I'm going to take some arbitrary integer and some arbitrary real and append them to the respective lists. They now correspond to each other in some mapping that I happen to be trying to make. I'm going to keep repeating this, each time taking some integer and some real that I hadn't yet taken before. Now, I'll never finish making a bijection this way. It's probably just as well too, since the moment I finish Cantor would come right along and tell me why I'm wrong. But, it intrigues me because I seem to have a procedure that as time goes along makes further progress towards the bijection I want. Every new step is more complete than the one before it, even if there's infinitely more of each that I haven't yet gotten to.
So this is a bit of a strange thought experiment in the counterfactual. What am I constructing? Given that I'm doing the process to infinite sets, I'll never have the complete result, but it definitely makes progress. So I want to potentially misuse terminology from computer science and say that my bijection is recursively enumerable. For any particular mapping it makes that we want to know, we can determine this mapping with a simulator with some potentially absurd but still finite amount of resources. Not that I have any way of knowing what particular amount of resources for any particular entry is, but it's finite.
So what is my bijection? Is it valid? Is it meaningful? Why is it allowed to coexist with Cantor's argument?
As a side note, iteration seems tricky.
Integers can be iterated 0, 1, 1, 2, 2, etc etc. I'm fine with that.
It's not nearly so obvious how to iterate real numbers to be guaranteed to eventually hit any particular one. My idea goes something like this. Consider the base 10 representation system, zero padded out to infinity in both directions. So 1 is going to be ....000001.000000.... and so on and so forth. Each such instance represents a real number, although some real numbers could have how many ever representations like 0.99repeating and 1. So to iterate over all real numbers, we instead iterate over all possible such strings.
I'm a bit lost here. 0.101001000100001000001... is a painful counterexample to anything I've come up with here. So I leave this thought incomplete.
Thanks, guys!
So, I have the set of integers and the set of real numbers. I understand Cantor's diagonalization argument, although I seem to be missing some details about why it necessarily has to apply. So I'm getting the impression that he's saying I couldn't possibly possess a particular bijection between the two sets. Because, whatever particular bijection I could try, he has a procedure which proves I'm wrong. So a bijection can't exist. I dunno, because that last bit seems like a bit of a leap of faith.
Suppose instead, I want to do this. I have the set of integers and the set of reals. I'm going to make two lists. I'm going to take some arbitrary integer and some arbitrary real and append them to the respective lists. They now correspond to each other in some mapping that I happen to be trying to make. I'm going to keep repeating this, each time taking some integer and some real that I hadn't yet taken before. Now, I'll never finish making a bijection this way. It's probably just as well too, since the moment I finish Cantor would come right along and tell me why I'm wrong. But, it intrigues me because I seem to have a procedure that as time goes along makes further progress towards the bijection I want. Every new step is more complete than the one before it, even if there's infinitely more of each that I haven't yet gotten to.
So this is a bit of a strange thought experiment in the counterfactual. What am I constructing? Given that I'm doing the process to infinite sets, I'll never have the complete result, but it definitely makes progress. So I want to potentially misuse terminology from computer science and say that my bijection is recursively enumerable. For any particular mapping it makes that we want to know, we can determine this mapping with a simulator with some potentially absurd but still finite amount of resources. Not that I have any way of knowing what particular amount of resources for any particular entry is, but it's finite.
So what is my bijection? Is it valid? Is it meaningful? Why is it allowed to coexist with Cantor's argument?
As a side note, iteration seems tricky.
Integers can be iterated 0, 1, 1, 2, 2, etc etc. I'm fine with that.
It's not nearly so obvious how to iterate real numbers to be guaranteed to eventually hit any particular one. My idea goes something like this. Consider the base 10 representation system, zero padded out to infinity in both directions. So 1 is going to be ....000001.000000.... and so on and so forth. Each such instance represents a real number, although some real numbers could have how many ever representations like 0.99repeating and 1. So to iterate over all real numbers, we instead iterate over all possible such strings.
I'm a bit lost here. 0.101001000100001000001... is a painful counterexample to anything I've come up with here. So I leave this thought incomplete.
Thanks, guys!
Re: Why can't I do this? (Infinite sets and cardinality)
It's not obvious how to do it because it can't be done.It's not nearly so obvious how to iterate real numbers to be guaranteed to eventually hit any particular one.
I'm not quite sure what you're getting at here. You seem to be saying "I have trouble with the idea that the reals are uncountable, because here's a method that I think should be able to count them. Only, the method doesn't work."
Re: Why can't I do this? (Infinite sets and cardinality)
See, you've kind of just done away the problematic part by saying "each time taking some integer and some real that I hadn't yet taken before". Cantor's argument said that you cant do that, since you'll eventually run out of integers, but not real numbers.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why can't I do this? (Infinite sets and cardinality)
Unparallelogram wrote:Suppose instead, I want to do this. I have the set of integers and the set of reals. I'm going to make two lists. I'm going to take some arbitrary integer and some arbitrary real and append them to the respective lists. They now correspond to each other in some mapping that I happen to be trying to make. I'm going to keep repeating this, each time taking some integer and some real that I hadn't yet taken before. Now, I'll never finish making a bijection this way. It's probably just as well too, since the moment I finish Cantor would come right along and tell me why I'm wrong. But, it intrigues me because I seem to have a procedure that as time goes along makes further progress towards the bijection I want. Every new step is more complete than the one before it, even if there's infinitely more of each that I haven't yet gotten to.
So this is a bit of a strange thought experiment in the counterfactual. What am I constructing? Given that I'm doing the process to infinite sets, I'll never have the complete result, but it definitely makes progress. So I want to potentially misuse terminology from computer science and say that my bijection is recursively enumerable. For any particular mapping it makes that we want to know, we can determine this mapping with a simulator with some potentially absurd but still finite amount of resources. Not that I have any way of knowing what particular amount of resources for any particular entry is, but it's finite.
At any finite stage, you don't get a bijection, only a onetoone correspondance between a finite subset of one and a finite subset of the other. When you say that you "enumerate" a bijection, I think you mean the following: let f be the function from (a subset of) the natural numbers to the real numbers that maps the number n to the real number that it is (eventually) paired with in this process. This would be welldefined, if you made your choices of the "arbitrary integer" and "arbitrary real" welldefined. However, it would never be a bijection. To see this, suppose your choice of the "arbitrary integer" was always an even integer. Since there are infinitely many even integers, you would never get stuck, and so could always continue your list in this way. So your function doesn't have any odd numbers in its domain. It is easy to see that the function would not then be a bijection between the two sets. In order to get a bijection in this way, you would have to eventually exhaust every integer in your list, and every real number in your list. You can exhaust every integer, but you can't exhaust every real number, since they aren't listable. (Cantor's diagonal argument told you that!) So you will never get a bijection in this way.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Why can't I do this? (Infinite sets and cardinality)
Your "side note" is not a side note at all, but is the crux of the matter; it is impossible and is equivalent to the fact that there are more real numbers than natural number, which is the very thing that you are trying to disprove. So obviously if you assume that such iteration is possible you will able to prove Cantor wrong since you are assuming something false. Maybe this well help shed light on the situation.
A slightly more general version of Cantor's diagnolization argument shows there exists no bijection between a set and its power set. This, I think, is more intuitive than the result that there are more reals than natural numbers in the sense of cardinality, since it seems reasonable that the power set is bigger than the set that generates it. Now, consider the power set of the natural numbers. I can easily construct a map from this set into the real numbers that is oneone. An example is one that takes
[imath]\{3\} \to .77377...., \quad \{1, 3, 5, ...\} \to .37373737..., \quad \{2, 4, 6, ...\} \to .737373...[/imath]
and so forth. So, there are at least as many real numbers in (0, 1) whose decimal expansion consists of only 3's and 7's than there are subsets of the natural numbers and hence more real numbers than natural numbers.
A slightly more general version of Cantor's diagnolization argument shows there exists no bijection between a set and its power set. This, I think, is more intuitive than the result that there are more reals than natural numbers in the sense of cardinality, since it seems reasonable that the power set is bigger than the set that generates it. Now, consider the power set of the natural numbers. I can easily construct a map from this set into the real numbers that is oneone. An example is one that takes
[imath]\{3\} \to .77377...., \quad \{1, 3, 5, ...\} \to .37373737..., \quad \{2, 4, 6, ...\} \to .737373...[/imath]
and so forth. So, there are at least as many real numbers in (0, 1) whose decimal expansion consists of only 3's and 7's than there are subsets of the natural numbers and hence more real numbers than natural numbers.
Re: Why can't I do this? (Infinite sets and cardinality)
Unparallelogram wrote:This has been bugging me since yesterday, ever since another math class decided to revisit Cantor's argument.
So, I have the set of integers and the set of real numbers. I understand Cantor's diagonalization argument, although I seem to be missing some details about why it necessarily has to apply. So I'm getting the impression that he's saying I couldn't possibly possess a particular bijection between the two sets. Because, whatever particular bijection I could try, he has a procedure which proves I'm wrong. So a bijection can't exist. I dunno, because that last bit seems like a bit of a leap of faith.
Your last remark there seems a little odd to me. I'm not totally sure why that particular aspect of Cantor's argument sometimes bothers people.
The structure of Cantor's diagonal argument is basically "Suppose, as a hypothesis, that an XYZ exists. Using that hypothesis, we eventually reach a contradiction. Therefore, no XYZ can exist."
(Here, "XYZ" = "bijection between the integers and the reals".)
I think you're not alone, though. In things I've read elsewhere, other people seem to sometimes misunderstand the strength of Cantor's conclusion.
Cantor's argument does more than just showing one particular proposed XYZ fails. It's a *general* argument, showing that the assumption that something's an XYZ leads to a contradiction. Thus there can't be an XYZ.
Re: Why can't I do this? (Infinite sets and cardinality)
If Cantor's diagonalization argument seems too sloppy for you, try this:
Thm: Let X be a set, and let P(X) be its power set. (The power set of X is the set of all subsets of X. This includes the empty set and X itself.) There is no bijection between X and P(X).
Proof: Suppose we had f:X > P(X) a bijection. We now define S to be the set of all x in X such that x is not an element of f(x). Remember, f(x) is some subset of X. So we're asking if x belongs to its image. If it isn't, then we say x belongs to S. Now, S is a perfectly good subset of X, and so it's an element of P(X). Thus, there's some element y of X so that f(y) = S because f is surjective. We now ask the question: Is y an element of S? Suppose that this is true, and y is an element of S. Thus y is not an element of f(y), by definition of S. But f(y) is S! So we get a contradiction. So we have to have that y is not an element of S. But, by definition, that means that y is in f(y). Once again, that's a contradiction. Thus there is no bijection between X and P(X).
Now, I claim that the set of reals is in bijective correspondence with the power set of the integers. Why? Here's a sketch:
1. The power set of the integers is in bijective correspondence with infinite binary sequences [imath]\ldots b_{2}, b_{1}, b_0, b_1, b_2, \ldots[/imath]. If you give me a subset, I'll write down the sequence that is 1 at each element of the subset and 0 elsewhere.
2. Every real number has a binary expansion that is unique if we do not allow the expansion to terminate in string of all 1's. (In the decimal expansion, if we have something like .4369999..., that's the same as .437. Here in the binary expansion world, that means we don't want an expansion like .010100100111111... and instead take .010100101.)
3. The set of all infinite binary strings above that terminate in all 1s is countable.
4. If a set is not countable and we remove a countable subset, that remaining set is not countable.
5. The set of reals is in bijective correspondence with the set of infinite binary sequences (uncountable) with string ending in all 1s thrown out (countable), and so it's not countable.
Thm: Let X be a set, and let P(X) be its power set. (The power set of X is the set of all subsets of X. This includes the empty set and X itself.) There is no bijection between X and P(X).
Proof: Suppose we had f:X > P(X) a bijection. We now define S to be the set of all x in X such that x is not an element of f(x). Remember, f(x) is some subset of X. So we're asking if x belongs to its image. If it isn't, then we say x belongs to S. Now, S is a perfectly good subset of X, and so it's an element of P(X). Thus, there's some element y of X so that f(y) = S because f is surjective. We now ask the question: Is y an element of S? Suppose that this is true, and y is an element of S. Thus y is not an element of f(y), by definition of S. But f(y) is S! So we get a contradiction. So we have to have that y is not an element of S. But, by definition, that means that y is in f(y). Once again, that's a contradiction. Thus there is no bijection between X and P(X).
Now, I claim that the set of reals is in bijective correspondence with the power set of the integers. Why? Here's a sketch:
1. The power set of the integers is in bijective correspondence with infinite binary sequences [imath]\ldots b_{2}, b_{1}, b_0, b_1, b_2, \ldots[/imath]. If you give me a subset, I'll write down the sequence that is 1 at each element of the subset and 0 elsewhere.
2. Every real number has a binary expansion that is unique if we do not allow the expansion to terminate in string of all 1's. (In the decimal expansion, if we have something like .4369999..., that's the same as .437. Here in the binary expansion world, that means we don't want an expansion like .010100100111111... and instead take .010100101.)
3. The set of all infinite binary strings above that terminate in all 1s is countable.
4. If a set is not countable and we remove a countable subset, that remaining set is not countable.
5. The set of reals is in bijective correspondence with the set of infinite binary sequences (uncountable) with string ending in all 1s thrown out (countable), and so it's not countable.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

 Posts: 224
 Joined: Tue Jun 17, 2008 11:04 pm UTC
Re: Why can't I do this? (Infinite sets and cardinality)
Unparallelogram wrote:But, it intrigues me because I seem to have a procedure that as time goes along makes further progress towards the bijection I want. Every new step is more complete than the one before it, even if there's infinitely more of each that I haven't yet gotten to.
...
So what is my bijection? Is it valid? Is it meaningful? Why is it allowed to coexist with Cantor's argument?
For infinite sets, "making progress at every step" does NOT imply that you will eventually finish all of it. For instance, I could attempt to list the natural numbers by writing 0, 2, 4, 6, 8, etc forever writing even numbers. At every step, I make progress by writing a new number, but it is NOT true that my list will eventually contain all natural numbers, because it will never contain any odd numbers.
So by asking "what is my bijection", you are implicitly assuming that you're building a bijection in the first place. You aren't. Even though you are adding a real number at each step and making progress, there will be some numbers that your mapping will never hit, no matter how far you go.
Unparallelogram wrote:So I'm getting the impression that he's saying I couldn't possibly possess a particular bijection between the two sets. Because, whatever particular bijection I could try, he has a procedure which proves I'm wrong. So a bijection can't exist. I dunno, because that last bit seems like a bit of a leap of faith.
You can restate the proof in an equivalent, but perhaps easier to understand way: Cantor's argument shows that every mapping from the integers to the reals misses some real numbers. Which numbers are missed will of course be different for different mappings, but given any mapping, the diagonal argument actually produces a number which that particular mapping fails to hit.
Then, it's clear that you can't have bijections from the integers to the reals. A bijection has to be a mapping that hits every real. Cantor's argument shows that every mapping misses some reals, so no mapping can be a bijection.
Re: Why can't I do this? (Infinite sets and cardinality)
Here's a nice reformulation of Cantor's diagonalization argument posted in the Logic Puzzles subforum a while back by Madge.

 Posts: 21
 Joined: Tue Jun 14, 2011 12:35 am UTC
Re: Why can't I do this? (Infinite sets and cardinality)
Unparallelogram wrote:It's not nearly so obvious how to iterate real numbers to be guaranteed to eventually hit any particular one. My idea goes something like this. Consider the base 10 representation system, zero padded out to infinity in both directions. So 1 is going to be ....000001.000000.... and so on and so forth.
It's a good thing that this isn't obvious because it's actually impossible!
Let's say that you have all the real numbers written out in these sort of "infinite decimal" expansions so that 1 is ...0001.000...
You can use Cantor's diagonalization on any infinite list of these numbers. It doesn't matter what order you put them in, Cantor will always show you how to find one element that is never in this list no matter how arbitrarily long (even infinitely long) your list is. Now this should tell you that there is at least one element in your range that isn't mapped to from any element in your domain, thus whatever this list is, it is not a bijection.
It might be helpful to remember that the way we define and compare and cardinality of two different sets makes use of bijections, even for finite sets. If there is another way you have of thinking about the cardinality of infinite sets it might not be the "right" or agreed upon way.
 agelessdrifter
 Posts: 225
 Joined: Mon Oct 05, 2009 8:10 pm UTC
Re: Why can't I do this? (Infinite sets and cardinality)
When you guys say "you'll eventually exhaust the integers but not the reals" isn't that sort handwavy? You'll never exhaust either because they're infinite sets.

 Posts: 88
 Joined: Wed Sep 22, 2010 4:06 pm UTC
 Location: The dark place where the counterexamples live.
Re: Why can't I do this? (Infinite sets and cardinality)
Well, for integers such an "iteratively defined" function makes sense (and is defined on all integers). This is because you don't have to write down the range of the function. If you try, you wouldn't come to an end. You just have to be able to say where each integer is mapped. Since the algorithm terminates for each integer, the function is well defined (and "exhausts" the integers in the sense that it is defined on each one).
The cake is a pie.
Re: Why can't I do this? (Infinite sets and cardinality)
agelessdrifter wrote:When you guys say "you'll eventually exhaust the integers but not the reals" isn't that sort handwavy? You'll never exhaust either because they're infinite sets.
The metaphor loses its power since it's not something a mortal being could actually do. But the concept is still the same, that there is no surjective mapping from the naturals to the reals. This is a wellproved fact that is quite beyond dispute, so it's something where we have to sharpen our intuition to match the reality at times.
 agelessdrifter
 Posts: 225
 Joined: Mon Oct 05, 2009 8:10 pm UTC
Re: Why can't I do this? (Infinite sets and cardinality)
Tirian wrote: But the concept is still the same, that there is no surjective mapping from the naturals to the reals. This is a wellproved fact that is quite beyond dispute,
Yeah I wasn't trying to dispute that idea, I just thought the explanation was being presented sort of ambiguously in some posts in this thread. Mindworm did a good job clarifying, though.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why can't I do this? (Infinite sets and cardinality)
agelessdrifter wrote:When you guys say "you'll eventually exhaust the integers but not the reals" isn't that sort handwavy? You'll never exhaust either because they're infinite sets.
You can eventually exhaust the integers in the following sense: you can pick one, and then another, and then another, and so on, in such a way that each individual integer will eventually get picked. So you will never have listed all of the integers, but every integer will eventually get listed. Does that make sense?
With the real numbers, you can't do either, because they are uncountable.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 8 guests