Counting the reals

[Mr Skeptic]

I want to count the reals on between 0 and 1, never mind that they're supposed to be uncountable.

 

Let F(x) be a function that mirrors each of the digits of a number across the decimal point; that is, every digit [math]a 10^b [/math] of the original number gets converted to [math]a 10^{-b}[/math]. F(x) is its own inverse. Since F(x) has an inverse, it is a bijection.

 

If you restrict the domain of F(x) to the natural numbers, then its range is the set of all numbers from 0 to 1 with as many digits as the natural number.

1 <--> .1

2 <--> .2

...

10 <--> .01

11 <--> .11

...

3256 <--> .6523

...

1234567 <--> .7654321

...

 

Now the real numbers from 0 to 1 can be represented as an infinite decimal expansion 0.xxxxxxxxxxxxxx... where each x is a digit. Since the natural numbers can have infinitely many digits*, then this would be a bijection from the naturals to the reals from 0 to 1, thus counting the reals from 0 to 1.

 

*Suppose that the naturals could have only n digits. Then take a number such as [math]10^n[/math] with n digits and multiply it by 10, resulting in [math]10^{n+1}[/math] digits. This number belongs to the naturals because the naturals are a closed set, and has n+1 digits. So the premise that the naturals could have only n digits must be false. Therefore, the naturals must be allowed to have an infinite number of digits.

 

Am I doing something wrong?

[Bignose]

I'm not sure if you are doing anything wrong, but how would you handle infinitely repeating decimal representations of fractions, like 1/3 or 1/7?

[timo]

There's a lot of things that could be said here; I'll start with this comment: Every natural number can be represented with a finite number of digits.

 

EDIT: Hm ... and sometimes spending 15 minutes to think about the best formulation can make you look very stupid when someone else responded during that time, making your post a bit redundant.

[Mr Skeptic]

I'm not sure if you are doing anything wrong, but how would you handle infinitely repeating decimal representations of fractions, like 1/3 or 1/7?

 

By different infinities. For example [math]F(1/3) = F(.33333...) = \sum^{\infty}_{n=0}3*10^n[/math] = ...33333, an infinite number consisting of 3's. This is much less elegant than the infinite expansion 0.33333... because it diverges so you can't approximate it.

 

There's a lot of things that could be said here; I'll start with this comment: Every natural number can be represented with a finite number of digits.

 

How many digits?

[timo]

How many digits?

Depends on the number and the base you use for the representation, e.g. four in the case of 6123 in decimal representation. I've not claimed "every natural number can be represented with 100 digits" or something like that.

[Bignose]

Ok, then I have another one, what do you do with something like [math]\frac{\pi}{4}[/math] ? That will be between 0 and 1.

 

Also, actually the main point about 1/7 is, yes, it is a repeating decimal, but since it is infinite, which digit do you start with? This is the same issue with [math]\frac{\pi}{4}[/math]. Which digit do you start with?

[Aeternus]

By different infinities. For example [math]F(1/3) = F(.33333...) = \sum^{\infty}_{n=0}3*10^n[/math] = ...33333, an infinite number consisting of 3's. This is much less elegant than the infinite expansion 0.33333... because it diverges so you can't approximate it.

 

 

 

How many digits?

 

 

I'm pretty sure [math] \forall x \in \mathbb{N} : \textrm{x has a finite decimal expansion} [/math]. In your example here with a number with infinitely many 3 digits, just because there are numbers with increasing numbers of three digits, and there are infinitely many of these, does not imply that there are numbers of infinite size/length. You might say that as you enumerate the numbers the number of digits tends to infinity but that is not the same as saying there is an element in the natural numbers with an infinite decimal expansion. I'm pretty sure if such number were to exist in [math]\mathbb{N}[/math], various things such as the Peano axioms wouldn't hold.

 

Secondly, Cantors diagonalisation argument is very general, it doesn't require a certain method of enumeration, it only posits that one exists and goes on to show that given any enumeration an element can be produced that is in the reals (although the argument is easily generalised to lots of different uncountable sets) but will not be produced by the enumeration.

 

I could be wrong, so someone please correct me if so.

 

[edit]

 

