Register to reply

On Real Enumeration

by hddd123456789
Tags: enumeration, real
Share this thread:
hddd123456789
#1
Nov10-12, 02:53 PM
P: 82
Hey, I've been reading up on Cantor's work recently, and was wondering if the following series can be considered an enumeration for the reals between 0 and 1 in binary:

[0] => 0.00000...
[1] => 0.10000...
[2] => 0.01000...
[3] => 0.11000...
[4] => 0.00100...
[5] => 0.10100...
[6] => 0.01100...
[7] => 0.11100...
[8] => 0.00010...
[9] => 0.10010...
[10] => 0.01010...
[11] => 0.11010...
[12] => 0.00110...
[13] => 0.10110...
[14] => 0.01110...
[15] => 0.11110...
.
.
.

If not then can you please explain why this isn't an accurate enumeration? Thank You!
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Number Nine
#2
Nov10-12, 03:01 PM
P: 772
Cantor clearly shows why in his diagonalization argument. I can easily create an infinite length binary string that isn't on your list.
hddd123456789
#3
Nov10-12, 03:07 PM
P: 82
I don't get it, the list I made is defined to go through every possible combination of 0's and 1's for a binary expansion of any number of digits. So how could there be a binary string not in the set of every possible binary strings?

Number Nine
#4
Nov10-12, 03:12 PM
P: 772
On Real Enumeration

Quote Quote by hddd123456789 View Post
I don't get it, the list I made is defined to go through every possible combination of 0's and 1's for a binary expansion of any number of digits. So how could there be a binary string not in the set of every possible binary strings?
Again, the diagonalization argument provides an explicit procedure for constructing such a string.

The first digit in your first string is zero, so the first digit in my string is one.
The second digit in your second string is one, so the second digit in my string is zero
And so on...

My string differs from every string on your list. Your enumeration fails.
micromass
#5
Nov10-12, 03:14 PM
Mentor
micromass's Avatar
P: 18,330
Which number corresponds to 0.101010101010101... ??
hddd123456789
#6
Nov10-12, 03:19 PM
P: 82
Could you please elaborate? I have just a basic understanding of these ideas, I admit, but I see n=1,5,9,13, which all start with the example you gave. And if you continued with your list, I can keep giving you n's which start with the sequence you give.
micromass
#7
Nov10-12, 03:22 PM
Mentor
micromass's Avatar
P: 18,330
Quote Quote by hddd123456789 View Post
Could you please elaborate? I have just a basic understanding of these ideas, I admit, but I see n=1,5,9,13, which all start with the example you gave. And if you continued with your list, I can keep giving you n's which start with the sequence you give.
Yes, you can find a number which corresponds with the first few values of my sequence. But the point is, you can never give a number which corresponds with my entire sequence.

I'm sure you can find numbers which correspond to
0.1
0.101
0.10101
0.1010101
and so on.

But can you find a number corresponding with the entire (infinite) sequence 0.101010101010101... ?? That's what Cantor's theorem is about.
slider142
#8
Nov10-12, 03:24 PM
P: 898
Quote Quote by hddd123456789 View Post
Could you please elaborate? I have just a basic understanding of these ideas, I admit, but I see n=1,5,9,13, which all start with the example you gave. And if you continued with your list, I can keep giving you n's which start with the sequence you give.
While that is true, the point of the construction is that even though you can add our new constructed number to your list, we can then immediately construct another a number that is not in your infinite list. The fact that there is always such a number available, no matter how many numbers you add to your list is the point of the diagonalization argument. We explicitly construct a number that is designed to not be equal to any individual number in a given list, whether that list is finite or infinite.
hddd123456789
#9
Nov10-12, 03:38 PM
P: 82
Quote Quote by micromass View Post
Yes, you can find a number which corresponds with the first few values of my sequence. But the point is, you can never give a number which corresponds with my entire sequence.

I'm sure you can find numbers which correspond to
0.1
0.101
0.10101
0.1010101
and so on.