If you are suggesting that you can take infinitely many natural numbers together somehow, then I think you are misunderstanding what it means for a set to be countable ( http://en.wikipedia.org/wiki/Countable ).

 

I have noticed you have a little "proof" that there must exist numbers in the natural numbers with infinite decimal expansions. You seem to suggest that because there are infinitely many natural numbers with increasing finite decimal expansions that there must exist a natural number with an infinite decimal expansion. As I said above, just because something "tends" to something, doesn't mean that something exists. I'm sure someone else can explain this better than me. Your example simply proves that for a given n digits, a number with n+1 digits must exist, this shows that there is no maximum n number of digits (ie the number of digits TENDS to infinity) but does not show that there is a number in the set with infinitely many digits. Note that you have assumed a number with n digits, which has a finite number of digits, adding 1 digit to it will never make it infinite.

[Fuzzwood]

[math] \forall x \in \mathbb{N} : \textrm{x has a finite decimal expansion} [/math]

 

fixed

[Aeternus]

Oops Don't know why I did that :\

[Xerxes]

Now the real numbers from 0 to 1 can be represented as an infinite decimal expansion 0.xxxxxxxxxxxxxx... where each x is a digit. Since the natural numbers can have infinitely many digits, then this would be a bijection from the naturals to the reals from 0 to 1, thus counting the reals from 0 to 1.

Cantor's diagonalization argument showed, oh ages ago, this is not true.

 

*Suppose that the naturals could have only n digits. Then take a number such as [math]10^n[/math] with n digits and multiply it by 10, resulting in [math]10^{n+1}[/math] digits. This number belongs to the naturals because the naturals are a closed set, and has n+1 digits. So the premise that the naturals could have only n digits must be false. Therefore, the naturals must be allowed to have an infinite number of digits.

Your argument fails, as you are assuming n is in N. As N is, by definition infinite and countable, this is circular

 

I'm pretty sure [math]\forall x \in \mathbb{N}[/math'] x has a finite decimal expansion.

Me too! I'm positive, in fact! Let's see; each n in N has a decimal expansion as n = n.0. Yay!

 

1/7 is, yes, it is a repeating decimal, but since it is infinite,

1/7 is infinite? Right

 

Cantors diagonalisation argument is very general, it doesn't require a certain method of enumeration,

Do you know of one that doesn't involve a countable set? Aren't all countable sets isomorphic to N?

 

...33333, an infinite number consisting of 3's.

No it's not! See that 3 on the "end"? That tells you it halts at some point. Maybe you mean 3333....?

[Bignose]

Sorry, Xerxes, should have been clearer. 1/7 itself is clearly finite, but its decimal representation has an infinite number of digits. Since I was talking about the number of digits in a decimal representation, I figured that saying "infinite" in that context, and the context of the previous posts and answer to that post, it would be obvious. Apparently it wasn't. Sheesh

[Mr Skeptic]

Cantor's diagonalization argument showed, oh ages ago, this is not true.

 

Hm, but consider the binary numbers,

0001

0010

0011

0100

...

1100 is not on the list

 

Then you can take the diagonal from the top right to the bottom left, and invert each of the digits, to get a different number not on the list. Would this not show that the natural numbers (in binary) are just as uncountable?

 

Your argument fails, as you are assuming n is in N. As N is, by definition infinite and countable, this is circular

 

Is countable by definition different from uncountable?

 

Me too! I'm positive, in fact! Let's see; each n in N has a decimal expansion as n = n.0. Yay!

 

But does that make it finite? There is no maximum number of digits a natural number can have.

 

1/7 is infinite? Right

 

I think it was clear what he meant, about its decimal expansion

 

Do you know of one that doesn't involve a countable set? Aren't all countable sets isomorphic to N?

 

Depends on what you mean by countable. Finite sets are not isomorphic to N.

 

No it's not! See that 3 on the "end"? That tells you it halts at some point. Maybe you mean 3333....?

 

Yes, but what about the 3 at the start? In my example, the decimal expansion keeps going toward the left. Yes, that is much less elegant because it diverges instead of converging, but it has no end on that side.

 

Ok, then I have another one, what do you do with something like [math]\frac{\pi}{4}[/math] ? That will be between 0 and 1.

 