But can you find a number corresponding with the entire (infinite) sequence 0.101010101010101... ?? That's what Cantor's theorem is about.
Oh ok, I get that. In that case, I see this now as more of a logical problem: yes, I can't come up with a number corresponding with your binary expansion, but at the same time, can't I be sure that, logically, it must exist? After all, each binary expansion in my list in my OP was defined to infinity so is a real, and each n is associated with exactly one of the unique binary expansions. So while I don't have a formulaic way of giving you an n for a particular binary expansion, why can't I apply logic that it must be in the set based on the definition and have a unique n associated with it?
micromass
#10
Nov10-12, 03:40 PM
Mentor
micromass's Avatar
P: 18,330
Quote Quote by hddd123456789 View Post
Oh ok, I get that. In that case, I see this now as more of a logical problem: yes, I can't come up with a number corresponding with your binary expansion, but at the same time, can't I be sure that, logically, it must exist? After all, each binary expansion in my list in my OP was defined to infinity so is a real, and each n is associated with exactly one of the unique binary expansions. So while I don't have a formulaic way of giving you an n for a particular binary expansion, why can't I apply logic that it must be in the set based on the definition?
Every number on your list has only finitely many nonzero decimals. So any number with infinite nonzero decimals won't be on the list. That proves that the number is not on the list.
Number Nine
#11
Nov10-12, 03:51 PM
P: 772
why can't I apply logic that it must be in the set based on the definition
Your definition says no such thing.

After all, each binary expansion in my list in my OP was defined to infinity so is a real, and each n is associated with exactly one of the unique binary expansions.
That's irrelevant. The point is that your list is not exhaustive. You have an injective function to the reals; but that's not what an enumeration is.
lavinia
#12
Nov10-12, 05:08 PM
Sci Advisor
P: 1,716
you list only has numbers with finitely many zeros
hddd123456789
#13
Nov10-12, 09:09 PM
P: 82
Thank you all for your responses! It hit me that I had read this idea of finitely many nonzero digits before so I think I understand what you are saying now.

I'm curious though, being outside of academia myself, to what extent are Cantor's ideas criticized? Specifically, I'm speaking about the idea that a one-to-one correspondence with the naturals is enough to sensibly conclude that the two sets are of equal cardinality even though the members of one set, in the case of the even numbers for example, might be twice in measure of the members of the other set. And I'm asking this in context to the fact that we are doing the counting without reference to a measurable interval. (Sorry for the non-standard terminology).

I mean, if I generally want to know how many of two marker types there are on an infinitely long road, and you give me that marker type A is spaced X units apart, and marker type B is spaced Y units apart, I couldn't possibly give you a sensible answer without being given some interval to divide the markers into.

What I don't get is that if Cantor himself developed the measure of the cardinality of infinite sets, namely aleph-0, then why not use alepth-0 as an interval measure into which one puts members of two different sets in order to determine their cardinality. In this case, I imagine that one would get a different result for the naturals and the even naturals.
micromass
#14
Nov10-12, 09:19 PM
Mentor
micromass's Avatar
P: 18,330
Quote Quote by hddd123456789 View Post
I'm curious though, being outside of academia myself, to what extent are Cantor's ideas criticized?
It is not. Every serious mathematician has accepted Cantor's ideas as true. The only criticism comes from laymen and philosophers.
That said: there are of course attempts to make other axiom systems. Other axioms might mean that Cantor's theorems become false. But that doesn't mean that anybody doubts the truth of Cantor's theorems as they are only true in the given axiom system.

Specifically, I'm speaking about the idea that a one-to-one correspondence with the naturals is enough to sensibly conclude that the two sets are of equal cardinality even though the members of one set, in the case of the even numbers for example, might be twice in measure of the members of the other set.
That sets are of equal cardinality if there exists a one-to-one correspondence between them is a definition. We have defined it to be true. Another definition might give another answer, but this definition has turned out to be quite fruitful.
Furthermore, when you say that the even numbers are "twice in measure", then you first need to define measure.

And I'm asking this in context to the fact that we are doing the counting without reference to a measurable interval. (Sorry for the non-standard terminology).
Yeah, I don't really get this. Could you explain?

I mean, if I generally want to know how many of two marker types there are on an infinitely long road, and you give me that marker type A is spaced X units apart, and marker type B is spaced Y units apart, I couldn't possibly give you a sensible answer without being given some interval to divide the markers into.
Well, infinite roads and infinite markers don't exist. Don't make the mistake that Cantor's infinities actually say something about actual reality. They are purely abstract mathematical ideas. They are useful in describing mathematics. But they don't necessarily say anything about reality.