Also, actually the main point about 1/7 is, yes, it is a repeating decimal, but since it is infinite, which digit do you start with? This is the same issue with [math]\frac{\pi}{4}[/math]. Which digit do you start with?

 

Yes, what is troubling about this is that it is just as impossible to say what an infinitely long natural number "starts" with as it is to say what an irrational number "ends" with.

 

It should be writable as an infinite sum though. Just like an irrational number is written as an infinite sum, but you can't actually write it as a decimal expansion either.

 

I'm pretty sure [math] \forall x \in \mathbb{N} : \textrm{x has a finite decimal expansion} [/math]. In your example here with a number with infinitely many 3 digits, just because there are numbers with increasing numbers of three digits, and there are infinitely many of these, does not imply that there are numbers of infinite size/length. You might say that as you enumerate the numbers the number of digits tends to infinity but that is not the same as saying there is an element in the natural numbers with an infinite decimal expansion. I'm pretty sure if such number were to exist in [math]\mathbb{N}[/math], various things such as the Peano axioms wouldn't hold.

 

This is probably what is wrong with my argument. However, I cannot see how there can be an infinite number of numbers, each with a different number of digits, without the number of digits also being infinite. Which of the Peano axioms wouldn't hold with infinitely many digits?

 

Secondly, Cantors diagonalisation argument is very general, it doesn't require a certain method of enumeration, it only posits that one exists and goes on to show that given any enumeration an element can be produced that is in the reals (although the argument is easily generalised to lots of different uncountable sets) but will not be produced by the enumeration.

 

What if you do the diagonalization argument with the natural numbers?

 