What I don't get is that if Cantor himself developed the measure of the cardinality of infinite sets, namely aleph-0, then why not use alepth-0 as an interval measure into which one puts members of two different sets in order to determine their cardinality. In this case, I imagine that one would get a different result for the naturals and the even naturals.
Sorry. Could you expand?? I'm not understanding what you're trying to say.

Are you talking about the distance between different natural numbers?? And you're saying that the distance between the even numbers is bigger than the distance between natural numbers?? That makes sense and it is true. But Cantor doesn't talk about distances. A distance is another type of structure. Cantor just talks about sets and nothing else. If you want to talk about distances, then you shouldn't go to Cantor but to the theory of topology or metric spaces.
hddd123456789
#15
Nov11-12, 10:44 AM
P: 82
Quote Quote by micromass View Post
It is not. Every serious mathematician has accepted Cantor's ideas as true. The only criticism comes from laymen and philosophers.
That said: there are of course attempts to make other axiom systems. Other axioms might mean that Cantor's theorems become false. But that doesn't mean that anybody doubts the truth of Cantor's theorems as they are only true in the given axiom system.
Right, I did read that his continuum hypothesis is neither provable nor disprovable in ZFC, so is it then the case that criticism can only be made on grounds of an axiomatic system? And have there been attempts to develop an axiom system with the specific intent of dealing with the intuitive (at least for me) inconsistencies that result from saying the set of naturals and even naturals have the same cardinality, for example (while recognizing, of course, that this is completely consistent in ZFC)?

Quote Quote by micromass View Post
That sets are of equal cardinality if there exists a one-to-one correspondence between them is a definition. We have defined it to be true. Another definition might give another answer, but this definition has turned out to be quite fruitful.
Furthermore, when you say that the even numbers are "twice in measure", then you first need to define measure.
I understand the part about it being a definition, but like I said, it doesn't make intuitive sense to me as I am not convinced that infinities of different sizes, as Cantor showed them to exist, should have different properties than numbers of different sizes. Again, I realize that infinities have different properties then natural numbers due to definitions in ZFC. So I guess what I'm really criticizing is the ZFC definition of infinity? And by twice the measure, I really just meant, in this case, 2x, as opposed to x.

Quote Quote by micromass View Post
Yeah, I don't really get this. Could you explain?
I just mean, that if you ask me how many markers spaced X units apart are there, I would require from you a clearly measured interval to know how many such markers fit inside that interval. And by measured, I don't necessarily mean a countable number like 1 or 2, it could also be 1*aleph-0 or 2*aleph-0. Otherwise, the vaguely defined infinity simply absorbs all attempts to put a discreet measure on it.

Quote Quote by micromass View Post
Well, infinite roads and infinite markers don't exist. Don't make the mistake that Cantor's infinities actually say something about actual reality. They are purely abstract mathematical ideas. They are useful in describing mathematics. But they don't necessarily say anything about reality.
I don't need Cantor's infinities to say anything about reality, but I do need them to say something intuitively sensible. And the idea that there are as many naturals as even naturals is not intuitive to me since, if I'm understanding correctly, half as many even naturals would fit in an interval aleph-0 in length as the naturals.

Quote Quote by micromass View Post
Sorry. Could you expand?? I'm not understanding what you're trying to say.

Are you talking about the distance between different natural numbers?? And you're saying that the distance between the even numbers is bigger than the distance between natural numbers?? That makes sense and it is true. But Cantor doesn't talk about distances. A distance is another type of structure. Cantor just talks about sets and nothing else. If you want to talk about distances, then you shouldn't go to Cantor but to the theory of topology or metric spaces.
Yes, I suppose I am speaking about distances, but I can't see how we can try and make definitions of infinities without reference to the distance between the elements of infinite sets. Again, I can see that this is perfectly consistent with the mainstream axiom system of ZFC, but it is unintuitive non-the-less. I will look into areas of study you mentioned, thank you!
jbriggs444
#16
Nov12-12, 07:17 AM
P: 963
Quote Quote by hddd123456789 View Post
And have there been attempts to develop an axiom system with the specific intent of dealing with the intuitive (at least for me) inconsistencies that result from saying the set of naturals and even naturals have the same cardinality, for example (while recognizing, of course, that this is completely consistent in ZFC)?
You don't have to develop new axioms to rescue this particular intuition. You just need a new definition.