If you are suggesting that you can take infinitely many natural numbers together somehow, then I think you are misunderstanding what it means for a set to be countable ( http://en.wikipedia.org/wiki/Countable ).

 

Countably infinite?

 

I have noticed you have a little "proof" that there must exist numbers in the natural numbers with infinite decimal expansions. You seem to suggest that because there are infinitely many natural numbers with increasing finite decimal expansions that there must exist a natural number with an infinite decimal expansion. As I said above, just because something "tends" to something, doesn't mean that something exists. I'm sure someone else can explain this better than me.

 

I think that all irrational numbers are also calculated by taking a limit to infinity. This does seem to be different in the naturals and reals though. Need to think a bit more on this one.

 

Your example simply proves that for a given n digits, a number with n+1 digits must exist, this shows that there is no maximum n number of digits (ie the number of digits TENDS to infinity) but does not show that there is a number in the set with infinitely many digits. Note that you have assumed a number with n digits, which has a finite number of digits, adding 1 digit to it will never make it infinite.

 

I did a proof by negation. So I assumed that there was a maximum finite number of digits n for the naturals, then showed that there would be a number with n+1 digits. Then the assumption is false, meaning that there is not a maximum finite number of digits for [math] n \in \mathbb{N}[/math]

 

---

 

Is there anything wrong with saying there are an infinite number of zeros to the left of any finite number?

[uncool]

Hm, but consider the binary numbers,

0001

0010

0011

0100

...

1100 is not on the list

 

Then you can take the diagonal from the top right to the bottom left, and invert each of the digits, to get a different number not on the list. Would this not show that the natural numbers (in binary) are just as uncountable?

No, it does not. The reason that the proof works is that it shows ANY enumeration does not work. You have just shown an enumeration. I, on the other hand, say that the enumeration

1

10

11

100

... is an enumeration of the binary integers. If you try the diagonal argument, the result you get (which should be something like ....11110) is not a natural binary number, as all binary natural numbers are defined to have a finite number of nonzero entries.

 

 

Is countable by definition different from uncountable?

Yes - in fact, the class of all countable sets is disjoint from the class of uncountable sets. S being countable means that there is a surjective function from the natural numbers to S - that is, there is an enumeration that covers all elements of S (but there might be repeats). Uncountable means that the set S does not have such a function.

 

 

 

But does that make it finite? There is no maximum number of digits a natural number can have.

There is no maximum number of digits that every natural number can have - but each number itself has to be finite.

 

 

 

I think it was clear what he meant, about its decimal expansion

I will agree here.

 

 

 

Depends on what you mean by countable. Finite sets are not isomorphic to N.

That is correct.

 

 

Yes, but what about the 3 at the start? In my example, the decimal expansion keeps going toward the left. Yes, that is much less elegant because it diverges instead of converging, but it has no end on that side.

Which means that it is not a natural number. Natural numbers, by definition, are finite.

 

 

 

Yes, what is troubling about this is that it is just as impossible to say what an infinitely long natural number "starts" with as it is to say what an irrational number "ends" with.

There is no such thing as an infinitely long natural number. All natural numbers are finite in length when expressed in binary.

 

It should be writable as an infinite sum though. Just like an irrational number is written as an infinite sum, but you can't actually write it as a decimal expansion either.

You can express an irrational number as an infinite sum - because that is the definition of an infinite sum. It's that the partial sum converges to the irrational number. However, there is no such definition that will work for numbers expanding on the left.

 

 

 

This is probably what is wrong with my argument. However, I cannot see how there can be an infinite number of numbers, each with a different number of digits, without the number of digits also being infinite. Which of the Peano axioms wouldn't hold with infinitely many digits?

First, every digit has an element of N such that that digit is nonzero. However, that does not mean that there is an element of N such that every digit (or even infinitely many digits) are nonzero. And the induction axiom is not true, if you allow "infinitely many" digits. For example, let phi(n) be the expression "n is finite in length." Clearly, phi(0) is true. Also, clearly phi(n) -> phi(n+1). Thereore, phi should be true for all n - but clearly, your thing is not finite in length.

 

Secondly, Cantors diagonalisation argument is very general, it doesn't require a certain method of enumeration, it only posits that one exists and goes on to show that given any enumeration an element can be produced that is in the reals (although the argument is easily generalised to lots of different uncountable sets) but will not be produced by the enumeration.

 

What if you do the diagonalization argument with the natural numbers?

You can't - as I showed above.

 

 

 

Countably infinite?

The natural numbers are infinite, and yet can be enumerated.

 

 

 

I think that all irrational numbers are also calculated by taking a limit to infinity. This does seem to be different in the naturals and reals though. Need to think a bit more on this one.

Not all irrational numbers have to be calculated in that way - algebraic numbers can usually be left alone. However, if you want to learn a lot about the algebraic numbers, then it is nice to be able to relate them to rationals by using limits of sequences.

 

 

 

I did a proof by negation. So I assumed that there was a maximum finite number of digits n for the naturals, then showed that there would be a number with n+1 digits. Then the assumption is false, meaning that there is not a maximum finite number of digits for [math] n \in \mathbb{N}[/math]

You are correct - there are an infinite number of digits. However, for any natural number, only finitely many of them can be nonzero. That is, what you proved is that for all digits, there exists a number n such that that digit is nonzero. However, that does not prove what you are trying to prove, which is that there exists a number n such that every digit (or even infinitely many of them) is nonzero. You have switched the "for all" quantifier and the existence quantifier.

 

Is there anything wrong with saying there are an infinite number of zeros to the left of any finite number?

No, there is not. However, there is no natural, or real, number with infinitely many nonzero entries to the left of the decimal point.

=Uncool-

[Mr Skeptic]

No, it does not. The reason that the proof works is that it shows ANY enumeration does not work. You have just shown an enumeration. I, on the other hand, say that the enumeration

1

10

11

100

... is an enumeration of the binary integers. If you try the diagonal argument, the result you get (which should be something like ....11110) is not a natural binary number, as all binary natural numbers are defined to have a finite number of nonzero entries.

 

The new number need only have as many digits as there are numbers in the list, in this case 4. Also, it would be 1100, not 1110.

 

There is no maximum number of digits that every natural number can have - but each number itself has to be finite.

 

Fine, then. They are all finite but have a number of digits that keeps getting bigger and bigger without end, and the number itself gets bigger and bigger without end.

 

 

Which means that it is not a natural number. Natural numbers, by definition, are finite.

 

Do you have a link for that?

 

You can express an irrational number as an infinite sum - because that is the definition of an infinite sum. It's that the partial sum converges to the irrational number. However, there is no such definition that will work for numbers expanding on the left.

 

Eh? So then [math] \sum_{n=0}^{\infty}\frac{1}{2^n} = 2[/math] shows that 2 is irrational?

 

First, every digit has an element of N such that that digit is nonzero. However, that does not mean that there is an element of N such that every digit (or even infinitely many digits) are nonzero. And the induction axiom is not true, if you allow "infinitely many" digits. For example, let phi(n) be the expression "n is finite in length." Clearly, phi(0) is true. Also, clearly phi(n) -> phi(n+1). Thereore, phi should be true for all n - but clearly, your thing is not finite in length.

 

Then the sum [math]\sum_{n=0}^{\infty}1[/math] is finite. Since that sum is usually considered to be infinite, then perhaps finite = infinite according to your proof? You say that "clearly" adding 1 to any finite number results in another finite number, but it is the "clear" things that are hardest to prove

[uncool]

The new number need only have as many digits as there are numbers in the list, in this case 4. Also, it would be 1100, not 1110.

Notice the ... - that means an infinite list. However, you are right in the 1100 thing.

 

Fine, then. They are all finite but have a number of digits that keeps getting bigger and bigger without end, and the number itself gets bigger and bigger without end.

Only as you change the number - any number by itself has a finite number of digits that stays constant.

 

 

Do you have a link for that?

http://en.wikipedia.org/wiki/Natural_number. Also, every mathematician uses it in that way - that is, that every natural number can be obtained by adding 1 to itself a finite number of times.

 

Eh? So then [math] \sum_{n=0}^{\infty}\frac{1}{2^n} = 2[/math] shows that 2 is irrational?

Where did I say that? All I'm saying is that there is no need to have infinite sums to find them.

 

Then the sum [math]\sum_{n=0}^{\infty}1[/math] is finite. Since that sum is usually considered to be infinite, then perhaps finite = infinite according to your proof? You say that "clearly" adding 1 to any finite number results in another finite number, but it is the "clear" things that are hardest to prove

How is that sum finite? My proof deals with numbers that are expressed as a finite list of digits in binary form. That number cannot be expressed in that form and therefore has nothing to do with the proof.

 

And usually it is the clearest things that can be most easily proven. That is why they are usually clear.

=Uncool-

[Mr Skeptic]

It seems that most of this disagreement is related to whether or not the natural numbers are finite. Finite seems to mean having an end, but there is no limit to how many digits a natural number can have, nor is there a limit to their size. There is no last or biggest natural number. How then can they be finite? How can an infinite set be composed of finite, unique numbers?

 

PS: the wikipedia article about natural numbers does not seem to say they are finite

 

PPS: Should this be split to a new thread, why are natural numbers finite?

[uncool]

Once again, you are mixing up quantifiers. You have proven that for all digits, there is a natural number such that that digit is nonzero. However, you have not proven that there is a natural number such that each digit is nonzero. You can have an infinite set using a finite possible set of digits - take, for example, the set 0, S(0) = 1, S(S(0)), etc., where S denotes the successor function. This clearly is the infinite set that is the natural numbers, but only uses a total of 4 symbols - S, (, 0, ).

 

Remember, there is a huge difference between the integers being infinite, and an individual integer being infinite.

=Uncool-

 

Actually, there happens to be another Peano axiom that your thing happens to violate - S(a) =/= 0 for any a.

Reason: Consider the "infinite number" ...999, which is all 9s. The successor of this number is ...000, which is exactly 0.

Also, in your system, it can be proven that ordering does not work.

=Uncool-

[Mr Skeptic]

Once again, you are mixing up quantifiers. You have proven that for all digits, there is a natural number such that that digit is nonzero. However, you have not proven that there is a natural number such that each digit is nonzero.

 

No, my proof only concerned the leftmost digit.

 

You can have an infinite set using a finite possible set of digits - take, for example, the set 0, S(0) = 1, S(S(0)), etc., where S denotes the successor function. This clearly is the infinite set that is the natural numbers, but only uses a total of 4 symbols - S, (, 0, ).

 

Or you could just use binary. 0 and 1. I'm talking about the number of digits, not the number of distinct digits.

 

Remember, there is a huge difference between the integers being infinite, and an individual integer being infinite.

=Uncool-

 

And yet each integer in the set is unique, and you can only have so many unique integers per so many digits. Simply saying it is so won't make it so. How can there be infinitely many integers with finitely many digits, and what would that finite number of digits be? Saying the number of digits is bigger than any finite number seems equivalent to saying it is infinite (not finite).

 

Actually, there happens to be another Peano axiom that your thing happens to violate - S(a) =/= 0 for any a.

Reason: Consider the "infinite number" ...999, which is all 9s. The successor of this number is ...000, which is exactly 0.

Also, in your system, it can be proven that ordering does not work.

=Uncool-

 

Well, it would be more like [math]10^{\infty}[/math], but I see what you mean. It would need a nonzero "first" digit at infinity, which seems like a contradiction. And if passed through my mirror function, it would become an infinitesimal [math]10^{-\infty}[/math]

 

Actually, the ...999 gives me more trouble than that, because mirroring it would give .999... = 1, and mirroring it back again would give 1 instead of ...999 . So then my mirror function isn't actually a function. That kind of messes up my idea

 

---

 

I still can't see how you can have infinitely many integers with finitely many digits though.

[uncool]

Each integer - individually - has finitely many digits. The set of all integers, on the other hand, has infinitely many digits.

 

And what your proof showed was that for all placeholders, there is an integer that makes that placeholder nonzero. Or, to state it like above, that the set of all integers uses each digit placeholder.

=Uncool-

[timo]

Considering that the non-countability of the reals is a well-known theorem with a well-known (1st semester mathematics at university) proof and certainly does not fall into the category of every student thinking "sounds logical, I accept the proof without carefully checking it", I think your time is better-spent by taking some time to understand what went wrong with your arguments, for example:

- Try to understand why "there is no number N of digits sufficient to represent all naturals" is not equivalent to "there are naturals with an infinite number of digits".

- Try to understand the meanings of the rotated 8's you use as if they were numbers (big hint: They are not). Does the limit of a series where all individual terms lie within some set S have to lie in S? What does that mean for your [math]\sum_1^\infty 1[/math]?

 

Or in short: The topic is dead since post #2 by bignose. Using your construction, 1/3 does not map on a natural number.

[Aeternus]

Perhaps you are misunderstanding what infinity means in this case, it doesn't mean that there is some value infinity at which we can take an element and then that element has infinitely many digits. Infinity in this case simply expresses the concept that there is no maximum natural number, here you have to understand, that does not mean that there is/are a/some natural number(s) that is/are infinity (which is what such natural numbers you describe with infinite decimal expansions seem to amount to), but simply that there is no largest natural number (ie [math]\infty [/math] is the Supremum of [math]\mathbb{N}[/math]). You seem to assume that because there is no largest natural number, that there must be some element infinity, but this isn't the case, if you consider the generation of the natural numbers by starting at 0, and then simply taking the successor (+1, s(?) etc) and you continue to do this as much as you like, you will never reach some number with an infinite decimal expansion (ie infinity), adding one to any finite number will still produce a finite number.

[Mr Skeptic]

Thank you, Aeternus, that makes sense. So then saying "as big as you like so long as it is finite" is like saying as "in the set of reals less the 2 you can get as close as you like to 2 so long as you don't actually get to 2"?

[Fred56]

It's a big one:

 

Infinite cardinality is the concept of a number greater than (outside of) some (largest) element of a set, which therefore also has infinite cardinality (and belongs to the set). This is logically inconsistent. There is no cardinality which falls outside any set of infinite cardinality. Zero (nothing) can belong to such a set, but zero is definitely not infinite, and nor are any of the set's members (except for the “infinite” one -the “biggest”+m).

In other words infinity is like a guest who checks in to a hotel to find he is already there, there are already an infinite number of him in fact, and they all have no idea who they are.

[uncool]

...What you wrote doesn't even make any sense...

=Uncool-

[Fred56]

Can you expand on the nonsense I'm (according to you) making? It makes sense to me...

 

...What you wrote doesn't even make any sense...

Are you saying that the concept of a number larger (outside) an infinite set is logically consistent? If so, could you please show me where I've made a mistake with the assumption (that it isn't). And how many members of the set of "infinite" cardinals can you write down and tell me are infinite? Please support your contention that I am not making sense...!?!??