Define "asymptotic density" for a subset S of the naturals by dividing (how many elements of S are less than n) by n and taking the limit as n increases without bound.

The even naturals have an "asymptotic density" of 0.5 If you choose to intuit this as "half of all naturals are even", we can't stop you.

A problem is that this notion of "how many" only works for subsets of the natural numbers and does not work for all subsets of the naturals.

For instance: { n : 2^k <= n < 2^k+1 for some even k } does not have an asymptotic density. This set is { 1, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 64, ... }. Intuitively, the density of this subset of the naturals ranges between 1/3 and 2/3 depending on how far out you count.
hddd123456789
#17
Nov12-12, 11:35 AM
P: 82
Quote Quote by jbriggs444 View Post
You don't have to develop new axioms to rescue this particular intuition. You just need a new definition.
Oh sorry, I didn't mean that, it would of course be silly to make a new axiom system from scratch lol. I just meant how the inclusion of the axiom of choice changes the title from ZF to ZFC.

Quote Quote by jbriggs444 View Post
Define "asymptotic density" for a subset S of the naturals by dividing (how many elements of S are less than n) by n and taking the limit as n increases without bound.

The even naturals have an "asymptotic density" of 0.5 If you choose to intuit this as "half of all naturals are even", we can't stop you.
You had me thinking you made this up on the spot for a second there But yeah, this is along the lines of what I was thinking.

Quote Quote by jbriggs444 View Post
A problem is that this notion of "how many" only works for subsets of the natural numbers and does not work for all subsets of the naturals.

For instance: { n : 2^k <= n < 2^k+1 for some even k } does not have an asymptotic density. This set is { 1, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 64, ... }. Intuitively, the density of this subset of the naturals ranges between 1/3 and 2/3 depending on how far out you count.
Which makes complete intuitive sense, doesn't it? For me, the bigger problem here is to assume that the density should converge as it goes to infinity (I hope I'm using 'converge' correctly here). After all, if Cantor has established that different sized infinities exist, then it matters which infinity we're talking about doesn't it? Just as the asymptotic density of n fluctuates as you go to higher values of n, it should equally fluctuate as n goes to higher values of infinity, no? It is at least intuitive, if you ask me.
jbriggs444
#18
Nov12-12, 12:41 PM
P: 963
Quote Quote by hddd123456789 View Post
Which makes complete intuitive sense, doesn't it? For me, the bigger problem here is to assume that the density should converge as it goes to infinity (I hope I'm using 'converge' correctly here).
Density is not guaranteed to converge. Which means that asymptotic density is not guaranteed to exist.

Assuming that density will converge does not make it so. Adding an axiom to make it so won't help -- that'll just give you an inconsistent formal system.

After all, if Cantor has established that different sized infinities exist, then it matters which infinity we're talking about doesn't it? Just as the asymptotic density of n fluctuates as you go to higher values of n, it should equally fluctuate as n goes to higher values of infinity, no? It is at least intuitive, if you ask me.
This bit is not clear.

The asymptotic density of n does not exist -- n is not defined.
The asymptotic density of S does exist. But it does not fluctuate.
The density of S intersect {1 .. n} could be defined as a function of n. That could be seen as fluctuating. Because it fluctuates it would not converge.

Perhaps you are saying that an intuitively satisfying notion of density should exist for any subset and should have a numeric value that converges as you "count through" the parent set, regardless of how you count through. I fear that such a metric is impossible to find.


Register to reply

Related Discussions
Show that the enumeration diverges Calculus & Beyond Homework 1
Numerical real-space, real-time green's functions? Quantum Physics 0
Consistent enumeration on a poset Set Theory, Logic, Probability, Statistics 1
Real analysis differentiation of a real function defined by a matrix Calculus & Beyond Homework 6
Combinatorial Bit Enumeration Set Theory, Logic, Probability, Statistics 19